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

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

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

-リスタート版[[GMRES 法]].
:リスタート|アルゴリズムの反復を所定のリスタート周期&math(m);で停止し, 得られた近似解を初期近似解として再びアルゴリズムを適用する.

-リスタートを適用することで, Arnoldi原理の長い漸化式に由来するGMRES法の問題点を解決出来る.
一方で, 収束性は悪化する.

-GMRES法と同様残差ノルム&math(\|\vec{r}_k\|_2);の単調減少性は保証される.

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

//---------------------------------------------
*アルゴリズム [#g3c09fe9]
**GMRES(m)法 [#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, m);
+　　&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}| \leq \epsilon \| \vec{b}\|_2); or &math(k = m); 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);
+　　　　exit
+　　End If
+End For
+Set &math(\vec{x}_0 = \vec{x}_m); and go to 2

**前処理付きGMRES(m)法 [#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, m);
+　　&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}| \leq \epsilon \| \vec{b}\|_2); or &math(k = m); 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);
+　　　　exit
+　　End If
+End For
+Set &math(\vec{x}_0 = \vec{x}_m); and go to 2

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

//---------------------------------------------
*適用事例 [#xb92758f]
準備中
*参考文献および参考書 [#y36be55d]

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

**教科書 [#m4b4f601]
[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