Page 113 - Compact Numerical Methods For Computers

Chapter 9

THE ALGEBRAIC EIGENVALUE PROBLEM

9.1. INTRODUCTION

The next three chapters are concerned with the solution of algebraic eigen-
value problems
Ax = ex (2.62)
and
Ax = eBx. (2.63)
The treatment of these problems will be highly selective, and only methods which
I feel are particularly suitable for small computers will be considered. The reader
interested in other methods is referred to Wilkinson (1965) and Wilkinson and
Reinsch (1971) for an introduction to the very large literature on methods for the
algebraic eigenproblem. Here I have concentrated on providing methods which
are reliable and easy to implement for matrices which can be stored in the
computer main memory, except for a short discussion in chapter 19 of two methods
suitable for sparse matrices. The methods have also been chosen to fit in with
ideas already developed so the reader should not feel on too unfamiliar ground.
Thus it is possible, even likely, that better methods exist for most applications and
any user should be aware of this. Section 10.5 discusses some of the possible
methods for real symmetric methods.

9.2. THE POWER METHOD AND INVERSE ITERATION
One of the simplest methods for finding the eigenvalue of largest magnitude of a
matrix A with its associated eigenvector is to iterate using the scheme

y = Ax i (9.1a)
i
x i+1 = y /|| y || (9.1b)
i
i
from some starting vector x until successive x i are identical. The eigenvector is
1
then given by x and the magnitude of the eigenvalue by ||y|| where || || represents
any vector norm. The simplicity of this algorithm and its requirement for only a
matrix-vector product makes it especially suitable for small computers, though
convergence may at times be very slow.
The method works as follows. Consider the expansion of x 1 in terms of the
f
eigenvectors f , j = 1, 2, . . . n, which span the space. This may not be possible for
j
non-symmetric matrices. However, the algorithm is generally less useful for such
matrices and will not be considered further in this context. Wilkinson (1965, chap
9) has a good discussion of the difficulties. Therefore, returning to the expansion
102