Reduction of a band-symmetric generalized eigenvalue problem

ABSTRACT

An algorithm is described for reducing the generalized eigenvalue problem Ax = &lgr;Bx to an ordinary problem, in case A and B are symmetric band matrices with B positive definite. If n is the order of the matrix and m the bandwidth, the matrices A and B are partitioned into m-by-m blocks; and the algorithm is described in terms of these blocks. The algorithm reduces the generalized problem to an ordinary eigenvalue problem for a symmetric band matrix C whose bandwidth is the same as A and B. The algorithm is similar to those of Rutishauser and Schwartz for the reduction of symmetric matrices to band form. The calculation of C requires order n2m operation. The round-off error in the calculation of C is of the same order as the sum of the errors at each of the n/m steps of the algorithm, the latter errors being largely determined by the condition of B with respect to inversion.

REFERENCES

• 1: Martin, R. S., and Wilkinson, J. H. The generalized eigenvalue problem. SIAM J. Numer. Analysis 12 (1970).
• 2: Rutishauser, H. On Jacobi rotation patterns. Proc. Symposia in Applied Math. Vol. 15 (1963) pp. 219-239.
• 3: Schwarz, H. R. Tridiagonalization of a symmetric band matrix. Num. Math. 12 (1963), 231-241.
• 4: Householder, A. A. Tile Theory of Matrices in Numerical Analysis. Blaisdell, New York, 1964.
• 5: Crawford, C. R. The numerical solution of the generalized eigenvalue problem. Ph.D. Thesis, U. of Michigan, Ann Arbor, Mich., 1970.
• 6: Fix, G., and Heiberger, R. An algorithm for the ill-conditioned generalized eigenvalue problem. Numer. Math., 1970.
• 7: William Kahan , James M. Varah, Two working algorithms for the eigenvalues of a symmetric tridiagonal matrix, Stanford University, Stanford, CA, 1966

INDEX TERMS

Keywords:
generalized eigenvalues, symmetric band matrices