数学において、GMRES法（generalized minimal residual method）は、連立一次方程式の数値解を求めるための反復法の一種である。残差をクリロフ部分空間において最小化することにより、近似解を計算する。ベクトルの計算にはアーノルディ法
が用いられる。ヨセフ・サードとマルティン・H・シュルツにより、1986年に開発された[1]。
目次
1 解法
2 収束特性
3 解法の拡張
3.1 前処理
3.2 リスタート
3.3 Flexible GMRES法
4 他の解法との比較
5 最小二乗問題の求解
6 補足
7 参考文献
q 1 , q 2 , … , q n {\displaystyle q_{1},q_{2},\ldots ,q_{n}\,}
を計算する。すなわち、xn ∈ Knはyn ∈ Rnを用いてxn = Qnynと書くことができる。ただしQnはq1, …, qnにより構成されるm×n行列とする。
アーノルディ過程では、
A Q n = Q n + 1 H ~ n {\displaystyle AQ_{n}=Q_{n+1}{\tilde {H}}_{n}}
を満たす(n+1)×n次上ヘッセンベルグ行列 H ~ n {\displaystyle {\tilde {H}}_{n}} が生成される。 Q n {\displaystyle Q_{n}} は直交行列なので、
e 1 = ( 1 , 0 , 0 , … , 0 ) {\displaystyle e_{1}=(1,0,0,\ldots ,0)\,}
を標準基底Rn+1の第1ベクトルとして、
∥ A x n − b ∥ = ∥ H ~ n y n − e 1 ∥ {\displaystyle \|Ax_{n}-b\|=\|{\tilde {H}}_{n}y_{n}-e_{1}\|}
が成り立つ。したがって、 x n {\displaystyle x_{n}} は残差
r n = H ~ n y n − e 1 . {\displaystyle r_{n}={\tilde {H}}_{n}y_{n}-e_{1}.}
のノルムを最小化することにより計算できる。これはn次の線形最小二乗問題である。
以上からGMRES法のアルゴリズムが得られる。すなわち、以下の反復を実行する。
アーノルディ法を1ステップ計算する
||rn||を最小化する y n {\displaystyle y_{n}} を見つける
x n = Q n y n {\displaystyle x_{n}=Q_{n}y_{n}} を計算する
残差が十分小さくなるまでこれを繰り返す
各反復で、行列ベクトル積Aqnを計算する必要がある。これはm次の一般密行列では約2m2回の浮動小数点数演算を要するが、疎行列ではO(m)とすることができる。行列ベクトル積の他に、第nステップの計算にはO(n m)の浮動小数演算が必要である。 第nステップでは、クリロフ部分空間Kn内での残差が最小化される。部分空間は常に次の部分空間に含まれるので、残差は単調に減少する。Aの次数をmとすると、m回目の反復の後ではクリロフ部分空間KmはRmと等しいので、GMRES法は厳密解に到達する。しかし、アイデアの骨子は、（mと比較して）少ない回数の反復でベクトルxnが十分な解の近似になる点にある。 一般にはこれは成り立たない。実際、Greenbaum・Ptak・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}\|}
収束特性