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. 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_k R_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_k Q_k. Note that $${\displaystyle A_{k+1}=R_{k}Q_{k}=Q_{k}^{-1}Q_{k}R_{k}Q_{k}=Q_{k}^{-1}A_{k}Q_{k}=Q_{k}^{\mathsf {T}}A_{k}Q_{k},}$$ 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,^{[citation needed]} but the Gershgorin circle theorem provides a bound on the error.

If the matrices converge, then the eigenvalues along the diagonal will appear according to their geometric multiplicity. To guarantee convergence, A must be a symmetric matrix, and for all non zero eigenvalues ${\displaystyle \lambda }$ there must not be a corresponding eigenvalue ${\displaystyle -\lambda }$. Due to the fact that a single QR iteration has a cost of ${\displaystyle {\mathcal {O}}(n^{3})}$ and the convergence is linear, the standard QR algorithm is extremely expensive to compute, especially considering it is not guaranteed to converge.

In the above crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix A to upper Hessenberg form (which costs ${\textstyle {\tfrac {10}{3}}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. (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 ${\textstyle 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.

If the original matrix is symmetric, then the upper Hessenberg matrix is also symmetric and thus tridiagonal, and so are all the A_k. In this case reaching Hessenberg form costs ${\textstyle {\tfrac {4}{3}}n^{3}+{\mathcal {O}}(n^{2})}$ arithmetic operations using a technique based on Householder reduction. Determining the QR decomposition of a symmetric tridiagonal matrix costs ${\displaystyle {\mathcal {O}}(n)}$ operations.

If a Hessenberg matrix ${\displaystyle A}$ has element ${\displaystyle a_{k,k-1}=0}$ for some ${\displaystyle k}$, i.e., if one of the elements just below the diagonal is in fact zero, then it decomposes into blocks whose eigenproblems may be solved separately; an eigenvalue is either an eigenvalue of the submatrix of the first ${\displaystyle k-1}$ rows and columns, or an eigenvalue of the submatrix of remaining rows and columns. The purpose of the QR iteration step is to shrink one of these ${\displaystyle a_{k,k-1}}$ elements so that effectively a small block along the diagonal is split off from the bulk of the matrix. In the case of a real eigenvalue that is usually the ${\displaystyle 1\times 1}$ block in the lower right corner (in which case element ${\displaystyle a_{nn}}$ holds that eigenvalue), whereas in the case of a pair of conjugate complex eigenvalues it is the ${\displaystyle 2\times 2}$ block in the lower right corner.

The rate of convergence depends on the separation between eigenvalues, so a practical algorithm will use shifts, either explicit or implicit, to increase separation and accelerate convergence. A typical symmetric QR algorithm isolates each eigenvalue (then reduces the size of the matrix) with only one or two iterations, making it efficient as well as robust.^{[clarification needed]}