In mathematics, a QR algorithm is an eigenvalue algorithm; that is, a procedure to calculate the eigenvalues of a matrix. The basic idea is to perform a QR decomposition, writing the matrix as a product of a orthogonal matrix and an upper triangular matrix, multiply the factors in the other order, and iterate.

Formally, let A₀ be the matrix of which we want to compute the eigenvalues. At the k-th step (starting with k = 0), we write A_k as the product of an orthogonal matrix Q_k and a upper triangular matrix R_k and we form A_k+1 = R_kQ_k. Note that

so all the A_k are similar and hence they have the same eigenvalues. The algorithm is numerically stable because it proceeds by orthogonal similarity transforms.

Under certain conditions (see Golub and Van Loan for details), the matrices A_k converge to a triangular matrix. The eigenvalues of a triangular matrix are listed on the diagonal, and the eigenvalue problem is solved.

A problem is that that the iterations are relatively expensive. This can be mitigated by bringing the matrix A first in Hessenberg form with another orthogonal similarity transform. This replaces a O(n³) procedure by one that is O(n²).

If the original matrix is symmetric, then the Hessenberg matrix is also symmetric and thus tridiagonal, and so are all the A_k. This decreases the computational cost of the algorithm further.

External links

References

• Golub, G. H. and Van Loan, C. F. Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996, ISBN 0801854148.