Eigenvalue computation — power method, inverse iteration: Exercises

Throughout, our workhorse matrix is $A = (2113), λ_{1, 2} = \frac{5 \pm 5}{2} \approx 3.6180, 1.3820.$ We reuse it so you can watch the same matrix answer many different questions.

Before starting, four reminders in plain words:

An eigenpair $(λ, v)$ satisfies $A v = λ v$ : the matrix only stretches $v$ , never rotates it. See Spectral Decomposition.
The identity matrix $I$ is the "do-nothing" matrix: $I v = v$ for every vector $v$ (in 2D, $I = (1001)$ ). We need it because " $A$ minus a number $σ$ " makes no sense — you can't subtract a number from a matrix — so we subtract $σ$ copies of the do-nothing matrix, written $A - σ I$ , which quietly means "subtract $σ$ from each diagonal entry."
The Rayleigh quotient of a vector $x$ is the number $μ = \frac{x ^{⊤} A x}{x ^{⊤} x}$ — read it as "if $x$ were an eigenvector, what stretch factor would it have?" See Rayleigh Quotient Iteration.
Normalize means: divide a vector by its length $∥ x ∥ = x_{1}^{2} + x_{2}^{2} + \dots$ so it has length $1$ . We do this every step so numbers don't explode.

The whole page in one picture. Before the algebra, look at the geometry the exercises live in. The figure below shows our unit vector starting at $x_{0} = (0 1)$ (pointing straight right) and swinging, step by step, toward the red dominant-eigenvector line. The dashed quarter-circle is the set of unit vectors (length exactly 1), and the angle marks $θ_{k}$ show how each step shaves the angle to the red line. Every L1–L3 exercise is really "how fast does the black arrow reach the red line, and how do I read the stretch factor off it?" Keep this picture in your head as you compute.

Figure — Eigenvalue computation — power method, inverse iteration

Notice two things you'll verify numerically later: (1) each black arrow lands closer to the red line than the last, and (2) the gaps between consecutive arrows shrink — that shrinking is the linear convergence of Exercise 3.1.

L1 — Recognition

Exercise 1.1 (L1)

Which of these vectors is an eigenvector of $A = (2113)$ , and with what eigenvalue? $u = (0 1), w = (1.618 1) .$

Recall Solution 1.1

WHAT to do: an eigenvector is one where $A v$ comes out as a plain multiple of $v$ — same direction, just scaled.

Test $u$ : $A u = (2113) (0 1) = (1 2)$ . Is $(1 2)$ a multiple of $(0 1)$ ? No — the second entry went from $0$ to $1$ . So $u$ is NOT an eigenvector.

Test $w$ : $A w = (1 \cdot 1 + 3 \cdot 1.618 2 \cdot 1 + 1 \cdot 1.618) = (5.854 3.618)$ . Is this a multiple of $(1.618 1)$ ? Check the ratio of first entries: $3.618/1 = 3.618$ . Check second: $5.854/1.618 = 3.618$ . Same factor → yes! $A w = 3.618 w$ .

Answer: $w$ is an eigenvector with eigenvalue $\approx 3.618 = λ_{1}$ ; $u$ is not.

Exercise 1.2 (L1)

The power method turns $A v = λ v$ into $A^{- 1} v = ? v$ and $(A - σ I) v = ? v$ . Fill the blanks in words.

Recall Solution 1.2

Start from $A v = λ v$ .

Multiply both sides by $A^{- 1}$ : $v = λ A^{- 1} v$ , so $A^{- 1} v = \frac{1}{λ} v$ . The eigenvector is unchanged; the eigenvalue flips to $1/ λ$ .
Subtract $σ v$ from $A v = λ v$ : $(A - σ I) v = (λ - σ) v$ (recall $I$ is the do-nothing matrix, so $σ I v = σ v$ ). Eigenvector unchanged; eigenvalue slides by $- σ$ .

This single fact — eigenvectors survive both operations, eigenvalues transform predictably — is the whole engine behind inverse and shifted iteration.

L2 — Application

Exercise 2.1 (L2)

Run two power-method steps on $A$ from $x_{0} = (0 1)$ . Report $x_{1}, x_{2}$ (normalized) and the Rayleigh estimates $μ_{0}, μ_{1}, μ_{2}$ using the consistent rule $μ_{k} = x_{k}^{⊤} A x_{k}$ (each $x_{k}$ has length 1).

Recall Solution 2.1

