Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 37 ยท Optimization and Eigenvalues

Eigenvalues: Power Iteration and Inverse Iteration

Compute dominant and smallest eigenvalues of a matrix with the power method, Rayleigh quotient, shifts and inverse iteration. Includes a PageRank-style example.

An eigenvector of a square matrix A is a nonzero vector v whose direction does not change when A multiplies it: A v = lambda v. The number lambda is the eigenvalue. Eigenvalues describe vibration frequencies, stability of dynamical systems, principal components of data and the long-run behaviour of Markov chains (including Google's original PageRank).

You were probably taught to find eigenvalues as roots of the characteristic polynomial det(A - lambda I) = 0. That is unusable numerically: for larger matrices it is hopelessly ill-conditioned and slow. Real algorithms are iterative. We start with the simplest, the power method, then see how shifts and inversion reach any eigenvalue we want.

The power method

Take a random starting vector x. Repeatedly multiply by A and normalize:

y = A x, x = y / |y|

Why it works: write the starting vector as a combination of eigenvectors, x0 = c1 v1 + c2 v2 + .... After k multiplications the i-th component is multiplied by lambda_i^k. The eigenvalue largest in magnitude, lambda_1, wins, so x turns toward v1. The convergence rate is the ratio |lambda_2 / lambda_1| per step: a close second eigenvalue means slow convergence.

The eigenvalue estimate is the Rayleigh quotient lambda ~ x^T A x / x^T x, which is quadratically accurate for symmetric matrices (if x has error epsilon, lambda has error epsilon^2).

flowchart LR
  A["Start with<br/>random vector x"] --> B["y = A x"]
  B --> C["Normalize<br/>x = y / |y|"]
  C --> D["Rayleigh quotient<br/>estimates lambda"]
  D --> B
Python Power method from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Speed depends on the eigenvalue gap

Python Convergence rate is |lambda2 / lambda1|

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When the ratio is 0.99 the method needs thousands of steps. The method also fails if the starting vector has no component along v1 (extremely unlikely with random starts), or if there are two dominant eigenvalues with equal magnitude and opposite sign (the vector keeps flipping).

Inverse iteration: the smallest eigenvalue

The eigenvalues of A^(-1) are 1 / lambda_i. So running the power method on A^(-1) finds the eigenvalue of A smallest in magnitude. In practice you never form the inverse: factor A once (LU) and solve A y = x each iteration, as in the linear systems chapter.

Shifts: any eigenvalue you like

Apply inverse iteration to A - sigma I. Its eigenvalues are lambda_i - sigma, so the method converges to the eigenvalue closest to the shift sigma, very fast if sigma is close. This shifted inverse iteration polishes an eigenvalue you already roughly know. Updating the shift to the current Rayleigh quotient every step gives Rayleigh quotient iteration, with cubic convergence for symmetric matrices.

Python Inverse iteration with a shift

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how few iterations are needed: when the shift is near an eigenvalue, the ratio |lambda_nearest - sigma| / |lambda_next - sigma| is tiny.

Application: PageRank in miniature

A random surfer follows links; the long-run fraction of time spent on each page is the dominant eigenvector (eigenvalue 1) of the column-stochastic transition matrix. The power method is exactly how it is computed for huge sparse web graphs, because it only needs matrix-vector products and never modifies the matrix.

Python PageRank with the power method

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Page 2 collects the most links, so it gets the highest rank. The damping term guarantees a unique dominant eigenvalue, so the iteration converges. To find all eigenvalues, power iteration is too slow; the QR algorithm is the standard tool.

Common mistakes

  • Expecting the power method to find a non-dominant eigenvalue.
  • Not normalizing: the vector overflows or underflows.
  • Using the characteristic polynomial for numerical work.
  • Applying symmetric-matrix theory to a non-symmetric matrix: eigenvalues can be complex, and the Rayleigh quotient is then less reliable.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which eigenvalue does the power method find?

    Repeated multiplication amplifies the dominant eigen-component most.
  2. 2. What controls the convergence speed of the power method?

    The error shrinks by about |lambda2/lambda1| each iteration.
  3. 3. How do you find the eigenvalue of A closest to a number sigma?

    A - sigma I has eigenvalues lambda - sigma; the smallest in magnitude belongs to the eigenvalue nearest sigma.
  4. 4. Why is PageRank computed with the power method?

    Each step is a sparse matrix-vector product, with no factorization needed.

Summary

  • Eigenpairs satisfy A v = lambda v; never find them through the characteristic polynomial.
  • The power method converges to the dominant eigenvalue at rate |lambda2/lambda1|; the Rayleigh quotient estimates lambda.
  • Inverse iteration finds the smallest eigenvalue; shifts find the eigenvalue nearest any chosen number.
  • PageRank is a power iteration on a damped transition matrix.

Next: The QR algorithm for eigenvalues