All the orthogonality relations in CG

We derive all the orthogonality relations in CG that you need to know. This is the foundation to build the final steps of CG.

Recall our definition of the search directions and residual vectors:

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

From these definitions, we can derive all the results below. Make sure you understand the reasoning behind each result.

Property 1. $x^{(k)}\in {\mathcal{K}}_k.$

This is because of the basic construction of iterative methods using the Krylov subspace.

Property 2. $\Delta x^{(k)}\in {\mathcal{K}}_{k+1}$ and $p^{(k+1)}\in {\mathcal{K}}_{k+1}.$

This is true because of the definition of the search directions above.

Property 3. $r^{(k)}\in {\mathcal{K}}_{k+1}.$

This is true because of the definition of the residual vectors and the Krylov subspace.

Property 4. If $y\in K_k$, then $Ay\in {\mathcal{K}}_{k+1}.$

This is true because of the definition of the Krylov subspace.

Note that these orthogonality relations are not a “new thing.” It’s a direct consequence of the basic starting point of CG

$$\underset{y}{\min }\Vert x-Q_{k}y{\Vert }_A$$

and the Krylov subspace. We have seen previously that this implies that $r^{(k)}$ is $\perp$ to ${\mathcal{K}}_k.$

Property 5. $r^{(k)}\perp {\mathcal{K}}_k.$

See the previous section.

Property 6. $r^{(k)}\perp r^{(l)},k\ne l.$

This is a consequence of the results listed above (Properties 3 and 5).

Property 7. $r^{(k)}\perp p^{(l)},l\le k.$

This is a consequence of Properties 2 and 5.

Property 8. $p^{(k)}\perp A{p}^{(l)},$ $k\ne l.$

So $p^{(k)}$ and $p^{(l)}$ are conjugate.

This is a consequence of the conjugacy of the $\Delta x^{(k)}$ and $\Delta x^{(k)}$, along with

$$\Delta x^{(k)}={\mu }_{k+1}{p}^{(k+1)}.$$

Property 9. $r^{(k)}\perp A{p}^{(l)},$ $l\le k-1;$ $r^{(k)}$ and $p^{(l)}$ are conjugate.

Proof. Since $r^{(k)}\perp Q_k$, we have $r^{(k)}\perp A{Q}_{k-1}.$ Since $p^{(l)}\in {\mathcal{K}}_l,$

$$r^{(k)}\perp A{p}^{(l)},l\le k-1.$$

$\square$