Residuals and solution increments in CG

We state and prove a key theorem to build the CG algorithm.

Theorem. As long as we have not converged, then

$$\begin{array}{rl}\text{span}\left\{r^{(0)},\dots ,r^{(k)}\right\}& =\text{span}\left\{\Delta x^{(0)},\dots ,\Delta x^{(k)}\right\}\\ & =\mathcal{K}(A,b,k+1)\end{array}$$

where

$$r^{(k)}=b-A{x}^{(k)},\Delta x^{(k)}=x^{(k+1)}-x^{(k)}$$

Proof §

Step 1 Recall that we search a solution in the Krylov subspace:

$$\begin{array}{c}{x}^{(k)}\in \mathcal{K}(A,b,k)\\ \Delta x^{(k)}=x^{(k+1)}-x^{(k)}\end{array}$$

This implies that

$$\text{span}\left\{\Delta x^{(0)},\dots ,\Delta x^{(k)}\right\}\subset \mathcal{K}(A,b,k+1)$$

The steps $\Delta x^{(j)}$ are conjugate so they must be linearly independent. Since the dimensions of the spaces match, we have

$$\text{span}\left\{\Delta x^{(0)},\dots ,\Delta x^{(k)}\right\}=\mathcal{K}(A,b,k+1)$$

Step 2

$$\begin{array}{c}{x}^{(k)}\in \mathcal{K}(A,b,k)\\ A{x}^{(k)}\in \mathcal{K}(A,b,k+1)\end{array}$$

by definition of the Krylov subspace. This implies that:

$$\Rightarrow r^{(k)}=b-A{x}^{(k)}\in \mathcal{K}(A,b,k+1)$$

So

$$\text{span}\left\{r^{(0)},\dots ,r^{(k)}\right\}\subset \mathcal{K}(A,b,k+1)$$

Let’s assume that the dimension of $\text{span}\left\{r^{(0)},\dots ,r^{(k)}\right\}$ is less than $k+1$.

Then there is a $j$ such that $r^{(j)}\in \mathcal{K}(A,b,j).$ We also have that $r^{(j)}\perp \mathcal{K}(A,b,j).$ So $r^{(j)}=0,$ which is a contradiction. So

$$\text{span}\left\{r^{(0)},\dots ,r^{(k)}\right\}=\mathcal{K}(A,b,k+1)$$

We have proved that

$$\text{span}\left\{r^{(0)},\dots ,r^{(k)}\right\}=\text{span}\left\{\Delta x^{(0)},\dots ,\Delta x^{(k)}\right\}$$

unless CG has converged to the exact solution.

$\square$