Past exam of the numerical analysis course of the University of Oxford / 2023 / 1 / c / Solution

Choose a shift $\mu$ which is not an eigenvalue. Inverse iteration applies power iteration to $B=(A-\mu I{)}^{-1}$, implemented by a linear system solve rather than by forming an explicit matrix inverse:A single LU decomposition of $A-\mu I$ can be reused for all the solves at this fixed shift. An eigenpair $A{u}_j={\lambda }_j{u}_j$ transforms intoThus an eigenvalue ${\lambda }_{\ast }$ uniquely closest to $\mu$ becomes the dominant eigenvalue of $B$. For a diagonalizable matrix, the argument in the preceding subpart gives convergence of diagonalizable fixed-shift inverse iteration, provided the starting coefficient in the target eigenspace is nonzero, with power iteration direction error $O(q_{\mu }^k)$, whereFor any prescribed simple eigenvalue, taking a sufficiently close but unequal shift makes the numerator small while the denominator stays close to its positive separation from the remaining eigenvalues. This makes $q_{\mu }$ small and gives very fast convergence per iteration. The Rayleigh quotient of $v_k$ estimates ${\lambda }_{\ast }$ directly. If ${\beta }_k$ estimates the associated eigenvalue of $B$, the corresponding estimate is $\mu +{\beta }_k^{-1}$.

The selection principle also applies when the other eigenvalues have nontrivial blocks in the Jordan normal form: their contributions acquire powers of $k$, multiplying strictly smaller geometric factors. A simple uniquely closest eigenvalue still attracts the direction when the Riesz projection of $v_0$ onto its generalized eigenspace is nonzero. For nonreal target eigenvalues, allow complex shifts and arithmetic; a real shift cannot distinguish a conjugate pair of equal distances. Setting $\mu ={\lambda }_{\ast }$ makes the solve singular, and an exactly zero starting target component prevents convergence to that target in exact arithmetic. When ${\lambda }_{\ast }<\mu$ is real, account for the sign behavior of fixed-shift inverse iteration.