Convention (fixing the inconsistency): the Rayleigh estimate belongs to whatever normalized vector we currently hold. So $μ_{k} = x_{k}^{⊤} A x_{k}$ for the same index $k$ . We report one $μ$ per vector: $μ_{0}$ for $x_{0}$ , $μ_{1}$ for $x_{1}$ , $μ_{2}$ for $x_{2}$ .

WHY normalize before each Rayleigh quotient: two reasons. (1) Numbers stay tame. Without rescaling, $A^{k} x_{0}$ grows like $λ_{1}^{k} \approx 3.61 8^{k}$ and overflows; dividing by the length $∥ y_{k} ∥$ each step keeps every $x_{k}$ on the unit circle. (2) The quotient formula simplifies. When $∥ x_{k} ∥ = 1$ the denominator $x_{k}^{⊤} x_{k} = 1$ , so $μ_{k} = x_{k}^{⊤} A x_{k}$ needs no division — the number you compute is the estimate.

WHY the Rayleigh quotient converges to the dominant eigenvalue: as the black arrow swings onto the red line (see the opening figure), $x_{k} \to v_{1}$ , so $A x_{k} \to λ_{1} x_{k}$ . Feed that into the quotient: $μ_{k} = x_{k}^{⊤} A x_{k} \to x_{k}^{⊤} (λ_{1} x_{k}) = λ_{1} (x_{k}^{⊤} x_{k}) = λ_{1}$ . So the closer the arrow gets to red, the closer $μ_{k}$ gets to $λ_{1} = 3.618$ — which is exactly the monotone climb $2.00 \to 3.00 \to 3.50$ we compute below.

Rayleigh at the seed $x_{0} = (0 1)$ (length 1 already): $μ_{0} = x_{0}^{⊤} A x_{0} = (1, 0) (1 2) = 2.00.$

Step 1 — WHAT we do: apply $A$ , then rescale to length 1. WHY: $A$ tilts the vector toward the dominant direction; rescaling removes the growth so only the direction survives. $y_{1} = A x_{0} = (1 2), ∥ y_{1} ∥ = 2^{2} + 1^{2} = 5 \approx 2.2361, x_{1} = (0.4472 0.8944) .$ Rayleigh at $x_{1}$ : first $A x_{1} = (0.8944 + 3 ( 0.4472 ) 2 ( 0.8944 ) + 0.4472) = (2.2361 2.2361)$ , then $μ_{1} = x_{1}^{⊤} A x_{1} = 0.8944 (2.2361) + 0.4472 (2.2361) = 3.00.$

Step 2: $y_{2} = A x_{1} = (2.2361 2.2361), ∥ y_{2} ∥ = 3.1623, x_{2} = (0.7071 0.7071) .$ Rayleigh at $x_{2}$ : $A x_{2} = (0.7071 + 3 ( 0.7071 ) 2 ( 0.7071 ) + 0.7071) = (2.8284 2.1213)$ , then $μ_{2} = x_{2}^{⊤} A x_{2} = 0.7071 (2.1213) + 0.7071 (2.8284) = 3.50.$

Answer: $x_{1} = (0.894, 0.447)$ , $x_{2} = (0.707, 0.707)$ , and $μ_{0} = 2.00, μ_{1} = 3.00, μ_{2} = 3.50$ — a clean monotone climb toward $λ_{1} = 3.618$ .

Exercise 2.2 (L2)

Do one shifted-inverse step targeting the small eigenvalue: $σ = 1.3$ , $x_{0} = (0 1)$ . Solve $(A - σ I) y = x_{0}$ , normalize, and give the Rayleigh estimate.

Recall Solution 2.2

WHAT to do: solve the linear system $(A - σ I) y = x_{0}$ for the unknown $y$ — do not build an inverse matrix. This is the message of LU Decomposition: to find $y$ with $M y = x_{0}$ , factor $M$ once and run forward/back-substitution, never form $M^{- 1}$ .

