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

For a nonzero real vector $x$, the Rayleigh quotient of the matrix $A$ isThe Rayleigh quotient iteration starts from a unit vector $v_0$. Given $v_k$, compute the shiftsolve the linear systemand normalize in the Euclidean norm:The next eigenvalue estimate is ${\mu }_{k+1}=R_A(v_{k+1})$. The process stops when the eigenpair residual is sufficiently small.

Differentiate the eigenvalue equationat $t=0$, where $A^{\prime }(0)=E$. Suppressing the argument $0$ givesLeft-multiplication by the transpose of the unit left eigenvector $u$ and use of $u^{T}A=\lambda u^T$ cancel the terms involving $v^{\prime }$:Because the eigenvalue is simple, $u^{T}v\ne 0$, and hence the first-order perturbation of a simple eigenvalue isThe definition of the operator norm, followed by the Cauchy-Schwarz inequality, givesTherefore

If $A$ is a real symmetric matrix, the finite-dimensional spectral theorem lets us choose the normalized left eigenvector and right eigenvector to be the same vector. Thus

More generally, the unitary diagonalization of a normal matrix shows that a real normal matrix also has coincident normalized left and right eigenspaces for each real eigenvalue. Since the question assumes $\lambda \in \mathbb{R}$, one can again choose $u=v$, and every such simple eigenvalue has

The displayed matrix is an upper bidiagonal matrix. For ${\lambda }_1=1$, the right eigenvector equation $(A-I)v=0$ successively givesWe may therefore take the unit right eigenvector to be $v=e_1$.

For a left eigenvector, $(A^T-I)u=0$ givesSince ${\lambda }_i-1=-1/i$,Choosing the initial scale $u_1=1$ producesAfter normalization,The eigenvalue sensitivity is thereforewhere $n!$ is the factorial. Hence

Let the computed eigenpair residual beDefine the rank-one matrixThenso $(\tilde{\lambda },\tilde{v})$ is an exact eigenpair of the perturbed matrix $A+E$. Moreover,which is the backward error of an approximate eigenpair.

Follow the simple eigenvalue branch from $\lambda (0)=\lambda$ for $A(t)=A+tE$. The first-order perturbation of a simple eigenvalue and part (b) giveSince the residual is at the machine precision scale, this proves