QR algorithm
|
|
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 A0 be the matrix of which we want to compute the eigenvalues. At the k-th step (starting with k = 0), we write Ak as the product of an orthogonal matrix Qk and a upper triangular matrix Rk and we form Ak+1 = RkQk. Note that
- <math> A_{k+1} = Q_k^{-1} A_k Q_k, <math>
so all the Ak 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 Ak 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(n3) procedure by one that is O(n2).
If the original matrix is symmetric, then the Hessenberg matrix is also symmetric and thus tridiagonal, and so are all the Ak. 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.