TABLE OF CONTENTS In this chapter we discuss iterative methods for finding eigenvalues of matrices that are too large to use the direct methods of Chapters 4 and 5. In other words, we seek algorithms that take far less than O( n 2) storage and O( n 3) flops. Since the eigenvectors of most n-by- n matrices would take n 2 storage to represent, this means that we seek algorithms that compute just a few user-selected eigenvalues and eigenvectors of a matrix.
We will depend on the material on Krylov subspace methods developed in section 6.6, the material on symmetric eigenvalue problems in section 5.2, and the material on the power method and inverse iteration in section 5.3. The reader is advised to review these sections.
The simplest eigenvalue problem is to compute just the largest eigenvalue in absolute value, along with its eigenvector. The power method (Algorithm 4.1) is the simplest algorithm suitable for this task: Recall that its inner loop is
where x i converges to the eigenvector corresponding to the desired eigenvector (provided that there is only one eigenvalue of largest absolute value, and x i does not lie in an invariant subspace not containing its eigenvector). Note that the algorithm uses A only to perform matrix-vector multiplication, so all that we need to run the algorithm is a "black-box" that takes x i as input and returns Ax i as output (see Example 6.13).
A closely related...
