Skip to main content

Unit 8.3.5 Practical 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.

\begin{equation*} \begin{array}{l} {\bf Given:~} A, b \\ x^{(0)} := 0 \\ r^{(0)} := b \\ k := 0 \\ {\bf while~} r^{(k)} \neq 0 \\ ~~~ {\bf if~} k = 0 \\ ~~~ ~~~ p^{(k)} = r^{(0)} \\ ~~~ {\bf else} \\ ~~~ ~~~\gamma_k := - p^{(k-1)\,T} A r^{(k)} / p^{(k-1)\,T} A p^{(k-1)} \\ ~~~ ~~~ p^{(k)} := r^{(k)} + \gamma_k p^{(k-1)} \\ ~~~ {\bf endif} \\ ~~~ \alpha_k := \frac{p^{(k)\,T} r^{(k)}}{p^{(k)\,T} A p^{(k)}} \\ ~~~ x^{(k+1)} := x^{(k)} + \alpha_k p^{(k)} \\ ~~~ r^{(k+1)} := r^{(k)} - \alpha_k A p^{(k)} \\ ~~~ k := k + 1 \\ {\bf endwhile} \end{array} \end{equation*}
Figure 8.3.5.1. Conjugate Gradient Method.
Homework 8.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).

\begin{equation*} \begin{array}{l} {\bf Given:~} A, b \\ x^{(0)} := 0 \\ r^{(0)} := b \\ k := 0 \\ {\bf while~} r^{(k)} \neq 0 \\ ~~~ {\bf if~} k = 0 \\ ~~~ ~~~ p^{(k)} = r^{(0)} \\ ~~~ {\bf else} \\ ~~~ ~~~ \gamma_k := -(p^{(k-1)\,T} A r^{(k)} ) /( p^{(k-1)\,T} A p^{(k-1)} )\\ ~~~ ~~~ p^{(k)} := r^{(k)} + \gamma_k p^{(k-1)} \\ ~~~ {\bf endif} \\ ~~~ \alpha_k := \frac{r^{(k)\,T} r^{(k)}}{p^{(k)\,T} A p^{(k)}} \\ ~~~ x^{(k+1)} := x^{(k)} + \alpha_k p^{(k)} \\ ~~~ r^{(k+1)} := r^{(k)} - \alpha_k A p^{(k)} \\ ~~~ k := k + 1 \\ {\bf endwhile} \end{array} \end{equation*}
\begin{equation*} \begin{array}{l} {\bf Given:~} A, b \\ x^{(0)} := 0 \\ r^{(0)} := b \\ k := 0 \\ {\bf while~} r^{(k)} \neq 0 \\ ~~~ {\bf if~} k = 0 \\ ~~~ ~~~ p^{(k)} = r^{(0)} \\ ~~~ {\bf else} \\ ~~~ ~~~ \gamma_k := (r^{(k)\,T} r^{(k)}) / (r^{(k-1)\,T} r^{(k-1)}) \\ ~~~ ~~~ p^{(k)} := r^{(k)} + \gamma_k p^{(k-1)} \\ ~~~ {\bf endif} \\ ~~~ \alpha_k := \frac{r^{(k)\,T} r^{(k)}}{p^{(k)\,T} A p^{(k)}} \\ ~~~ x^{(k+1)} := x^{(k)} + \alpha_k p^{(k)} \\ ~~~ r^{(k+1)} := r^{(k)} - \alpha_k A p^{(k)} \\ ~~~ k := k + 1 \\ {\bf endwhile} \end{array} \end{equation*}
Figure 8.3.5.2. Alternative Conjugate Gradient Method algorithms.
Homework 8.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

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

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.