Generalized minimal residual method

Remarks

Every $x \in x_0 + \mathcal{K}_k(A, r_0)$ has residual $p(A) r_0$ for a polynomial $p$ of degree at most $k$ with $p(0) = 1$, which gives clause 4. Clause 1 holds because the search spaces grow, and clause 2 follows from $A Q_k = Q_{k+1} \tilde{H}_k$ and the orthonormality of the columns of $Q_{k+1}$. For clause 3, if $\mathcal{K}_k(A, r_0)$ becomes invariant under $A$, then it contains $A^{-1} r_0$ and the residual vanishes. Clause 2 turns the large minimization into a small least squares problem with a Hessenberg matrix, solved by Givens rotations. Example: if $A = I + N$ with $N^2 = 0$, then $p(t) = (1 - t)^2$ vanishes on $A$, so $r_2 = 0$ for any $b$. The constant $\kappa_2(V)$ is the condition number of the eigenvector matrix; for normal $A$ it equals $1$. For highly non-normal $A$, the eigenvalues alone do not decide the convergence.

Going deeper

For a student

GMRES is the residual-minimizing iterative method for general nonsymmetric systems, while the conjugate gradient method minimizes the energy norm for symmetric positive definite ones. Since Arnoldi needs all basis vectors, the cost per step grows; restarted GMRES($m$) throws them away every $m$ steps, and it may then stagnate. It is almost always used with a preconditioner, often an incomplete LU factorization. The method is due to Saad and Schultz.