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 hn = (h1n, … hnn)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 gn ∈ Rn and γn ∈ R, this is
The vector y that minimizes this expression is given by
Again, the vectors are easy to update.
Read more about this topic: Generalized Minimal Residual Method
Famous quotes containing the words solving the, solving, squares and/or problem:
“Will women find themselves in the same position they have always been? Or do we see liberation as solving the conditions of women in our society?... If we continue to shy away from this problem we will not be able to solve it after independence. But if we can say that our first priority is the emancipation of women, we will become free as members of an oppressed community.”
—Ruth Mompati (b. 1925)
“Will women find themselves in the same position they have always been? Or do we see liberation as solving the conditions of women in our society?... If we continue to shy away from this problem we will not be able to solve it after independence. But if we can say that our first priority is the emancipation of women, we will become free as members of an oppressed community.”
—Ruth Mompati (b. 1925)
“And New York is the most beautiful city in the world? It is not far from it. No urban night is like the night there.... Squares after squares of flame, set up and cut into the aether. Here is our poetry, for we have pulled down the stars to our will.”
—Ezra Pound (1885–1972)
“It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
—John Dewey (1859–1952)