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 W. Kahan, Accurate Eigenvalues of a Symmetric Tri-Diagonal Matrix, Technical Report #CS41, Computer Science Dept., Stanford University, Stanford, Calif., 1966.
- 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 H. Rutishauser, “Correspondence to the Editor,” Comput. J., v. 6, 1963, p. 133.
- 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
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Math. Comp. 25 (1971), 591-597
- MSC: Primary 65F15
- DOI: https://doi.org/10.1090/S0025-5718-1971-0295555-4
- MathSciNet review: 0295555