The Conjugate Gradient Method As An Iterative Method
If we choose the conjugate vectors pk carefully, then we may not need all of them to obtain a good approximation to the solution . So, we want to regard the conjugate gradient method as an iterative method. This also allows us to approximately solve systems where n is so large that the direct method would take too much time.
We denote the initial guess for by x0. We can assume without loss of generality that x0 = 0 (otherwise, consider the system Az = b − Ax0 instead). Starting with x0 we search for the solution and in each iteration we need a metric to tell us whether we are closer to the solution (that is unknown to us). This metric comes from the fact that the solution is also the unique minimizer of the following quadratic function; so if f(x) becomes smaller in an iteration it means that we are closer to .
This suggests taking the first basis vector p1 to be the negative of the gradient of f at x = x0. The gradient of f equals Ax0−b. Starting with a "guessed solution" x0 (we can always guess that is 0 and set x0 to 0 if we have no reason to guess for anything else), this means we take p1 = b−Ax0. The other vectors in the basis will be conjugate to the gradient, hence the name conjugate gradient method.
Let rk be the residual at the kth step:
Note that rk is the negative gradient of f at x = xk, so the gradient descent method would be to move in the direction rk. Here, we insist that the directions pk be conjugate to each other. We also require that the next search direction be built out of the current residue and all previous search directions, which is reasonable enough in practice.
The conjugation constraint is an orthonormal-type constraint and hence the algorithm bears resemblance to Gram-Schmidt orthonormalization.
This gives the following expression:
(see the picture at the top of the article for the effect of the conjugacy constraint on convergence). Following this direction, the next optimal location is given by
with
where the last equality holds because pk+1 and xk are conjugate.
Read more about this topic: Conjugate Gradient Method
Famous quotes containing the word method:
“There is assuredly no more effectual method of clearing up one’s own mind on any subject than by talking it over, so to speak, with men of real power and grasp, who have considered it from a totally different point of view.”
—Thomas Henry Huxley (1825–95)