1 線形方程式の解法の選択
2 参考文献および参考書の記述
線形方程式,
>>> 実非対称/複素非エルミート,
>>> 安定性重視 >>> FOM 法
概要 †
- FOM法(完全直交化法)は1981年にSaadによって提案された非エルミート線形方程式向けのKrylov部分空間法である.
- 初期近似解を
, 対応する初期残差を
と置く.
この時, GMRES法の
反復目の近似解
は,
のように, 初期近似解
とクリロフ部分空間
で張るアフィン空間に含まれ,
の直交条件(Ritz-Galerkin条件)を満たすように設定される.
- Krylov部分空間の基底として, Arnoldi原理によって生成された正規直交基底を用いる.
Arnoldi原理は長い漸化式を持つため, 反復回数
の増加に伴って, 反復当たりの演算量および記憶容量が増大する.
このため, 実用上はリスタート版のFOM(m) 法やトランケート版のDIOM(m)法が用いられる.
- CG 法を非エルミート線形方程式へ拡張した解法であり, FOM法をエルミート線形方程式に対して適用した場合は, CG法と数学的に同値である.
導出 †
準備中
アルゴリズム †
FOM法 †
- Set an initial guess
![](image/math/fa3a3afb0aa0ca382ee374f06b9a19f7.png)
- Compute
![](image/math/4b8eff5bce1372339b42a4d2b3e76b3a.png)
- Set
![](image/math/fb3c9df9bf816a1b0ac6afcc666d1bc2.png)
- For
![](image/math/0cc3e61e0c894bbedc093686a39795d3.png)
-
![](image/math/9863edd95cf977fdb8dcd3b188587c99.png)
- For
![](image/math/3ef7ec52c16e73f031eaf5318b35389b.png)
-
![](image/math/4263b5f0d3bb257cbc279efbef0a661c.png)
-
![](image/math/2ccb0d4501310f01b13b08d50aea160d.png)
- End For
-
![](image/math/c15c931619c45bb28009fc1f86236ab2.png)
-
![](image/math/ed131f78109cef3523f7f234346ac0e2.png)
- For
![](image/math/8094e68eee193e2a094195acf7085f7f.png)
-
![](image/math/39c52dcb5945f0e653fc41af96a20d3e.png)
- End For
- If
then
-
![](image/math/bf1023b55ed58c198a2b1c4651032bb3.png)
-
![](image/math/99d59fc8eb5d247b3422e6bec3ebc9d0.png)
- Stop
- End If
-
![](image/math/d28eb0267f2ebd644f400d3374f275c8.png)
-
![](image/math/c06bd2a361acc0a53e18ef0070013a0a.png)
-
![](image/math/ff7906bd5bdeed48ea77a2a25de02112.png)
-
![](image/math/3e231b3bcf6b4cb267bffcbd673c3bbb.png)
-
![](image/math/f0dbe0ad96630eaea94baf054b8df77b.png)
-
![](image/math/eeae9c2f12a879f2e208b5e67bce6741.png)
- End For
前処理付きFOM法 †
- Set an initial guess
![](image/math/fa3a3afb0aa0ca382ee374f06b9a19f7.png)
- Compute
![](image/math/4b8eff5bce1372339b42a4d2b3e76b3a.png)
- Set
![](image/math/fb3c9df9bf816a1b0ac6afcc666d1bc2.png)
- For
![](image/math/0cc3e61e0c894bbedc093686a39795d3.png)
-
![](image/math/5c5ea424258606391f8aafc0878cedfe.png)
- For
![](image/math/3ef7ec52c16e73f031eaf5318b35389b.png)
-
![](image/math/4263b5f0d3bb257cbc279efbef0a661c.png)
-
![](image/math/2ccb0d4501310f01b13b08d50aea160d.png)
- End For
-
![](image/math/c15c931619c45bb28009fc1f86236ab2.png)
-
![](image/math/ed131f78109cef3523f7f234346ac0e2.png)
- For
![](image/math/8094e68eee193e2a094195acf7085f7f.png)
-
![](image/math/39c52dcb5945f0e653fc41af96a20d3e.png)
- End For
- If
then
-
![](image/math/bf1023b55ed58c198a2b1c4651032bb3.png)
-
![](image/math/ca49d7eae08ff4dd4d9dd85c4b712151.png)
- Stop
- End If
-
![](image/math/d28eb0267f2ebd644f400d3374f275c8.png)
-
![](image/math/c06bd2a361acc0a53e18ef0070013a0a.png)
-
![](image/math/ff7906bd5bdeed48ea77a2a25de02112.png)
-
![](image/math/3e231b3bcf6b4cb267bffcbd673c3bbb.png)
-
![](image/math/f0dbe0ad96630eaea94baf054b8df77b.png)
-
![](image/math/eeae9c2f12a879f2e208b5e67bce6741.png)
- End For
サンプルプログラム †
準備中
適用事例 †
準備中
参考文献および参考書 †
原著論文 †
[13] Yousef Saad, Krylov subspace methods for solving large unsymmetric linear systems, Mathematics of Computation 1981; 37(155):105–126.
教科書 †
[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA,
2003.
P159–161