Numerical Linear Algebra with Applications

21.7 GMRES

Assume A is a real n × n matrix, b is an n × 1 vector, and we want to solve the system Ax = b. Assume that x₀ is an initial guess for the solution, and r₀ = b − Ax₀ is the corresponding residual. The GMRES method looks for a solution of the form x_m= x₀ + Q_my_m, y_m∈ ^mwhere the columns of Q_mare an n-dimensional orthogonal basis for the Krylov subspace K_m(A, r₀) = {r₀, Ar₀,…, A^m−1r₀}_. The vector y_mis chosen so the residual

${\Vert r_m\Vert }_{\text{2}}={\Vert b-A(x_0+Q_m{y}_m)\Vert }_{\text{2}}={\Vert r_0-A{Q}_m{y}_m\Vert }_{\text{2}}$

has minimal norm over K_m(A, r₀). This is a least-squares problem. We must find ...