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
references.
Let A be a complex p × p matrix and suppose that it has distinct eigenvalues
{λ1,⋅⋅⋅,λm }
and that
|λ1|
>
|λk|
for all k. Also let the Jordan form of A be
( )
| J1 |
J = |( ... |)
Jm
with J_{1} an m_{1}× m_{1} matrix.
Jk = λkIk + Nk
where N_{k}^{rk}≠0 but N_{
k}^{rk+1} = 0. Also let
P− 1AP = J,A = PJP −1.
Now fix x ∈ F^{p}. Take Ax and let s_{1} be the entry of the vector Ax which has largest absolute
value. Thus Ax∕s_{1} is a vector y_{1} which has a component of 1 and every other entry of this vector
has magnitude no larger than 1. If the scalars
{s1,⋅⋅⋅,sn−1}
and vectors
{y1,⋅⋅⋅,yn− 1}
have
been obtained, let y_{n}≡ Ay_{n−1}∕s_{n} where s_{n} is the entry of Ay_{n−1} which has largest absolute
value. Thus
y = AAyn−-2⋅⋅⋅ =---Anx----- (14.1)
n snsn−1 snsn−1⋅⋅⋅s1
(14.1)
( Jn )
1 | 1 . | −1
= s-s---⋅⋅⋅s-P |( .. |) P x
n n−1 1 Jnm
( − n n )
n | λ1 J1 |
= ----λ-1----P | ... | P−1x (14.2)
snsn−1⋅⋅⋅s1 ( −n n )
λ1 Jm
Consider one of the blocks in the Jordan form. First consider the k^{th} of these blocks, k > 1. It
equals
∑rk( )
λ−1 nJnk = n λ−1 nλnk−iNik
i=0 i
which clearly converges to 0 as n →∞ since
|λ1|
>
|λk|
. An application of the ratio test or root
test for each term in the sum will show this. When k = 1, this block is
( ) ( )
−n n −n n ∑r1 n −n n−i i n [ −r1 r1 ]
λ1 J1 = λ1 Jk = i λ1 λ1 N 1 = r1 λ1 N1 + en
i=0
where lim_{n→∞}e_{n} = 0 because it is a sum of bounded matrices which are multiplied by
(n)
i
∕
(n)
r1
.
This quotient converges to 0 as n →∞ because i < r_{1}. It follows that 14.2 is of the
form
λn ( n) ( λ−r1Nr1+ e 0 ) λn ( n)
yn = ------1---- P 1 1 n P −1x ≡-----1----- wn
snsn−1⋅⋅⋅s1 r1 0 En snsn−1⋅⋅⋅s1 r1
where E_{n}→ 0,e_{n}→ 0. Let
( )
P−1x
_{m1} denote the first m_{1} entries of the vector P^{−1}x. Unless a
very unlucky choice for x was picked, it will follow that
( )
P− 1x
_{m1}
∕∈
ker
(N r11 )
. Then for large n,y_{n} is close to the vector
n ( ) ( − r1 r1 ) n ( )
----λ1----- n P λ1 N 1 0 P− 1x ≡----λ1----- n w ≡ z ⁄= 0
snsn−1⋅⋅⋅s1 r1 0 0 snsn−1⋅⋅⋅s1 r1
( ) ( −r r )
| N1 | | λ1 1N 11 |
P|( ... |) P −1P |( ... |) P −1x
( Jm − λ)1I 0
N1λ−1 r1N r11 0 −1
= P 0 0 P x = 0
Recall N_{1}^{r1+1} = 0. Now you could recover an approximation to the eigenvalue as follows.
(Ayn,yn)-≈ (Az,z) = λ
(yn,yn ) (z,z) 1
Here ≈ means “approximately equal”. However, there is a more convenient way to identify the
eigenvalue in terms of the scaling factors s_{k}.
∥ n ( ) ∥
∥∥---λ1-- n (wn − w)∥∥ ≈ 0
∥sn ⋅⋅⋅s1 r1 ∥∞
Pick the largest nonzero entry of w,w_{l}. Then for large n, it is also likely the case that the
largest entry of w_{n} will be in the l^{th} position because w_{m} is close to w. From the
construction,
= 1 and so, for large n it must be the case that λ_{1}≈ s_{n+1}.
This has proved the following theorem which justifies the power method.
Theorem 14.1.1Let A be a complex p × p matrix such that the eigenvalues are
{λ1,λ2,⋅⋅⋅,λr}
with
|λ1|
>
|λj|
for all j≠1. Then for x a given vector, let
Ax
y1 = s--
1
where s_{1}is an entry of Ax which has the largest absolute value. If the scalars
{s1,⋅⋅⋅,sn−1}
andvectors
{y1,⋅⋅⋅,yn−1}
have been obtained, let
Ayn-−1
yn ≡ sn
where s_{n}is the entry of Ay_{n−1}which haslargest absolute value. Then it is probably the case that
{sn}
will converge to λ_{1}and
{yn}
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, u_{1} which you hope is not unlucky.
If u_{k} is known,
uk+1 = Auk-
sk+1
where s_{k+1} is the entry of Au_{k} which has largest absolute value.
When the scaling factors s_{k} are not changing much, s_{k+1} will be close to the eigenvalue and
u_{k+1} will be close to an eigenvector.
Check your answer to see if it worked well. If things don’t work well, try another u_{1}. You
were miraculously unlucky in your choice.
Example 14.1.2Find the largest eigenvalue of A =
( )
5 − 14 11
|( − 4 4 − 4 |)
3 6 − 3
.
You can begin with u_{1}=
(1,⋅⋅⋅,1)
^{T} and apply the above procedure. However, you can
accelerate the process if you begin with A^{n}u_{1} and then divide by the largest entry to get the first
approximate eigenvector. Thus
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