数値線形代数

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

## 意義

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

### 現代の主流

現代においては

*共役勾配法
*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)
* 離散勾配法に基づく解法
*フィルターを用いた固有値問題の解法

などをはじめとした高速・高精度解法（反復法）の研究が主流になっている。
#### クリロフ部分空間法

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

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

#### 共役勾配法

**[[共役勾配法]]**（）は 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(m, l)
*STAB系の手法
** BiCGSTAB （biconjugate gradient stabilized method、双共役勾配安定化法、MATLABで利用可能）
** BiCGSTAB2
** QMRCGSTAB
** GBi-CGSTAB
* Block化した手法
** Block CG
** Block BiCGSTAB
** Block BiCGGR
** Block BiCGGR2
** Block GWBiCGSTAB

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

*連立方程式の解に対する精度保証付き数値計算
**並列計算
**悪条件問題 （、条件数が大きい問題）
**前処理行列
**H行列 （比較行列がM行列となる行列）を用いる方法（ペロン・フロベニウスの定理も使う、この方法は疎行列のときも適用可能）
**疎行列に対する精度保証法（コレスキー分解に基づく）
*固有値問題の解に対する精度保証付き数値計算
**ゲルシュゴリンの定理を使う方法（定石として確立されている）
**Krawczyk法（精度保証付き求根アルゴリズムの一つ）を使う方法
**大規模疎行列の場合
**対角化可能行列に対する Bauer-Fike型誤差評価、Hoffman-Wielandt型誤差評価
**一般化固有値問題（）
**逆固有値問題（）
*特異値分解の精度保証
*行列式の精度保証
*行列の乗法
* 行列方程式の解に対する精度保証
* 行列値関数（en）の精度保証（行列値関数の高精度計算法に関する研究についてはHighamなどによる業績が多数ある）
**行列指数関数
**行列の対数
**行列の平方根

## 可積分系との関係

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

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

等が研究されている。

## 関連項目
*行列解析 (en)
*条件数
### ソフトウェア・ライブラリ

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

### 手法

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

## 研究者・専門家
### 日本
*杉原正顯（共役勾配法の研究に従事）
*大石進一（数値線形代数の精度保証に貢献）
*速水謙
### 海外
*:en:Aleksey Krylov（クリロフ部分空間を導入）
#### ドイツ
*カール・グスタフ・ヤコブ・ヤコビ（固有値問題の解法である:en:Jacobi eigenvalue algorithmで知られる）
*イサイ・シューア（逆行列を求めるのに使うシューア補行列で知られる）
*フェルディナント・ゲオルク・フロベニウス（ペロン＝フロベニウスの定理で知られる）
*:en:Helmut Wielandt（固有値問題などについて業績がある）
*アンドレアス・フロマー
#### アメリカ合衆国
*リチャード・バルガ (en)
*ジーン・ゴラブ (en)
*クリーブ・モラー (en)

#### イギリス
*ジェームズ・H・ウィルキンソン
*ニコラス・ハイアム (en)
*ニック・トレフェセン (en)

## 出典

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

### 精度保証に関する論文

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

## 参考文献
### 洋書

* 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. .
* Golub, Gene H.; Van Loan, Charles F. (1996): *Matrix Computations* (3rd ed.), Baltimore: The Johns Hopkins University Press. .
* 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.
*  
* 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.

### 和書

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

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

## 外部リンク

*
*
*
*
* Some Journals in Numerical Linear Algebra
### 手法に関する解説記事
#### 反復法
*最小残差法
*MINRES 法
*CR法 (共役残差法)
*CG法 (共役勾配法)
*Arnoldi法
*行列の固有値問題
*

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

### 全米科学財団
*Collaborative Research: Randomized Numerical Linear Algebra (RandNLA) for multi-linear and non-linear data
*Numerical Linear Algebra and Eigenvalue Computations
### 科学研究費助成事業
*数値線形代数における高精度計算アルゴリズムの開発
*ロバストで高効率な数値線形代数アルゴリズムの開発
*量子計算を併用した数値線形代数学の開拓
*エクサ時代の非同期タスクを応用した高性能高次元数値線形代数の研究
*リーマン多様体上の最適化アルゴリズムおよびその数値線形代数への応用