数値線形代数

数値解析における数値線形代数（すうちせんけいだいすう、テンプレート:Lang-en-short）とは、線形代数で現れる問題（行列積、行列指数関数、連立方程式や固有値・特異値問題）の計算・求解を行うアルゴリズムを創出するための学問である^[1]^[2]^[3]。最適化問題・有限差分法・有限要素法などに応用されている^[1]。テンプレート:Seealso

意義

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

現代の主流

テンプレート:Seealso 現代においてはテンプレート:Div col

共役勾配法
GMRES法
ランチョス法
QR法
QZ法^{[A 1]}
dqds法 (differential quotient difference with shift)^{[A 2]}^{[A 3]}^{[A 4]}^{[A 5]}^{[A 6]}^{[A 7]}
oqds法 (orthogonal quotient difference with shift)^{[A 8]}^{[A 9]}^{[A 10]}
分割統治法^{[A 11]}^{[A 12]}
MRRR法 (multiple relatively robust representations)^{[A 13]}
MRTR法^{[A 14]}
Sakurai-Sugiura 法^{[A 15]}
CIRR 法 (Rayleigh-Ritz type method with contour integral)^{[A 16]}
離散勾配法に基づく解法^{[A 17]}^{[A 18]}
フィルターを用いた固有値問題の解法^{[A 19]}^{[A 20]}^{[A 21]}^{[A 22]}

テンプレート:Div col end などをはじめとした高速・高精度解法（反復法）の研究が主流になっている^[2]^[4]^[5]。

クリロフ部分空間法

テンプレート:Seealso 数値線形代数で現れる反復法の中には、クリロフ部分空間に理論的基盤を持つものが少なからず存在する。これらはクリロフ部分空間法（テンプレート:Lang-en-short）と総称され、数値線形代数において最も成功した手法とされている^[5]。主なクリロフ部分空間法として以下が知られている（共役勾配法については後述する）。テンプレート:Div col

en:Arnoldi iteration
ランチョス法
GMRES法
MINRES法^{[A 23]}（テンプレート:Lang-en-short、この手法は method of minimum residual^[1]^{[A 24]} とは異なる）
CR法^{[A 25]}（共役残差法、テンプレート:Lang-en-short）
QMR系
- QMR法^{[A 26]}^{[A 27]}（テンプレート:Lang-en-short、MATLABで利用可能）
- QMR-SYM法^{[A 28]}^{[A 29]}
- TFQMR法^{[A 30]}（テンプレート:Lang-en-short、MATLABで利用可能）

テンプレート:Div col end

共役勾配法

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

以下、代表的な亜種を挙げる。テンプレート:Div col

CGS (conjugate gradient squared method)^{[A 32]}
PCG （preconditioned conjugate gradient method、MATLABで利用可能）
SCG (scaled conjugate gradient)^{[A 33]}
ICCG （incomplete Cholesky conjugate gradient method、不完全コレスキー分解付共役勾配法）^[5]
COCG (conjugate orthogonal conjugate gradient method)^{[A 34]}
GPBiCG^{[A 35]}^{[A 36]}
GPBiCG $(m, l)$ ^{[A 37]}
STAB系の手法
- BiCGSTAB （biconjugate gradient stabilized method、双共役勾配安定化法、MATLABで利用可能）^{[A 38]}
- BiCGSTAB2^{[A 39]}
- QMRCGSTAB^{[A 40]}
- GBi-CGSTAB^{[A 41]}
Block化した手法
- Block CG^{[A 42]}^{[A 43]}
- Block BiCGSTAB^{[A 44]}
- Block BiCGGR^{[A 45]}
- Block BiCGGR2^{[A 46]}
- Block GWBiCGSTAB^{[A 47]}

テンプレート:Div col end

精度保証

数値線形代数における精度保証付き数値計算の研究も活発になっており^[6]^[7]、具体的には以下のような研究が行われている。テンプレート:Div col

