数値線形代数

数値解析における数値線形代数とは、線形代数で現れる問題の計算・求解を行うアルゴリズムを創出するための学問である。最適化問題・有限差分法・有限要素法などに応用されている。

1. 意義
-----

1.1. 直接解法の問題点
-------------

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

1.2. 現代の主流
----------

現代においては

共役勾配法
GMRES法
ランチョス法
QR法
QZ法
dqds法 
oqds法 
分割統治法
MRRR法 
MRTR法
Sakurai-Sugiura 法
CIRR 法 
離散勾配法に基づく解法
フィルターを用いた固有値問題の解法 などをはじめとした高速・高精度解法の研究が主流になっている。

1.2.1. クリロフ部分空間法
----------------

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

:en:Arnoldi iteration
ランチョス法
GMRES法
MINRES法
CR法
QMR系
QMR法
QMR-SYM法
TFQMR法

1.2.2. 共役勾配法
------------

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

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

CGS 
PCG
SCG 
ICCG
COCG 
GPBiCG
GPBiCG
STAB系の手法
BiCGSTAB
BiCGSTAB2
QMRCGSTAB
GBi-CGSTAB
Block化した手法
Block CG
Block BiCGSTAB
Block BiCGGR
Block BiCGGR2
Block GWBiCGSTAB

1.2.3. 精度保証
-----------

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

連立方程式の解に対する精度保証付き数値計算
並列計算
悪条件問題
前処理行列
H行列 を用いる方法
疎行列に対する精度保証法
固有値問題の解に対する精度保証付き数値計算
ゲルシュゴリンの定理を使う方法
Krawczyk法を使う方法
大規模疎行列の場合
対角化可能行列に対する Bauer-Fike型誤差評価、Hoffman-Wielandt型誤差評価
一般化固有値問題
逆固有値問題
特異値分解の精度保証
行列式の精度保証
行列の乗法
行列方程式の解に対する精度保証
行列値関数の精度保証
行列指数関数
行列の対数
行列の平方根

2. 可積分系との関係
-----------

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

dLVアルゴリズム
dhLVアルゴリズム
mdLVアルゴリズム
dhTodaアルゴリズム
I-SVDアルゴリズム 等が研究されている。

3. 関連項目
-------

行列解析 
条件数

3.1. ソフトウェア・ライブラリ
-----------------

BLAS
OpenBLAS
LAPACK
MATLAB
GNU Octave
INTLAB
NAG数値計算ライブラリ

3.2. 手法
-------

反復法
クリロフ部分空間
ハウスホルダー変換
ギブンス回転
べき乗法
逆べき乗法
ヤコビ法 
シュトラッセンのアルゴリズム
前処理行列
行列の分解
LU分解
QR分解
コレスキー分解
固有値分解 
特異値分解

4. 研究者・専門家
----------

4.1. 日本
-------

杉原正顯
大石進一
速水謙

4.2. 海外
-------

:en:Aleksey Krylov

4.2.1. ドイツ
----------

カール・グスタフ・ヤコブ・ヤコビ
イサイ・シューア
フェルディナント・ゲオルク・フロベニウス
:en:Helmut Wielandt
アンドレアス・フロマー

4.2.2. アメリカ合衆国
--------------

リチャード・バルガ 
ジーン・ゴラブ 
クリーブ・モラー 

4.2.3. イギリス
-----------

ジェームズ・H・ウィルキンソン
ニコラス・ハイアム 
ニック・トレフェセン 

5. 出典
-----

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

5.2. 精度保証に関する論文
---------------

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

6. 参考文献
-------

6.1. 洋書
-------

Demmel, J. W. . Applied numerical linear algebra. SIAM.
Ciarlet, P. G., Miara, B., & Thomas, J. M. . Introduction to numerical linear algebra and optimization. Cambridge University Press.
Trefethen, Lloyd; Bau III, David . Numerical Linear Algebra . Philadelphia: SIAM. 978-0-89871-361-9}}.
Golub, Gene H.; Van Loan, Charles F. . Matrix Computations . Baltimore: The Johns Hopkins University Press. 0-8018-5413-X}}.
Matrix Iterative Analysis, Varga, Richard S., Springer, 2000.
Higham, N. J. . Functions of matrices: theory and computation. SIAM.
Higham, N. J. . Accuracy and stability of numerical algorithms. SIAM.
David S. Watkins , The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM.
Liesen, J., & Strakos, Z. . Krylov subspace methods: principles and analysis. OUP Oxford.

6.2. 和書
-------

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

7. 関連特許
-------

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

8. 外部リンク
--------

[1]

8.1. 手法に関する解説記事
---------------

8.1.1. 反復法
----------

[2]
[3]
[4]
[5]
[6]
[7]

8.1.2. 精度保証
-----------

8.2. 研究グループ・部会
--------------

nla_grp 
siagla 
[8]
[9] 
[10] 

8.3. 全米科学財団
-----------

[11]
[12]

8.4. 科学研究費助成事業
--------------

[13]
[14]
[15]
[16]
[17]