A stable, rational QR algorithm for the computation of the eigenvalues of an Hermitian, tridiagonal matrix

Reinsch, Christian H.

doi:10.1090/S0025-5718-1971-0295555-4

A stable, rational QR algorithm for the computation of the eigenvalues of an Hermitian, tridiagonal matrix
HTML articles powered by AMS MathViewer

by Christian H. Reinsch PDF

Math. Comp. 25 (1971), 591-597 Request permission

Abstract:

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 4n additions, 10n multiplications, 2n 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 7n 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.

References

W. Barth, R. S. Martin, and J. H. Wilkinson, Handbook Series Linear Algebra: Calculation of the eigenvalues of a symmetric tridiagonal matrix by the method of bisection, Numer. Math. 9 (1967), no. 5, 386–393. MR 1553954, DOI 10.1007/BF02162154
Hilary Bowdler, R. S. Martin, C. Reinsch, and J. H. Wilkinson, Handbook Series Linear Algebra: The $QR$ and $QL$ algorithms for symmetric matrices, Numer. Math. 11 (1968), no. 4, 293–306. MR 1553961, DOI 10.1007/BF02166681
Dennis J. Mueller, Householder’s method for complex matrices and eigensystems of hermitian matrices, Numer. Math. 8 (1966), 72–92. MR 192647, DOI 10.1007/BF02165240
J. G. F. Francis, The $QR$ transformation: a unitary analogue to the $LR$ transformation. I, Comput. J. 4 (1961/62), 265–271. MR 130111, DOI 10.1093/comjnl/4.3.265

Accurate Eigenvalues of a Symmetric Tri-Diagonal Matrix

R. S. Martin, C. Reinsch, and J. H. Wilkinson, Handbook Series Linear Algebra: Householder’s tridiagonalization of a symmetric matrix, Numer. Math. 11 (1968), no. 3, 181–195. MR 1553959, DOI 10.1007/BF02161841
James M. Ortega and Henry F. Kaiser, The $LL^{T}$ and $QR$ methods for symmetric tridiagonal matrices, Comput. J. 6 (1963/64), 99–101. MR 156456, DOI 10.1093/comjnl/6.1.99
Heinz Rutishauser, Solution of eigenvalue problems with the $LR$-transformation, Nat. Bur. Standards Appl. Math. Ser. 1958 (1958), no. 49, 47–81. MR 90118

Comput. J.

J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
J. H. Wilkinson, Global convergence of tridiagonal $\textrm {QR}$ algorithm with origin shifts, Linear Algebra Appl. 1 (1968), 409–420. MR 234622, DOI 10.1016/0024-3795(68)90017-7