Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 4 / 39C (Numerical Analysis)

Since $A$ is diagonalizable over the complex numbers, write $x^{(0)}={\sum }_i{a}_i{v}_i$. Provided iteration does not encounter zero, its direction is that ofWith one strictly dominant eigenvalue and $a_n\ne 0$, all other contributions are smaller by factors $(|{\lambda }_i|/|{\lambda }_n|{)}^k$. The dominant eigenvalue is real, since nonreal eigenvalues of a real matrix occur in conjugate pairs of equal modulus. The normalized power method therefore converges to a signed unit eigenvector if ${\lambda }_n>0$, and alternates between opposite unit eigenvectors if ${\lambda }_n<0$. A quotient such as $(x^{(k)}{)}^{T}A{x}^{(k)}$ approaches ${\lambda }_n$ in either case. If $a_n=0$, replace it by the largest active modulus; if $A{x}^{(k)}=0$, the prescribed iteration is undefined.

With two dominant eigenvalues of equal modulus and both components active, the iterates approach their real invariant plane rather than one direction. Distinct real equal-modulus eigenvalues are $\rho ,-\rho$ and produce a limiting two-cycle. A conjugate pair $\rho e^{\pm i\theta }$ produces a rotation in suitable coordinates on that plane: the normalized directions are periodic when the angle is rational relative to $2\pi$ and otherwise generally keep rotating without convergence. If the two eigenvalues are equal and real, the initial projection is itself one eigenvector in their repeated eigenspace, and converges or alternates as in the single-value case; one orbit cannot recover every independent eigenvector of that eigenspace.

For distinct dominant values, retain unnormalized consecutive vectors $y,Ay,A^{2}y$ in the nearly invariant plane and solveThe roots of ${\lambda }^2-s\lambda +p$ estimate the two eigenvalues. Corresponding eigenvectors are $Ay-{\lambda }_{2}y$ and $Ay-{\lambda }_{1}y$, since applying $A$ and using the recurrence multiplies them by ${\lambda }_1$ and ${\lambda }_2$. This is dominant eigenpair extraction from a two-step Krylov recurrence. Equivalent extraction uses the $2\times 2$ matrix of $A$ on the computed plane. It needs two independent iterates and nonzero projections onto both distinct eigenvectors.

The given vectors satisfyand $y_k,y_{k+1}$ are independent, so their span is invariant under $A$. On that plane the characteristic polynomial is ${\lambda }^2-2\lambda +2$. ThereforeIndeed $A{v}_{\pm }=y_{k+2}-(1\mp i)y_{k+1}=(1\pm i)v_{\pm }$. No third eigenvalue is determined by these data.

The displayed $x_k=(1,1,1)$ has norm $\sqrt{3}$, although a large-$k$ normalized iterate should have norm one. This harmless source normalization is resolved by dividing all three displayed vectors by $\sqrt{3}$; the recurrence, eigenvalues and eigenvector directions are unchanged.