Home »

Qr algorithm

The meaning of «qr algorithm»

In numerical linear algebra, the QR algorithm or QR iteration is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR algorithm was developed in the late 1950s by John G. F. Francis and by Vera N. Kublanovskaya, working independently.[1][2][3] The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the reverse order, and iterate.

Formally, let A be a real matrix of which we want to compute the eigenvalues, and let A0:=A. At the k-th step (starting with k = 0), we compute the QR decomposition Ak=QkRk where Qk is an orthogonal matrix (i.e., QT = Q−1) and Rk is an upper triangular matrix. We then form Ak+1 = RkQk. Note that

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,[4] the matrices Ak converge to a triangular matrix, the Schur form of A. The eigenvalues of a triangular matrix are listed on the diagonal, and the eigenvalue problem is solved. In testing for convergence it is impractical to require exact zeros,[citation needed] but the Gershgorin circle theorem provides a bound on the error.

In this crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix A to upper Hessenberg form (which costs 10 3 n 3 + O ( n 2 ) {\displaystyle {\begin{matrix}{\frac {10}{3}}\end{matrix}}n^{3}+{\mathcal {O}}(n^{2})} arithmetic operations using a technique based on Householder reduction), with a finite sequence of orthogonal similarity transforms, somewhat like a two-sided QR decomposition.[5][6] (For QR decomposition, the Householder reflectors are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) Determining the QR decomposition of an upper Hessenberg matrix costs 6 n 2 + O ( n ) {\displaystyle 6n^{2}+{\mathcal {O}}(n)} arithmetic operations. Moreover, because the Hessenberg form is already nearly upper-triangular (it has just one nonzero entry below each diagonal), using it as a starting point reduces the number of steps required for convergence of the QR algorithm.

Related Searches

Schur decomposition
contact us full version