Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 39A (Numerical Analysis)

Expand the initial vector in the orthonormal eigenbasis. After $j$ unshifted steps, the coefficient ratio of mode $i<n$ to the dominant mode is $(c_i/c_n)({\lambda }_i/{\lambda }_n{)}^j$. Since ${\lambda }_{n-1}=1$ and $c_{n-1},c_n\ne 0$, the sharp asymptotic contraction factor isNormalization only changes the dominant coefficient by a higher-order error; its eventual sign is the sign of $c_n$.

With shift $1/2$, the unwanted eigenvalues lie in $[-1/2,1/2]$, and both endpoints occur. The dominant shifted eigenvalue is $1/2+ϵ$. HenceThe negative endpoint can alternate in sign, but the norm error has this factor, and the even-iteration comparison removes the alternation.

Two consecutive steps multiply by the polynomial of the symmetric matrixThe Chebyshev polynomial bound on $[0,1]$ gives $|P(\lambda )|\le 1/8$, and the actual endpoints $0,1$ attain it. At the dominant eigenvalue, $P(1+ϵ)=1/8+ϵ+{ϵ}^2$. ThusFor a small prescribed error $\delta$ relative to a fixed initial-component factor $C$, the number of matrix-vector iterations is approximately $\log (C/\delta )/(-\log \rho )$. The three leading denominators are $ϵ,2ϵ,4ϵ$. Therefore the iteration counts are in the ratio $1:1/2:1/4$: the single shift halves and the alternating double shift quarters the leading count. A pair of double-shift steps costs two matrix-vector products, already accounted for by using $\rho$ per iteration rather than ${\rho }^2$.