Eigenvalue computation — power method, inverse iteration

1. The seed idea: why repeated multiplication finds the dominant eigenvector

HOW the derivation goes (from scratch): Write any start vector in the eigenbasis: $x_0 = c_1 v_1 + c_2 v_2 + \cdots + c_n v_n, \qquad c_1\neq 0.$ Apply $A$ once: $Av_i = \lambda_i v_i$ , so $A x_0 = c_1\lambda_1 v_1 + \cdots + c_n\lambda_n v_n.$ Apply $k$ times (each $A$ multiplies $v_i$ by $\lambda_i$ again): $A^k x_0 = c_1\lambda_1^k v_1 + c_2\lambda_2^k v_2 + \cdots + c_n\lambda_n^k v_n.$ Now factor out the dominant term $\lambda_1^k$ — this is the crucial algebraic move: $A^k x_0 = \lambda_1^k\left[ c_1 v_1 + c_2\left(\tfrac{\lambda_2}{\lambda_1}\right)^k v_2 + \cdots + c_n\left(\tfrac{\lambda_n}{\lambda_1}\right)^k v_n\right].$

The error shrinks at rate $\left|\frac{\lambda_2}{\lambda_1}\right|^k$ — linear convergence, governed by the gap between the two biggest eigenvalues.

2. Power Method — algorithm

We can't let the vector blow up ( $\lambda_1^k$ ) or vanish, so we normalize each step.

WHY the Rayleigh quotient? If $x_k\approx v_1$ then $Ax_k\approx \lambda_1 x_k$ , so $\frac{x_k^\top A x_k}{x_k^\top x_k}\approx\frac{x_k^\top(\lambda_1 x_k)}{x_k^\top x_k}=\lambda_1.$ It also minimizes $\|Ax_k - \mu x_k\|$ over $\mu$ , i.e. it's the best least-squares eigenvalue for the current vector — hence accurate even when $x_k$ is only approximate. (For symmetric $A$ it's accurate to $O(\text{error}^2)$ .)

Figure — Eigenvalue computation — power method, inverse iteration

Worked example Power method by hand

$A=\begin{pmatrix}2&1\\1&3\end{pmatrix}$ , $x_0=\binom{1}{0}$ . True eigenvalues: $\lambda = \frac{5\pm\sqrt5}{2}\approx 3.618,\,1.382$ .

Step 1. $y_1=Ax_0=\binom{2}{1}$ . Why? Just $A$ times the seed. Normalize ( $\|y_1\|=\sqrt5$ ): $x_1=\binom{0.894}{0.447}$ . Rayleigh: $\mu_1=\frac{x_0^\top A x_0}{1}=2$ . Why this step? $x_0^\top Ax_0 = (1,0)\binom{2}{1}=2$ . Crude, but it's our first guess. Step 2. $y_2=Ax_1=\binom{2.236}{2.236}$ . Normalize ( $\|y_2\|=3.162$ ): $x_2=\binom{0.707}{0.707}$ . Rayleigh: $\mu_2 = x_1^\top A x_1 = 3.20$ . Why? Now the vector leans toward $v_1$ , so the estimate jumps up. Step 3. $y_3=Ax_2=\binom{2.121}{2.828}$ , $x_3=\binom{0.6}{0.8}$ , $\mu_3\approx 3.5$ . Continuing $\to 3.618$ . Why it works: ratio $\lambda_2/\lambda_1=0.382$ , so each step roughly cuts error by $0.382$ .

3. Getting the smallest eigenvalue: inverse iteration

HOW (derivation): From $Av_i=\lambda_i v_i$ , multiply by $A^{-1}/\lambda_i$ : $A^{-1}v_i = \tfrac{1}{\lambda_i} v_i.$ So power method applied to $A^{-1}$ converges to $v_n$ (the eigenvector of $\min|\lambda|$ ), at rate $\left|\frac{\lambda_n}{\lambda_{n-1}}\right|^k$ .

4. Shifted inverse iteration — hunt any eigenvalue

WHY shift: the eigenvalue of $(A-\sigma I)^{-1}$ is $\dfrac{1}{\lambda_i-\sigma}$ . If we pick $\sigma$ close to a target eigenvalue $\lambda_j$ , then $\lambda_j-\sigma$ is tiny, so $\frac{1}{\lambda_j-\sigma}$ is huge — it dominates all others. Inverse iteration then converges to $v_j$ explosively fast.

Worked example Shifted inverse iteration

Same $A=\begin{pmatrix}2&1\\1&3\end{pmatrix}$ . Target the small eigenvalue $\approx1.382$ ; guess $\sigma=1.3$ . $A-\sigma I=\begin{pmatrix}0.7&1\\1&1.7\end{pmatrix}$ , $\det=0.19$ . Step: solve $(A-\sigma I)y=x_0$ with $x_0=\binom{1}{0}$ : $y=\frac{1}{0.19}\begin{pmatrix}1.7&-1\\-1&0.7\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}8.95\\-5.26\end{pmatrix}$ . Why? Inverse of a $2\times2$ . Normalize: $x_1\approx\binom{0.862}{-0.507}$ . Rayleigh: $x_1^\top A x_1\approx 1.39$ — already near $1.382$ in one step! Why so fast: $|\lambda-\sigma|=0.082$ tiny, dominates massively.

