Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 39A / iii

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