GMRES 法
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[1 線形方程式の解法の選択]]&br;
[[2 参考文献および参考書の記述]]&br;
線形方程式, &math(Ax=b); >>> 実非対称/複素...
#contents
---------------------------------------------
*概要 [#y944675d]
-GMRES法(一般化最小残差法)は1986年にSaadとSchultzによって...
-初期近似解を&math(\vec{x}_0);, 対応する初期残差を&math(\...
この時, GMRES法の&math(k);反復目の近似解&math(\vec{x}_k);...
#br
CENTER:&math(\vec{x}_k \in \vec{x}_0 + {\mathcal K}_k(A,\...
#br
のように, 初期近似解&math(\vec{x}_0);とクリロフ部分空間&m...
#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) 法]]やトランケ...
-[[GCR 法]]と数学的に同値である.
-[[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/\be...
+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}\ve...
+ 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...
+ End For
+ &math(c_k = \frac{h_{k,k}}{ \sqrt{ h_{k,k}^2+ | h_{k...
+ &math(s_k = \frac{h_{k+1,k}}{ \sqrt{ h_{k,k}^2+ | h_...
+ &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); t...
+ &math(\vec{y}_k = H_k^{-1} \vec{e}_1);
+ &math(\vec{x}_k = \vec{x}_0 + \sum_{i=1}^k \vec{...
+ 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/\be...
+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}\ve...
+ 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...
+ End For
+ &math(c_k = \frac{h_{k,k}}{ \sqrt{ h_{k,k}^2+ | h_{k...
+ &math(s_k = \frac{h_{k+1,k}}{ \sqrt{ h_{k,k}^2+ | h_...
+ &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); t...
+ &math(\vec{y}_k = H_k^{-1} \vec{e}_1);
+ &math(\vec{x}_k = \vec{x}_0 + K^{-1} \sum_{i=1}^...
+ Stop
+ End If
+End For
//---------------------------------------------
*サンプルプログラム [#z4fb948d]
準備中
//---------------------------------------------
*適用事例 [#xb92758f]
準備中
*参考文献および参考書 [#t1b3c233]
**原著論文 [#r3a47c2b]
[15] Yousef Saad and Martin H. Schultz, GMRES: a generali...
**教科書 [#o9b766b8]
[2] Richard Barrett, Michael W. Berry, Tony F. Chan, Jame...
Victor Eijkhout, Roldan Pozo, Charles Romine and Henk A. ...
Solution of Linear Systems: Building Blocks for Iterative...
1993.&br;
P19–21
[14] Yousef Saad, Iterative Methods for Sparse Linear Sys...
2003.&br;
P164–172
[27] Henk A. van der Vorst, Iterative Krylov Methods for ...
Press: New York, NY, 2003.&br;
P65–84
[23] Masaaki Sugihara and Kazuo Murota, Theoretical Numer...
Tokyo, 2009, (in Japanese).&br;
P173–181
[29] 藤野 清次, 張 紹良, 反復法の数理 (応用数値計算ライブ...
P57–63
終了行:
[[1 線形方程式の解法の選択]]&br;
[[2 参考文献および参考書の記述]]&br;
線形方程式, &math(Ax=b); >>> 実非対称/複素...
#contents
---------------------------------------------
*概要 [#y944675d]
-GMRES法(一般化最小残差法)は1986年にSaadとSchultzによって...
-初期近似解を&math(\vec{x}_0);, 対応する初期残差を&math(\...
この時, GMRES法の&math(k);反復目の近似解&math(\vec{x}_k);...
#br
CENTER:&math(\vec{x}_k \in \vec{x}_0 + {\mathcal K}_k(A,\...
#br
のように, 初期近似解&math(\vec{x}_0);とクリロフ部分空間&m...
#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) 法]]やトランケ...
-[[GCR 法]]と数学的に同値である.
-[[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/\be...
+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}\ve...
+ 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...
+ End For
+ &math(c_k = \frac{h_{k,k}}{ \sqrt{ h_{k,k}^2+ | h_{k...
+ &math(s_k = \frac{h_{k+1,k}}{ \sqrt{ h_{k,k}^2+ | h_...
+ &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); t...
+ &math(\vec{y}_k = H_k^{-1} \vec{e}_1);
+ &math(\vec{x}_k = \vec{x}_0 + \sum_{i=1}^k \vec{...
+ 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/\be...
+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}\ve...
+ 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...
+ End For
+ &math(c_k = \frac{h_{k,k}}{ \sqrt{ h_{k,k}^2+ | h_{k...
+ &math(s_k = \frac{h_{k+1,k}}{ \sqrt{ h_{k,k}^2+ | h_...
+ &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); t...
+ &math(\vec{y}_k = H_k^{-1} \vec{e}_1);
+ &math(\vec{x}_k = \vec{x}_0 + K^{-1} \sum_{i=1}^...
+ Stop
+ End If
+End For
//---------------------------------------------
*サンプルプログラム [#z4fb948d]
準備中
//---------------------------------------------
*適用事例 [#xb92758f]
準備中
*参考文献および参考書 [#t1b3c233]
**原著論文 [#r3a47c2b]
[15] Yousef Saad and Martin H. Schultz, GMRES: a generali...
**教科書 [#o9b766b8]
[2] Richard Barrett, Michael W. Berry, Tony F. Chan, Jame...
Victor Eijkhout, Roldan Pozo, Charles Romine and Henk A. ...
Solution of Linear Systems: Building Blocks for Iterative...
1993.&br;
P19–21
[14] Yousef Saad, Iterative Methods for Sparse Linear Sys...
2003.&br;
P164–172
[27] Henk A. van der Vorst, Iterative Krylov Methods for ...
Press: New York, NY, 2003.&br;
P65–84
[23] Masaaki Sugihara and Kazuo Murota, Theoretical Numer...
Tokyo, 2009, (in Japanese).&br;
P173–181
[29] 藤野 清次, 張 紹良, 反復法の数理 (応用数値計算ライブ...
P57–63
ページ名:
![[JICFuS Wiki]](image/pukiwiki.png "[JICFuS Wiki]")
