Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 41D (Numerical Analysis)

Starting with $A_0=A$, suppose columns $1,\dots ,j-1$ have already been reduced to tridiagonal form. Let $x$ be the part of column $j$ in rows $j+1,\dots ,n$. A Householder reflection $P_j$ on these coordinates can map $x$ to $\pm \Vert x\Vert e_1$. Extend it by the identity on the first $j$ coordinates and call the resulting orthogonal matrix $U_j$.

The updatezeros every entry below row $j+1$ in column $j$. Because it is an orthogonal similarity, it preserves eigenvalues; because the same transformation is applied on both sides, it preserves symmetry and zeros the corresponding row entries without disturbing earlier columns. After $n-2$ such steps,is symmetric and tridiagonal and has the same eigenvalues as $A$. Every reflector is obtained from finitely many matrix entries using finitely many arithmetic operations and a square root, so this is a finite construction.

The spectral expansion givesFor $j\le n-2$, the coefficient tends to zero because $|{\lambda }_j|<|{\lambda }_n|$. Thus every possible limit belongs toThe identical argument with the coefficients $c_j$ provesThe statement is conditional because, when ${\lambda }_{n-1}=-{\lambda }_n$, the component along $w_{n-1}$ generally alternates rather than converges.

Let $E_2=(e_1,e_2)$ andBecause $Q_k{R}_k$ is the QR factorization of $H^{k+1}$, $S_k$ is the span of the first two columns $q_1^{(k)},q_2^{(k)}$ of $Q_k$.

The first row of the tridiagonal eigenvalue equation isIn the generic case ${\lambda }_{n-1}\ne {\lambda }_n$, the two dominant coefficient vectors are independent, sinceHere $h_{12}\ne 0$, since otherwise the displayed eigenvalue equation and the nonzero $b_j$ would force all eigenvalues to equal $h_{11}$. The strict spectral gap below the dominant pair now impliesThis is two-dimensional subspace iteration. If the dominant eigenvalue is repeated, $H$ acts as a scalar on $W$; the same QR argument either captures all of $W$ or separates its missing direction from the strictly smaller eigenspaces, and the conclusion below is unchanged.

Since $q_2^{(k)}\in S_k$ and $q_3^{(k)}\perp S_k$,The space $W$ is invariant under $H$, soShifting the index does not affect the limit, and thereforeThus the unshifted QR algorithm asymptotically deflates a $2\times 2$ block associated with the equal-modulus dominant pair.