QR algorithm

In numerical linear algebra, the QR algorithm is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in the late 1950s by John G.F. Francis (England) and by Vera N. Kublanovskaya (USSR), working independently. 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 A₀:=A. At the k-th step (starting with k = 0), we compute the QR decomposition A_k=Q_kR_k where Q_k is an orthogonal matrix (i.e., Q^T = Q⁻¹) and R_k is an upper triangular matrix. We then 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, the matrices A_k 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, but the Gershgorin circle theorem provides a bound on the error.

...
Wikipedia