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

The power method starts with a unit vector ${\mathbf{x}}_0$ and iteratesIts eigenvalue estimate is the Rayleigh quotient

By the real spectral theorem, choose an orthonormal eigenbasis ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ and writeAssume $|{\lambda }_1|>|{\lambda }_2|$, ${\lambda }_1\ne 0$, and $c_1\ne 0$. Before normalization,Thus the direction error is $O(|{\lambda }_2/{\lambda }_1{|}^k)$. Orthogonality makes the linear terms vanish from the Rayleigh quotient:ConsequentlyThis is the quadratic Rayleigh-quotient improvement for the power method.

An orthonormal eigenbasis isThe starting vector has the orthogonal decompositionHence its component in the dominant eigenspace is exactly zero. Normalizing $A^k{\mathbf{x}}_0$ givesSince the two remaining eigenvectors are orthogonal,ThereforeThe limit is not the leading eigenvalue $9$ because the nonorthogonality assumption in part (a) fails. On the active spectrum of the power method, the leading eigenvalue is $6$ and the next is $2$; indeedin agreement with the squared spectral-ratio estimate.

Fix a shift $s$ that is not an eigenvalue of $A$. Inverse iteration computesand may use $r({\mathbf{x}}_k)$ as the eigenvalue estimate.

For a real symmetric matrix, suppose that one eigenvalue ${\lambda }_{\ast }$ is uniquely closest to $s$ and that ${\mathbf{x}}_0$ has a nonzero component in its eigenspace. Since the iteration is the power method applied to $(A-sI{)}^{-1}$, the normalized vectors converge, up to sign, to an eigenvector for ${\lambda }_{\ast }$. If ${\lambda }_{\mathrm{next}}$ is the second-closest eigenvalue to the shift, the asymptotic direction-error ratio isThus a shift close to the desired eigenvalue gives rapid convergence. The Rayleigh quotients converge to ${\lambda }_{\ast }$ and, for a simple eigenvalue, their errors are of second order in the vector error. This is convergence of fixed-shift inverse iteration.