Set up the system. Here $M = A - σ I = (0.7 1 1 1.7)$ (subtract $σ = 1.3$ from each diagonal entry — that's what $- σ I$ does). We solve $(0.7 1 1 1.7) (y _{2} y _{1}) = (0 1) .$ Solve by elimination (this is what LU does under the hood). From row 1: $0.7 y_{1} + y_{2} = 1$ . From row 2: $y_{1} + 1.7 y_{2} = 0$ , i.e. $y_{1} = - 1.7 y_{2}$ . Substitute into row 1: $0.7 (- 1.7 y_{2}) + y_{2} = 1 \Rightarrow (- 1.19 + 1) y_{2} = 1 \Rightarrow - 0.19 y_{2} = 1 \Rightarrow y_{2} = - 5.263.$ Back-substitute: $y_{1} = - 1.7 (- 5.263) = 8.947$ . So $y = (- 5.263 8.947)$ — obtained without ever computing $M^{- 1}$ , exactly as preached.

Normalize: $∥ y ∥ = 8.94 7^{2} + 5.26 3^{2} = 10.38$ , so $x_{1} = (- 0.507 0.862)$ . Rayleigh: $μ = x_{1}^{⊤} A x_{1}$ . First $A x_{1} = (0.862 - 3 ( 0.507 ) 2 ( 0.862 ) - 0.507) = (- 0.659 1.217)$ , then $μ = 0.862 \cdot 1.217 + (- 0.507) (- 0.659) = 1.383.$

Answer: $x_{1} \approx (0.862, - 0.507)$ , $μ \approx 1.383$ — essentially $λ_{2} = 1.382$ in a single step.

L3 — Analysis

Exercise 3.1 (L3)

For our $A$ , power-method error shrinks like $r^{k}$ with $r = ∣ λ_{2} / λ_{1} ∣$ . Compute $r$ . How many steps to cut the error by a factor of $1000$ ? Relate this to the shrinking arrow-gaps in the opening figure.

Recall Solution 3.1

WHY this ratio: the derivation factors out $λ_{1}^{k}$ , leaving the leftover component scaled by $(λ_{2} / λ_{1})^{k}$ . That leftover is the error, so its size after $k$ steps is $r^{k}$ . See Convergence Rates. $r = \frac{1.3820}{3.6180} = 0.3820.$ We need $r^{k} \leq 1 0^{- 3}$ . Take logs (log = "how many times do I multiply to reach this?"): $k \geq \frac{l n ( 1 0 ^{- 3} )}{l n ( 0.3820 )} = \frac{- 6.9078}{- 0.9622} = 7.18.$ Answer: $r \approx 0.382$ ; about $k = 8$ steps to gain three decimal digits. This is linear convergence — a fixed number of steps per digit. In the opening figure, this $r = 0.382$ is exactly why each black arrow's angular gap to the red line is $\sim 0.382$ times the previous gap — the arrows visibly pile up against the red line.

Exercise 3.2 (L3)

For shifted inverse iteration with $σ = 1.3$ targeting $λ_{2} = 1.382$ , the rate is $\frac{λ _{2} - σ}{λ _{1} - σ}$ . Compute it and contrast with Exercise 3.1.

Recall Solution 3.2

WHY these two gaps: after shifting and inverting, the target eigenvalue $λ_{2}$ becomes the huge one $\frac{1}{λ _{2} - σ}$ , and the nearest competitor is $λ_{1}$ (the only other eigenvalue). The rate is the ratio of the "distance to target" over "distance to competitor": $r = \frac{λ _{2} - σ}{λ _{1} - σ} = \frac{∣1.382 - 1.3∣}{∣3.618 - 1.3∣} = \frac{0.082}{2.318} = 0.0354.$ Answer: $r \approx 0.035$ — one step already gains $\sim 1.5$ digits, versus $0.382$ for plain power method. Choosing $σ$ near the target is what makes inverse iteration explosive: shrink $∣ λ_{2} - σ ∣$ and the rate plummets.

L4 — Synthesis

Exercise 4.1 (L4)

The dominant eigenvector of $A$ is $v_{1} \propto (1.618 1)$ . The other eigenvector is $v_{2} \propto (- 0.618 1)$ (the eigenvector of $λ_{2} = 1.382$ ). Suppose I start power method from the seed $x_{0} = (- 0.618 1)$ — i.e. exactly the $v_{2}$ direction. In exact arithmetic, where does power method converge, and why? What rescues it in real computation? Use the geometry of the opening figure to explain.

Recall Solution 4.1

Check the seed really is $v_{2}$ : $A (- 0.618 1) = (1 - 1.854 2 - 0.618) = (- 0.854 1.382)$ . Is that $λ_{2} (- 0.618 1)$ ? Compute $1.382 \cdot (- 0.618 1) = (- 0.854 1.382)$ . Exact match — so $x_{0}$ is genuinely the $v_{2}$ direction, with zero component along $v_{1}$ , i.e. $c_{1} = 0$ .

WHY it fails: the derivation needed $x_{0} = c_{1} v_{1} + c_{2} v_{2}$ with $c_{1} \neq = 0$ . If $c_{1} = 0$ , then $A^{k} x_{0} = c_{2} λ_{2}^{k} v_{2}$ forever — it converges to $v_{2}$ and reports $λ_{2}$ , not $λ_{1}$ . Power method amplifies the largest present component; if the dominant one is absent it can't invent it.

Geometric picture: in the opening figure the red line is $v_{1}$ . A seed lying exactly on the perpendicular eigen-direction $v_{2}$ is a black arrow that $A$ maps straight back onto itself — it never swings toward the red line, because there's no red-line component to amplify. It's a knife-edge balance point.

WHAT rescues it: floating-point rounding. Every real multiplication injects a tiny error, which almost surely has a nonzero $v_{1}$ component. That seed of $v_{1}$ then gets amplified by $r^{- k}$ and eventually takes over — the black arrow, nudged off the knife-edge, slides onto the red line after all. Lesson: a random seed has $c_{1} \neq = 0$ with probability 1, so we never worry in practice.

Exercise 4.2 (L4)

You want the eigenvalue of $A$ nearest to $2.5$ . Design the method, pick the shift, and predict the convergence rate. (Eigenvalues: $1.382, 3.618$ .)

Recall Solution 4.2

WHAT to build: shifted inverse iteration with $σ = 2.5$ (put the shift exactly at the target region).

$λ_{1} - σ = 3.618 - 2.5 = 1.118$ , $λ_{2} - σ = 1.382 - 2.5 = - 1.118$ . They're equidistant! $σ = 2.5$ is the midpoint of the two eigenvalues.
The eigenvalues of $(A - σ I)^{- 1}$ are $\frac{1}{1.118}$ and $\frac{1}{- 1.118}$ — equal magnitude, opposite sign. Rate $r = \frac{λ _{2} - σ}{λ _{1} - σ} = 1.$

WHY this is the worst case: rate $= 1$ means no convergence — the method stalls because neither transformed eigenvalue dominates. Fix: nudge the shift off-center, e.g. $σ = 2.6$ : then $λ_{1} - σ = 1.018$ , $λ_{2} - σ = - 1.218$ , and the closer eigenvalue is $λ_{1}$ , so it converges to $λ_{1}$ at rate $1.018/1.218 = 0.836$ . Answer: never place $σ$ exactly between two eigenvalues; bias it toward the one you want.

L5 — Mastery

Exercise 5.1 (L5)

Prove that for our symmetric $A$ , the Rayleigh quotient error is second order: if $x = v_{1} + ϵ d$ (a perturbation of the true unit eigenvector by a small $ϵ$ in a unit direction $d ⊥ v_{1}$ ), then $μ (x) - λ_{1} = O (ϵ^{2})$ , not $O (ϵ)$ . Verify numerically for our $A$ with $ϵ = 0.1$ .

Recall Solution 5.1

WHY symmetry matters: for symmetric $A$ , eigenvectors are orthogonal, and $μ (x)$ is a smooth function whose gradient vanishes at every eigenvector (each eigenvector is a critical point of the Rayleigh quotient — this is the Rayleigh Quotient Iteration insight). A function at a critical point changes only quadratically.

Proof. Write $x = v_{1} + ϵ d$ with $v_{1}^{⊤} v_{1} = 1$ , $v_{1}^{⊤} d = 0$ , $d^{⊤} d = 1$ . $μ (x) = \frac{x ^{⊤} A x}{x ^{⊤} x} = \frac{( v _{1} + ϵ d ) ^{⊤} A ( v _{1} + ϵ d )}{( v _{1} + ϵ d ) ^{⊤} ( v _{1} + ϵ d )} .$ Expand the numerator, using $A v_{1} = λ_{1} v_{1}$ and — crucially — symmetry, which gives $v_{1}^{⊤} A = (A v_{1})^{⊤} = λ_{1} v_{1}^{⊤}$ : $num = λ_{1} + 2 ϵ = λ_{1} v_{1}^{⊤} d = 0 v_{1}^{⊤} A d + ϵ^{2} d^{⊤} A d = λ_{1} + ϵ^{2} d^{⊤} A d .$ Denominator: $(v_{1} + ϵ d)^{⊤} (v_{1} + ϵ d) = 1 + 2 ϵ v_{1}^{⊤} d + ϵ^{2} = 1 + ϵ^{2} .$ $μ (x) = \frac{λ _{1} + ϵ ^{2} d ^{⊤} A d}{1 + ϵ ^{2}} = λ_{1} + ϵ^{2} (d^{⊤} A d - λ_{1}) + O (ϵ^{4}) .$ The linear-in- $ϵ$ term cancelled (thanks to $v_{1}^{⊤} A d = λ_{1} v_{1}^{⊤} d = 0$ , which needed symmetry). Hence $μ (x) - λ_{1} = O (ϵ^{2})$ . $■$

Numeric check ( $ϵ = 0.1$ ): take $v_{1}$ the unit dominant eigenvector and $d$ the unit orthogonal direction ( $= v_{2}$ ). Form $x = v_{1} + 0.1 d$ and compute $μ (x) = \frac{x ^{⊤} A x}{x ^{⊤} x}$ . The result gives $μ (x) - λ_{1} \approx - 0.0198$ , whereas the vector error is $0.1$ . Ratio $0.0198/0. 1^{2} \approx 1.98$ — a clean $O (ϵ^{2})$ (the constant $∣ d^{⊤} A d - λ_{1} ∣ = ∣ λ_{2} - λ_{1} ∣ = 2.236$ , and $2.236 \cdot 0. 1^{2} / (1 + 0.01) \approx 0.0221$ , matching order). A linear error would have given $\sim 0.1$ , five times bigger.

Exercise 5.2 (L5)

Explain, using the transformation rules, why Rayleigh Quotient Iteration (updating the shift to the current Rayleigh estimate every step) converges cubically for symmetric matrices, and why plain shifted inverse iteration (fixed $σ$ ) is only linear. Connect to the QR Algorithm and Characteristic Polynomial.

Recall Solution 5.2

Fixed shift (linear): with $σ$ constant, each step multiplies the error by the fixed ratio $r = \frac{λ _{j} - σ}{λ _{m} - σ} < 1$ . Constant ratio → error like $r^{k}$ → linear. See Convergence Rates.

Adaptive shift (cubic) — the full chain: set $σ_{k} = μ (x_{k})$ , the Rayleigh quotient of the current vector, and let $ϵ_{k} = ∥ x_{k} - v_{j} ∥$ be the current vector error.

Shift accuracy (from Exercise 5.1): because the Rayleigh quotient is second-order accurate at a symmetric eigenvector, the shift lands within $∣ σ_{k} - λ_{j} ∣ = O (ϵ_{k}^{2})$ of the true eigenvalue. This is the crucial input — the shift error is quadratically small, not merely linearly small.
One inverse-iteration step with that shift: the transformed target eigenvalue is $\frac{1}{λ _{j} - σ _{k}}$ , and the nearest competitor is $\frac{1}{λ _{m} - σ _{k}}$ with $λ_{m}$ a fixed distance away. So the one-step contraction factor is $\frac{λ _{j} - σ _{k}}{λ _{m} - σ _{k}} \approx \frac{O ( ϵ _{k}^{2} )}{O ( 1 )} = O (ϵ_{k}^{2}) .$
Compound the two: the new error is the old error times that contraction factor: $ϵ_{k + 1} = ϵ_{k} \cdot O (ϵ_{k}^{2}) = O (ϵ_{k}^{3}) .$ That is cubic convergence — the number of correct digits triples every step (3, 9, 27, …). The engine is the feedback loop: an accurate vector → a quadratically-accurate shift → a quadratically-strong contraction → an even more accurate vector.

Concrete link to QR and the characteristic polynomial:

The QR Algorithm is, in disguise, shifted inverse iteration run on all eigenvectors at once. It uses Rayleigh-type Wilkinson shifts (essentially $σ_{k} =$ a corner Rayleigh quotient of the current matrix) to inherit exactly this cubic speed on symmetric problems — which is why practical libraries use QR, not the definitions we started from.
We avoid the Characteristic Polynomial route ( $det (A - λ I) = 0$ ) entirely: for $n \geq 5$ that polynomial has no closed-form roots (Abel–Ruffini), and even numerically its roots are wildly sensitive to coefficient errors. Iteration sidesteps the polynomial: every eigenvalue is found by shifting and solving, and the Rayleigh feedback makes it cubically fast. Slogan: "don't root the polynomial — shift, solve, and let Rayleigh chase the answer."

Recall One-line recap of the whole page

Power method rides the biggest stretch; inverse iteration flips to the smallest; shifting aims anywhere; the Rayleigh quotient reads off the eigenvalue quadratically (symmetric case); and letting the shift chase that quotient buys cubic speed — the seed of the QR Algorithm.