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

---------------------------------------------
*概要 [#y944675d]
-GMRES法(一般化最小残差法)は1986年にSaadとSchultzよって提案された非エルミート線形方程式向けのKrylov部分空間法である.

-初期近似解を&math(\vec{x}_0);, 対応する初期残差を&math(\vec{r}_0:=\vec{b}-A\vec{x}_0);と置く.
この時, GMRES法の&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,r_0));で張るアフィン空間に含まれ, 最小残差条件
#br
CENTER:&math(\min \| \vec{r}_k \|_2);
#br
を満たすように設定される.
このため, 残差ノルム&math(\| \vec{r}_k \|_2);の単調減少性が保証される.

-GMRES法の残差ベクトル&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
の直交性を持つ.

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

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

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


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

//---------------------------------------------
*アルゴリズム [#g3c09fe9]
**GMRES法 [#xc2f5148]
+Set an initial guess &math(\vec{x}_0);
+Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0);
+Set &math(\beta=\|\vec{r}_0\|_2, \vec{v}_1=\vec{r}_0/\beta, \vec{e}_1=[\beta, 0, \ldots, 0]^T);
+For &math(k = 1, 2, \ldots);
+　　&math(\vec{w}_{k+1} = A \vec{v}_k);
+　　For &math(i = 1, 2, \ldots, k);
+　　　　&math(h_{i,k} = (\vec{w}_{k+1},\vec{v}_i));
+　　　　&math(\vec{w}_{i,k} = \vec{w}_{i,k} - h_{i,k}\vec{v}_i);
+　　End For
+　　&math(h_{k+1,k} = \| \vec{w}_{k+1} \|_2);
+　　&math(\vec{w}_{k+1} = \vec{w}_{k+1} / h_{k+1,k});
+　　For &math(i = 1, 2, \ldots, k-1);
+　　　　&math( \left( \begin{array}{c} h_{i,k} \\ h_{i+1,k} \end{array} \right) = \left( \begin{array}{cc} \overline{c}_i & \overline{s}_i \\ -s_i & c_i \end{array} \right) \left( \begin{array}{c} h_{i,k} \\ h_{i+1,k} \end{array} \right) );
+　　End For
+　　&math(c_k = \frac{h_{k,k}}{ \sqrt{ h_{k,k}^2+ | h_{k+1,k} |^2 }});
+　　&math(s_k = \frac{h_{k+1,k}}{ \sqrt{ h_{k,k}^2+ | h_{k+1,k} |^2 }});
+　　&math(e_{k+1} = -s_k e_k);
+　　&math(e_k = \overline{c}_k e_k);
+　　&math(h_{k,k} = \sqrt{ h_{k,k}^2+ | h_{k+1,k} |^2 });
+　　&math(h_{k+1,k}=0);
+　　If &math( |e_{k+1}| / \| \vec{b}\|_2 \leq \epsilon); then
+　　　　&math(\vec{y}_k = H_k^{-1} \vec{e}_1);
+　　　　&math(\vec{x}_k = \vec{x}_0 + \sum_{i=1}^k \vec{v}_i y_i);
+　　　　Stop
+　　End If
+End For

**前処理付きGMRES法 [#xc2f5148]
+Set an initial guess &math(\vec{x}_0);
+Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0);
+Set &math(\beta=\|\vec{r}_0\|_2, \vec{v}_1=\vec{r}_0/\beta, \vec{e}_1=[\beta, 0, \ldots, 0]^T);
+For &math(k = 1, 2, \ldots);
+　　&math(\vec{w}_{k+1} = AK^{-1} \vec{v}_k);
+　　For &math(i = 1, 2, \ldots, k);
+　　　　&math(h_{i,k} = (\vec{w}_{k+1},\vec{v}_i));
+　　　　&math(\vec{w}_{i,k} = \vec{w}_{i,k} - h_{i,k}\vec{v}_i);
+　　End For
+　　&math(h_{k+1,k} = \| \vec{w}_{k+1} \|_2);
+　　&math(\vec{w}_{k+1} = \vec{w}_{k+1} / h_{k+1,k});
+　　For &math(i = 1, 2, \ldots, k-1);
+　　　　&math( \left( \begin{array}{c} h_{i,k} \\ h_{i+1,k} \end{array} \right) = \left( \begin{array}{cc} \overline{c}_i & \overline{s}_i \\ -s_i & c_i \end{array} \right) \left( \begin{array}{c} h_{i,k} \\ h_{i+1,k} \end{array} \right) );
+　　End For
+　　&math(c_k = \frac{h_{k,k}}{ \sqrt{ h_{k,k}^2+ | h_{k+1,k} |^2 }});
+　　&math(s_k = \frac{h_{k+1,k}}{ \sqrt{ h_{k,k}^2+ | h_{k+1,k} |^2 }});
+　　&math(e_{k+1} = -s_k e_k);
+　　&math(e_k = \overline{c}_k e_k);
+　　&math(h_{k,k} = \sqrt{ h_{k,k}^2+ | h_{k+1,k} |^2 });
+　　&math(h_{k+1,k}=0);
+　　If &math( |e_{k+1}| / \| \vec{b}\|_2 \leq \epsilon); then
+　　　　&math(\vec{y}_k = H_k^{-1} \vec{e}_1);
+　　　　&math(\vec{x}_k = \vec{x}_0 + K^{-1} \sum_{i=1}^k \vec{v}_i y_i);
+　　　　Stop
+　　End If
+End For

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

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

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

**原著論文 [#r3a47c2b]
[15] Yousef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing 1986; 7(3):856–869.

**教科書 [#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;
P19–21

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

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

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

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