Eigenvalue computation — power method, inverse iteration: Worked examples

4.8.21 · D3 · Maths › Numerical Methods › Eigenvalue computation — power method, inverse iteration

Yahan har symbol parent note se liya gaya hai: $A$ hamara $n \times n$ matrix hai, ek eigenpair $(λ, v)$ satisfy karta hai $A v = λ v$ , $∥ \cdot ∥$ ordinary vector length $x_{1}^{2} + \dots + x_{n}^{2}$ hai, aur Rayleigh quotient $μ = \frac{x ^{⊤} A x}{x ^{⊤} x}$ current best eigenvalue guess hai. Hum sirf inhi ko reuse karte hain.

The scenario matrix

Neeche ka har cell iteration ke behave karne ka ek alag tarika hai. Last column batata hai ki kaunsa example use karta hai.

#	Scenario class	Kya mushkil banata hai	Example
C1	Do positive eigenvalues, clear gap	baseline power method	Ex 1
C2	Dominant eigenvalue negative	$x_{k}$ har step sign flip karta hai	Ex 2
C3	Equal magnitude, opposite sign ( $λ_{1} = - λ_{2}$ )	power method kabhi settle nahi hota	Ex 3
C4	Bad seed ( $c_{1} = 0$ )	amplification ke paas kuch grab karne ko nahi	Ex 4
C5	Smallest eigenvalue chahiye	inverse iteration, LU not $A^{- 1}$	Ex 5
C6	Interior / any eigenvalue	shifted inverse iteration	Ex 6
C7	Degenerate shift ( $σ = λ_{j}$ exactly)	$A - σ I$ singular	Ex 7
C8	Complex conjugate pair	real power method oscillate karta hai, koi limit nahi	Ex 8
C9	Real-world word problem	ek story ko eigenproblem mein translate karo	Ex 9
C10	Exam twist: rate prediction	convergence predict karo iterate karne se pehle	Ex 10
C11	Defective / repeated eigenvalue	$n$ se kam eigenvectors	Ex 11

Ex 1 — C1 · Baseline power method (positive gap)

True eigenvalues Characteristic Polynomial solve karte hain $det (A - λ I) = (4 - λ) (3 - λ) - 2 = λ^{2} - 7 λ + 10 = 0$ , isliye $λ = 5, 2$ . Hum $λ_{1} = 5$ aim kar rahe hain.

Index convention: $x_{k}$ woh vector hai jo $k$ steps ke baad milta hai ( $x_{0}$ seed hai), aur $μ_{k} = \frac{x _{k}^{⊤} A x _{k}}{x _{k}^{⊤} x _{k}}$ Rayleigh quotient hai jo usi same $x_{k}$ se bana hai.

$y_{1} = A x_{0} = (2 4)$ . Yeh step kyun? Ek multiply hi poora engine hai — $A$ vector ko apne sabse strong stretch ki taraf khichta hai. $∥ y_{1} ∥ = 20 = 4.472$ , isliye $x_{1} = (0.447 0.894)$ .
Seed se Rayleigh: $μ_{0} = \frac{x _{0}^{⊤} A x _{0}}{x _{0}^{⊤} x _{0}} = \frac{( 1 , 0 ) ( 2 4 )}{1} = 4$ . Kyun? $μ_{0}$ , $x_{0}$ use karta hai, isliye yeh hamara crude starting estimate hai — us vector ke liye least-squares eigenvalue.
$y_{2} = A x_{1} = (2 \cdot 0.894 + 3 \cdot 0.447 4 \cdot 0.894 + 0.447) = (3.130 4.024)$ , $5.098$ se normalize: $x_{2} = (0.614 0.789)$ . Ab $μ_{1} = x_{1}^{⊤} A x_{1} = (0.894, 0.447) (3.130 4.024) = 4.998$ . Kyun? $μ_{1}$ , $x_{1}$ use karta hai, jo already strongly $v_{1}$ ki taraf lean kar chuka hai, isliye estimate almost poori tarah $5$ tak jump karta hai.
Agli step: $μ_{2} = x_{2}^{⊤} A x_{2} = (0.789, 0.614) A (0.614 0.789) = 5.000$ (teen places tak), aur $x_{3} \approx (0.681 0.732)$ $v_{1}$ ki taraf drift karta rehta hai. Indexing kyun: har $μ_{k}$ apne $x_{k}$ ke saath pair hota hai, isliye hum $μ_{0}, μ_{1}, μ_{2}$ order mein report karte hain.

