Two New Classes of Algorithms for Finding the Eigenvalues and Eigenvectors of Real Symmetric Matrices

ABSTRACT

The algorithms described in this paper are essentially Jacobi-like iterative procedures employing Householder orthogonal similarity transformations and Jacobi orthogonal similarity transformations to reduce a real symmetrix matrix to diagonal form. The convergence of the first class of algorithms depends upon the fact that the algebraic value of one diagonal element is increased at each step in the iteration and the convergence of the second class of algorithms depends upon the fact that the absolute value of one off-diagonal element is increased at each step in the iteration. Then it is shown how it is possible to combine one algorithm from each class together into a “mixed” strategy for diagonalizing a real symmetric matrix.

REFERENCES

• 1: FoRsYTHE, G. E., AND HENRICI, P. The cyclic Jcobi method for computing The principal vIues of complex matrix. Trans. Amer. Soc. S (1960), 1-23.
• 2: GIVENS, W. Numerical eonputtion of the eharcteristic vlues of a real symmetric nzatrix. Oak Ridge Nat. Lb. Report, ORNL 1574 Ok tdge, Tenn., 1954.
• 3: HOUSEHOLDER, A. S., AND BAUEI , L. On certain nethods for expanding the elmracteristie polynomial. Numer. Math. I (1959), 29-37.
• 4: LA BUUDE, C. D. A new a}gerithm for diagoulizing a real symmetric matrix. Math, Comput. (to appear).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Performance, Theory, Verification