Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 41C (Numerical Analysis)

Since $H$ is diagonalizable, write $H=V\Lambda V^{-1}$. ThenIf the spectral radius $\rho (H)<1$, every eigenvalue satisfies $|{\lambda }_i|<1$, so ${\Lambda }^k\to 0$ and hence $z^{(k)}\to 0$ for every initial vector. Conversely, taking $z^{(0)}$ to be an eigenvector of any eigenvalue $\lambda$ shows that convergence for every initial vector forces ${\lambda }^k\to 0$, hence $|\lambda |<1$. Therefore

Because $A$ is symmetric positive definite,Thus the only stationary point is $x_{\ast }=A^{-1}b$, andThe final term is positive unless $x=x_{\ast }$, proving that $A^{-1}b$ is the unique minimizer.

The gradient descent iteration isFor the error $e^{(k)}=x^{(k)}-A^{-1}b$,Part (a) shows that convergence for every initial vector is equivalent to
$|1-\alpha {\lambda }_i|<1$ for every eigenvalue of $A$. Since all eigenvalues are positive,

Since $r^{(k)}=b-A{x}^{(k)}=-\nabla f(x^{(k)})$, exact line search minimizes
$f(x^{(k)}+\alpha r^{(k)})$. Differentiating with respect to $\alpha$ givessoMoreover,and substitution of the displayed step size yieldsThus consecutive residuals are orthogonal.