GCR 法

1 線形方程式の解法の選択
2 参考文献および参考書の記述
線形方程式, >>> 実非対称/複素非エルミート, >>> 安定性重視 >>> GCR 法

概要 †

• GCR法(共役残差法)は1983年にEisenstat, Elman, Schultzによって提案された非エルミート線形方程式向けのKrylov部分空間法である.

• 初期近似解を, 対応する初期残差をと置く. この時, GCR法の反復目の近似解は,
   
  
   
  のように, 初期近似解とクリロフ部分空間で張るアフィン空間に含まれ, 残差ベクトルが
   
  
   
  の直交条件(Petrov-Galerkin条件)を満たすように設定される.

• GCR法の残差ベクトルは, 最小残差条件
   
  
   
  を満たし, 残差ノルムの単調減少性が保証される.

• Krylov部分空間の基底として, Arnoldi原理によって生成された正規直交基底を用いる. Arnoldi原理は長い漸化式を持つため, 反復回数の増加に伴って, 反復当たりの演算量および記憶容量が増大する. このため, 実用上はリスタート版のGCR(m) 法やトランケート版のORTHOMIN(m) 法が用いられる.

• GMRES 法と数学的に同値である.

• CR 法を非エルミート線形方程式へ拡張した解法であり, GCR法をエルミート線形方程式に対して適用した場合は, CR法と数学的に同値である.

導出 †

準備中

アルゴリズム †

GCR法 †

1. Set an initial guess
2. Compute
3. For
4. 　　
5. 　　
6. 　　
7. 　　
8. 　　
9. 　　
10. End For

前処理付きGCR法 †

1. Set an initial guess
2. Compute
3. For
4. 　　
5. 　　
6. 　　
7. 　　
8. 　　
9. 　　
10. End For

サンプルプログラム †

準備中

適用事例 †

準備中

参考文献および参考書 †

原著論文 †

[5] Stanley C. Eisenstat, Howard C. Elman and Martin H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM Journal on Numerical Analysis 1983; 20(2):345–357.

教科書 †

[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA, 2003.
P194–196

[23] Masaaki Sugihara and Kazuo Murota, Theoretical Numerical Linear Algebra, Iwanami Press: Tokyo, 2009, (in Japanese).
P164–173

[29] 藤野 清次, 張 紹良, 反復法の数理 (応用数値計算ライブラリ)　朝倉書店, 1996.
P63–70