Verify: $λ = 5$ ke liye true $v_{1}$ : $(A - 5 I) v = 0 \Rightarrow - v_{1} + v_{2} = 0$ , isliye $v_{1} \propto (1 1) = (0.707 0.707)$ normalized. Hamara $x_{3}$ $(0.707 0.707)$ ki taraf drift kar raha hai. ✓ Aur $μ_{k} \to 5$ . ✓

Ex 2 — C2 · Dominant eigenvalue negative

Is page ke liye rounding rule: saare decimals teen places tak round kiye jaate hain, half upar.

$y_{1} = A x_{0} = (2 - 4)$ , $∥ y_{1} ∥ = 20 = 4.472$ , $x_{1} = (0.447 - 0.894)$ . Kyun? Standard iterate. Notice karo ki pehla component negative ho gaya.
$y_{2} = A x_{1} = (2 \cdot 0.447 - 4 \cdot ( - 0.894 )) = (0.894 3.576)$ , $∥ y_{2} ∥ = 3.686$ , $x_{2} = (0.243 0.970)$ . Sign note kyun karo? $- 4$ se multiply karna har step sign flip karta hai — $x_{k}$ $v_{1} = (0 1)$ ke along $+, -, +, -$ alternate karta hai.
Rayleigh signed value padhta hai: $μ_{2} = x_{2}^{⊤} A x_{2} = (- 4) (0.970)^{2} + 2 (0.243)^{2} = - 3.64$ . Quotient kyun phir bhi kaam karta hai: $x^{⊤} A x$ sign carry karta hai, isliye ek negative dominant eigenvalue correctly report hota hai chahe vector flip kare.

Verify: $v_{1} = (0 1)$ , $λ_{1} = - 4$ . $x_{k} \to \pm (0 1)$ aur $μ_{k} \to - 4$ . ✓

Ex 3 — C3 · Equal magnitude, opposite sign

$y_{1} = A x_{0} = (3 0) \Rightarrow x_{1} = (1 0)$ . Yeh kyun dekhein? Strict-gap assumption toot gayi hai, isliye "landslide" argument khatam hota hai.
$y_{2} = A x_{1} = (0 3) \Rightarrow x_{2} = (0 1) = x_{0}$ . Yeh kyun matter karta hai: hum waapas wahan hain jahan shuru kiya tha — vector $(0 1)$ aur $(1 0)$ ke beech forever oscillate karta hai, kabhi eigenvector par settle nahi hota.
$μ_{k} = x_{k}^{⊤} A x_{k} = 0$ har step (off-diagonal $A$ , axis vectors). $0$ kyun? Na axis vector eigenvector hai; do components $\pm 3$ kabhi separate nahi hote kyunki unke magnitudes tie karte hain.

Neeche ka figure exactly yahi iterates plot karta hai. Ise dekhein: coloured arrows $x_{0}, x_{1}, x_{2}, x_{3}$ sirf do dashed axes par land karte hain — yeh $(0 1)$ (lavender/butter) aur $(1 0)$ (coral/mint) ke beech hop karte hain aur kabhi true eigenvector lines (do grey dashed diagonals $v (+ 3)$ aur $v (- 3)$ ) ki taraf rotate nahi hote. Woh visual "trapped on the axes" isliye hai ki estimate stall hoti hai: seed exactly do eigenvectors ke beech mein baitha hai, isliye koi bhi use khich nahi sakta.

Figure — Eigenvalue computation — power method, inverse iteration

