Conjugate gradient - gradients orthogonality proof

Question

I need to prove that $\left<r_{k+1}, r_k\right> = 0$ ($r_{k} = \nabla f(x_k)$) in the conjugate gradient method for quadratic functions.

We can use the property of quadratic functions: $$ r_{k+1} = r_{k} - \alpha_{k} A d_{k} $$ and multiply it by $r_{k}$: $$ \left<r_{k+1}, r_k\right> = \left\lVert{r_{k}}\right\lVert^2 - \alpha_{k} \left< A d_{k}, r_{k} \right> $$ $\alpha_{k}$ is chosen to be locally optimal ($f(x_{k} - \alpha_{k} d_{k}) \to \min$): $$ f(x_{k} - \alpha_{k} d_{k}) = f(x_{k}) - \alpha_{k} \left< r_{k}, d_{k}\right> + \frac{1}{2}\alpha_{k}^{2} \left< A d_{k}, d_{k}\right> $$ $$ \frac{\partial{f}}{\partial{\alpha_k}} = - \left< r_{k}, d_{k}\right> + \alpha_{k} \left< A d_{k}, d_{k}\right> = 0 $$ $$ \alpha_{k} = \frac{\left< r_{k}, d_{k}\right>}{\left< A d_{k}, d_{k}\right>} $$ on substituting: $$ \left<r_{k+1}, r_k\right> = \left\lVert{r_{k}}\right\lVert^{2} - \frac{\left< r_{k}, d_{k}\right>}{\left< A d_{k}, d_{k}\right>} \left< A d_{k}, r_{k} \right> $$

I'm stuck here. How can we simplify it and get $\frac{\left< r_{k}, d_{k}\right>}{\left< A d_{k}, d_{k}\right>} \left< A d_{k}, r_{k} \right> = \left\lVert{r_{k}}\right\lVert^{2}$?

Answer 1

I am aware of the following proof using various properties of the CG method - there might be one out there with less required properties. For another question I outlined the derivation of the method and will re-use results here.

The sort of defining property of the CG iterates $\boldsymbol x^k$ is that they are optimal with respect to the space spanned by the update directions $\boldsymbol p^j$: $$ \big \langle \underbrace{A \boldsymbol x^k - \boldsymbol b}_{=: \boldsymbol r^k}, \boldsymbol p^j \big \rangle = 0, \quad j = 0, \dots, k-1$$

Another useful property of CG is that the space spanned by the update directions $V_k := \text{span} \Big \{ \boldsymbol p^0 , \dots \boldsymbol p^{k-1} \Big \}$ equals the space spanned by the residuals: $V_k = R_k := \text{span} \Big \{ \boldsymbol r^0 , \dots \boldsymbol r^{k-1} \Big \}$. As a consquence, $$ \big \langle \boldsymbol r^{k+1}, \boldsymbol p^j \big \rangle = 0, \quad j = 0, \dots, k \Leftrightarrow \big \langle \boldsymbol r^{k+1}, \boldsymbol r^j \big \rangle = 0, \quad j = 0, \dots, k$$ which implies also in particular $$\big \langle \boldsymbol r^{k+1}, \boldsymbol r^k \big \rangle = 0.$$