Krylov methods approximate large matrix problems using only matrix-vector products, making them central for sparse systems and large eigenvalue problems.
Krylov subspace
Definition. The \(k\)-th Krylov subspace generated by \(A\) and \(r\) is \(\mathcal K_k(A,r)=\operatorname{span}\{r,Ar,\ldots,A^{k-1}r\}\). It contains polynomial approximations \(p_{k-1}(A)r\).
Arnoldi iteration
Proposition. Arnoldi iteration constructs an orthonormal basis of \(\mathcal K_k\) and a Hessenberg projection of \(A\). The projected small problem provides approximations to eigenvalues or linear-system corrections.
Lanczos iteration
Proposition. For symmetric \(A\), Arnoldi reduces to Lanczos iteration with a tridiagonal projected matrix. This three-term recurrence is efficient but may require reorthogonalization in finite precision.
GMRES
Theorem. GMRES chooses \(x_k\in x_0+\mathcal K_k(A,r_0)\) minimizing \(\|b-Ax_k\|_2\). Its convergence is governed by polynomial approximation of zero on the relevant spectral or pseudospectral set.
Finite precision behavior
Remark. Krylov methods are mathematically projection methods, but their actual behavior depends on loss of orthogonality, restart choices, and preconditioning. These are part of the numerical method, not implementation afterthoughts.
Krylov spaces and polynomial approximation
Starting from residual \(r_0=b-Ax_0\), the \(k\)th Krylov space is \[ \mathcal K_k(A,r_0) =\operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. \] Any iterate \(x_k\in x_0+\mathcal K_k\) has error \[ e_k=p_k(A)e_0 \] for a polynomial \(p_k\) of degree at most \(k\) with \(p_k(0)=1\). Convergence is therefore a polynomial approximation problem on the spectrum or field of values.
Conjugate gradients
Theorem. For symmetric positive definite \(A\), conjugate gradients produces \[ x_k=\arg\min_{x\in x_0+\mathcal K_k(A,r_0)} \|x-x^*\|_A, \qquad \|v\|_A^2=v^\top Av. \] Moreover, \[ \frac{\|e_k\|_A}{\|e_0\|_A} \le2\left( \frac{\sqrt\kappa-1}{\sqrt\kappa+1} \right)^k, \quad \kappa=\kappa_2(A). \]
Proof. CG residual orthogonality and conjugate search directions give the energy minimization property. Hence \[ \|e_k\|_A \le\min_{\substack{p\in\mathcal P_k\\p(0)=1}} \max_{\lambda\in[\lambda_{\min},\lambda_{\max}]} |p(\lambda)|\,\|e_0\|_A. \] Scale the interval to \([-1,1]\) and choose the normalized Chebyshev polynomial. Its extremal bound gives the displayed rate.
Arnoldi, Lanczos, and GMRES
Arnoldi orthogonalization builds \[ AQ_k=Q_{k+1}\bar H_k, \] where \(\bar H_k\) is upper Hessenberg. GMRES chooses \(x_k\) to minimize the Euclidean residual over \(x_0+\mathcal K_k\), reducing the problem to a small least-squares solve. For symmetric \(A\), Arnoldi becomes the three-term Lanczos recurrence; MINRES handles symmetric indefinite systems.
Proposition. GMRES satisfies \[ \frac{\|r_k\|_2}{\|r_0\|_2} \le \min_{\substack{p\in\mathcal P_k\\p(0)=1}} \|p(A)\|_2. \] If \(A=V\Lambda V^{-1}\), this is at most \[ \kappa_2(V) \min_p\max_{\lambda\in\sigma(A)}|p(\lambda)|. \]
For nonnormal matrices the eigenvalue-only bound can be poor because \(\kappa(V)\) is large. Field-of-values or pseudospectral bounds better capture transient behavior.
Finite precision and restarting
Loss of orthogonality creates ghost Ritz values in Lanczos and can delay GMRES. Reorthogonalization controls this at extra cost. Restarted GMRES limits storage but discards polynomial information and can stagnate. Flexible Krylov methods allow iteration-dependent preconditioners while modifying the recurrence to remain mathematically valid.