Generalized minimal residual method

In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of a 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. In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of a 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.GMRES is a generalization of the MINRES method developed by Chris Paige and Michael Saunders in 1975. GMRES also is a special case of the DIIS method developed by Peter Pulay in 1980. DIIS is also applicable to non-linear systems. Denote the Euclidean norm of any vector v by ‖ v ‖ {displaystyle |v|} . 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 ‖ b ‖ = 1 {displaystyle |b|=1} . The n-th Krylov subspace for this problem is GMRES approximates the exact solution of A x = b {displaystyle Ax=b} by the vector x n ∈ K n {displaystyle x_{n}in K_{n}} that minimizes the Euclidean norm of the residual r n = A x n − b {displaystyle r_{n}=Ax_{n}-b} . The vectors b , A b , … A n − 1 b {displaystyle b,Ab,ldots A^{n-1}b} might be close to linearly dependent, so instead of this basis, the Arnoldi iteration is used to find orthonormal vectors q 1 , q 2 , … , q n {displaystyle q_{1},q_{2},ldots ,q_{n},} which form a basis for K n {displaystyle K_{n}} . Hence, the vector x n ∈ K n {displaystyle x_{n}in K_{n}} can be written as x n = Q n y n {displaystyle x_{n}=Q_{n}y_{n}} with y n ∈ R n {displaystyle y_{n}in mathbb {R} ^{n}} , where Q n {displaystyle Q_{n}} is the m-by-n matrix formed by q 1 , … , q n {displaystyle q_{1},ldots ,q_{n}} . The Arnoldi process also produces an ( n + 1 {displaystyle n+1} )-by- n {displaystyle n} upper Hessenberg matrix H ~ n {displaystyle { ilde {H}}_{n}} with Because columns of Q n {displaystyle Q_{n}} are orthonormal, we have