数値線形代数

数値解析における数値線形代数（すうちせんけいだいすう、英: Numerical linear algebra）とは、線形代数で現れる問題（行列積、行列指数関数、連立方程式や固有値・特異値問題）の計算・求解を行うアルゴリズムを創出するための学問である。最適化問題・有限差分法・有限要素法などに応用されている。

→「数値解析」および「線形代数」も参照

意義

どんなに次元の高い連立方程式でも、原理的にはクラメルの公式を使えば解くことはできる。しかし、クラメルの公式による数値解法ではものすごく時間がかかってしまうということが分かっている。このため、これまで様々な数値線形代数のアルゴリズムが開発されてきた。ガウスの消去法はその先駆けとも言える。

現代の主流

→「固有値問題の数値解法」も参照

現代においては

  • 共役勾配法
  • GMRES法
  • ランチョス法
  • QR法
  • QZ法
  • dqds法 (differential quotient difference with shift)
  • oqds法 (orthogonal quotient difference with shift)
  • 分割統治法
  • MRRR法 (multiple relatively robust representations)
  • MRTR法
  • Sakurai-Sugiura 法
  • CIRR 法 (Rayleigh-Ritz type method with contour integral)
  • 離散勾配法に基づく解法
  • フィルターを用いた固有値問題の解法

などをはじめとした高速・高精度解法（反復法）の研究が主流になっている。

クリロフ部分空間法

→「クリロフ部分空間」も参照

数値線形代数で現れる反復法の中には、クリロフ部分空間に理論的基盤を持つものが少なからず存在する。これらはクリロフ部分空間法（英: Krylov subspace methods）と総称され、数値線形代数において最も成功した手法とされている。主なクリロフ部分空間法として以下が知られている（共役勾配法については後述する）。

  • en:Arnoldi iteration
  • ランチョス法
  • GMRES法
  • MINRES法（英: minimal residual、この手法は method of minimum residual とは異なる）
  • CR法（共役残差法、英: conjugate residual method）
  • QMR系
    • QMR法（英: quasi minimal residual、MATLABで利用可能）
    • QMR-SYM法
    • TFQMR法（英: transpose free quasi minimal residual、MATLABで利用可能）

共役勾配法

→「共役勾配法」、「非線形共役勾配法」、「双共役勾配法」、および「en:LOBPCG」も参照

共役勾配法（英: conjugate gradient method）は Hestenes-Stiefel によって開発された連立方程式の数値解法であり、係数行列が正定値対称行列であるときに適用できる。この方法はガウス＝ザイデル法、ヤコビ法、SOR法よりも収束が速いとされることから、1980年代以降から様々な亜種が開発されたり、非対称行列への適用が試みられているが、前処理行列の取り方が問題によって異なるために決定版と言える解法がまだ存在してない。

以下、代表的な亜種を挙げる。

  • CGS (conjugate gradient squared method)
  • PCG （preconditioned conjugate gradient method、MATLABで利用可能）
  • SCG (scaled conjugate gradient)
  • ICCG （incomplete Cholesky conjugate gradient method、不完全コレスキー分解付共役勾配法）
  • COCG (conjugate orthogonal conjugate gradient method)
  • GPBiCG
  • GPBiCG
  • STAB系の手法
    • BiCGSTAB （biconjugate gradient stabilized method、双共役勾配安定化法、MATLABで利用可能）
    • BiCGSTAB2
    • QMRCGSTAB
    • GBi-CGSTAB
  • Block化した手法
    • Block CG
    • Block BiCGSTAB
    • Block BiCGGR
    • Block BiCGGR2
    • Block GWBiCGSTAB

精度保証

数値線形代数における精度保証付き数値計算の研究も活発になっており、具体的には以下のような研究が行われている。

可積分系との関係

→「可積分系」および「可積分アルゴリズム」も参照

可積分系・力学系と数値線形代数の間に関係があるという事実が注目されている。具体的には戸田格子（ソリトン方程式の一つ）とQR法・qd法、可積分系と特異値分解との関係が明らかになった。これらを背景に、離散可積分系から数値線形代数に有用な反復法を開発する試みが行われている。例えば

  • dLVアルゴリズム
  • dhLVアルゴリズム
  • mdLVアルゴリズム
  • dhTodaアルゴリズム
  • I-SVDアルゴリズム

等が研究されている。

関連項目

ソフトウェア・ライブラリ

→「線型代数学ライブラリの比較」も参照

手法

研究者・専門家

日本

海外

ドイツ

アメリカ合衆国

イギリス

出典

[脚注の使い方]

反復法・高精度計算に関する論文

精度保証に関する論文

可積分アルゴリズムに関する論文

参考文献

洋書

  • Demmel, J. W. (1997): Applied Numerical Linear Algebra, SIAM.
  • Ciarlet, P. G., Miara, B., & Thomas, J. M. (1989): Introduction to Numerical Linear Algebra and Optimization, Cambridge University Press.
  • Trefethen, Lloyd; Bau III, David (1997): Numerical Linear Algebra (1st ed.), Philadelphia: SIAM.ISBN 978-0-89871-361-9.
  • Golub, Gene H.; Van Loan, Charles F. (1996): Matrix Computations (3rd ed.), Baltimore: The Johns Hopkins University Press.ISBN 0-8018-5413-X.
  • G. W. Stewart: Matrix Algorithms Vol I: Basic Decompositions, SIAM, ISBN 0-89871-414-1 (1998).
  • G. W. Stewart: Matrix Algorithms Vol II: Eigensystems, SIAM, ISBN 0-89871-503-2 (2001).
  • Varga, Richard S.: Matrix Iterative Analysis, Springer, 2000.
  • Saad, Yousef (2003). Iterative Methods for Sparse Linear Systems (2nd ed. ed.). SIAM.ISBN 978-0-89871534-7.OCLC 51266114  [1]
  • Raf Vandebril, Marc Van Barel, and Nicola Mastronardi: Matrix Computations and Semiseparable Matrices, Volume 1: Linear systems, Johns Hopkins Univ. Press, ISBN 978-0-8018-8714-7 (2008).
  • Raf Vandebril, Marc Van Barel, and Nicola Mastronardi: Matrix Computations and Semiseparable Matrices, Volume 2: Eigenvalue and Singular Value Methods, Johns Hopkins Univ. Press, ISBN 978-0-8018-9052-9 (2008).
  • Higham, N. J. (2008): Functions of Matrices: Theory and Computation, SIAM.
  • Higham, N. J. (2002): Accuracy and Stability of Numerical Algorithms, SIAM.
  • David S. Watkins (2008): The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM.
  • Liesen, J., & Strakos, Z. (2012): Krylov Subspace Methods: Principles and Analysis, Oxford Univ. Press, Oxford.
  • Claude Brezinski, Gérard Meurant and Michela Redivo-Zaglia (2022): A Journey through the History of Numerical Linear Algebra, SIAM, ISBN 978-1-61197-722-6.

和書

関連特許

  • 「固有値分解装置、及び固有値分解法」 特許5017666（日本）、PCT/JP2007/051575
  • 「特異値分解装置、及び特異値分解法」 特許5011545（日本）、PCT/JP2006/318713

外部リンク

手法に関する解説記事

反復法

精度保証

研究グループ・部会

全米科学財団

科学研究費助成事業

「https://ja.wikipedia.org/w/index.php?title=数値線形代数&oldid=103835128」から取得
Uses material from the Wikipedia article 数値線形代数, released under the CC BY-SA 4.0 license.