Verify: True eigenvectors $(1 1) / 2 (λ = 3)$ aur $(- 1 1) / 2 (λ = - 3)$ hain. Hamara seed $(0 1) = \frac{1}{2} (1 1) + \frac{1}{2} (- 1 1)$ ka $+ 3$ aur $- 3$ par equal weight hai, isliye woh kabhi separate nahi hote. ✓

Ex 4 — C4 · Bad seed ( $c_{1} = 0$ )

$y_{1} = A x_{0} = (2 0)$ , $x_{1} = (1 0)$ . Kyun? $c_{1} = 0$ hone se $v_{1}$ piece nahi hai jo $λ_{1}^{k}$ se multiply ho, isliye pehla component exactly $0$ forever rehta hai.
$μ_{k} = x_{k}^{⊤} A x_{k} = 2$ forever. Kyun: exact arithmetic mein iteration $v_{2}$ par trapped hai, subdominant $λ_{2} = 2$ report karta hai, $λ_{1} = 5$ nahi.
Rescue: seed perturb karo, $x_{0} = (1 ε)$ tiny $ε$ ke saath. Ab decomposition mein $c_{1} = ε \neq = 0$ hai; har step us weight ko $5$ se multiply karta hai doosre ke $2$ ke against — har step relative factor $5/2 = 2.5$ — isliye yeh grow karta hai aur eventually dominate karta hai.

Verify: Exact $x_{0} = (1 0)$ ke saath, $μ_{k} = 2$ (galat). $ε = 0.001$ ke saath, enough steps ke baad $μ_{k} \to 5$ . ✓

Ex 5 — C5 · Smallest eigenvalue via inverse iteration

$A y_{1} = x_{0}$ solve karo, yaani $(2113) y_{1} = (0 1)$ . Solve kyun, invert kyun nahi? Parent ka rule: solve, invert mat karo — $A$ ko LU-factor karo (dekho LU Decomposition) ek baar, phir har step cheap substitution hai. $det A = 5$ , isliye $y_{1} = \frac{1}{5} (- 1 3) = (- 0.2 0.6)$ .
Normalize: $∥ y_{1} ∥ = 0.632$ , $x_{1} = (- 0.316 0.949)$ . Kyun? Vector ko blow up hone se rokta hai jab small- $λ$ direction amplify hoti hai.
Original $A$ par Rayleigh: $μ_{1} = x_{1}^{⊤} A x_{1}$ . $A$ kyun, $A^{- 1}$ kyun nahi? Hume $A$ ka eigenvalue chahiye, aur eigenvectors shared hain. $A x_{1} = (0.0 1.582)$ roughly; $μ_{1} = (0.949) (1.582) + (- 0.316) (0) \approx 1.50$ .
Ek aur solve $μ \to 1.382$ push karta hai.

Verify: $λ = 1.382$ ke liye $v$ : $(A - 1.382 I) v = 0 \Rightarrow 0.618 v_{1} + v_{2} = 0$ , $v \propto (- 0.618 1) \to (- 0.526 0.851)$ normalized. Hamara $x_{1} = (- 0.316 0.949)$ already us taraf lean kar raha hai; $μ \to 1.382$ . ✓ (Compare karo Rayleigh Quotient Iteration se jo cubic speed ke liye har step $σ$ update karta hai.)

Ex 6 — C6 · Any interior eigenvalue via shift

$A - σ I = diag (3.1, 0.1, - 1.9)$ form karo. Shift kyun? Iske inverse ke eigenvalues $\frac{1}{λ - σ} = \frac{1}{3.1}, \frac{1}{0.1}, \frac{1}{- 1.9} = 0.32, 10, - 0.53$ hain. Middle direction ab huge value $10$ rakhti hai — yeh dominate karti hai.
$(A - σ I) y = x_{0}$ solve karo: component-wise $y = (\frac{0.577}{3.1}, \frac{0.577}{0.1}, \frac{0.577}{- 1.9}) = (0.186, 5.77, - 0.304)$ . Ek solve kyun kaafi hai: $v_{2}$ component $10$ se multiply hua, single step mein baaki sab ko dwarf kar diya.
Normalize ( $∥ y ∥ = 5.78$ ): $x_{1} = (0.032, 0.998, - 0.053)$ — essentially $(0, 1, 0)^{⊤}$ , middle eigenvector. Normalize kyun? Huge factor $10$ ne $y$ ko blow up kar diya; $∥ y ∥$ se divide karna ise unit length par rescale karta hai taaki agla step (aur Rayleigh quotient) numerically sane rahe.
$A$ par Rayleigh: $μ_{1} = x_{1}^{⊤} A x_{1} = 6 (0.032)^{2} + 3 (0.998)^{2} + 1 (0.053)^{2} \approx 2.99$ . Itna close kyun? Ek step, kyunki shift $λ = 3$ ke bilkul paas hai.

