Convergence Theory of Krylov Methods
How the spectrum and structure of a matrix determine, through polynomial approximation, how fast a Krylov solver converges.
Convergence as polynomial approximation
The error of a Krylov method after m steps can be written as a polynomial of degree m in the matrix, applied to the initial error, where the polynomial equals one at the origin. The method implicitly chooses the best such polynomial. Convergence is therefore governed by a question of approximation theory: how small can a degree-m polynomial, pinned to one at zero, be made over the region of the complex plane containing the eigenvalues?
The symmetric case
For symmetric positive-definite matrices the eigenvalues are real and positive, and the relevant polynomial problem is solved by Chebyshev polynomials over the eigenvalue interval. This yields the classic conjugate gradient bound: the error decreases at a rate set by the square root of the condition number. A tighter, often more realistic picture comes from eigenvalue clustering: CG converges in roughly as many steps as there are distinct eigenvalue clusters, converging superlinearly as it captures the extreme eigenvalues.
The nonsymmetric case
For nonsymmetric matrices the eigenvalues alone can be misleading, because the eigenvectors may be far from orthogonal (the matrix is non-normal). Convergence then depends on more subtle quantities such as the field of values or pseudospectra, and GMRES can stagnate for many iterations before rapid convergence even when the eigenvalues look benign. This is why nonsymmetric solvers are harder to analyze and to precondition.
- Clustered eigenvalues: fast convergence, a low-degree polynomial suffices
- Wide-spread spectrum: slow convergence, motivating preconditioning to cluster it
- Non-normality: eigenvalues insufficient, pseudospectra needed for prediction
- Superlinear convergence: acceleration as extreme eigenvalues are resolved
Practical implications
The theory explains why preconditioning is essential: its purpose is to reshape the spectrum into tight clusters so a low-degree polynomial can make the error small. It also warns that eigenvalue estimates alone do not guarantee fast convergence for nonsymmetric problems, guiding the choice between GMRES, BiCGStab, and MINRES and the design of effective preconditioners for stiff simulation.