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

Author:
Christian H. Reinsch

Journal:
Math. Comp. **25** (1971), 591-597

MSC:
Primary 65F15

DOI:
https://doi.org/10.1090/S0025-5718-1971-0295555-4

MathSciNet review:
0295555

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 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.

**[1]**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**, https://doi.org/10.1007/BF02162154**[2]**Hilary Bowdler, R. S. Martin, C. Reinsch, and J. H. Wilkinson,*Handbook Series Linear Algebra: The 𝑄𝑅 and 𝑄𝐿 algorithms for symmetric matrices*, Numer. Math.**11**(1968), no. 4, 293–306. MR**1553961**, https://doi.org/10.1007/BF02166681**[3]**Dennis J. Mueller,*Householder’s method for complex matrices and eigensystems of hermitian matrices*, Numer. Math.**8**(1966), 72–92. MR**0192647**, https://doi.org/10.1007/BF02165240**[4]**J. G. F. Francis,*The 𝑄𝑅 transformation: a unitary analogue to the 𝐿𝑅 transformation. I*, Comput. J.**4**(1961/1962), 265–271. MR**0130111**, https://doi.org/10.1093/comjnl/4.3.265**[5]**W. Kahan,*Accurate Eigenvalues of a Symmetric Tri-Diagonal Matrix*, Technical Report #CS41, Computer Science Dept., Stanford University, Stanford, Calif., 1966.**[6]**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**, https://doi.org/10.1007/BF02161841**[7]**James M. Ortega and Henry F. Kaiser,*The 𝐿𝐿^{𝑇} and 𝑄𝑅 methods for symmetric tridiagonal matrices*, Comput. J.**6**(1963/1964), 99–101. MR**0156456**, https://doi.org/10.1093/comjnl/6.1.99**[8]**Heinz Rutishauser,*Solution of eigenvalue problems with the 𝐿𝑅-transformation*, Nat. Bur. Standards Appl. Math. Ser.**1958**(1958), no. 49, 47–81. MR**0090118****[9]**H. Rutishauser, ``Correspondence to the Editor,''*Comput. J.*, v. 6, 1963, p. 133.**[10]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[11]**J. H. Wilkinson,*Global convergence of tridiagonal 𝑄𝑅 algorithm with origin shifts*, Linear Algebra and Appl.**1**(1968), 409–420. MR**0234622**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F15

Retrieve articles in all journals with MSC: 65F15

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1971-0295555-4

Keywords:
Hermitian matrix,
symmetric matrix,
tridiagonal matrix,
all eigenvalues,
*QR* transformation

Article copyright:
© Copyright 1971
American Mathematical Society