conjugate gradient: monotone decreasing krylov sequence of function values

Question

On p.10 of Boyd's notes on Conjugate Gradient, he says that a property of the Krylov sequence is that $f(x_{k+1}) \leq f(x_k)$ where $f(x) := \tfrac 12 x^T A x + b^T x$. I tried expanding this as \begin{align} f(x_{k+1}) = f(x_k + \alpha_k p_k) = f(x_k) + f(\alpha_k p_k) + 2\alpha_k x_k^T A p_k \end{align} but don't see how $f(\alpha_k p_k) + 2\alpha_k x_k^T A p_k \leq 0$.

Answer 1

With the correct $f(x):=\frac{1}{2}x^TAx-b^Tx$ and using $r_k=b-Ax_k$, the fact that $r_k^Tp_k=r_k^Tr_k$ (see (5:4a) in the original paper), and the definition of $\alpha_k=r_k^Tr_k/p_k^TAp_k$, we have $$ f(x_{k+1})=f(x_k)+\frac{1}{2}\alpha_k^2 p_k^TAp_k-\alpha_k r_k^Tp_k=f(x_k)-\frac{1}{2}\frac{(r_k^Tr_k)^2}{p_k^TAp_k}. $$ Since $A$ is SPD, $$ f(x_k)-f(x_{k+1})=\frac{1}{2}\frac{(r_k^Tr_k)^2}{p_k^TAp_k}>0. $$