Generalized Minimal Residual Method - Convergence

Convergence

The nth iterate minimizes the residual in the Krylov subspace K_n. Since every subspace is contained in the next subspace, the residual decreases monotonically. After m iterations, where m is the size of the matrix A, the Krylov space K_m is the whole of Rm and hence the GMRES method arrives at the exact solution. However, the idea is that after a small number of iterations (relative to m), the vector x_n is already a good approximation to the exact solution.

This does not happen in general. Indeed, a theorem of Greenbaum, Pták and Strakoš states that for every monotonically decreasing sequence a₁, …, a_m−1, a_m = 0, one can find a matrix A such that the ||r_n|| = a_n for all n, where r_n is the residual defined above. In particular, it is possible to find a matrix for which the residual stays constant for m − 1 iterations, and only drops to zero at the last iteration.

In practice, though, GMRES often performs well. This can be proven in specific situations. If A is positive definite, then

where and denote the smallest and largest eigenvalue of the matrix, respectively.

If A is symmetric and positive definite, then we even have

where denotes the condition number of A in the Euclidean norm.

In the general case, where A is not positive definite, we have

where P_n denotes the set of polynomials of degree at most n with p(0) = 1, V is the matrix appearing in the spectral decomposition of A, and σ(A) is the spectrum of A. Roughly speaking, this says that fast convergence occurs when the eigenvalues of A are clustered away from the origin and A is not too far from normality.

All these inequalities bound only the residuals instead of the actual error, that is, the distance between the current iterate x_n and the exact solution.