A stable, rational QR algorithm for the computation of the eigenvalues of an Hermitian, tridiagonal matrix
Christian H. Reinsch · Mathematics of Computation · 1971
The most efficient program for finding all the eigenvalues of a symmetric matrix is a combination of the Householder tridiagonalization and the QR algorithm. The latter, if carried out in a natural way, requires 4 n additions, 10 n multiplications, 2 n divisions, and n square roots per iteration ( n the order of the matrix). In 1963, Ortega and Kaiser showed that the process can be carried out using no square roots (and saving 7 n multiplications). However, their algorithm is unstable and several modifications were suggested to increase its accuracy. We, too, want to give such a modification together with some examples demonstrating the achieved accuracy.