Page 115 - Compact Numerical Methods For Computers

104 Compact numerical methods for computers
eventually introduce a component in the right direction’. However, if the matrix
A has elements which can be represented exactly within the machine, that is, if A
can be scaled so that all elements are integers small enough to fit in one machine
word, it is quite likely that rounding errors in the ‘right direction’ will not occur.
Certainly such matrices arise often enough to warrant caution in choosing a
starting vector. Acton (1970) and Ralston (1965) discuss the power method in
more detail.
The power method is a simple, yet highly effective, tool for finding the extreme
eigensolutions of a matrix. However, by applying it with the inverse of the shifted
matrix A' (9.9) an algorithm is obtained which permits all distinct eigensolutions
to be determined. The iteration does not, of course, use an explicit inverse, but
solves the linear equations
A'y = x i (9.10a)
i

then normalises the solution by
x i+l = y /||y ||. (9.10b)
i
i
Note that the solution of a set of simultaneous linear equations must be found at
each iteration.
While the power method is only applicable to the matrix eigenproblem (2.62),
inverse iteration is useful for solving the generalised eigenproblem (2.63) using
A' = A – kB (9.11)
in place of (9.9). The iteration scheme is now
A'y = Bx i (9.12a)
i
x = y /||y ||. (9.12b)
i+1 i i
Once again, the purpose of the normalisation of y in (9.1b), (9.10b) and (9.12b) is
simply to prevent overflow in subsequent calculations (9.1a), (9.10a) or (9.12a).
The end use of the eigenvector must determine the way in which it is standard-
ised. In particular, for the generalised eigenproblem (2.63), it is likely that x
should be normalised so that
T
x Bx = 1. (9.13)
Such a calculation is quite tedious at each iteration and should not be performed
until convergence has been obtained, since a much simpler norm will suffice, for
instance the infinity norm

(9.14)

where y j is the jth element of y. On convergence of the algorithm, the eigenvalue
is
(9.14)
e = k + x /y j
j
(where the absolute value is not used).
Inverse iteration works by the following mechanism. Once again expand x as
1