GMRES法
Q n {\displaystyle Q_{n}} は直交行列なので、
e 1 = ( 1 , 0 , 0 , ... , 0 ) {\displaystyle e_{1}=(1,0,0,\ldots ,0)\,}
を標準基底Rの第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次の一般密行列では約2m回の浮動小数点数演算を要するが、疎行列ではO(m)とすることができる。行列ベクトル積の他に、第nステップの計算にはO(n m)の浮動小数演算が必要である。