Conjugate Gradients algorithm

We have now derived all the equations we need to formulate the Conjugate Gradients algorithm. Each step of CG is described below.

Compute the step-size:

${\mu }_k=\frac{\Vert r^{(k-1)}{\Vert }_2^2}{(p^{(k)}{)}^{T}A{p}^{(k)}}$

The solution increments are conjugate with all the previous steps:

$$x^{(k)}=x^{(k-1)}+{\mu }_k{p}^{(k)}$$

The residual is orthogonal to all the previous residuals:

$$r^{(k)}=r^{(k-1)}-{\mu }_{k}A{p}^{(k)}$$

We use our computationally efficient equation for the search directions:

$${\tau }_k=\frac{\Vert r^{(k)}{\Vert }_2^2}{\Vert r^{(k-1)}{\Vert }_2^2}$$

The search directions are conjugate with each other:

$$p^{(k+1)}=r^{(k)}+{\tau }_k{p}^{(k)}$$

Finally, we increase the iteration index:

$$k\leftarrow k+1$$