Optimal step size

We know how to compute $p^{(k+1)}$. We can now calculate the optimal step sizes ${\mu }_{k+1}$ using the orthogonality relations.

Recall the basic definitions:

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

Multiply by $A$

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

We use the definition of the residual: $r^{(k)}=b-A{x}^{(k)}$. So we get:

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

Recall that $r^{(k+1)}\perp p^{(k+1)}$. Let’s multiply by $(p^{(k+1)}{)}^T$ to the left:

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

We can simplify it a bit more using our three-term recurrence:

$$p^{(k+1)}=r^{(k)}+{\tau }_k{p}^{(k)},\text{and}{r}^{(k)}\perp p^{(k)}.$$

Take a dot product with $r^{(k)}$:

$$[r^{(k)}{]}^T{p}^{(k+1)}=\Vert r^{(k)}{\Vert }_2^2+{\tau }_{k}0$$

We have proved that:

Theorem. The optimal step-size in CG is given by:

$$\begin{array}{c}\Delta x^{(k)}=x^{(k+1)}-x^{(k)}={\mu }_{k+1}{p}^{(k+1)}\\ {\mu }_{k+1}=\frac{\Vert r^{(k)}{\Vert }_2^2}{(p^{(k+1)}{)}^{T}A{p}^{(k+1)}}\end{array}$$