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

---------------------------------------------
*概要 [#y944675d]
-FOM法(完全直交化法)は1981年にSaadよって提案された非エルミート線形方程式向けのKrylov部分空間法である.

*概要 [#dda4fec0]
-初期近似解を&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(\vec{r}_k \bot A{\mathcal K}_k(A,\vec{r}_0));
#br
の直交条件(Ritz-Galerkin条件)を満たすように設定される.

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

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


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

//---------------------------------------------
*アルゴリズム [#g3c09fe9]
**FOM法 [#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
+　　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
+　　&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);
+End For

**前処理付きFOM法 [#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
+　　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
+　　&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);
+End For

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

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

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

**原著論文 [#j6a5214f]
[13] Yousef Saad, Krylov subspace methods for solving large unsymmetric linear systems, Mathematics of Computation 1981; 37(155):105–126.

**教科書 [#p14a21d5]
[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA,
2003.&br;
P159–161
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS