QR algorithm

Remarks

Since $R_k = Q_k^T A_k$, one has $A_{k+1} = Q_k^T A_k Q_k$, so every $A_k$ is similar to $A$ and has the same eigenvalues. Suppose the eigenvalues of $A$ have pairwise distinct absolute values, and a mild condition on the eigenvectors holds. Then the entries of $A_k$ below the diagonal tend to $0$, and the diagonal entries tend to the eigenvalues. Example: for $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$, $Q_0 = \tfrac{1}{\sqrt5}\begin{pmatrix} 2 & -1 \\ 1 & 2 \end{pmatrix}$ and $R_0 = \tfrac{1}{\sqrt5}\begin{pmatrix} 5 & 4 \\ 0 & 3 \end{pmatrix}$. So $A_1 = R_0 Q_0 = \tfrac15 \begin{pmatrix} 14 & 3 \\ 3 & 6 \end{pmatrix}$; the trace stays $4$ and the off-diagonal entry drops from $1$ to $0.6$. Non-example of convergence: for the rotation $A = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$, which is orthogonal, one may take $Q_0 = A$, $R_0 = I$, so $A_1 = A$ and the sequence is constant; its eigenvalues $\pm i$ have equal absolute value. Practical versions first reduce $A$ to Hessenberg form, use shifts $A_k - \sigma_k I = Q_k R_k$, $A_{k+1} = R_k Q_k + \sigma_k I$, and split off converged eigenvalues. The algorithm was found independently by John G. F. Francis and Vera Kublanovskaya around 1960.