The QR algorithm is an iterative method for computing the eigenvalues and Schur decomposition of a square
matrix. A shifted step starts with a complex matrix 
and a shift 
,
forms the QR decomposition
 |
and reverses the factors to obtain
 |
where 
is a unitary matrix, 
is an upper triangular
matrix, 
is the identity matrix, and the superscript H
denotes conjugate transpose. Each step is
therefore a similarity transformation
and preserves the eigenvalues.
For a dense matrix, a Hessenberg decomposition first produces a Hessenberg matrix,
reducing the work in subsequent iterations. Francis's implicitly shifted form realizes
the transformations without explicitly factoring each shifted matrix.
Local transformations create and move a small departure from Hessenberg form down
the matrix, a procedure called bulge chasing. For a real matrix, conjugate-pair shifts permit real arithmetic
and produce the 
and 
blocks of the real Schur
decomposition. Small subdiagonal entries allow completed blocks to be separated
from the remaining problem, a step called deflation (Watkins 2011).
The basic unshifted iteration does not converge for every matrix. Shift selection and deflation are central to practical implementations. The accumulated transformation gives Schur vectors, which need not be eigenvectors; these can instead be recovered by solving the corresponding triangular or block-triangular linear systems of equations.
