収束特性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/10 15:00 UTC 版)
第nステップでは、クリロフ部分空間Kn内での残差が最小化される。部分空間は常に次の部分空間に含まれるので、残差は単調に減少する。Aの次数をmとすると、m回目の反復の後ではクリロフ部分空間KmはRmと等しいので、GMRES法は厳密解に到達する。しかし、アイデアの骨子は、（mと比較して）少ない回数の反復でベクトルxnが十分な解の近似になる点にある。 一般にはこれは成り立たない。実際、Greenbaum・Pták・Strakošの定理によれば、任意の単調減少列a1, …, am−1、am = 0について、上で定義されたrnに関して、すべてのnで||rn|| = anとなるような行列Aを見つけることができる。特に、m − 1回の反復で一定の値を保ちながら、最後の1反復で残差が0になるような行列を見つけることができる。 ただ、実際にはGMRES法は良い性能を示すことも多い。これは特定の場合に証明できる。Aが正定値なら、 λ m i n {\displaystyle \lambda _{\mathrm {min} }} 、 λ m a x {\displaystyle \lambda _{\mathrm {max} }} をそれぞれ最小、最大固有値として、 ‖ r n ‖ ≤ ( 1 − λ m i n ( A ⊤ + A ) 2 λ m a x ( A T + A ) ) n / 2 ‖ r 0 ‖ {\displaystyle \|r_{n}\|\leq \left(1-{\frac {\lambda _{\mathrm {min} }(A^{\top }+A)}{2\lambda _{\mathrm {max} }(A^{T}+A)}}\right)^{n/2}\|r_{0}\|} が成り立つ。 Aが対称正定値なら、 κ 2 ( A ) {\displaystyle \kappa _{2}(A)} をAのユークリッドノルムでの条件数として、 ‖ r n ‖ ≤ ( κ 2 2 ( A ) − 1 κ 2 2 ( A ) ) n / 2 ‖ r 0 ‖ {\displaystyle \|r_{n}\|\leq \left({\frac {\kappa _{2}^{2}(A)-1}{\kappa _{2}^{2}(A)}}\right)^{n/2}\|r_{0}\|} が成り立つ。 Aが正定値でない場合には、Pnをp(0) = 1を満たす高々n次の多項式集合、VをAのスペクトル分解に現れる行列、σ(A)をAのスペクトルとして、 ‖ r n ‖ ≤ inf p ∈ P n ‖ p n ( A ) ‖ ≤ κ 2 ( V ) inf p ∈ P n max λ ∈ σ ( A ) | p ( λ ) | {\displaystyle \|r_{n}\|\leq \inf _{p\in P_{n}}\|p_{n}(A)\|\leq \kappa _{2}(V)\inf _{p\in P_{n}}\max _{\lambda \in \sigma (A)}|p(\lambda )|} を得る。おおざっぱに言えば、これはAの固有値が0から遠くかつ密集しており、Aが正規行列からそれほど離れていない場合に、速く収束することを意味している。 これらの不等式は誤差、つまり現在の反復ベクトルxnと真の解との距離ではなく、残差に関するものである。
※この「収束特性」の解説は、「GMRES法」の解説の一部です。
「収束特性」を含む「GMRES法」の記事については、「GMRES法」の概要を参照ください。
- 収束特性のページへのリンク
