Minimal residual method

Remarks

The Lanczos algorithm gives an orthonormal basis $Q_{k+1}$ of $\mathcal{K}_{k+1}(A, r_0)$ with $A Q_k = Q_{k+1} \tilde{T}_k$, where $\tilde{T}_k$ is $(k+1) \times k$ and tridiagonal. The minimization reduces to a small least squares problem with $\tilde{T}_k$. A QR factorization of $\tilde{T}_k$ by Givens rotations can be updated with each new column, and this yields the short recurrences of clause 1. Clause 2 uses that $A$ is orthogonally diagonalizable, so $\norm{p(A)}_2 = \max_\lambda \abs{p(\lambda)}$. Example: if $A$ has only the eigenvalues $1$ and $-1$, then $p(t) = 1 - t^2$ gives $r_2 = 0$. For a nonsymmetric $A$ the Lanczos recurrence no longer produces an orthonormal basis, and one needs GMRES with its long recurrences.

Going deeper

For a student

MINRES is mathematically GMRES specialized to symmetric matrices, where the Arnoldi process becomes the Lanczos process. It fills the gap left by the conjugate gradient method, which can break down when $A$ is indefinite. For symmetric positive definite $A$ both apply: conjugate gradients minimize the energy norm of the error, MINRES the Euclidean norm of the residual. Like other Krylov iterative methods, it is used with a preconditioner, which must be symmetric positive definite to keep the symmetry. The method is due to Paige and Saunders.