QR Algorithm¶
An eigenvalue iteration that repeatedly QR-factorizes a shifted matrix and reverses the factors, preserving similarity while driving it toward real or complex Schur form for deflation.
Core Idea¶
The QR algorithm computes matrix eigenvalues through a sequence of orthogonal or unitary similarity transformations. In the unshifted idealization, factor the current square matrix as A_k=Q_k R_k, then reverse the factors: A_(k+1)=R_k Q_k. Because R_k Q_k=Q_k^* A_k Q_k, the new matrix is similar to the old one and has the same eigenvalues. Under appropriate conditions, repeated steps drive the matrix toward triangular complex Schur form, or quasi-triangular real Schur form.
Practical QR is not merely this classroom loop. Dense solvers normally reduce the matrix to upper Hessenberg form, choose shifts to accelerate convergence, chase the resulting bulge implicitly, detect negligible subdiagonal entries, and deflate converged blocks. These roles make the method both recognizable and computationally viable.
Scope of Application¶
QR is the foundational dense eigenvalue method for real and complex matrices. Symmetric or Hermitian problems reduce to tridiagonal form and preserve that structure; general problems reduce to Hessenberg form. Applications span vibrations, stability, control, quantum models, Markov processes, data analysis, and any computation requiring a full or substantial spectrum.
Large sparse problems often use Krylov methods when only a few eigenvalues are wanted, because a full dense QR computation wastes structure and storage. Specialized symmetric eigensolvers may use divide-and-conquer, bisection, or MRRR after reduction. QR remains the conceptual and implementation baseline, not the only eigenvalue tool.
Clarity¶
For a shifted step, factor A_k-mu_k I=Q_k R_k and set A_(k+1)=R_k Q_k+mu_k I. Substitution gives A_(k+1)=Q_k^* A_k Q_k. Thus shifts change convergence behavior without changing eigenvalues. When a subdiagonal entry becomes negligible relative to nearby diagonal entries, the matrix splits approximately into independent blocks and the converged block can be deflated.
Manages Complexity¶
Similarity transformation converts a global polynomial-root problem into progressive structural simplification. Hessenberg reduction makes later iterations cheap because zeros below the first subdiagonal are preserved. Shifts focus progress near a target eigenvalue; deflation shrinks the active problem; bulge chasing realizes the transformation without dense factorization at every step.
Abstract Reasoning¶
The similarity equation is the load-bearing proof. Every exact iterate has the same characteristic polynomial. If off-diagonal structure converges away, the invariant spectrum becomes readable from triangular blocks. This separates correctness of the target from convergence of the representation.
Shifts can be chosen from trailing entries because they need not equal exact eigenvalues to preserve similarity. Exceptional shifts and multi-shift strategies handle stagnation.
Knowledge Transfer¶
The literal role package transfers among symmetric, nonsymmetric, real, complex, single-shift, double-shift, and multishift solvers. Reduction, shifted similarity, bulge chasing, convergence, and deflation remain recognizable while kernels differ.
The broader pattern—preserve an invariant while iteratively changing representation toward readable normal form—transfers beyond matrices. That residue belongs to Iteration, Invariance, Refinement, and Normal Form. Without QR factors and spectral Schur structure it is not the QR algorithm.
Relationships to Other Abstractions¶
Current abstraction QR Algorithm Domain-specific
Parents (1) — more general patterns this builds on
-
QR Algorithm is a kind of Algorithm Prime
QR Algorithm specializes
prime:algorithm, the minimal proposed parent.
Hierarchy paths (2) — routes to 2 parentless roots
- QR Algorithm → Algorithm → Function (Mapping)
Neighborhood in Abstraction Space¶
QR Algorithm sits in a sparse region of the domain-specific corpus (84th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Applied Linear & Special Functions (18 abstractions)
Nearest neighbors
- Quadratic Space — 0.83
- Conjugate Gradient Method — 0.81
- Compact Operator — 0.81
- Matrix exponential — 0.80
- Tensor Sketch — 0.80
Computed from structural-signature embeddings · 2026-09-08