## Subsection8.3.5Practical Conjugate Gradient Method algorithm

We have noted that $p^{(k)} = r^{(k)} + \gamma_k p^{(k-1)} .$ Since $p^{(k)}$ is A-conjugate to $p^{(k-1)}$ we find that

\begin{equation*} p^{(k-1)\,T} A p^{(k)} = p^{(k-1)\,T} A r^{(k)} + \gamma_k p^{(k-1)\,T} A p^{(k-1)} \end{equation*}

so that

\begin{equation*} \gamma_k = - p^{(k-1)\,T} A r^{(k)} / p^{(k-1)\,T} A p^{(k-1)}. \end{equation*}

This yields the first practical instantiation of the Conjugate Gradient method, given in Figure 8.3.5.1.

###### Homework8.3.5.1.

In Figure 8.3.5.1 we compute

\begin{equation*} \alpha_k := \frac{p^{(k)\,T} r^{(k)}}{p^{(k)\,T} A p^{(k)}}. \end{equation*}

Show that an alternative formula for $\alpha_k$ is given by

\begin{equation*} \alpha_k := \frac{r^{(k)\,T} r^{(k)}}{p^{(k)\,T} A p^{(k)}}. \end{equation*}
Hint

Use the fact that $p^{(k)} = r^{(k)} + \gamma_k p^{(k-1)}$ and the fact that $r^{(k)}$ is orthogonal to all previous search directions to show that $p^{(k)\,T} r^{(k)} = r^{(k)\,T} r^{(k)} \text{.}$

Solution

We need to show that $p^{(k)\,T} r^{(k)} = r^{(k)\,T} r^{(k)} \text{.}$

\begin{equation*} \begin{array}{l} p^{(k)\,T} r^{(k)} \\ ~~~=~~~~ \lt r^{(k)} + \gamma_k p^{(k-1)} \gt \\ ( r^{(k)} + \gamma_k p^{(k-1)})^T r^{(k)} \\ ~~~ = ~~~~ \lt \mbox{ distribute } \gt \\ r^{(k)\,T} r^{(k)} + \gamma_k p^{(k-1)\,T} r^{(k)} \\ ~~~ = ~~~~ \lt p^{(k-1)\,T} r^{(k)} = 0 \gt \\ r^{(k)\,T} r^{(k)}. \end{array} \end{equation*}

The last homework justifies the refined Conjugate Gradient Method in Figure 8.3.5.2 (Left).

###### Homework8.3.5.2.

For the Conjugate Gradient Method discussed so far,

• Show that

\begin{equation*} r^{(k)\,T} r^{(k)} = - \alpha_{k-1} r^{(k)\,T} A p^{k-1}. \end{equation*}
• Show that

\begin{equation*} p^{(k-1)\,T} A p^{(k-1)} = r^{(k-1)\,T}r^{(k-1)} / \alpha_{k-1} . \end{equation*}
Hint

Recall that

$$r^{(k)} = r^{(k-1)} - \alpha_{k-1} A p^{(k-1)}. \label{chapter08-CGM-eq2}\tag{8.3.4}$$

and rewrite (8.3.4) as

\begin{equation*} A p^{(k-1)} = ( r^{(k-1)}- r^{(k)} ) / \alpha_{k-1} . \end{equation*}

and recall that in the previous iteration

\begin{equation*} p^{(k-1)} = r^{(k-1)} - \gamma_{k-1} p^{(k-2)}. \end{equation*}
Solution
\begin{equation*} r^{(k)\,T} r^{(k)} = r^{(k)\,T} r^{(k-1)} - \alpha_{k-1} r^{(k)\,T} A p^{k-1} = - \alpha_{k-1} r^{(k)\,T} A p^{k-1}. \end{equation*}
\begin{equation*} \begin{array}{l} p^{(k-1)\,T} A p^{(k-1)} \\ ~~~=~~~~ \\ ( r^{(k-1)} - \gamma_{k-1} p^{(k-2)} )^T A p^{(k-1)} \\ ~~~=~~~~ \\ r^{(k-1)\,T} A p^{(k-1)} \\ ~~~=~~~~ \\ r^{(k-1)\,T}( r^{(k-1)}- r^{(k)} ) / \alpha_{k-1} \\ ~~~=~~~~ \\ r^{(k-1)\,T}r^{(k-1)} / \alpha_{k-1} . \end{array} \end{equation*}

From the last homework we conclude that

\begin{equation*} \gamma_k = -(p^{(k-1)\,T} A r^{(k)} ) /( p^{(k-1)\,T} A p^{(k-1)} ) = r^{(k)\,T} r^{(k)} / r^{(k-1)\,T} r^{(k-1)}. \end{equation*}

This is summarized in on the right in Figure 8.3.5.2.