Next: First conjugate-gradient program
Up: ITERATIVE METHODS
Previous: Magic
Define the solution, the solution step (from one iteration to the next),
and the gradient by
| ![\begin{eqnarray}
X &=& \bold A \ x \ S_j &=& \bold A \ s_j \ G_j &=& \bold A \ g_j\end{eqnarray}](img112.gif) |
(39) |
| (40) |
| (41) |
A linear combination in solution space,
say s+g, corresponds to S+G in the conjugate space,
because
.According to equation
(31),
the residual is
| ![\begin{displaymath}
R \eq Y\ -\ \bold A \ x \eq Y \ -\ X\end{displaymath}](img114.gif) |
(42) |
The solution x is obtained by a succession of steps sj, say
| ![\begin{displaymath}
x \eq s_1 \ +\ s_2 \ +\ s_3 \ +\ \cdots\end{displaymath}](img115.gif) |
(43) |
The last stage of each iteration is to update the solution and the residual:
solution update:
residual update: ![$R \ \leftarrow R \ -\ S$](img117.gif)
The gradient vector g is a vector with the same number
of components as the solution vector x.
A vector with this number of components is
| ![\begin{eqnarray}
g &=& \bold A' \ R \eq \hbox{gradient}
\ G &=& \bold A \ g \eq \hbox{conjugate gradient}\end{eqnarray}](img118.gif) |
(44) |
| (45) |
The gradient g in the transformed space is G,
also known as the ``conjugate gradient.''
The minimization (35) is now generalized
to scan not only the line with
,but simultaneously another line with
.The combination of the two lines is a plane:
| ![\begin{displaymath}
Q(\alpha ,\beta ) \eq
( R - \alpha G - \beta S) \ \cdot\ (R - \alpha G - \beta S )\end{displaymath}](img119.gif) |
(46) |
The minimum is found at
and
, namely,
| ![\begin{displaymath}
0\eq G \ \cdot\ ( R - \alpha G - \beta S )\end{displaymath}](img122.gif) |
(47) |
| ![\begin{displaymath}
0\eq S \ \cdot\ ( R - \alpha G - \beta S )\end{displaymath}](img123.gif) |
(48) |
The solution is
| ![\begin{displaymath}
\left[
\begin{array}
{c}
\alpha \
\beta \end{array} \r...
...begin{array}
{c}
(G\cdot R) \ (S\cdot R) \end{array} \right]\end{displaymath}](img124.gif) |
(49) |
Next: First conjugate-gradient program
Up: ITERATIVE METHODS
Previous: Magic
Stanford Exploration Project
10/21/1998