Conjugate Gradient Method (CG)

Introduction to Conjugate Gradient Algorithm

Algorithm ( Conjugate Gradient Method ):

Compute ${\mathit{r}}^{\left(0\right)}=\mathit{b}-\mathit{A}{\mathit{x}}^{\left(0\right)}$, and set ${\mathit{p}}^{\left(0\right)}={\mathit{r}}^{\left(0\right)}$;

For $j=0,1,\cdots$ until convergence, do:

• Step length: ${\alpha }_j=\frac{⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩}{⟨{\mathit{p}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩}$;
• Approximate solution: ${\mathit{x}}^{(j+1)}={\mathit{x}}^{\left(j\right)}+{\alpha }_j{\mathit{p}}^{\left(j\right)}$;
• Residual: ${\mathit{r}}^{(j+1)}={\mathit{r}}^{\left(j\right)}-{\alpha }_j\mathit{A}{\mathit{p}}^{\left(j\right)}$;
• Improvement this step: ${\tau }_j=\frac{⟨{\mathit{r}}^{(j+1)},{\mathit{r}}^{(j+1)}⟩}{⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩}$;
• Search direction: ${\mathit{p}}^{(j+1)}={\mathit{r}}^{(j+1)}+{\tau }_j{\mathit{p}}^{\left(j\right)}$;

End

The most expensive part for computation of this algorithm is computing $\mathit{A}\mathit{p}$, whose cost is $O(m^2)$. However, It is needed for only once per iteration!

Question: How can we derive the CG method?

Derivation from Projection Method

Perform the projection method with $\mathbf{K}=\mathbf{L}=\mathrm{span}\{{\mathit{r}}^{\left(j\right)},{\mathit{p}}^{(j-1)}\}$:

$${\mathit{x}}^{(j+1)}={\mathit{x}}^{\left(j\right)}+{\mathit{\delta }}^{\left(j\right)}$$

where ${\mathit{\delta }}^{\left(j\right)}\in \mathbf{K}$. Then:

$${\mathit{r}}^{(j+1)}=\mathit{b}-\mathit{A}{\mathit{x}}^{(j+1)}$$

Based on the requirement of Projection Method:

$${\mathit{r}}^{(j+1)}\mathrm{\perp }\mathbf{L}=\mathrm{span}\{{\mathit{r}}^{\left(j\right)},{\mathit{p}}^{(j-1)}\}$$

$$⟹⟨{\mathit{r}}^{(j+1)},{\mathit{r}}^{\left(j\right)}⟩=0,⟨{\mathit{r}}^{(j+1)},{\mathit{p}}^{(j-1)}⟩=0$$

Since ${\mathit{\delta }}^{\left(j\right)}\in \mathbf{K}$, we can write (in a strange way) ${\mathit{\delta }}^{\left(j\right)}={\alpha }_j({\mathit{r}}^{\left(j\right)}+{\tau }_{j-1}{\mathit{p}}^{(j-1)})$, where ${\mathit{r}}^{\left(j\right)}+{\tau }_{j-1}{\mathit{p}}^{(j-1)}$ is the new search direction.

$$\begin{gathered} {\mathit{p}}^{\left(j\right)}={\mathit{r}}^{\left(j\right)}+{\tau }_{j-1}{\mathit{p}}^{(j-1)} \\ \Rightarrow {\mathit{r}}^{\left(j\right)}={\mathit{p}}^{\left(j\right)}-{\tau }_{j-1}{\mathit{p}}^{(j-1)} \end{gathered}$$

where ${\alpha }_j,{\tau }_{j-1}$ are to be determined.

Claim: We can find (How to prove?):

$${\mathit{r}}^{(j+1)}={\mathit{r}}^{\left(j\right)}-{\alpha }_j\mathit{A}{\mathit{p}}^{\left(j\right)}$$

Proof:

$${\mathit{p}}^{\left(j\right)}={\mathit{r}}^{\left(j\right)}+{\tau }_{j-1}{\mathit{p}}^{(j-1)},\iff {\mathit{r}}^{\left(j\right)}={\mathit{p}}^{\left(j\right)}-{\tau }_{j-1}{\mathit{p}}^{(j-1)};$$

Then:

$${\mathit{r}}^{(j+1)}=\mathit{b}-\mathit{A}{\mathit{x}}^{(j+1)}=\mathit{b}-\mathit{A}({\mathit{x}}^{\left(j\right)}+{\mathit{\delta }}^{\left(j\right)})$$

$$=(\mathit{b}-\mathit{A}{\mathit{x}}^{\left(j\right)})-\mathit{A}{\mathit{\delta }}^{\left(j\right)}={\mathit{r}}^{\left(j\right)}-\mathit{A}{\delta }^{\left(j\right)}$$

$$={\mathit{r}}^{\left(j\right)}-\mathit{A}{\alpha }_j({\mathit{r}}^{\left(j\right)}+{\tau }_{j-1}{\mathit{p}}^{(j-1)})$$

$$={\mathit{r}}^{\left(j\right)}-{\alpha }_j\mathit{A}({\mathit{p}}^{\left(j\right)}-{\tau }_{j-1}{\mathit{p}}^{(j-1)})-{\alpha }_j{\tau }_{j-1}\mathit{A}{\mathit{p}}^{(j-1)}$$

$$={\mathit{r}}^{\left(j\right)}-{\alpha }_j\mathit{A}{\mathit{p}}^{\left(j\right)}$$

End of proof.

Because:

$$0=⟨{\mathit{r}}^{(j+1)},{\mathit{r}}^{\left(j\right)}⟩=⟨{\mathit{r}}^{\left(j\right)}-{\alpha }_j\mathit{A}{\mathit{p}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩=⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩-{\alpha }_j⟨{\mathit{r}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩$$

We have:

$${\alpha }_j=\frac{⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩}{⟨{\mathit{r}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩}$$

Also:

$$0=⟨{\mathit{r}}^{(j+1)},{\mathit{p}}^{(j-1)}⟩\Rightarrow {\tau }_{j-1}=\frac{⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩}{⟨{\mathit{r}}^{(j-1)},{\mathit{r}}^{(j-1)}⟩}$$

Properties of Conjugate Gradient Method

It can be proved that CG satisfies the following properties:

• $⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(i\right)}⟩=0,i\ne j;$
• $⟨\mathit{A}{\mathit{p}}^{\left(j\right)},{\mathit{p}}^{\left(i\right)}⟩=0,i\ne j$.

Note that for ${\alpha }_j$, the formulas just derived here are slightly different from those described in the algorithm, but they are in fact equivalent. We can show:

$${\alpha }_j=\frac{⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩}{⟨{\mathit{r}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩}=\frac{⟨{\mathit{r}}^{\left(j\right)},{\mathit{r}}^{\left(j\right)}⟩}{⟨{\mathit{p}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩},$$

$$⟸⟨{\mathit{r}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩=⟨{\mathit{p}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩;$$

$$⟨{\mathit{r}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩=⟨{\mathit{p}}^{\left(j\right)}-{\tau }_{j-1}{\mathit{p}}^{(j-1)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩$$

$$=⟨{\mathit{p}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩-{\tau }_{j-1}⟨{\mathit{p}}^{(j-1)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩$$

$$=⟨{\mathit{p}}^{\left(j\right)},\mathit{A}{\mathit{p}}^{\left(j\right)}⟩$$

In this way we prove the equivalence of formulas.