Computationally efficient search directions

We have derived all the important relations in CG. We need one more step to make computing the search directions a little bit computationally more efficient.

Recall the basic three-term recurrence for the search directions:

$$\begin{array}{c}{p}^{(k+1)}=r^{(k)}+{\tau }_k{p}^{(k)}\\ {\tau }_k=-\frac{(p^{(k)}{)}^{T}A{r}^{(k)}}{(p^{(k)}{)}^{T}A{p}^{(k)}}\\ {\tau }_k=-\frac{(p^{(k)}{)}^{T}A{r}^{(k)}}{(p^{(k)}{)}^{T}A{p}^{(k)}}=-\frac{(A{p}^{(k)}{)}^T{r}^{(k)}}{(p^{(k)}{)}^{T}A{p}^{(k)}}\end{array}$$

Let’s substitute $A{p}^{(k)}$. From our previous derivations:

$$\begin{array}{c}{x}^{(k)}-x^{(k-1)}={\mu }_k{p}^{(k)}\\ A{x}^{(k)}-A{x}^{(k-1)}={\mu }_{k}A{p}^{(k)}\\ -r^{(k)}+r^{(k-1)}={\mu }_{k}A{p}^{(k)}\\ -A{p}^{(k)}=\frac{r^{(k)}-r^{(k-1)}}{{\mu }_k}\end{array}$$

Substitute in ${\tau }_k$:

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

Recall that $r^{(k)}\perp r^{(k-1)}:$

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

Use the equation for ${\mu }_k$:

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

So:

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

Substitute back in ${\tau }_k$:

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

We have proved that:

Theorem. The optimal search directions in CG are given by:

$$\begin{array}{c}{p}^{(k+1)}=r^{(k)}+{\tau }_k{p}^{(k)}\\ {\tau }_k=\frac{\Vert r^{(k)}{\Vert }_2^2}{\Vert r^{(k-1)}{\Vert }_2^2}\end{array}$$