15.2. THE SHIFTED INVERSE POWER METHOD 351

where Ek→ 0, y is some eigenvector for λ n, and Ck is of moderate size, remaining boundedas k→ ∞ due to the fact that from the construction, uk+1 has all entries no larger than 1.Therefore, for large k, and letting ≊ denote “approximately equal”,

uk+1−Cky =CkEk ≊ 0

and multiplying by (A−αI)−1 yields

(A−αI)−1 uk+1− (A−αI)−1 Cky = (A−αI)−1 uk+1−Ck

(1

λ n−α

)y

≊ (A−αI)−1 uk+1−(

1λ n−α

)uk+1 ≊ 0.

Therefore, for large k, uk is approximately equal to an eigenvector of (A−αI)−1. There-fore,

(A−αI)−1 uk ≊1

λ n−αuk

and so you could take the dot product of both sides with uk and approximate λ n by solvingthe following for λ n.

(A−αI)−1 uk ·uk

|uk|2=

1λ n−α

How else can you find the eigenvalue from this? Suppose uk = (w1, · · · ,wn)T and from

the construction |wi| ≤ 1 and wk = 1 for some k. Then

Sk+1uk+1 = (A−αI)−1 uk ≊ (A−αI)−1 (Ck−1y)=1

λ n−α(Ck−1y)≊

1λ n−α

uk.

Hence the entry of (A−αI)−1 uk which has largest absolute value is approximately 1λ n−α

and so it is likely that you can estimate λ n using the formula

Sk+1 =1

λ n−α.

Of course this would fail if (A−αI)−1 uk had consistently more than one entry havingequal absolute value, but this is unlikely.

Here is how you use the shifted inverse power method to find the eigenvalue andeigenvector closest to α.

1. Find (A−αI)−1 .

2. Pick u1. It is important that u1 = ∑mj=1 a jx j +y where y is an eigenvector which goes

with the eigenvalue closest to α and the sum is in an “invariant subspace correspond-ing to the other eigenvalues”. Of course you have no way of knowing whether thisis so but it typically is so. If things don’t work out, just start with a different u1. Youwere phenomenally unlucky in your choice.

3. If uk has been obtained,

uk+1 =(A−αI)−1 uk

Sk+1

where Sk+1 is the element of (A−αI)−1 uk which has largest absolute value.