QR algorithm

Repeatedly factoring a matrix as Q times R, then multiplying the two factors back together in the OPPOSITE order -- somehow this drives the matrix toward triangular.

The QR algorithm generates $A_0=A,\,A_1,\,A_2,\ldots$ by factoring $A_k=Q_kR_k$ (any valid QR factorization) and setting $A_{k+1}=R_kQ_k$ . Since $A_{k+1}=Q_k^{-1}A_kQ_k$ and $Q_k$ is orthogonal, every $A_k$ is similar to $A$ and therefore shares its eigenvalues exactly; under mild conditions the below-diagonal entries shrink toward zero, so $A_k$ 's diagonal converges to $A$ 's own eigenvalues. Practical implementations reduce $A$ to Hessenberg form first and use shifts to accelerate convergence.

Examples

After several QR-algorithm iterations, a matrix's below-diagonal entries shrink toward zero while its diagonal entries settle onto the original matrix's own eigenvalues, one per position.