Generalized minimal residual method

In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of an indefinite nonsymmetric 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 GMRES method was developed by Yousef Saad and Martin H. Schultz in 1986. It is a generalization and improvement of the MINRES method due to Paige and Saunders in 1975. The MINRES method requires that the matrix is symmetric, but has the advantage that it only requires handling of three vectors. GMRES is a special case of the DIIS method developed by Peter Pulay in 1980. DIIS is applicable to non-linear systems. Denote the Euclidean norm of any vector v by . Denote the (square) system of linear equations to be solved by The matrix A is assumed to be invertible of size m-by-m. Furthermore, it is assumed that b is normalized, i.e., that . The n-th Krylov subspace for this problem is where is the initial error given an initial guess . Clearly if . GMRES approximates the exact solution of by the vector that minimizes the Euclidean norm of the residual . The vectors might be close to linearly dependent, so instead of this basis, the Arnoldi iteration is used to find orthonormal vectors which form a basis for . In particular, . Therefore, the vector can be written as with , where is the m-by-n matrix formed by . In other words, finding finding the n-th approximation of the solution (i.e., ) is reduced to finding the vector , which is determined via minimizing the residue as described below. The Arnoldi process also constructs , an ()-by- upper Hessenberg matrix which satisfies an equality which is used to simplify the calculation of (see below). Note that, for symmetric matrices, a symmetric tri-diagonal matrix is actually achieved, resulting in the MINRES method. Because columns of are orthonormal, we have where is the first vector in the standard basis of , and being the first trial vector (usually zero).