Skip to content

Conjugate Gradient Method (CG)⚓︎

Introduction to Conjugate Gradient Algorithm⚓︎

Algorithm ( Conjugate Gradient Method ):

Compute r(0)=bAx(0), and set p(0)=r(0);

For j=0,1, until convergence, do:

  • Step length: αj=r(j),r(j)p(j),Ap(j);
  • Approximate solution: x(j+1)=x(j)+αjp(j);
  • Residual: r(j+1)=r(j)αjAp(j);
  • Improvement this step: τj=r(j+1),r(j+1)r(j),r(j);
  • Search direction: p(j+1)=r(j+1)+τjp(j);

End

The most expensive part for computation of this algorithm is computing Ap, whose cost is O(m2). 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 K=L=span{r(j),p(j1)}:

x(j+1)=x(j)+δ(j)

where δ(j)K. Then:

r(j+1)=bAx(j+1)

Based on the requirement of Projection Method:

r(j+1)L=span{r(j),p(j1)}
r(j+1),r(j)=0,r(j+1),p(j1)=0

Since δ(j)K, we can write (in a strange way) δ(j)=αj(r(j)+τj1p(j1)), where r(j)+τj1p(j1) is the new search direction.

p(j)=r(j)+τj1p(j1)r(j)=p(j)τj1p(j1)

where αj,τj1 are to be determined.

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

r(j+1)=r(j)αjAp(j)

Proof:

p(j)=r(j)+τj1p(j1),r(j)=p(j)τj1p(j1);

Then:

r(j+1)=bAx(j+1)=bA(x(j)+δ(j))
=(bAx(j))Aδ(j)=r(j)Aδ(j)
=r(j)Aαj(r(j)+τj1p(j1))
=r(j)αjA(p(j)τj1p(j1))αjτj1Ap(j1)
=r(j)αjAp(j)

End of proof.

Because:

0=r(j+1),r(j)=r(j)αjAp(j),r(j)=r(j),r(j)αjr(j),Ap(j)

We have:

αj=r(j),r(j)r(j),Ap(j)

Also:

0=r(j+1),p(j1)τj1=r(j),r(j)r(j1),r(j1)

Properties of Conjugate Gradient Method⚓︎

It can be proved that CG satisfies the following properties:

  • r(j),r(i)=0,ij;
  • Ap(j),p(i)=0,ij.

Note that for αj, the formulas just derived here are slightly different from those described in the algorithm, but they are in fact equivalent. We can show:

αj=r(j),r(j)r(j),Ap(j)=r(j),r(j)p(j),Ap(j),
r(j),Ap(j)=p(j),Ap(j);
r(j),Ap(j)=p(j)τj1p(j1),Ap(j)
=p(j),Ap(j)τj1p(j1),Ap(j)
=p(j),Ap(j)

In this way we prove the equivalence of formulas.