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)
“More than a decade after our fellow citizens began bedding down on the sidewalks, their problems continue to seem so intractable that we have begun to do psychologically what government has been incapable of doing programmatically. We bring the numbers down—not by solving the problem, but by deciding it’s their own damn fault.”
—Anna Quindlen (b. 1952)
“An afternoon of nurses and rumours;
The provinces of his body revolted,
The squares of his mind were empty,
Silence invaded the suburbs,”
—W.H. (Wystan Hugh)
“Most childhood problems don’t result from “bad” parenting, but are the inevitable result of the growing that parents and children do together. The point isn’t to head off these problems or find ways around them, but rather to work through them together and in doing so to develop a relationship of mutual trust to rely on when the next problem comes along.”
—Fred Rogers (20th century)