Why an iteration for eigenvalues
An eigenvalue problem cannot be solved by a finite sequence of rational operations in general, so computation must be iterative. For large matrices one rarely wants all eigenpairs; one wants the largest one, or the one nearest a target. The power method and inverse iteration achieve this using only matrix–vector products or linear solves. They are the simplest eigenvalue algorithms and the basis of more elaborate ones. This unit uses the notions of linear-system solution and factorization from the units on elimination and on iterative solvers, and the error analysis of floating-point arithmetic is only mentioned, not analyzed.
Definitions and hypotheses
Let be a real matrix. Assume throughout that is diagonalizable with real eigenvalues and eigenvectors forming a basis.
Definition 17.1.1
(Strictly dominant eigenvalue)
The eigenvalue is strictly dominant if for all . The others are then ordered so that , and the ratio satisfies .
Write the starting vector as . The coefficient measures how much of the wanted eigenvector the start contains; the theorems below assume .
Definition 17.1.2
(Power method and Rayleigh quotient)
The power method produces , so that . The Rayleigh quotient of a nonzero vector is ; it is most useful when is symmetric.
Definition 17.1.3
(Inverse iteration with shift )
Let be a real number that is not an eigenvalue of . Inverse iteration with shift is the power method applied to : solve and normalize .
The matrix is factored once, and each step then costs only two triangular solves.
Convergence theorems
Theorem 17.1.4
(Convergence of the power method)
Assume is strictly dominant, , and . Then
and hence with . Consequently approaches the line spanned by at geometric rate (with alternating in sign if ).
Proof
(Expanding the start in the eigenbasis)
Expand and use to get . Dividing by gives the identity, and the triangle inequality with gives the bound. Normalizing a vector that approaches yields a unit vector approaching ; the factor produces the alternation when .
Theorem 17.1.5
(Rayleigh quotient in the symmetric case)
Under the hypotheses of the power-method theorem, suppose also that is symmetric, and take orthonormal. Then for the power iterates
so the eigenvalue estimate converges at rate , twice as fast as the vector.
Proof
(Orthonormal expansion of the Rayleigh quotient)
The quotient is unchanged by scaling, so with , . Orthonormality gives and , hence
Use , the denominator , and .
Proof X-ray
Why the error is squared
Symmetry is used exactly once: it allows an orthonormal eigenbasis, so that both and are sums of squares with no cross terms . Subtracting then removes the term from the numerator, so only the squares of the small coefficients remain. Each of them, divided by , carries , which is where comes from. Dominance enters through , and keeps the denominator away from zero. For a nonsymmetric matrix the cross terms survive at first order, and the rate falls back to ; a concrete matrix is examined under the common mistakes below.
Theorem 17.1.6
(Convergence of inverse iteration)
Let not be an eigenvalue and suppose for all , and that . Then the iterates approach the line spanned by at geometric rate .
Proof
(Inverse iteration is the power method for the inverse)
, so . The eigenvalues of are ; the one of largest modulus has index , strictly dominant by hypothesis. Apply the power-method theorem to : the ratio is .
Choosing closer to makes the rate faster, at no extra cost per step. The system is then nearly singular, but this does not harm the direction of the computed solution in practice, because the large errors lie in the direction of itself.
Worked examples
Worked example 17.1.7
(Power method with Rayleigh quotients)
Let , with eigenvalues (vector ) and (vector ), and . Here . Unnormalized iterates are , i.e. . The Rayleigh quotients are
| 0 | |||
| 1 | |||
| 2 | |||
| 3 |
For instance, has , and . Successive error ratios , , approach , as the Rayleigh-quotient theorem predicts.
Worked example 17.1.8
(Inverse iteration with a shift)
For the same take , nearest to . Then with determinant , and the rate is . Starting from , one solve gives (up to scale) , and a second solve gives . In the eigenbasis, with ; for we get , , and as predicted. The Rayleigh quotients are and , converging to the eigenvalue , which the unshifted power method cannot find.
Worked example 17.1.9
(A negative dominant eigenvalue)
Let and , so and . Then , and the normalized iterates approach for even and for odd . The sequence has no limit, yet the line it approaches is the eigenvector line of , exactly as the power-method theorem states. The Rayleigh quotient does converge:
For the errors are and , a ratio close to . The symmetric bound gives and , which indeed dominate the actual errors.
Common mistakes and subtle points
Common mistake
(Assuming a dominant eigenvalue exists)
If (for instance ), there is no dominant eigenvalue and the iteration need not converge to any line. A shift may restore dominance, because it moves all eigenvalues by the same amount.
Common mistake
(Ignoring the starting component)
If exactly, the iteration converges to another eigenvector in exact arithmetic; rounding errors in floating point usually reintroduce a component along , but slowly, so a start with tiny is poor.
Common mistake
(Expecting the vectors to converge)
The vector converges only up to scale and sign, as the negative-eigenvalue example shows; use the Rayleigh quotient or the ratio of components to estimate .
Each power step costs one matrix–vector product; each inverse step costs one solve with the stored factorization, never an explicit inverse. Non-diagonalizable matrices and complex spectra require a separate analysis, which the theorems above do not cover. The symmetry hypothesis of the Rayleigh-quotient theorem is also not decorative.
Counterexample mode
The doubled rate needs symmetry
Claim: the Rayleigh quotient of power iterates always converges at rate . Take the nonsymmetric matrix , with eigenvalues (vector ) and (vector ), so , and . Then with , and . Hence
For () the error is ; for () it is . The ratio is about , close to , not ; indeed the error behaves like . The repaired statement is the theorem as stated: for symmetric the rate is , while for a general diagonalizable the Rayleigh quotient only inherits the rate of the vectors.
Exercises
Quick check
(For (eigenvalues and ) and , compute for and find a formula for using eigenvectors.)
Find the eigenvectors for and first, then expand in them.
Solution · Answer
, , . The eigenvectors are for and for , and . Thus . For : and , as computed. The ratio of first components is approaching .
Quick check
(Show that the power method with and does not converge, and propose a shift that repairs it.)
Compute the first few iterates and the eigenvalues of .
Solution · Answer
The eigenvalues are , with equal modulus, so there is no dominant eigenvalue. The iterates are , which alternate and do not converge. The matrix has eigenvalues and , so the power method on it has a strictly dominant eigenvalue (eigenvector , ratio ), and the eigenvalue of is recovered by subtracting .
Quick check
(The error of a power iteration decreases like . How many iterations guarantee a reduction by a factor ?)
Take logarithms of both sides.
Solution · Answer
We need , i.e. . So iterations.
Quick check
(For and shift , give the convergence rate of inverse iteration and carry out two solves from .)
The eigenvalue nearest is ; the other is .
Solution · Answer
The rate is . has determinant and inverse . First solve: . Second solve: . The ratio of the components moves from to , approaching the ratio of the eigenvector for the eigenvalue .