数学において、GMRES法（GMRESほう、generalized minimal residual method）は、連立一次方程式の数値解を求めるための反復法の一種である[1]。残差をクリロフ部分空間において最小化することにより、近似解を計算する。ベクトルの計算にはアーノルディ法[2]が用いられる。ヨセフ・サードとマルティン・H・シュルツにより、1986年に開発された[3]。
解法

解くべき方程式を

A x = b . {\displaystyle Ax=b.\,}

とする。ただし行列Aは正則なm次正方行列、bは正規化された（ユークリッドノルム||・||に関して||b|。= 1となる）ベクトルとする。

この問題のn次クリロフ部分空間は

K n = span { b , A b , A 2 b , … , A n − 1 b } . {\displaystyle K_{n}=\operatorname {span} \,\{b,Ab,A^{2}b,\ldots ,A^{n-1}b\}.\,}

である。GMRES法では、残差Axn ? bを最小化するベクトルxn ∈ Knによって、Ax = bの厳密解を近似する。

b, Ab, …, An?1bは線形従属に近いため、これを用いる代わりに、アーノルディ法を用いてKnの基底を構成する正規直交化ベクトル列

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]。すなわち、以下の反復を実行する。
アーノルディ法を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?の定理[4]によれば、任意の単調減少列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が正規行列からそれほど離れていない場合に、速く収束することを意味している[5]。

これらの不等式は誤差、つまり現在の反復ベクトルxnと真の解との距離ではなく、残差に関するものである。
解法の拡張
前処理

他の反復法と同様に、GMRES法も通常は収束を速める目的で前処理と組み合わせて使用される[6][7]。
リスタート

nを反復回数として、反復のコストはO(n2)である。すなわち、nとして、連立方程式の本数Nを用いると、直接解法と同程度の求解コストがかかることになる。したがって、GMRES法ではk回の反復の後に、xkを初期ベクトルとして、リスタートを行うことがある。これをGMRES(k)と呼ぶ。しかしながら、リスタートを行うと、収束は非常に遅くなることが知られている。
Flexible GMRES法

前処理をより効率的に行えるよう、アルゴリズムに変更を加えた手法である[8]。前処理に反復解法を用いることができる(前処理にGMRES自身を用いるなど)。
他の解法との比較

アーノルディ法は対称行列の場合にはランチョス法[9]に帰着する。対応するクリロフ部分空間法はPaige・SaundersによるMINRES法（minimal residual method[10][11][12]）である。非対称な場合と異なり、MINRES法は3項漸化式で与えられる。一般行列の場合には、GMRES法のように短い漸化式で残差ノルムを最小化するようなクリロフ部分空間法は存在しないことが知られている。