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:
“You are right to demand that an artist engage his work consciously, but you confuse two different things: solving the problem and correctly posing the question.”
—Anton Pavlovich Chekhov (1860–1904)
“Cultural expectations shade and color the images that parents- to-be form. The baby product ads, showing a woman serenely holding her child, looking blissfully and mysteriously contented, or the television parents, wisely and humorously solving problems, influence parents-to-be.”
—Ellen Galinsky (20th century)
“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)
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)