Some Perspectives on the Eigenvalue Problem
David S. Watkins · SIAM Review · 1993
This expository paper explores the relationships among a number of algorithms for solving eigenvalue problems, including the power method, subspace iteration, the $QR$ algorithm, and the Arnoldi and symmetric Lanczos algorithms. The symmetric Lanczos algorithm is shown to be identical to the three-term recursion (Stieltjes procedure) for computing orthogonal polynomials with respect to a measure on the real line. The connection between measures on the line and symmetric tridiagonal (Jacobi) matrices is investigated. If such a matrix is transformed by a step of the $QR$ algorithm, there is a corresponding transformation in the measure. The tridiagonal matrices are also exploited for the construction of Gaussian quadrature formulas for measures on the line. The developments on the real line are replicated with suitable modifications on the unit circle via Lanczos-like procedures for unitary operators. The best-known procedure of this type is the recursion of Szego for computing orthogonal polynomials on the unit circle. The approach taken in this paper is to develop recursions that compute orthogonal Laurent polynomials (rational functions) rather than polynomials. These recursions are then modified to yield the Szegö recursion.