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

The power method starts from $q_0\ne 0$ and iteratesIf the eigenvalue of largest modulus is separated by a spectral gap and the initial vector is nonorthogonal to a corresponding eigenvector, the iterates converge in direction to that eigenvector.

Inverse iteration with shift $s$ instead solvesIt applies the power method to $(A-sI{)}^{-1}$ and therefore finds an eigenvector whose eigenvalue is closest to $s$.

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$.