** Next:** Short memory of the
** Up:** WHAT ARE ADJOINTS FOR?
** Previous:** WHAT ARE ADJOINTS FOR?

The orthogonality principle (25) transforms according to the
dot-product test (27) to the form
| |
(29) |

Forming the dot product and
applying formula (22), we can see that
| |
(30) |

Equation (30) proves the orthogonality of the gradient directions from
different iterations. Since the gradients are orthogonal, after *n*
iterations they form a basis in the *n*-dimensional space. In other
words, if the model space has *n* dimensions, each vector in this
space can be represented by a linear combination of the gradient
vectors formed by *n* iterations of the conjugate-gradient
method. This is true as well for the vector , which
points from the solution of equation (1) to the initial
model estimate . Neglecting computational errors, it takes
exactly *n* iterations to find this vector by successive optimization
of the coefficients. This proves that the
conjugate-gradient method converges to the exact solution in a
finite number of steps (assuming that the model belongs to a
finite-dimensional space).
The method of conjugate gradients simplifies formula (26)
to the form

| |
(31) |

which in turn leads to the simplification of formula (8),
as follows:
| |
(32) |

If the gradient is not equal to zero, the residual is guaranteed to
decrease. If the gradient is equal to zero, we have already
found the solution.

** Next:** Short memory of the
** Up:** WHAT ARE ADJOINTS FOR?
** Previous:** WHAT ARE ADJOINTS FOR?
Stanford Exploration Project

11/12/1997