Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 40C / d / Solution

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