1 線形方程式の解法の選択 概要 †
導出 †2次関数最小化としての導出 †線形方程式 ![]() は, ![]() を(反復法で)解くことで, 線形方程式 逐次最小化法 †最小化問題(1)を解く単純な反復法として, 適当な初期近似解
を繰り返すアルゴリズムが考えられる.
このアルゴリズムは逐次最小化法とよばれ, 1次元最小化の係数 最急降下法 †探索方向ベクトル ![]() のように 共役方向法 †一方, 一般の逐次最小化法で得られる近似解 ![]() に属する.
ここで, 逐次最小化法(の探索方向ベクトル ![]() を仮定すると, 以下が成り立つ.
このように逐次最小化法の探索方向ベクトル 共役勾配法 †最急降下法に基づく共役方向法として, ![]() ![]() と設定する方法を共役勾配法(Conjugate Gradient法)と呼ぶ.
また, CG法の ![]() のように変形出来る. クリロフ部分空間法としての導出 †初期近似解を ![]() の基底を列に持つ ![]() と書ける.
ここで, CG法は, Lanczos原理に基づき基底 Lanczos原理 †行列
ここで, 行列 ![]() と置くと, Lanczos原理の行列表現 ![]() を得る.
ここで, Ritz-Galerkin条件 †CG法のベクトル ![]() の直交性を持つよう設定される. この直交条件をRitz-Galerkin条件と呼ぶ. CG法導出の基本原理 †Lanczos原理の行列表現(4)およびRitz-Galerkin条件(5)より, ![]() が成り立つ.
ここで, ![]() を解くことで計算される. 導出の詳細 †係数行列 一方, CG法の導出はLanczos法やSYMMLQ法と少し異なる.
行列 ![]() と書ける. 式(7)および ![]() の漸化式により計算出来る.
ただし, 一方で, ![]() の関係式およびRitz-Galerkin条件(5)から, ![]() が成り立つ.
これらの条件が成り立つよう, 漸化式の ![]() のように設定される. アルゴリズム †CG法 †
前処理付きCG法 †
サンプルプログラム †準備中 適用事例 †準備中 参考文献および参考書 †原著論文 †[10] Magnes R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards 1952; 49(6):409–436. 教科書 †[2] Richard Barrett, Michael W. Berry, Tony F. Chan, James Demmel, June Donato, Jack Dongarra,
Victor Eijkhout, Roldan Pozo, Charles Romine and Henk A. van der Vorst, Templates for the
Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM: Philadelphia, PA,
1993. [14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA,
2003. [27] Henk A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University
Press: New York, NY, 2003. [23] Masaaki Sugihara and Kazuo Murota, Theoretical Numerical Linear Algebra, Iwanami Press:
Tokyo, 2009, (in Japanese). [29] 藤野 清次, 張 紹良, 反復法の数理 (応用数値計算ライブラリ) 朝倉書店, 1996. |