QR algorithm

The QR algorithm computes eigenvalues through repeated QR decompositions and similarity updates. Shifted and unshifted forms have different convergence rates; the unshifted QR algorithm uses a zero shift at every step.

The real Schur form of a real square matrix $A$ is $Q^{\top }AQ=T$, where $Q$ is orthogonal and $T$ is upper quasi-triangular. Its diagonal consists of one-by-one blocks for real eigenvalues and two-by-two blocks for complex-conjugate pairs.

The rotation generator $\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)$ already forms one two-by-two block with eigenvalues $\pm i$. No real upper-triangular matrix can have those eigenvalues, because its diagonal entries would all be real. Real Schur form therefore permits real arithmetic without pretending every eigenvalue is real. Its orthogonal transformations are also preferable numerically to using a potentially ill-conditioned eigenvector matrix.^[ref]

For $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, one shifted QR algorithm step with real QR shift $\mu$ gives, with a consistent choice of factor signs,To verify this, factor $A-\mu I=QR$ with $Q=(1+{\mu }^2{)}^{-1/2}\left(\begin{array}{cc}-\mu & -1\\ 1& -\mu \end{array}\right)$. Its columns are orthonormal, and $R=Q^T(A-\mu I)$ is upper triangular. Then $A_1=Q^{T}AQ$. Thus $A_1$ is diagonal exactly when $\mu =\pm 1$, the two eigenvalues. The bottom-right-entry shift is zero and leaves the matrix unchanged under the positive-diagonal factor convention. This illustrates why a poorly chosen QR shift can stall even a two-by-two symmetric eigenvalue computation.

A QR shift is a scalar ${\mu }_k$ subtracted before the QR factorization in a QR algorithm step and restored after reversing the factors:The final identity uses the orthogonality of $Q_k$, proving that the eigenvalues are preserved. Choosing a shift near an eigenvalue can accelerate block deflation in the QR algorithm. A common choice is the current bottom-right entry, but it can stall, as in Exact-shift diagonalization of a two-state swap matrix.