16.1 The Power Method For Eigenvalues
This chapter discusses numerical methods for finding eigenvalues. However, to do this correctly, you must
include numerical analysis considerations which are distinct from linear algebra. The purpose of this
chapter is to give an introduction to some numerical methods without leaving the context of linear algebra.
In addition, some examples are given which make use of computer algebra systems. For a more thorough
discussion, you should see books on numerical methods in linear algebra like some listed in the
Let A be a complex p × p matrix and suppose that it has distinct eigenvalues
. Also let the Jordan form of A
with J1 an m1 × m1 matrix.
where Nkrk≠0 but N
krk+1 = 0. Also let
Now fix x ∈ Fp. Take Ax and let s1 be the entry of the vector Ax which has largest absolute value. Thus
Ax∕s1 is a vector y1 which has a component of 1 and every other entry of this vector has
magnitude no larger than 1. If the scalars
yn ≡ Ayn−1∕sn
is the entry of Ayn−1
which has largest absolute value.
Consider one of the blocks in the Jordan form. First consider the kth of these blocks, k > 1. It
which clearly converges to 0 as n →∞ since
. An application of the ratio test or root test for
each term in the sum will show this. When
this block is
where limn→∞en = 0 because it is a sum of bounded matrices which are multiplied by
quotient converges to 0 as n →∞
because i < r1
. It follows that 16.2
is of the form
where En → 0,en → 0. Let
denote the first m1
entries of the vector P−1x
. Unless a very
unlucky choice for x
was picked, it will follow that
Then for large n, yn
is close to
However, this is an eigenvector because
= 0. Now you could recover an approximation to the eigenvalue as follows.
Here ≈ means “approximately equal”. However, there is a more convenient way to identify the eigenvalue
in terms of the scaling factors sk.
Pick the largest nonzero entry of w, wl. Then for large n, it is also likely the case that the largest entry of
wn will be in the lth position because wm is close to w. From the construction,
In other words, for large n
Therefore, for large n,
= 1 and so, for large
it must be the case that λ1 ≈ sn+1
This has proved the following theorem which justifies the power method.
Theorem 16.1.1 Let A be a complex p × p matrix such that the eigenvalues are
for all j≠
1. Then for x a given vector, let
where s1 is an entry of Ax which has the largest absolute value. If the scalars
have been obtained, let
where sn is the entry of Ayn−1 which has largest absolute value. Then it is probably the case that
converge to λ1 and
will converge to an eigenvector associated with λ1. If it doesn’t, you picked an
incredibly inauspicious initial vector x.
In summary, here is the procedure.
Finding the largest eigenvalue with its eigenvector.
- Start with a vector, u1 which you hope is not unlucky.
- If uk is known,
where sk+1 is the entry of Auk which has largest absolute value.
- When the scaling factors sk are not changing much, sk+1 will be close to the eigenvalue and uk+1 will
be close to an eigenvector.
- Check your answer to see if it worked well. If things don’t work well, try another u1. You were
miraculously unlucky in your choice.
Example 16.1.2 Find the largest eigenvalue of A =
You can begin with u1=
and apply the above procedure. However, you can accelerate the
process if you begin with Anu1
and then divide by the largest entry to get the first approximate
Divide by the largest entry to obtain a good aproximation.
Now begin with this one.
Divide by 12 to get the next iterate.
Another iteration will reveal that the scaling factor is still 12. Thus this is an approximate eigenvalue. In
fact, it is the largest eigenvalue and the corresponding eigenvector is
The process has
worked very well.