14.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
been obtained, let
yn ≡ Ayn−1∕sn
is the entry of Ayn−1
which has largest absolute
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
This quotient converges to 0 as n →∞
because i < r1
. It follows that 14.2
is of the
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,
is close to the vector
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
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 14.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
will 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 14.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 eigenvector. Thus
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
process has worked very well.