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

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

*概要 [#ua8d5a40]
-初期近似解を&math(\vec{x}_0);, 対応する初期残差を&math(\vec{r}_0:=\vec{b}-A\vec{x}_0);と置く.
この時, GCR法の&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条件)を満たすように設定される.

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

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

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

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

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

//---------------------------------------------
*アルゴリズム [#g3c09fe9]
**GCR法 [#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 = 1, 2, \ldots);
+　　&math(\quad \alpha_k = (A\vec{p}_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_{i,k} = -(A\vec{p}_i,A\vec{r}_{k+1})/(A\vec{p}_i,A\vec{p}_i), \quad i = 1, 2, \ldots, k);
+　　&math(\quad \vec{p}_{k+1} = \vec{r}_{k+1} + \sum_{i=0}^k \beta_{i,k} \vec{p}_i);
+　　&math(\quad A\vec{p}_{k+1} = A\vec{r}_{k+1} + \sum_{i=0}^k \beta_{i,k} A\vec{p}_i);
+End For

**前処理付きGCR法 [#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 = 1, 2, \ldots);
+　　&math(\quad \alpha_k = (A\vec{p}_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_{i,k} = -(A\vec{p}_i,AK^{-1}\vec{r}_{k+1})/(A\vec{p}_i,A\vec{p}_i), \quad i = 1, 2, \ldots, k);
+　　&math(\quad \vec{p}_{k+1} = K^{-1}\vec{r}_{k+1} + \sum_{i=0}^k \beta_{i,k} \vec{p}_i);
+　　&math(\quad A\vec{p}_{k+1} = AK^{-1}\vec{r}_{k+1} + \sum_{i=0}^k \beta_{i,k} A\vec{p}_i);
+End For


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

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

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

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

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

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

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