連立方程式の解に対する精度保証付き数値計算^[6]^[7]^{[B 1]}^{[B 2]}
- 並列計算^{[B 3]}
- 悪条件問題（テンプレート:Lang-en-short、条件数が大きい問題）^{[B 4]}^{[B 5]}^{[B 6]}^{[B 7]}
- 前処理行列^{[B 8]}^{[B 9]}^{[B 10]}
- H行列（比較行列がM行列^[1]となる行列）を用いる方法（ペロン・フロベニウスの定理^[1]も使う、この方法は疎行列のときも適用可能）^[6]^{[B 11]}
- 疎行列に対する精度保証法（コレスキー分解に基づく）^[6]^{[B 12]}
固有値問題の解に対する精度保証付き数値計算^[1]^[6]^[7]^{[B 13]}^{[B 14]}^{[B 15]}
- ゲルシュゴリンの定理を使う方法（定石として確立されている）^[1]^[6]^[7]
- Krawczyk法（精度保証付き求根アルゴリズムの一つ）を使う方法^[6]^[7]^{[B 16]}^{[B 17]}^{[B 18]}
- 大規模疎行列の場合^[6]^{[B 19]}
- 対角化可能行列に対する Bauer-Fike型誤差評価、Hoffman-Wielandt型誤差評価^[7]^{[B 20]}^{[B 21]}^{[B 22]}
- 一般化固有値問題（テンプレート:Lang-en-short）^{[B 23]}
- 逆固有値問題（テンプレート:Lang-en-short）^{[B 24]}^{[B 25]}
特異値分解の精度保証^[7]^{[B 26]}^{[B 27]}
行列式の精度保証^{[B 28]}^{[B 29]}
行列の乗法^{[B 30]}^{[B 31]}
行列方程式の解に対する精度保証^{[B 32]}^{[B 33]}^{[B 34]}^{[B 35]}^{[B 36]}^{[B 37]}^{[B 38]}^{[B 39]}
行列値関数（en）の精度保証（行列値関数の高精度計算法に関する研究についてはHighamなどによる業績が多数ある^{[A 48]}^{[A 49]}^{[A 50]}^{[A 51]}）
- 行列指数関数^{[B 40]}
- 行列の対数^{[B 41]}
- 行列の平方根^{[B 42]}

テンプレート:Div col end

可積分系との関係

テンプレート:Seealso 可積分系・力学系と数値線形代数の間に関係があるという事実が注目されている^[8]^[9]^{[C 1]}^{[C 2]}。具体的には戸田格子（ソリトン方程式の一つ）とQR法^[8]^[9]・qd法^{[C 3]}、可積分系と特異値分解^[8]^[9]^{[C 4]}^{[C 5]}との関係が明らかになった。これらを背景に、離散可積分系から数値線形代数に有用な反復法を開発する試みが行われている。例えばテンプレート:Div col

dLVアルゴリズム^{[C 6]}^{[C 7]}^{[C 8]}^{[C 9]}
dhLVアルゴリズム^{[C 10]}^{[C 11]}^{[C 12]}^{[C 13]}
mdLVアルゴリズム^{[A 3]}^{[A 4]}^{[C 9]}^{[C 14]}^{[C 15]}^{[C 16]}
dhTodaアルゴリズム^{[C 17]}^{[C 18]}^{[C 19]}
I-SVDアルゴリズム^{[C 20]}^{[C 21]}^{[C 22]}

テンプレート:Div col end 等が研究されている^[8]^[9]。

研究者・専門家

日本

杉原正顯（共役勾配法の研究に従事^{[A 41]}）
大石進一（数値線形代数の精度保証に貢献^[6]^[7]）
速水謙

海外

en:Aleksey Krylov（クリロフ部分空間を導入）

ドイツ

