Three-term recurrence

We derive an efficient three-term relation for the search directions $p^{(l)}$.

Using the orthogonality conditions, we can derive an efficient three-term recurrent relation.

Recall that

$$r^{(k)}=p^{(k+1)}+\sum _{l=1}^k{\alpha }_l{p}^{(l)}$$

The search directions $p^{(l)}$ are conjugate. So this is, in fact, a type of QR decomposition of the matrix

$$[r^{(0)},\dots ,r^{(k)}]$$

using $A$-orthogonality. Note that the search directions $p^{(l)}$ do not have norm 1. They are just conjugate.

Recall the algorithms to compute the QR factorization $A=QR$ and the Lanczos process, $AQ=QT$. In both cases, we found the columns of $Q$ using a recurrence and orthogonality. The same ideas can be applied here. Consider

$$r^{(k)}=p^{(k+1)}+\sum _{l=1}^k{\alpha }_l{p}^{(l)}$$

and multiply to the left by $[p^{(r)}{]}^{T}A$, we get

$$[p^{(r)}{]}^{T}A{r}^{(k)}=[p^{(r)}{]}^{T}A{p}^{(k+1)}+\sum _{l=1}^k{\alpha }_l[p^{(r)}{]}^{T}A{p}^{(l)}$$

From the orthogonality relations, we have that for $r<k$:

$$[p^{(r)}{]}^{T}A{r}^{(k)}=0$$

and

$$[p^{(r)}{]}^{T}A{p}^{(l)}=0,r\ne l$$

So for $r<k$, we get

$$0={\alpha }_r[p^{(r)}{]}^{T}A{p}^{(r)}$$

and $[p^{(r)}{]}^{T}A{p}^{(r)}\ne 0$ since $A$ is SPD. So ${\alpha }_r=0$, $r<k$. We are only left with the term $l=k$:

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

There is only one term left. Let us denote for convenience:

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

Multiply by $A$ and take a dot product with $p^{(k)}$:

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

Theorem. The search directions in CG satisfy:

$$\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)}}\end{array}$$

${\tau }_k$ is the negative of the $A$-projection of $r^{(k)}$ onto $p^{(k)}$.

We find the new search direction by taking a vector in $K_{k+1}$ and making it conjugate to the previous $p^{(k)}$.

$p^{(k+1)}$ is a linear combination of the residual and the previous search direction.