The unshifted QR algorithm starts at , factors , and formsfor 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.
LetThenThus is a QR decomposition of the matrix power . In particular, the first columns of span the same subspace as the first columns of whenever those columns are independent.
An unshifted QR step preserves the bandwidth of a real symmetric banded matrix. A Givens-rotation implementation exposes this as bulges created during triangularization and removed when the factors are multiplied in reverse order.
The accumulated orthogonal factor in QR iteration is the factor of a matrix power, so its leading columns span the same spaces as simultaneous power iteration.
Let a real symmetric matrix have an orthonormal eigenbasis , withWrite two starting vectors asFor two-column subspace iteration to recover
, the two projections onto that dominant subspace must be independent. The exact condition isRequiring each of the four coefficients to be nonzero does not imply this determinant condition.
, the two projections onto that dominant subspace must be independent. The exact condition isRequiring each of the four coefficients to be nonzero does not imply this determinant condition.
For an upper Hessenberg matrix iterate, when an off-block subdiagonal entry tends to zero, QR iteration asymptotically separates the corresponding invariant spectral blocks even if eigenvalues within one block have equal modulus.
Articles by others on the same topic
There are currently no matching articles.