Verify: $v_{2} = (0, 1, 0)$ , $λ = 3$ . $x_{1} \to (0, 1, 0)$ aur $μ \to 3$ . ✓

Ex 7 — C7 · Degenerate shift ( $σ = λ_{j}$ exactly)

Pehle, convergence-rate formula yaad karo aur uske indices name karo. Shifted inverse iteration mein error har step se shrink hoti hai: $\frac{λ _{j} - σ}{λ _{m} - σ},$ jahan $λ_{j}$ target eigenvalue hai (woh jo $σ$ ke sabse paas hai, jiska eigenvector hume chahiye) aur $λ_{m}$ $σ$ ke second-closest eigenvalue hai (sabse slow-decaying leftover). Yeh sirf parent ka power-method rate $∣ λ_{2} / λ_{1} ∣$ hai, transformed matrix $(A - σ I)^{- 1}$ par apply hota hai jiske eigenvalues $\frac{1}{λ _{i} - σ}$ hain: biggest $\frac{1}{λ _{j} - σ}$ hai, next biggest $\frac{1}{λ _{m} - σ}$ hai, aur unka ratio boxed expression hai.

$A - 3 I = diag (3, 0, - 2)$ . Singular kyun? Middle diagonal entry $0$ hai (woh hai $λ_{j} - σ = 3 - 3$ ), isliye $det = 3 \cdot 0 \cdot (- 2) = 0$ — koi inverse nahi, linear solve ka koi unique answer nahi.
Rate $\frac{λ _{j} - σ}{λ _{m} - σ} = \frac{0}{∣1 - 3∣} = 0$ kehta hai "zero steps mein converge karo". Yahan rate kyun compute karo? Yeh "secretly good news" quantify karta hai: $0$ ka rate matlab method instantly answer dena chahta hai — singularity ideal limit hai, failure nahi — lekin exact-zero denominator entry system ko as written unsolvable banata hai.
Practical fix: $σ = 3 \pm 1 0^{- 6}$ par back off karo. Yeh kyun kaam karta hai: ab $A - σ I$ invertible hai lekin nearly singular, middle direction $\sim 1 0^{6}$ se amplify hoti hai, aur — remarkably — near-singularity harmless hai: error vector $v_{2}$ ke saath align karta hai, exactly wahi jo hum chahte hain.

Verify: $det (A - 3 I) = 0$ (singular), jabki $det (A - 2.999999 I) \neq = 0$ . ✓

Ex 8 — C8 · Complex conjugate pair

$y_{1} = A x_{0} = (1 0)$ , $x_{1} = (1 0)$ . Kyun? $A$ $9 0^{\circ}$ rotate karta hai; seed bas turn karta hai.
$y_{2} = A x_{1} = (0 - 1)$ , $x_{2} = (0 - 1)$ . Phir $x_{3} = (- 1 0)$ , $x_{4} = (0 1) = x_{0}$ . Cycle kyun karta hai: ek rotation ka koi real eigenvector nahi hota, isliye power method ko lock karne ke liye koi real direction nahi hai — vector period 4 ke saath loop karta hai.
$μ_{k} = x_{k}^{⊤} A x_{k} = 0$ always (rotation $x ⊥ A x$ bhejta hai). $0$ kyun: $x^{⊤} (A x)$ ek vector aur uske $9 0^{\circ}$ turn ka dot product hai — always zero.

