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.