With , repeat the shifted QR algorithm:
The QR shift is chosen from , for example its bottom-right entry or an eigenvalue of a trailing two-by-two block. Explicitly using the orthogonality of gives
Thus each update is a matrix similarity preserving eigenvalues. Accumulate if eigenvectors or the full reduction are wanted. Once a subdiagonal entry is negligible, block deflation in the QR algorithm separates the corresponding blocks and iteration continues on the active block.
For an efficient QR algorithm, first reduce a general real matrix to upper Hessenberg matrix by orthogonal similarities. For a real symmetric matrix, use Householder tridiagonalization; the resulting symmetric tridiagonal matrix is the usual input in this setting. These structures are preserved by suitable QR algorithm implementations and greatly reduce the work per iteration.
The output is the eigenvalues, together with an orthogonal reduction when the factors are accumulated. In the symmetric case the target is a diagonal matrix, whose diagonal entries are the real eigenvalues; the accumulated orthogonal columns are eigenvectors. For a general real matrix, the target is the real form in a Schur decomposition: an upper block triangular matrix with diagonal blocks of size one or two. The two-by-two blocks represent complex conjugate eigenvalue pairs. An arbitrary unshifted iteration need not converge, so these describe the intended converged output, with appropriate shifts and block deflation in the QR algorithm.
QR shift 2026-10-31
A QR shift is a scalar subtracted before the QR factorization in a QR algorithm step and restored after reversing the factors:
The final identity uses the orthogonality of , 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.
Unshifted QR algorithm Created 2026-09-24 Updated 2026-11-05
The unshifted QR algorithm starts at , factors , and forms
for real data with orthogonal . Each step is an orthogonal similarity, so it preserves eigenvalues. It is the zero-shift case of the QR algorithm; complex data use a unitary factor and conjugate transpose.
Convergence needs hypotheses. For a real symmetric matrix with suitably separated eigenvalue moduli and nondegenerate starting projections, the simultaneous iteration interpretation of the QR algorithm explains convergence toward diagonal form. Equal moduli can prevent that behavior: for , the valid factorization , leaves every iterate equal to . Its eigenvalues remain coupled.
For nonsymmetric matrices, the useful target is generally a triangular form or a real Schur form, rather than a diagonal matrix. Shifts and block deflation in the QR algorithm improve practical convergence. The similarity identity by itself is not a convergence theorem.