Figure yeh spin dikhata hai. Ise dekhein: chaar coloured arrows $x_{0}, x_{1}, x_{2}, x_{3}$ unit circle par ek quarter-turn apart baithe hain, aur annotation "+90 deg each step" rotation trace karta hai; chaar hops ke baad hum $x_{0}$ par waapis hain. Koi bhi arrow kisi fixed line ki taraf drift nahi kar raha — visual proof ki koi real eigenvector exist nahi karta jis par converge kiya ja sake.

Verify: $(01 - 1 0)$ ke eigenvalues $\pm i$ hain, dono $∣ λ ∣ = 1$ , koi real gap nahi. $A^{4} = I$ isliye $x_{4} = x_{0}$ . ✓

Ex 9 — C9 · Word problem (PageRank-style)

$y_{1} = M x_{0}$ . Columns sum $1$ karte hain, isliye multiply karna importance redistribute karta hai. $y_{1} = (\frac{1}{3}, \frac{1}{6}, \frac{1}{2})$ . $M$ sahi operator kyun hai: ek page ki importance = links ke through aane wali importances ka sum, jo exactly ek matrix–vector product hai.
$∥ \cdot ∥_{1}$ se normalize karo; $y_{1}$ already $1$ sum karta hai. Iterate karo: $y_{2} = M y_{1} = (0.5, 0.167, 0.333)$ ; $y_{3} = M y_{2} = (0.333, 0.25, 0.417)$ .
Vector ko eigenvector ki taraf settle hote dekhein, aur $λ_{1} = 1$ padh lo. $λ_{1} = 1$ kyun guaranteed hai: column sums $= 1$ matlab $1^{⊤} M = 1^{⊤}$ (all-ones row-vector eigenvalue $1$ ke liye left eigenvector hai), eigenvalue $1$ force karta hai; Perron–Frobenius theorem ise dominant banata hai. Isliye power method yahan converge karta hai, aur limiting Rayleigh quotient $1$ ke barabar hota hai.
Fixed point: $x = M x$ directly solve karo. Row 1 se, $x_{1} = x_{3}$ ; row 2 se, $x_{2} = 0.5 x_{1}$ ; row 3 se, $x_{3} = 0.5 x_{1} + x_{2} = x_{1}$ ✓. Isliye $x = (2, 1, 2)$ scale tak → $∥ \cdot ∥_{1}$ se normalize karo (sum $= 5$ ) to $(0.4, 0.2, 0.4)$ .

Conclusion: Steady importances $(0.4, 0.2, 0.4)$ hain — pages 1 aur 3 most important ke liye tie karte hain, page 2 least hai. Hamara forecast (page 3 top par) almost sahi tha: yeh lead ke liye tie karta hai.

Verify: $M (0.4, 0.2, 0.4)^{⊤} = (0.4, 0.2, 0.2 + 0.2) = (0.4, 0.2, 0.4)$ . ✓ Eigenvalue $= 1$ , importances sum $1$ karte hain. ✓

Ex 10 — C10 · Exam twist: predict the rate before iterating

Power method error factor per step $r = \frac{λ _{2}}{λ _{1}} = \frac{9}{10} = 0.9$ . Yeh ratio kyun: parent ne dikhaya tha surviving decay term $(λ_{2} / λ_{1})^{k}$ hai. $0. 9^{k} \leq 1 0^{- 3}$ chahiye.
Solve karo: $k \geq \frac{ln 1 0 ^{- 3}}{ln 0.9} = \frac{- 6.908}{- 0.10536} = 65.6 \Rightarrow k = 66$ steps. Log kyun: $0.9$ ko ek power tak raise karna ek target hit karne ke liye $ln$ se invert hota hai. (Dekho Convergence Rates.)
Shift-invert rate: $(A - σ I)^{- 1}$ ke eigenvalues ke sizes $\frac{1}{∣ λ - σ ∣}$ hain. Ex 7 formula use karte hue target $λ_{j} = 9$ aur second-closest $λ_{m} = 10$ ke saath: distances $∣9 - 9.1∣ = 0.1$ aur $∣10 - 9.1∣ = 0.9$ , isliye rate $= \frac{∣ λ _{j} - σ ∣}{∣ λ _{m} - σ ∣} = \frac{0.1}{0.9} = 0.111$ .
$0.11 1^{k} \leq 1 0^{- 3}$ chahiye: $k \geq \frac{- 6.908}{ln 0.111} = \frac{- 6.908}{- 2.198} = 3.14 \Rightarrow k = 4$ steps.

