Generalized minimal residual method

In mathematics, the generalized minimal residual method (usually abbreviated GMRES) is an iterative method for the numerical solution of a system of linear equations. The method approximates the solution by the vector in a Krylov subspace with minimal residual. The Arnoldi iteration is used to find this vector.

The method

Denote the system of linear equations which needs to be solved by

$Ax=b.\,$

The matrix A is assumed to be invertible of size m-by-m. Furthermore, it is assumed that b is normalized, i.e., ||b|| = 1 (in this article, ||·|| denotes the Euclidean norm).

The nth Krylov subspace for this problem is

$K_{n}=\operatorname {span} \,\{b,Ab,A^{2}b,\ldots ,A^{n-1}b\}.\,$

GMRES approximates the exact solution of Ax = b by the vector x_n ∈ K_n that minimizes the norm of the residual Ax_n − b.

The vectors b, Ab, … Aⁿ⁻¹b are almost linearly dependent, so instead of this basis, Arnoldi iteration is used to find orthonormal vectors

$q_{1},q_{2},\ldots ,q_{n}\,$

which form a basis for K_n. Hence, the vector x_n can be written as x_n = Q_ny_n with y_n ∈ Rⁿ.

The Arnoldi process also produces an (n+1)-by-n upper Hessenberg matrix H_n with

$AQ_{n}=Q_{n+1}H_{n}.\,$

Because $Q_{n}$ is orthogonal, we have

$\|Ax_{n}-b\|=\|H_{n}y_{n}-e_{1}\|,\,$

where

$e_{1}=(1,0,0,\ldots ,0)\,$

is the first vector in the standard basis of Rⁿ. Hence, $x_{n}$ can be found by minimizing ||H_ny_n − e₁||. This is a linear least squares problem of size n.

This yields the GMRES method. At every step of the iteration:

1. do one step of the Arnoldi method;
2. find the $y_{n}$ which minimizes ||H_ny_n − e₁||;
3. compute $x_{n}=Q_{n}y_{n}$;
4. repeat if the residual ||H_ny_n − e₁|| is not yet small enough.

The cost of one iteration is one matrix-vector product Aq_n and $O(n^{2})$ floating-point operations.

Analysis

After m iterations, where m is the size of the matrix A, the Krylov space K_m is the whole of R^m 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.

The speed with which x_n converges is hard to determine. Generally, fast convergence occurs when the eigenvalues of A are clustered away from the origin and A is not too far from normality. Furthermore, A should be sparse matrix or have some other structure so that the matrix-vector product can be computed quickly.

More precisely, the norm of the residuals satisfy

$\|Ax_{n}-b\|\leq \inf _{p\in P_{n}}\|p_{n}(A)\|\leq \kappa (V)\inf _{p\in P_{n}}\max _{\lambda \in \sigma (A)}|p(\lambda )|,\,$

where P_n denotes the set of polynomials of degree at most n with p(0) = 1, κ denotes the condition number, V is the matrix appearing in the spectral decomposition of A, and σ(A) is the spectrum of A (Trefethen & Bau, Thm 35.2).

Extensions of the method

Like other iterative methods, GMRES is usually combined with a preconditioning method in order to speed up convergence.

The cost of the iterations grow like O(n²), where n is the iteration number. Therefore, the method is sometimes restarted after a number, say k, of iterations, with x_k as initial guess. The resulting method is called GMRES(k).

References

• Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997. ISBN 0-89871-361-7.