5. The 80/20 core

Recall Feynman: explain to a 12-year-old

Imagine a stretchy sheet of rubber. Push a dot on it and let go — the sheet pulls it along whatever direction stretches the most. Do this push again and again, and the dot always ends up sliding along that strongest stretch line. That's the power method: the strongest stretch is the "biggest eigenvalue" direction. Now flip the rubber's rule so the weakest stretch becomes strongest — that's inverse iteration, finding the small one. And if you want a specific stretch, you "tilt" the sheet (a shift) so your favourite direction becomes the strongest, and it pops out almost instantly.

Flashcards

What does

A^k x_0

converge to (in direction)?

The dominant eigenvector

v_1

(largest

|\lambda|

), provided

c_1\neq0

and

|\lambda_1|>|\lambda_2|

Why factor out

\lambda_1^k

in the derivation?

To expose ratios

(\lambda_i/\lambda_1)^k\to0

, showing all non-dominant components decay.

Power method convergence rate?

Linear, governed by

|\lambda_2/\lambda_1|^k

What is the Rayleigh quotient and why use it?

\mu=\frac{x^\top Ax}{x^\top x}

; best least-squares eigenvalue estimate for a given vector, accurate even for approximate

x

(quadratically accurate if

A

symmetric).

How do eigenvalues of

A^{-1}

relate to

A

's?

Reciprocals

1/\lambda_i

; eigenvectors unchanged.

What does inverse iteration find and why?

Smallest

|\lambda|

A

, because it's the largest of

A^{-1}=1/\lambda

Why solve

Ay=x

instead of computing

A^{-1}

Cheaper & stabler; LU-factor once, back-substitute each step (

O(n^2)

O(n^3)

Eigenvalues of

A-\sigma I

\lambda_i-\sigma

, same eigenvectors.

Why does a shift

\sigma\approx\lambda_j

speed up inverse iteration?

1/(\lambda_j-\sigma)

becomes huge, dominating all others → very fast convergence to

v_j

Convergence rate of shifted inverse iteration?

|(\lambda_j-\sigma)/(\lambda_m-\sigma)|^k

\lambda_m

= next-closest eigenvalue to

\sigma

Condition for power method to start?

Seed must have nonzero component along dominant eigenvector (

c_1\neq0

Connections

LU Decomposition — used to solve $(A-\sigma I)y=x$ cheaply each iteration.
Characteristic Polynomial — why direct eigenvalue formulas fail for $n\ge5$ (Abel–Ruffini).
Rayleigh Quotient Iteration — update $\sigma$ to the current Rayleigh quotient each step → cubic convergence.
QR Algorithm — the industrial method computing all eigenvalues.
Spectral Decomposition — eigenbasis expansion $x_0=\sum c_i v_i$ underpinning the derivation.
Convergence Rates — linear vs quadratic vs cubic.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, eigenvalue nikalna direct formula se possible nahi hota bade matrices ke liye (degree 5+ polynomial ka koi general solution nahi). Isliye hum iterative methods use karte hain. Power method ka core idea bilkul simple hai: agar tum kisi random vector ko $A$ se baar-baar multiply karte raho, to woh vector dheere-dheere us direction me mud jaata hai jisko $A$ sabse zyada stretch karta hai. Yehi direction dominant eigenvector hai, aur uska stretch factor sabse bada eigenvalue $\lambda_1$ . Maths me: $A^k x_0$ likho eigenbasis me, $\lambda_1^k$ bahar nikaalo, to baaki saare terms me $(\lambda_i/\lambda_1)^k$ aata hai jo $k$ bada hone par zero ho jaata hai — sirf $v_1$ bachta hai.

Eigenvalue ki value padhne ke liye Rayleigh quotient $\mu=\frac{x^\top Ax}{x^\top x}$ use karte hain — ye approximate vector ke liye bhi accha estimate deta hai. Har step me vector ko normalize karna zaroori hai warna $\lambda_1^k$ ki wajah se number blow up ya zero ho jaayega.

Ab agar chhota eigenvalue chahiye? Trick: $A^{-1}$ ke eigenvalues $1/\lambda$ hote hain, eigenvectors same. To $A$ ka smallest $\to$ $A^{-1}$ ka largest. Power method $A^{-1}$ par chalao — bas $A^{-1}$ compute mat karo, instead har step me $Ay=x$ solve karo (LU ek baar factor karke). Ye fast bhi hai aur stable bhi.

Sabse powerful cheez: shift. $A-\sigma I$ ke eigenvalues $\lambda_i-\sigma$ hote hain. Agar $\sigma$ apne target eigenvalue ke paas rakho, to $1/(\lambda_j-\sigma)$ bahut bada ho jaata hai aur convergence rocket ki tarah fast — kabhi-kabhi ek hi step me answer aa jaata hai. Yaad rakho mantra: "Power se BIG, inverse se SMALL, shift se ANY", aur "solve karo, invert mat karo".

Eigenvalue computation — power method, inverse iteration

1. The seed idea: why repeated multiplication finds the dominant eigenvector

2. Power Method — algorithm

3. Getting the smallest eigenvalue: inverse iteration

4. Shifted inverse iteration — hunt any eigenvalue

5. The 80/20 core

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Numerical Methods

Connections