Verify: $0. 9^{66} = 9.1 \times 1 0^{- 4} \leq 1 0^{- 3}$ ✓; $0. 9^{65} = 1.0 \times 1 0^{- 3}$ (just above) isliye $66$ correct hai. $0.11 1^{4} = 1.5 \times 1 0^{- 4} \leq 1 0^{- 3}$ ✓, $0.11 1^{3} = 1.4 \times 1 0^{- 3}$ (too big) isliye $4$ correct hai. 66 vs 4 — ek achhe shift se $16 \times$ speedup. ✓

Ex 11 — C11 · Defective / repeated eigenvalue

Eigen-check: $(A - 3 I) = (0010)$ ka one-dimensional nullspace $v_{1} = (0 1)$ hai. "Defective" kyun: algebraic multiplicity $2$ lekin geometric multiplicity $1$ — ek eigenvector short, isliye $A$ not diagonalizable hai aur Spectral Decomposition apply nahi hota; iske bajaye aap Jordan form use karte ho.
$y_{1} = A x_{0} = (3 1)$ , $x_{1} = (0.949 0.316)$ . $y_{2} = A x_{1} = (3 \cdot 0.949 0.316 + 0.949) = (2.846 1.265)$ , $x_{2} = (0.914 0.406)$ . Drift kyun? Har multiply off-diagonal $1$ ke through thoda $v_{1}$ feed karta hai; pehla component grow karta hai.
$y_{3} = A x_{2} = (3 \cdot 0.914 0.406 + 0.914) = (2.742 1.320)$ , $x_{3} = (0.901 0.434)$ — $v_{1} = (0 1)$ ki taraf creep kar raha hai, lekin slowly. Slow kyun: equal eigenvalues ke saath koi ratio $∣ λ_{2} / λ_{1} ∣ < 1$ nahi hai fast decay drive karne ke liye; convergence sirf algebraic hai (like $1/ k$ ), geometric nahi. Dekho Convergence Rates.
Rayleigh: $μ_{2} = x_{2}^{⊤} A x_{2} = 3 (0.406)^{2} + 2 (0.406) (0.914) + 3 (0.914)^{2} = 3.742$ . Yeh overshoot karta hai phir $3$ par settle hota hai jab $x_{k} \to (0 1)$ .

Verify: $A = (3013)$ ka single eigenvalue $3$ hai (multiplicity $2$ ), ek eigenvector $(0 1)$ ; $μ_{k} \to 3$ aur $x_{k} \to (0 1)$ . ✓

Recall Scenario checklist (self-test)

Har symptom ko uske fix se match karo. Vector har step sign flip karta hai ::: Dominant eigenvalue negative hai — signed Rayleigh quotient padho (Ex 2). Vector cycle karta hai, kabhi settle nahi hota, real matrix ::: Ya toh tie $λ_{1} = - λ_{2}$ (break karne ke liye shift, Ex 3) ya complex pair (QR use karo, Ex 8). Estimate wrong (smaller) eigenvalue par stuck hai ::: Bad seed with $c_{1} = 0$ ; $x_{0}$ perturb karo (Ex 4). Smallest eigenvalue chahiye ::: Inverse iteration — LU-solve, invert mat karo (Ex 5). Interior eigenvalue chahiye ::: Uske paas shift karo, phir inverse iterate karo (Ex 6). Linear solve "singular" keh raha hai ::: $σ$ exactly ek eigenvalue hit kar gaya; $σ$ ko $\pm 1 0^{- 6}$ nudge karo (Ex 7). Convergence painfully slow, single eigenvalue ::: Defective/repeated eigenvalue — sirf algebraic decay; QR use karo (Ex 11).