Let A be an n´n matrix.
If there exists a number l and a non-zero vector x such that 
,
then l is
said to be an eigen-value of A, and x the corresponding eigen-vector. The evaluation of eigen-values and eigen-vectors of
matriccs is a problem that arises in a variety of contexts. Note
that if we have an eigen-value l and an eigen-vector x,
then b x, where b is any
real number, is also an eigen-vector, since
.
This shows that an eigen-vector is not unique and may be scaled, if desired (for instance, one might want the sum of the components of the eigenvector to be unity).
Writing as
we conclude from the theorem in STEP 11 that this equation can have a non-zero solution only if the determinant of |A - lI| is zero. If we expand this determinant, then we get an n-th degree polynomial in l known as the characteristic polynomial of A. Thus, one way to find the eigen-values of A is to obtain its characteristic polynomial and then to find the n zeros of this polynomial (some of them may be complex!). For example, let
.
Then
.
This last matrix has the determinant
.
The zeros of this quadratic yield the eigen-values.
Although the characteristic polynomial is easy to work out in this sirnple 2 x 2 example, as n increases, it becomes more complicated (and, of course, it has a correspondingly higher degree). Moreover, even if we can find thc characteristic polynomial, the analytic formulae for the roots of a cubic or quartic are somewhat inconvenient to use, and in any case, we must use numerical methods (cf. Steps 7-10) to find the roots of the polynomials of degree n> 4. It is therefore common to use alternative, direct numerical methods to find eigen-values and eigen-vectors of a matrix.
If we are only interested in the eigen-value of largest magnitude, then a popular approach to its evaluation is the power method. We shall discuss later on, how this method may be modified to find the eigen-value of smallest magnitude. Methods for finding all the eigen-values are beyond the scope of this book. (One such method, called the QR method, is based on QR factorization .
Suppose that the n eigen-values
of A are 
and that they are ordered in such
a way that
.
Then the method, which is readily
implemented on a computer can be used to find 
We begin with a starting vector w(0)
and compute the vectors
for j = 1, 2, . . ., so that induction yields
,
where Aj is A, multiplied by itself j times. Thus w(j) is the product of w(0) and the j-th power of A, which explains why this approach is called the power method.
It turns out that at the j-th
iteration an approximation to the eigen-vector x
associated with 
is given by the k-th
components of w(j) and w(j-1),
respectively, and an approximation to is given by
for any 
Although there
are n possible choices for k, it is usual
to choose it so that 
is the
component of w(j) with the largest
magnitude.
We will now use the power method to find the largest eigen-value of the matrix
.
As a starting vector we take
.
Since the second component of w(1)
has the largest magnitude, take k = 2 so that the
first approximation to 
is
Subsequent iterations of the power method yield
These calculations allow to conclude that the largest eigen-value is about 2.6.
In the preceding example, the reader will have noted that the components of w(j) were growing in size as j increases. Overflow problems would arise, if this growth were to continue; hence, in practice, it is usual to use instead the scaled power method. This is identical to the power method except that the vectors w(j) are scaled at each iteration. Thus, suppose w(0) be given and set y(0) = w(0). Then we will carry out for j = 1, 2, . , . the steps:
so that the p-th component of
w(j) has the largest
magnitude;
, i.e.,
for some 
.
.In Step c, there are n choices
for k. As for the unscaled power method, k is usually chosen to be the value for
which 
has the largest magnitude, i.e., k
is taken to be the value p obtained in Step b.
Another option is to choose k to be the value of p
from the previous iteration, although often this results
in the same value. The effect of Step d is to produce a
vector y(j) with components of
magnitude not more than unity.
As an example, we apply the scaled power method to the matrix in the preceding section. We take the value of k in each iteration to be p. The starting vector w(0) is the same as before and y(0) = w(0). Then the first four iterations of the scaled power method yield:
Note that the eigen-value estimates are the same as before and the w(j)s are just multiples of those obtained in the preceding section.
We shall now discuss the use of the power method to find the eigen-value 
of the smallest
magnitude. If A has an inverse, then 
may be written as
It follows that the smallest eigen-alue of A may be found by finding the largest eigen-value of A-1 and then taking the reciprocal. Thus, if the unscaled power method were used, we would calculate the vectors
In general, it is more efficient to
solve the linear system 
than to find
the inverse of A (Step 14).
It may be shown that the convergence rate of the power method is linear and that, under suitable conditions,
,
where C is some positive
constant. Thus, the bigger the gap between 
the faster the rate of convergence. Since
the power method is an iterative method, one has to stop
at some stage. It is usual to carry on the process until successive estimates of
the eigen-value agree
to a certain tolerance or, alternatively, until a given
maximum number of iterations is exceeded.
Difficulties with the
power method usually arise when our assumptions about the
eigen-values are not valid. For instance, if 
then the sequence of estimates for 
may not converge. Even if the sequence does
converge, one may not be able to get an approximation to
the eigen-vector associated with . A short
discussion of such difficulties may be found in Conte and
de Boor (1980).
apply eight iterations of the power method. Find the characteristic
polynomial, and hence find
the two true eigen-values of the matrix. Verify that the
approximations are converging to the eigen-value with the
larger magnitude.
