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:

So to iterate, we just compute

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.

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