[[1 線形方程式の解法の選択]]&br;
[[2 参考文献および参考書の記述]]&br;
線形方程式, &math(Ax=b); >>> 実対称/複素エルミート, &math(A=A^H); >>> 正定値 >>> CG 法
#contents

---------------------------------------------

*概要 [#y944675d]
1952年にHestenesとStiefelよって提案された, 正定値エルミート(HPD)線形方程式向けに提案されたKrylov部分空間法.
-1952年にHestenesとStiefelよって提案された, 正定値エルミート(HPD)線形方程式向けに提案されたKrylov部分空間法である.

-初期近似解を&math(x_0);対応する初期残差を&math(r_0:=b-Ax_0);と置く.
また, 線形方程式&math(Ax=b);の真の解を&math(x^\ast:=A^{-1}b);と置く.
この時, CG法の&math(k);反復目の近似解&math(x_k);は, 
#br
#math(x_k \in x_0 + {\mathcal K}_k(A,r_0), \quad {\mathcal K}_k(A,r_0) := {\bf span}\{r_0, Ar_0, \ldots, A^{k-1}r_0 \})
#br
のように, 初期近似解&math(x_0);とクリロフ部分空間&math({\mathcal K}_k(A,r_0));で張るアフィン空間に含まれ, アフィン空間上で2次関数
#br
#math(\phi(x):= (x-x^\ast, A(x-x^\ast)))
#br
を最小化するように設定される.
(行列&math(A);が正定値の時, &math(\phi(x) \geq 0 = \phi(x^\ast));である.)

-CG法の近似解&math(x_k);に対応する残差ベクトル&math(r_k=b-Ax_k);は
#br
#math(r_k \bot {\mathcal K}_k(A,r_0))
#br
の直交性(Ritz-Galerkin条件)を持つ.

-CG法の収束性は
#br
#math(\phi(x_k) \leq \phi(x_0) \cdot 4 \left( \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1} \right)^{2k} )
#br
で表され, 2次関数値&math(\phi(x_k));は単調に減少する.
ここで, &math(\kappa=);(最大固有値)/(最小固有値)であるとする.
ただし, 一般に収束判定に用いられる残差ノルム&math(\| r_k \|_2);は単調減少しない点に注意する.


//---------------------------------------------
*導出 [#w048acf0]
準備中
//
//~線形方程式&math(Ax=b);の真の解を&math(x^\ast:=A^{-1}b);と置く.
//この時, 2次関数
//#br
//#math(\phi(x):= (x-x^\ast, A(x-x^\ast)))
//#br
//は, &math(\phi(x) \geq 0 = \phi(x^\ast));を満たす.
//そこで, 2次関数&math(\phi(x));の最小化問題を(反復法で)解くことで, 線形方程式&math(Ax=b);の解を得ることを考える.
//
//~2次関数&math(\phi(x));の最小化問題を解く単純な反復法として, 適当な初期近似解&math(x_0);に対し,
//
//+何らかの方法で, 探索方向ベクトル&math(p_k);を定める.
//+&math(\phi(x_k+\alpha_k p_k));を最小化するよう&math(\alpha_k);を設定し, &math(x_{k+1} = x_k + \alpha_k p_k);のように解を更新する.
//
//を繰り返すアルゴリズム(逐次最小化法)が考えられる.
//ここで, &math(\alpha_k = \frac{ (r_k,p_k)}{(p_k,Ap_k)});として容易に計算出来る.
//
//~最も自然な探索方向ベクトルの選び方として, 
//#br
//#math(p_k = -\nabla \phi(x_k) = r_k)
//#br
//が考えられる.
//この方法は再急降下法と呼ばれ, 


//---------------------------------------------
*アルゴリズム [#n7b3760f]
**CG法 [#vf9dca7d]
+Set an initial guess &math(x_0);
+Compute &math(r_0=b-Ax_0, p_0 = r_0);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (r_k, r_k)/ (p_k, Ap_k));
+　　&math(\quad x_{k+1} = x_k + \alpha_k p_k);
+　　&math(\quad r_{k+1} = r_k - \alpha_k A p_k);
+　　&math(\quad \beta_k = (r_{k+1},r_{k+1})/(r_k,r_k));
+　　&math(\quad p_{k+1} = r_{k+1} + \beta_k p_k);
+End For

**前処理付きCG法 [#da0d7d55]
+Set an initial guess &math(x_0);
+Compute &math(r_0=b-Ax_0, p_0 = r_0);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (K^{-1} r_k, r_k)/ (p_k, Ap_k));
+　　&math(\quad x_{k+1} = x_k + \alpha_k p_k);
+　　&math(\quad r_{k+1} = r_k - \alpha_k A p_k);
+　　&math(\quad \beta_k = (K^{-1} r_{k+1},r_{k+1})/(K^{-1} r_k,r_k));
+　　&math(\quad p_{k+1} = K^{-1} r_{k+1} + \beta_k p_k);
+End For


//---------------------------------------------
*サンプルプログラム [#pae4c166]
準備中


//---------------------------------------------
*適用事例 [#v6f0663d]
準備中


//---------------------------------------------
*参考文献および参考書 [#t1b3c233]

**原著論文 [#r3a47c2b]
[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.

**教科書 [#o9b766b8]
[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.&br;
P14–17

[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA,
2003.&br;
P187–194

[27] Henk A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University
Press: New York, NY, 2003.&br;
P37–47

[23] Masaaki Sugihara and Kazuo Murota, Theoretical Numerical Linear Algebra, Iwanami Press:
Tokyo, 2009, (in Japanese).&br;
P148–153&br;

[29] 藤野 清次, 張 紹良, 反復法の数理 (応用数値計算ライブラリ)　朝倉書店, 1996.&br;
P31–35
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS