Shifted Inverse Power Method for Closest Eigenvalue

Welcome to our final lesson in this module on the Power Method. So far, we've learned how to find the largest eigenvalue using the standard Power Method and the smallest eigenvalue using the Inverse Power Method. This leaves an important question: how can we find an eigenvalue that isn't at either extreme, but is instead close to a specific value we're interested in?

Today, we will address this by combining the techniques from our previous lessons. We will explore the Shifted Inverse Power Method, a versatile algorithm that allows you to find the eigenvalue of a matrix closest to any given scalar, $α$ . This method is a powerful tool that effectively allows us to "zoom in" on any part of a matrix's eigenvalue spectrum.

The Core Idea: Shifting and Inverting

The logic behind this method is a beautiful combination of two simple ideas you're already familiar with.

First, let's consider the effect of "shifting" a matrix. If we have a matrix $A$ with an eigenpair $(λ, v)$ such that $A v = λ v$ , what happens if we subtract $α I$ from $A$ , where $α$ is some scalar and $I$ is the identity matrix?

(A - α I) v = A v - α I v = λ v - α v = (λ - α) v

The new matrix, $A - α I$ , has the same eigenvector $v$ , but its corresponding eigenvalue is now $λ - α$ . In other words, shifting the matrix simply shifts all its eigenvalues by $α$ .

Second, we recall the principle of the Inverse Power Method: the eigenvalues of an inverse matrix $B^{- 1}$ are the reciprocals of the eigenvalues of $B$ .

Now, let's put these two ideas together. We start with matrix $A$ and shift it by $α$ to get $B = A - α I$ . The eigenvalues of $B$ are $(λ_{i} - α)$ for all eigenvalues $λ_{i}$ of $A$ . If we then take the inverse of $B$ , the resulting matrix, $B^{- 1} = (A - α I)^{- 1}$ , will have eigenvalues equal to $1/ (λ_{i} - α)$ .

This is where the magic happens. Suppose we choose our shift, $α$ , to be very close to a specific eigenvalue of $A$ , let's call it $λ_{j}$ . The term $λ_{j} - α$ will then be very small. Consequently, its reciprocal, $1/ (λ_{j} - α)$ , will be very large. This means that for the shifted inverse matrix, $(A - α I)^{- 1}$ , the eigenvalue corresponding to $λ_{j}$ will be the dominant one!

The following video provides an excellent derivation and visual explanation of this exact concept.

8: Shifted Inverse Power Method - Learning Linear Algebra

This video from the Mu Prime Math channel walks through the derivation of the Shifted Inverse Power Method and explains the core intuition behind why it works.

First, watch the section that derives the key relationship between the eigenvalues of the original matrix and the shifted inverse matrix, from the derivation. Next, focus on the crucial part of the video that explains how this relationship allows us to make any eigenvalue dominant. Pay close attention to the graph shown, which visualizes how choosing an \alpha close to a \lambda makes the new eigenvalue huge (the core idea).

The Shifted Inverse Power Method Algorithm

Having established the principle, the algorithm itself is a straightforward application of the Power Method to our new, cleverly constructed matrix.

Choose a Shift: Select a scalar $α$ that is an approximation of the eigenvalue you want to find.
Form the Shifted Matrix: Construct the matrix $B = A - α I$ .
Apply the Power Method to $B^{- 1}$ : This is the "Inverse Power Method" step.
- Choose an initial non-zero vector $x^{(0)}$ .
- For $k = 1, 2, \dots$ , perform the iteration:
  a. Calculate $y^{(k)} = B^{- 1} x^{(k - 1)}$ . As a practical matter, it is more efficient to solve the linear system $B y^{(k)} = x^{(k - 1)}$ for $y^{(k)}$ rather than explicitly computing $B^{- 1}$ .
  b. Find the element of $y^{(k)}$ with the largest absolute value. Let this be $σ^{(k)}$ . This is our estimate for the dominant eigenvalue of $B^{- 1}$ .
  c. Update the vector: $x^{(k)} = \frac{1}{σ ^{(k)}} y^{(k)}$ .
Convergence: As $k$ increases, $x^{(k)}$ converges to the eigenvector $v_{j}$ of $A$ that corresponds to the eigenvalue $λ_{j}$ closest to $α$ . The value $σ^{(k)}$ converges to $σ_{d o m} = 1/ (λ_{j} - α)$ .
Recover the Eigenvalue: Once the process has converged to a stable $σ$ and $v$ , you can find the original eigenvalue $λ_{j}$ by rearranging the relationship from step 4:
$λ_{j} = \frac{1}{σ} + α$

The following reading formally states this proposition and provides a concise summary.

9.3. The power method — Linear algebra - Interactive textbooks

The interactive textbook from TU Delft provides a formal proposition for the Shifted Inverse Power Method, which neatly summarizes the algorithm we've just discussed.

Please read the short section titled Shifted Inverse Power Method. Focus on Proposition 9.3.4, which encapsulates the entire method.

A Worked Example

Now, let's look at how this process works in practice with a hand-calculation example, similar to what you might encounter in an exam. The Wikiversity resource provides a very detailed walkthrough.

Shifted inverse iteration - Wikiversity

This resource demonstrates the method with a 3x3 matrix, targeting the eigenvalue \lambda=4 by using a shift \alpha = 4.2.

In the "Example" section, follow the calculation for "Case 1". Read from the sentence "For the eigenvalue..." down to where the first updated vector, X_1, is calculated. Pay attention to these key steps: The shifted matrix (A - 4.2I) is constructed. The first iteration is not performed by finding the inverse, but by solving the system of equations (A - 4.2I)Y_0 = X_0. This is the practical application of the method. The resulting vector Y_0 is then normalized to get X_1. Note that this example normalizes using the vector norm, but the principle is the same as normalizing by the largest component, which you are used to.

This example shows the concrete computational steps. You would continue this iterative process of solving the system and re-normalizing until the vector $x^{(k)}$ and the scaling factor $σ^{(k)}$ stabilize. Once they do, you use the final formula $λ = 1/ σ + α$ to get your answer.

Conclusion

In this lesson, we have completed our tour of the power method and its variants. By combining a matrix shift with the inverse power method, we have unlocked a technique to find any eigenvalue in a matrix's spectrum, provided we have a reasonable starting guess.

The key takeaways are:

Shifting: The matrix $A - α I$ has eigenvalues $λ_{i} - α$ .
Inverting: The matrix $(A - α I)^{- 1}$ has eigenvalues $1/ (λ_{i} - α)$ .
Targeting: Choosing $α$ close to an eigenvalue $λ_{j}$ makes $1/ (λ_{j} - α)$ the dominant eigenvalue of the shifted inverse matrix.
Recovering: After finding the dominant eigenvalue $σ$ of $(A - α I)^{- 1}$ using the Power Method, the original eigenvalue is recovered with the formula $λ_{j} = 1/ σ + α$ .

This concludes our module on iterative methods for finding eigenvalues. While powerful, these methods can be slow for large matrices. A common strategy in numerical linear algebra is to first transform a matrix into a much simpler form. In our next module, we will begin exploring this by learning how to reduce a symmetric matrix to a tridiagonal form using Householder transformations.

Recommended resources

The Core Idea: Shifting and Inverting

The Shifted Inverse Power Method Algorithm

A Worked Example

Conclusion