7. QR Iteration

The iteration takes the form $Q^{(k + 1)}R^{(k)} = AQ^{(k)}$. The first $p$ columns converge to an orthonormal basis for the $p$-dimensional eigenspace associated with $A$’s largest eigenvalues. This assumes that there aren’t several eigenvalues with the same modulus.

This somehow magically converges into a Schur form:

\[AU = UT\\ A^{(k)} = (Q^{(k)})^TAQ^{(k)}.\]

So to iterate, we just compute

\[A^{(k)} = Q^{(k)}R^{(k)}\\ A^{(k+1)} = R^{(k)}Q^{(k)}.\]

Problems with QR Iteration

Because we are computing a QR iteration at each step, this takes $O(n^4)$ time, which is not efficient! However, by converting our matrix into an upper Hessenberg matrix, we can do QR in $O(n^2)$ time.

\[A = QHQ^T\]

where $Q$ is orthogonal and $H$ is upper Hessenberg.