カール・グスタフ・ヤコブ・ヤコビ（固有値問題の解法であるen:Jacobi eigenvalue algorithmで知られる^[1]^[2]）
イサイ・シューア（逆行列を求めるのに使うシューア補行列で知られる^[1]）
フェルディナント・ゲオルク・フロベニウス（ペロン＝フロベニウスの定理で知られる^[1]）
en:Helmut Wielandt（固有値問題などについて業績がある^[1]^[7]）
アンドレアス・フロマー

アメリカ合衆国

イギリス

出典

テンプレート:脚注ヘルプテンプレート:Reflist

参考文献

洋書

テンプレート:Div col

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. テンプレート:ISBN2.
Golub, Gene H.; Van Loan, Charles F. (1996): Matrix Computations (3rd ed.), Baltimore: The Johns Hopkins University Press. テンプレート:ISBN2.
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.
テンプレート:Cite book [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.

テンプレート:Div col end

和書

テンプレート:Div col

仁木滉, & 河野敏行. (1998). 楽しい反復法. 共立出版.
河村哲也. (2005). 線形代数と数値解析, 朝倉書店.
杉原正顯, 室田一雄, 線形計算の数理, 岩波書店, 2009年.
山本哲朗. (2010). 行列解析の基礎–Advanced 線形代数, SGC ライブラリ 79. サイエンス社.
線形方程式の反復解法、一般社団法人日本計算工学会編、藤野清次著、阿部邦美著、杉原正顯著、丸善出版、2013年09月。

テンプレート:Div col end

外部リンク

テンプレート:外部リンクの注意

手法に関する解説記事

反復法

精度保証

研究グループ・部会

テンプレート:Twitter (イギリスの数値線形代数研究グループ)
テンプレート:Twitter (SIAMの数値線形代数研究部会)
The GAMM Activity Group on Applied and Numerical Linear Algebra
計算数理グループ (名古屋大学の数値線形代数研究グループ)
日本応用数理学会「行列・固有値問題の解法とその応用」研究部会 (Algorithms for Matrix / Eigenvalue Problems and their Applications) (日本応用数理学会の研究部会)

全米科学財団

科学研究費助成事業

テンプレート:Applied-math-stub テンプレート:Linear algebra テンプレート:数学テンプレート:Commonscat

↑ ^1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 ^1.14 テンプレート:Cite book
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 森正武. 数値解析第2版. 共立出版.
↑ ^3.0 ^3.1 ^3.2 数値線形代数の数理とHPC, 櫻井鉄也, 松尾宇泰, 片桐孝洋編（シリーズ応用数理 / 日本応用数理学会監修, 第6巻）共立出版, 2018.8
↑ 戸川隼人. (1977). 共役勾配法. シリーズ新しい応用の数学.
↑ ^5.0 ^5.1 ^5.2 ^5.3 藤野清次, & 張紹良. (1996). 反復法の数理. 朝倉書店.
↑ ^6.0 ^6.1 ^6.2 ^6.3 ^6.4 ^6.5 ^6.6 ^6.7 ^6.8 引用エラー: 無効な <ref> タグです。「basic」という名前の注釈に対するテキストが指定されていません
↑ ^7.0 ^7.1 ^7.2 ^7.3 ^7.4 ^7.5 ^7.6 ^7.7 ^7.8 大石進一：「精度保証付き数値計算」、コロナ社、（1999年）
↑ ^8.0 ^8.1 ^8.2 ^8.3 解析学百科II 可積分系の数理、朝倉書店、中村佳正 et al. (2018)
↑ ^9.0 ^9.1 ^9.2 ^9.3 可積分系の機能数理、共立出版、中村佳正。

引用エラー: 「A」という名前のグループの <ref> タグがありますが、対応する <references group="A"/> タグが見つかりません
引用エラー: 「B」という名前のグループの <ref> タグがありますが、対応する <references group="B"/> タグが見つかりません
引用エラー: 「C」という名前のグループの <ref> タグがありますが、対応する <references group="C"/> タグが見つかりません

[Yamamoto1-1] 1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 ^1.14 テンプレート:Cite book

[mori-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 森正武. 数値解析第2版. 共立出版.

[hpc-3] 3.0 ^3.1 ^3.2 数値線形代数の数理とHPC, 櫻井鉄也, 松尾宇泰, 片桐孝洋編（シリーズ応用数理 / 日本応用数理学会監修, 第6巻）共立出版, 2018.8

[26] 戸川隼人. (1977). 共役勾配法. シリーズ新しい応用の数学.

[zhang-27] 5.0 ^5.1 ^5.2 ^5.3 藤野清次, & 張紹良. (1996). 反復法の数理. 朝倉書店.

[basic-53] 6.0 ^6.1 ^6.2 ^6.3 ^6.4 ^6.5 ^6.6 ^6.7 ^6.8 引用エラー: 無効な <ref> タグです。「basic」という名前の注釈に対するテキストが指定されていません

[oishi-54] 7.0 ^7.1 ^7.2 ^7.3 ^7.4 ^7.5 ^7.6 ^7.7 ^7.8 大石進一：「精度保証付き数値計算」、コロナ社、（1999年）

[pedia-101] 8.0 ^8.1 ^8.2 ^8.3 解析学百科II 可積分系の数理、朝倉書店、中村佳正 et al. (2018)

[func-102] 9.0 ^9.1 ^9.2 ^9.3 可積分系の機能数理、共立出版、中村佳正。

[1]

[2]

[3]

[A 1]

[A 2]

[A 3]

[A 4]

[A 5]

[A 6]

[A 7]

[A 8]

[A 9]

[A 10]

[A 11]

[A 12]

[A 13]

[A 14]

[A 15]

[A 16]

[A 17]

[A 18]

[A 19]

[A 20]

[A 21]

[A 22]

[4]

[5]

[A 23]

[A 24]

[A 25]

[A 26]

[A 27]

[A 28]

[A 29]

[A 30]

[A 31]

[A 32]

[A 33]

[A 34]

[A 35]

[A 36]

[A 37]

[A 38]

[A 39]

[A 40]

[A 41]

[A 42]

[A 43]

[A 44]

[A 45]

[A 46]

[A 47]

[6]

[7]

[B 1]

[B 2]

[B 3]

[B 4]

[B 5]

[B 6]

[B 7]

[B 8]

[B 9]

[B 10]

[B 11]

[B 12]

[B 13]

[B 14]

[B 15]

[B 16]

[B 17]

[B 18]

[B 19]

[B 20]

[B 21]

[B 22]

[B 23]

[B 24]

[B 25]

[B 26]

[B 27]

[B 28]

[B 29]

[B 30]

[B 31]

[B 32]

[B 33]

[B 34]

[B 35]

[B 36]

[B 37]

[B 38]

[B 39]

[A 48]

[A 49]

[A 50]

[A 51]

[B 40]

[B 41]

[B 42]

数値線形代数

目次

意義

現代の主流

クリロフ部分空間法

共役勾配法

精度保証

可積分系との関係

関連項目

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

手法

研究者・専門家

日本

海外

ドイツ

アメリカ合衆国

イギリス

出典

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

精度保証に関する論文

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

参考文献

洋書

和書

関連特許

外部リンク

手法に関する解説記事

反復法

精度保証

研究グループ・部会

全米科学財団

科学研究費助成事業

ナビゲーションメニュー

数値線形代数

意義

現代の主流

クリロフ部分空間法

共役勾配法

精度保証

可積分系との関係

関連項目

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

手法

研究者・専門家

日本

海外

ドイツ

アメリカ合衆国

イギリス

出典

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

精度保証に関する論文

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

参考文献

洋書

和書

関連特許

外部リンク

手法に関する解説記事

反復法

精度保証

研究グループ・部会

全米科学財団

科学研究費助成事業

ナビゲーション メニュー

検索

ナビゲーションメニュー