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

---------------------------------------------
*参考文献および参考書 [#vc40ce99]
*概要 [#y944675d]
-CR法(共役残差法)は1952年にStiefelによって提案されたエルミート線形方程式向けのKrylov部分空間法である.

[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.
-初期近似解を&math(\vec{x}_0);, 対応する初期残差を&math(\vec{r}_0:=\vec{b}-A\vec{x}_0);と置く.
この時, CR法の&math(k);反復目の近似解&math(\vec{x}_k);は,
#br
CENTER:&math(\vec{x}_k \in \vec{x}_0 + {\mathcal K}_k(A,\vec{r}_0), \quad {\mathcal K}_k(A,\vec{r}_0) := {\bf span}\{\vec{r}_0, A\vec{r}_0, \ldots, A^{k-1}\vec{r}_0 \});
#br
のように, 初期近似解&math(\vec{x}_0);とクリロフ部分空間&math({\mathcal K}_k(A,\vec{r}_0));で張るアフィン空間に含まれ, 残差ベクトル&math(\vec{r}_k=\vec{b}-A\vec{x}_k);が
#br
CENTER:&math(\vec{r}_k \bot A{\mathcal K}_k(A,\vec{r}_0));
#br
の直交条件(Petrov-Galerkin条件)を満たすように設定される.

[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
-CR法の残差ベクトル&math(\vec{r}_k=\vec{b}-A\vec{x}_k);は, 最小残差条件
#br
CENTER:&math(\min \| \vec{r}_k \|_2);
#br
を満たし, 残差ノルム&math(\| \vec{r}_k \|_2);の単調減少性が保証される.

-[[MINRES 法]]と数学的に同値である.

-[[CG 法]]と異なり, 不定値な行列に対しても適用可能である.

//---------------------------------------------
*導出 [#y765dbc2]
準備中

//---------------------------------------------
*アルゴリズム [#g3c09fe9]
**CR法 [#x87397e4]
+Set an initial guess &math(\vec{x}_0);
+Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0, \vec{p}_0 = \vec{r}_0);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (A\vec{r}_k, \vec{r}_k)/ (A\vec{p}_k, A\vec{p}_k));
+　　&math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{p}_k);
+　　&math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k A \vec{p}_k);
+　　&math(\quad \beta_k = (A\vec{r}_{k+1},\vec{r}_{k+1})/(A\vec{r}_k,\vec{r}_k));
+　　&math(\quad \vec{p}_{k+1} = \vec{r}_{k+1} + \beta_k \vec{p}_k);
+　　&math(\quad A\vec{p}_{k+1} = A\vec{r}_{k+1} + \beta_k A\vec{p}_k);
+End For

**前処理付きCR法 [#da0d7d55]
+Set an initial guess &math(\vec{x}_0);
+Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0, \vec{p}_0 = K^{-1}\vec{r}_0);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (AK^{-1} \vec{r}_k, K^{-1}\vec{r}_k)/ (K^{-1}A\vec{p}_k, A\vec{p}_k));
+　　&math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{p}_k);
+　　&math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k A \vec{p}_k);
+　　&math(\quad K^{-1}\vec{r}_{k+1} = K^{-1}\vec{r}_k - \alpha_k K^{-1}A \vec{p}_k);
+　　&math(\quad \beta_k = (AK^{-1} \vec{r}_{k+1},K^{-1}\vec{r}_{k+1})/(AK^{-1} \vec{r}_k,K^{-1}\vec{r}_k));
+　　&math(\quad \vec{p}_{k+1} = K^{-1} \vec{r}_{k+1} + \beta_k \vec{p}_k);
+　　&math(\quad A\vec{p}_{k+1} = AK^{-1} \vec{r}_{k+1} + \beta_k A\vec{p}_k);
+End For


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

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

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

**原著論文 [#r3a47c2b]
[22] Eduard Stiefel, Relaxationsmethoden bester strategie zur l¨osung linearer gleichungssysteme, Commentarii Mathematici Helvetici 1952; 29(1):157–179.

**教科書 [#o9b766b8]
[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA,
2003.&br;
P187–194
P194

[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;
P31–35
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS