Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 40C (Numerical Analysis)

Forthe gradient is $\nabla F(x)=Ax-b=-r$. The steepest descent method with exact line search for a positive-definite quadratic therefore uses

For $A=\mathrm{diag}(1,\gamma )$ and $b=0$, the minimizer is $x^{\ast }=0$. PutStarting from $x^{(0)}=(\gamma ,1{)}^T$, direct substitution gives ${\alpha }_k=2/(\gamma +1)$ and, inductively,The Euclidean norm is unchanged by the alternating sign, soFor a positive-definite matrix, the spectral condition number of a positive-definite matrix isHere ${\kappa }_2(A)=\gamma$, and hence

The Conjugate gradient method starts with $p_0=r_0$ and updatesBy finite termination of the conjugate gradient method, it reaches the exact solution in at most the number of distinct eigenvalues. This matrix has two, so at mostare required in exact arithmetic.

Since $\nabla F(x^{(k)})=-r^{(k)}$, the Heavy-ball method isMultiplication by $A$ and use of $A{x}^{(j)}=b-r^{(j)}$ give the heavy-ball residual recurrenceWith the usual initialization $x^{(-1)}=x^{(0)}=0$, both initial residuals equal $b$. Induction in the recurrence shows thatfor a polynomial $p_k$ of degree at most $k$. ThereforeThis is ${\mathcal{K}}_k(A,b)$ under the zero-indexed Krylov subspace convention in the question; under the convention whose order-$j$ space ends at $A^{j-1}b$, it is ${\mathcal{K}}_{k+1}(A,b)$.

Because $A{x}^{\ast }=b$, the error $e^{(k)}=x^{\ast }-x^{(k)}$ obeysThus the heavy-ball error propagation matrix is

If $A=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)$, permute the coordinates fromtoFor the corresponding permutation matrix $P$,

Put $s={\gamma }^{-1/2}$. ThenFor an eigenvalue $\lambda$, the corresponding $2\times 2$ block has characteristic polynomialFor $\lambda =1$,so the polynomial isFor $\lambda =\gamma$, it isIts discriminant is $\beta (\beta -4)<0$, so its conjugate roots have product $\beta$ and modulus $\sqrt{\beta }$. Both blocks therefore have the same spectral radius, andThis is the heavy-ball rate for a two-eigenvalue diagonal quadratic.

By contrast, the steepest-descent factor isThe heavy-ball factor is $1-{\gamma }^{-1/2}$, which is substantially smaller for $\gamma \gg 1$: it gives an iteration scale of order $\sqrt{\gamma }$ rather than order $\gamma$.