Convergence for Conjuguate gradient method I am trying to probe this corollary in a numerical PDE book:
If $A\in \mathbb{R^{n\times n}}$  is symmetric and positive definite, then the conjugate gradient method reaches the exact solution in at most $n$ iterations. 
 A: Starting from $x_0$, the conjugate gradients generate approximations $x_1,\ldots,x_k$  such that the residuals $r_i:=b-Ax_i$ are mutually orthogonal, that is, $r_k\perp r_i$, $i=1,\ldots,k-1$. Since orthogonal vectors are linearly independent if and only if they are nonzero and there cannot be more than $n$ linearly independent $n$-vectors, we must have $r_m=0$ for some $m\leq n$.
A: Here is the sketch of a direct approach:
Let $\{\vec{v}^{(0)}, ...\vec{v}^{(n-1)}\}$ be an $A$-orthogonal set of vectors. Let $\alpha^{(k)}=\frac{\vec{v}^{(k)T}\vec{v}^{(k)}}{\vec{v}^{(k)T}A\vec{v}^{(k)}}$, and $\vec{x}^{(k+1)}=\vec{x}^{(k)}+\alpha^{(k)}\vec{v}^{(k)}$.
First show that the set $\{\vec{v}^{(0)}, ...\vec{v}^{(n-1)}\}$ is linearly independent.
Then write residue $\vec{r}^{(0)}$ in terms of this set:
$$\vec{r}^{(0)}=\vec{x}-\vec{x}^{(0)}=\sum \delta_j \vec{v}^{(j)}$$ 
You can find $\delta_j$ by multiplying both sides by $\vec{v}^{(k)T}A$ to cancel the other terms.
You can find that $\vec{r}^{(0)}=\sum \alpha^{(j)}\vec{v}^{(j)}$. From this, you can prove that $\vec{r}^{(n)}=\vec{0}$.
