GMRES法
GMRES法では、
‖ H ~ n y n − e 1 ‖ {\displaystyle \|{\tilde {H}}_{n}y_{n}-e_{1}\|}
を最小化するベクトル y n {\displaystyle y_{n}} を見つける必要がある。 これはQR分解を計算することで実現できる。すなわち、
Ω n H ~ n = R ~ n . {\displaystyle \Omega _{n}{\tilde {H}}_{n}={\tilde {R}}_{n}.}
を満たすn+1次正方直交行列Ωnとn+1×n次上三角行列 R ~ n {\displaystyle {\tilde {R}}_{n}} を計算する。三角行列の行数は列数より1多いので、最下行はすべて零である。したがって、 R n {\displaystyle R_{n}} をn×n次三角行列として、これを
R ~ n = [ R n 0 ] , {\displaystyle {\tilde {R}}_{n}={\begin{bmatrix}R_{n}\\0\end{bmatrix}},}
と分解することができる。
QR分解は、零の行と1列分の値が異なるだけなので、簡単に更新することができる。つまりhn = (h1n, ... hnn)として
から容易に解くことができる。実際、gn ∈ Rn、γn ∈ Rとして、ベクトル Ω n e 1 {\displaystyle \Omega _{n}e_{1}} を
g ~ n = [ g n γ n ] {\displaystyle {\tilde {g}}_{n}={\begin{bmatrix}g_{n}\\\gamma _{n}\end{bmatrix}}}
と表すと、これは
‖ H ~ n y n − e 1 ‖ = ‖ R ~ n y n − Ω n e 1 ‖ = ‖ [ R n 0 ] y − [ g n γ n ] ‖ {\displaystyle \|{\tilde {H}}_{n}y_{n}-e_{1}\|=\|{\tilde {R}}_{n}y_{n}-\Omega _{n}e_{1}\|=\left\|{\begin{bmatrix}R_{n}\\0\end{bmatrix}}y-{\begin{bmatrix}g_{n}\\\gamma _{n}\end{bmatrix}}\right\|}
と書ける。これを最小化するベクトルyは
y n = R n − 1 g n {\displaystyle y_{n}=R_{n}^{-1}g_{n}}
で与えられる。 g n {\displaystyle g_{n}} の更新も容易に行うことができる。
Any nonincreasing convergence curve is possible for GMRES. SIAM journal on matrix analysis and applications, 17(3), 465-469.
↑ Trefethen & Bau, Thm 35.2
↑ Baglama, J., Calvetti, D., Golub, G. H., & Reichel, L. (1998). Adaptively preconditioned GMRES algorithms. SIAM Journal on Scientific Computing, 20(1), 243-269.
↑ Burrage, K., & Erhel, J. (1998). On the performance of various adaptive preconditioned GMRES strategies. Numerical linear algebra with applications, 5(2), 101-121.
↑ Frayssé, V., Giraud, L., & Gratton, S. (1998). A set of Flexible-GMRES routines for real and complex arithmetics. Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique TR/PA/98/20.