Generalized Minimal Residual Method - Solving The Least Squares Problem

Solving The Least Squares Problem

One part of the GMRES method is to find the vector which minimizes

Note that is an (n+1)-by-n matrix, hence it gives an over-constrained linear system of n+1 equations for n unknowns.

The minimum can be computed using a QR decomposition: find an (n+1)-by-(n+1) orthogonal matrix Ω_n and an (n+1)-by-n upper triangular matrix such that

The triangular matrix has one more row than it has columns, so its bottom row consists of zero. Hence, it can be decomposed as

where is an n-by-n (thus square) triangular matrix.

The QR decomposition can be updated cheaply from one iteration to the next, because the Hessenberg matrices differ only by a row of zeros and a column:

where h_n = (h_1n, … h_nn)T. This implies that premultiplying the Hessenberg matrix with Ω_n, augmented with zeroes and a row with multiplicative identity, yields almost a triangular matrix:

This would be triangular if σ is zero. To remedy this, one needs the Givens rotation

where

With this Givens rotation, we form

Indeed,

is a triangular matrix.

Given the QR decomposition, the minimization problem is easily solved by noting that

Denoting the vector by

with g_n ∈ Rn and γ_n ∈ R, this is

The vector y that minimizes this expression is given by

Again, the vectors are easy to update.