Turn a nearby eigenvalue into a dominant one
Power iteration amplifies eigenvectors associated with eigenvalues of largest magnitude. To target an eigenvalue near a chosen shift , one can instead apply power iteration to . The operation is implemented by solving a linear system; explicitly forming the inverse is unnecessary.
Assume and is symmetric, with orthonormal eigenvectors and real eigenvalues . Choose a shift that is not an eigenvalue, and suppose
Definition 5.4.1
(Shifted inverse iteration)
Starting with , , inverse iteration with shift solves and normalizes:
In exact arithmetic because is invertible. With a fixed shift, one factorization of may be reused for all solves.
Theorem 5.4.2
(Geometric convergence of the iteration line)
Suppose . Then the angle between the line spanned by and converges to zero at least geometrically. More precisely, writing
we have
The angle is between lines, so an alternating sign of does not spoil convergence.
Proof
(Powers of the shifted inverse)
Induction on (2) shows that is the normalized version of
Divide every coefficient by the coefficient. The Euclidean norm of the resulting orthogonal part equals the tangent of the angle between the two lines, and it is at most the right side of (3). Condition (1) makes .
Proof X-ray
Why the shift changes the target
The inverse shifted matrix has eigenvalues . The eigenvalue of closest to becomes the largest in magnitude after inversion. A strict closest eigenvalue and a nonzero initial coefficient are both needed for the stated one-dimensional conclusion.
A two-dimensional calculation
Worked example 5.4.3
(Inverse iteration for a diagonal matrix)
Take , and . The inverse eigenvalues are and , so the error ratio is . The ratio of the second coordinate to the first after steps is . The vector may reverse sign, but its line rapidly approaches the first coordinate axis.
Common mistake
(Assuming the shifted matrix is positive definite)
The shift is closer to than , yet is indefinite. Symmetry is retained, but positive definiteness is not guaranteed. A Cholesky solver requiring an SPD matrix therefore cannot be assumed applicable to every shift.
Residuals give an a posteriori certificate
Theorem 5.4.4
(Residual certificate for a symmetric matrix)
For the symmetric matrix , any unit vector and any real number , define . Then
Thus the interval contains at least one eigenvalue.
Proof
(Expansion in the eigenbasis)
Expand ; then
Since the coefficients have squared sum one, (4) follows.
For a nonzero non-unit vector the analogous bound divides the residual norm by . Symmetry is essential for this form of the certificate. The certificate does not by itself identify which eigenvalue it locates or certify an eigenvector direction when eigenvalues cluster.
Proposition 5.4.5
(The Rayleigh quotient minimizes the residual)
For a fixed unit vector , the Rayleigh quotient minimizes over real .
Proof
(Completing the square in the shift)
Expand the square: . This is a quadratic in with positive leading coefficient, and its derivative vanishes only at .
Common mistake
(Trusting a residual that was computed carelessly)
A small residual gives a mathematical certificate in exact arithmetic. A computed residual must itself be evaluated accurately enough for the intended guarantee: if and are nearly equal, their floating-point difference can be dominated by rounding error.
Counterexample mode
A shift alone does not create a missing component
For and , inverse iteration with remains on the second coordinate axis. The target eigenvector is never reached in exact arithmetic because its initial coefficient is zero. Likewise, a shift exactly equal to an eigenvalue makes the system singular and violates the hypotheses. Rounding can introduce a missing component in an actual computation. Equal-distance distinct eigenvalues can also prevent convergence: for and , the inverse iteration alternates between two lines when both components are nonzero.
Worked examples with certificates
Worked example 5.4.6
(A loose certificate from a poor vector)
Let and the unit vector . Then and , so . The interval is , which contains the eigenvalue but not . The bound (4) is not sharp: . A large residual gives a weak statement, though still a correct one.
Worked example 5.4.7
(Certificates along the iteration)
Continue with , and . At each iterate compute and :
| 0 | 2.5 | 1.5 |
| 1 | 1.01523 | 0.21320 |
| 2 | 1.000078 | 0.015306 |
For the interval ends exactly at the two eigenvalues, so equality holds in (4). At the interval is , which contains , and at one has while the certificate radius is . The certified radius falls by factors of about and then ; asymptotically the factor per step is .
Worked example 5.4.8
(Two eigenvalues at equal distance from the shift)
For , and , the inverse eigenvalues are and . Each solve gives , then , and the next solve gives . The iterates alternate between two different lines and do not converge, although every residual certificate with equals and correctly places an eigenvalue in .
Practice with solutions
Quick check
(For eigenvalues and shift , what is the inverse-iteration ratio ?)
Compare the two distances to the shift.
Solution · Answer
.
Quick check
(Why can alternate sign even though its line converges?)
Look at the sign of .
Solution · Answer
The dominant inverse eigenvalue is negative when ; the coefficient then changes sign at each step, while the line it spans is unchanged.
Quick check
(A unit vector has Rayleigh quotient and residual norm . What does (4) guarantee?)
Use and .
Solution · Answer
At least one eigenvalue lies in ; the certificate alone does not label which one it is.
Quick check
(If the eigenvalue nearest the shift has multiplicity two, why does the proof of convergence to a specified single eigenvector not apply?)
Which hypothesis fails?
Solution · Answer
The strict inequality (1) fails and the dominant inverse eigenspace has dimension two. If the initial projection onto it is nonzero, the line converges to the line of that projection; otherwise it is never reached in exact arithmetic.