Conjugate-gradient theory for programmers

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}$$ (39) (40) (41)

A linear combination in solution space, say s+g, corresponds to S+G in the conjugate space, because $S+G = \bold A s + \bold A \bold g = \bold A(s+g)$.According to equation (31), the residual is

$$R \eq Y\ -\ \bold A \ x \eq Y \ -\ X$$ (42)

The solution x is obtained by a succession of steps s_j, say

$$x \eq s_1 \ +\ s_2 \ +\ s_3 \ +\ \cdots$$ (43)

The last stage of each iteration is to update the solution and the residual:

		solution update: 		 $x \ \leftarrow x \ +\ s$		residual update: 		 $R \ \leftarrow R \ -\ S$

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}$$ (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 $\alpha$,but simultaneously another line with $\beta$.The combination of the two lines is a plane:  

$$Q(\alpha ,\beta ) \eq ( R - \alpha G - \beta S) \ \cdot\ (R - \alpha G - \beta S )$$ (46)

The minimum is found at $\partial Q / \partial \alpha \,=\,0$ and $\partial Q / \partial \beta \,=\,0$, namely,

$$0\eq G \ \cdot\ ( R - \alpha G - \beta S )$$ (47)

$$0\eq S \ \cdot\ ( R - \alpha G - \beta S )$$ (48)

The solution is

$$\left[ \begin{array} {c} \alpha \ \beta \end{array} \r... ...begin{array} {c} (G\cdot R) \ (S\cdot R) \end{array} \right]$$ (49)