Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 4 / 40A / b

The unshifted QR algorithm computes the eigenvalues of $A$. For a real symmetric matrix it drives $A_k$ toward a diagonal or block-diagonal matrix; the accumulated orthogonal factors simultaneously approximate its eigenvectors.

Since $A_k=Q_k{R}_k$,Thus every step is an orthogonal similarity, so it preserves eigenvalues and symmetry.

For a symmetric $r$-banded matrix, its subdiagonal entries can be eliminated by Givens rotations ordered along the band. Each rotation creates only the next local bulge; multiplication in reverse order chases that bulge out without creating entries beyond the original upper band. Symmetry supplies the corresponding lower band. This is symmetric bandwidth preservation under QR iteration, and proves that $A_{k+1}$ is again $r$-banded.

For $k=1$ the claim is just $A=Q_0{R}_0$. Ifthen $A_k={\tilde{Q}}_k^{T}A{\tilde{Q}}_k=Q_k{R}_k$, and henceInduction proves $A^k={\tilde{Q}}_k{\tilde{R}}_k$ for all $k\ge 1$.

Let $q_1$ and $q_n$ be the first and last columns of ${\tilde{Q}}_k$. Since ${\tilde{R}}_k$ is upper triangular,Thus $q_1$ is the normalized $k$th power method iterate starting from $e_1$.

Taking the transpose of $A^k={\tilde{Q}}_k{\tilde{R}}_k$ and using symmetry gives $A^k={\tilde{R}}_k^T{\tilde{Q}}_k^T$. ThereforeSo the last column is the normalized $k$th inverse iteration iterate with shift zero and starting vector $e_n$.