Linear Algebra and Analysis

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 references.

Let A be a complex p × p matrix and suppose that it has distinct eigenvalues

{λ1,⋅⋅⋅,λm}

and that

> for all k. Also let the Jordan form of A be

( ) | J1 | J = |( ... |) J m

with J₁ an m₁ × m₁ matrix.

Jk = λkIk + Nk

where N_k^r_k≠0 but N _k^r_k+1 = 0. Also let

−1 − 1 P AP = J,A = P JP .

Now fix x ∈ F^p. Take Ax and let s₁ be the entry of the vector Ax which has largest absolute value. Thus Ax∕s₁ is a vector y₁ which has a component of 1 and every other entry of this vector has magnitude no larger than 1. If the scalars

and vectors 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

AAy Anx yn = ----n−2 ⋅⋅⋅ = ----------- (16.1) snsn− 1 snsn−1 ⋅⋅⋅s1

(16.1)

Consider one of the blocks in the Jordan form. First consider the k^th of these blocks, k > 1. It equals

rk ( ) λ−nJn = ∑ n λ−nλn−iN i 1 k i=0 i 1 k k

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 k = 1, this block is

( ) ( ) − n n −n n r∑1 n −n n−i i n [− r1 r1 ] λ1 J1 = λ 1 Jk = i λ1 λ1 N1 = r1 λ1 N 1 + en i=0

where lim_n→∞e_n = 0 because it is a sum of bounded matrices which are multiplied by

∕. This quotient converges to 0 as n →∞ because i < r₁. It follows that 16.2 is of the form

λn ( n ) ( λ− r1N r1+ 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

_m1 denote the first m₁ entries of the vector P⁻¹x. Unless a very unlucky choice for x was picked, it will follow that _m1ker. Then for large n, y_n is close to the vector

( ) ( −r r ) ( ) ----λn1----- n P λ1 1N11 0 P −1x ≡----λn1---- n w ≡ z ⁄= 0 snsn−1⋅⋅⋅s1 r1 0 0 snsn−1⋅⋅⋅s1 r1

However, this is an eigenvector because

A−λ1I ( ) ◜-----◞◟----−◝1 λ−1 r1N r11 0 −1 (A− λ1I)w = P (J − λ1I)P P 0 0 P x =

Recall N₁^r₁+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.

∥ ( ) ∥ ∥∥--λn1--- n (w − w )∥∥ ≈ 0 ∥sn⋅⋅⋅s1 r1 n ∥ ∞

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,

n ( ) n ( ) ---λ1-- n wnl = 1 ≈--λ1--- n wl sn ⋅⋅⋅s1 r1 sn⋅⋅⋅s1 r1

In other words, for large n

n ( ) ---λ1-- n ≈ 1∕wl sn ⋅⋅⋅s1 r1

Therefore, for large n,

( ) ( ) --λn1-- n ---λn+11---- n + 1 sn⋅⋅⋅s1 r1 ≈ sn+1sn⋅⋅⋅s1 r1

and so

( ) ( ) n ∕ n + 1 ≈ -λ1- r1 r1 sn+1

But lim_n→∞

∕ = 1 and so, for large n it must be the case that λ₁ ≈ s_n+1.

This has proved the following theorem which justifies the power method.

In summary, here is the procedure.

1. Start with a vector, u₁ which you hope is not unlucky.
2. If u_k is known,

   Au uk+1 = ---k sk+1

   where s_k+1 is the entry of Au_k which has largest absolute value.

3. 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.
4. Check your answer to see if it worked well. If things don’t work well, try another u₁. You were miraculously unlucky in your choice.

You can begin with u₁=

^T and apply the above procedure. However, you can accelerate the process if you begin with Aⁿu₁ and then divide by the largest entry to get the first approximate eigenvector. Thus

( ) ( ) ( ) 5 − 14 11 20 1 2.5558× 1021 |( − 4 4 − 4 |) |( 1 |) = |( − 1.2779 × 1021 |) 15 3 6 − 3 1 − 3.6562 × 10

Divide by the largest entry to obtain a good aproximation.

( 21 ) ( ) | 2.5558 × 10 | 1 | 1.0 | ( − 1.2779× 1021 ) 2.5558-×-1021-= ( − 0.5 ) − 3.6562× 1015 − 1.4306 × 10−6

Now begin with this one.

( ) ( ) ( ) | 5 − 14 11 | | 1.0 | | 12.000 | ( − 4 4 − 4 ) ( − 0.5 ) = ( − 6.0000 ) 3 6 − 3 − 1.4306 × 10−6 4.2918× 10−6

Divide by 12 to get the next iterate.

( ) ( ) 12.000 1.0 |( − 6.0000 |) 1- = |( − 0.5 |) 4.2918 × 10−6 12 3.5765 × 10−7

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.