Chapter 15

Numerical Methods, Eigenvalues15.1 The Power Method For Eigenvalues

This chapter presents some simple ways to find eigenvalues and eigenvectors. It is only anintroduction to this important subject. However, I hope to convey some of the ideas whichare used. As indicated earlier, the eigenvalue eigenvector problem is extremely difficult.Consider for example what happens if you find an eigenvalue approximately. Then youcan’t find an approximate eigenvector by the straight forward approach because A−λ I isinvertible whenever λ is not exactly equal to an eigenvalue.

Of course computer algebra systems allow you to ask for eigenvalues and eigenvectorsand get the answer with no effort. This chapter is going to describe some of the ideas whichlead to software which is able to give such answers.

The power method allows you to approximate the largest eigenvalue and also the eigen-vector which goes with it. By considering the inverse of the matrix, you can also find thesmallest eigenvalue. The method works in the situation of a nondefective matrix A whichhas a real eigenvalue of algebraic multiplicity 1, λ n which has the property that |λ k|< |λ n|for all k ̸= n. Such an eigenvalue is called a dominant eigenvalue.

Let {x1, · · · ,xn} be a basis of eigenvectors for Fn such that Axn = λ nxn. Now let u1 besome nonzero vector. Since {x1, · · · ,xn} is a basis, there exists unique scalars, ci such that

u1 =n

∑k=1

ckxk.

Assume you have not been so unlucky as to pick u1 in such a way that cn = 0. Then letAuk = uk+1 so that

um = Amu1 =n−1

∑k=1

ckλmk xk +λ

mn cnxn. (15.1)

For large m the last term, λmn cnxn, determines quite well the direction of the vector on the

right. This is because |λ n| is larger than |λ k| for k < n and so for a large m, the sum,∑

n−1k=1 ckλ

mk xk, on the right is fairly insignificant. Therefore, for large m, um is essentially a

multiple of the eigenvector xn, the one which goes with λ n. The only problem is that thereis no control of the size of the vectors um. You can fix this by scaling. Let S2 denote theentry of Au1 which is largest in absolute value. We call this a scaling factor. Then u2 willnot be just Au1 but Au1/S2. Next let S3 denote the entry of Au2 which has largest absolutevalue and define u3 ≡ Au2/S3. Continue this way. The scaling just described does notdestroy the relative insignificance of the term involving a sum in 15.1. Indeed it amounts tonothing more than changing the units of length. Also note that from this scaling procedure,the absolute value of the largest element of uk is always equal to 1. Therefore, for large m,

um =λ

mn cnxn

S2S3 · · ·Sm+(relatively insignificant term) .

Therefore, the entry of Aum which has the largest absolute value is essentially equal to theentry having largest absolute value of

A(

λmn cnxn

S2S3 · · ·Sm

)=

λm+1n cnxn

S2S3 · · ·Sm≊ λ num

347