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}$?

• Are you sure it is orthogonality wrt. the standard scalar product? Usually the "conjugated" in CG means orthogonal wrt. the scalar product that the symmetric matrix $A$ induces. Jun 9, 2017 at 6:42

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.$$