Subsection 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*}
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
Solution
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{.}\)
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*}
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
Solution
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*}
\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.