Eigenvalue computation — power method, inverse iteration: Visual walkthrough

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

Step 1 — Matrix ek arrow ke saath kya karta hai

KYA. Ek matrix $A$ ek machine hai: isme ek arrow (ek vector) daalo, wo doosra arrow nikalta hai. Zyaadatar ye arrow ko ghoomata bhi hai aur uski length bhi badal deta hai.

HUM KYUN CARE KARTE HAIN. Eigenvectors wo khaas arrows hain jinhein machine bilkul nahi ghomaati — wo sirf unhe stretch ya shrink karti hai. Agar hum unhe dhundh lein, toh hum machine ko poori tarah samajh lete hain.

PICTURE. Figure mein grey arrows ordinary inputs hain — har output (dashed) apne input se alag direction mein point karta hai. Lekin do coloured arrows same direction mein wapas aate hain, sirf lambe ya chhote hote hain. Ye hi eigenvectors hain.

Figure — Eigenvalue computation — power method, inverse iteration

$λ$ 1 se bada ho sakta hai (stretch), 0 aur 1 ke beech ho sakta hai (shrink), ya negative ho sakta hai (flip aur stretch). Hum ye sab dekhenge.

Step 2 — Eigenvectors ko strength ke hisaab se line up karo

KYA. Maano hamare $n \times n$ matrix $A$ mein $n$ eigenvectors $v_{1}, \dots, v_{n}$ hain, har eigenvalue ke liye ek. Hum eigenvalues ko size ke hisaab se sort karte hain, sabse bada pehle: $∣ λ_{1} ∣ > ∣ λ_{2} ∣ \geq \dots \geq ∣ λ_{n} ∣.$

Absolute value $∣ \cdot ∣$ kyun? Kyunki hum care karte hain kitna arrow stretch hota hai, na ki wo kis taraf flip hota hai. $- 4$ ka stretch factor ek arrow ko utna hi kheenchta hai jitna $+ 4$ ; length $∣ - 4 ∣ = 4$ se multiply hoti hai chahe kuch bhi ho. $∣ λ ∣$ raw stretching power ko measure karta hai.

Shuruaat mein strict $>$ kyun. Hum demand karte hain ki $∣ λ_{1} ∣$ strictly sabse bada ho — pehle place ke liye koi tie nahi. Wo akela champion dominant eigenvalue hai, aur $v_{1}$ dominant eigenvector hai. Step 5 mein hum dekhenge exactly kyun tie method ko tod deti hai.

PICTURE. Ek "stretch-strength" bar chart: sabse ooncha bar $∣ λ_{1} ∣$ hai, akela baaki sab se upar khada hai. Har chhota bar ek kamzor direction hai jo ye race haar jaayegi.

Step 3 — Blend ko machine mein EK BAAR daalo

KYA. Poore mix pe $A$ apply karo. Matrix-times-a-sum sum ke across split ho jaata hai, aur har eigenvector $A v_{i} = λ_{i} v_{i}$ maanta hai: $A x_{0} = c_{1} v_{1} scaled by λ_{1} (λ_{1} v_{1}) + c_{2} v_{2} scaled by λ_{2} (λ_{2} v_{2}) + \dots + c_{n} (λ_{n} v_{n}) .$

YE KEY SIMPLIFICATION KYUN HAI. Humein actually kuch ghoomaana nahi pada. Kyunki har ingredient ek eigenvector hai, machine sirf har ingredient ko independently uske apne $λ_{i}$ se rescale karti hai. Mushkil matrix multiply $n$ aasaan number multiplies ban jaata hai.

PICTURE. Do ingredients andar jaate hain (ek lamba $v_{1}$ -part, ek chhota $v_{2}$ -part). Ek pass ke baad, $v_{1}$ -part $λ_{1}$ factor se badh gaya hai, $v_{2}$ -part chhote $λ_{2}$ se. Blended arrow already $v_{1}$ ki taraf jhuk gaya hai.

Step 4 — Isse $k$ baar daalo: ratios appear hote hain

KYA. Baar baar karo. Har pass ingredient $i$ ko $λ_{i}$ se ek baar aur multiply karta hai, toh $k$ passes ke baad har ek ko $k$ baar hit kiya ja chuka hai: $A^{k} x_{0} = c_{1} λ_{1}^{k} v_{1} + c_{2} λ_{2}^{k} v_{2} + \dots + c_{n} λ_{n}^{k} v_{n} .$

$A^{k}$ matlab hai "machine ko $k$ baar apply karo".
$λ_{i}^{k}$ stretch factor hai $k$ -th power tak uthaya hua — repeated stretching interest ki tarah compound hoti hai.

Ab crucial move: champion ke factor $λ_{1}^{k}$ ko aage nikaal lo. $A^{k} x_{0} = λ_{1}^{k} [c_{1} v_{1} + c_{2} (\frac{λ _{2}}{λ _{1}})^{k} v_{2} + \dots + c_{n} (\frac{λ _{n}}{λ _{1}})^{k} v_{n}] .$

Bracket ke bahar: $λ_{1}^{k}$ , ek giant overall scaling jo hum baad mein normalize karke cancel kar lenge.
Andar: $c_{1} v_{1}$ untouched baitha hai, lekin har doosre term pe ab ek ratio $(\frac{λ _{i}}{λ _{1}})^{k}$ hai.

$λ_{1}^{k}$ kyun factor out karo aur $λ_{2}^{k}$ ya kuch nahi kyun? Kyunki hum har direction ko champion ke against compare karna chahte hain. Har stretch ko sabse bade stretch se divide karne se absolute sizes fairness ratio ban jaati hain: "runner-up $i$ winner ke against kaise measure karta hai?" Wahi ratio race decide karta hai.

PICTURE. Equation ek stack of terms ki tarah redraw ki gayi; $c_{1} v_{1}$ term solid aur full-height hai, har doosra term apne shrinking ratio label ke saath tagged hai.

Step 5 — Kyun har loser fade hota hai: ratio powers mar jaate hain

KYA. Har $i \geq 2$ ke liye humne sort kiya ki $∣ λ_{i} ∣ < ∣ λ_{1} ∣$ . Isliye $\frac{λ _{i}}{λ _{1}} < 1 ⟹ \frac{λ _{i}}{λ _{1}}^{k} k \to \infty 0.$

KYUN. Size mein 1 se chhota number, khud se baar baar multiply hoke, zero ho jaata hai — jaise ek kaagaz ko baar baar aadha modhna, uski thickness original ka fraction zero ho jaati hai. Toh bracket ke andar $c_{1} v_{1}$ ke alawa har term pighal jaata hai: $\frac{A ^{k} x _{0}}{λ _{1}^{k}} ⟶ c_{1} v_{1} .$ Poora iterated arrow $v_{1}$ direction mein point karta hai. Sabse zyada stretch hone wali direction landslide se jeetti hai.

PICTURE. Ratios $r_{i} = ∣ λ_{i} / λ_{1} ∣$ ko step $k$ ke against decaying curves $r_{i}^{k}$ ke roop mein plot kiya gaya. Saari curves floor ki taraf dive karti hain; 1 ke sabse kareeb wali curve sabse dheere dive karti hai — wo hai runner-up $r_{2}$ , aur wo pace set karta hai.

Common mistake Do tarike jisme ye ruk sakta hai

Trap A — koi champion nahi (ek tie). Agar $∣ λ_{2} ∣ = ∣ λ_{1} ∣$ toh $∣ λ_{2} / λ_{1} ∣ = 1$ ; uski power kabhi nahi shrink hoti. Do directions kabhi alag nahi hote, toh arrow unke beech wobble karta rehta hai aur kabhi settle nahi hota. Kyun theek lagta hai: algebra abhi bhi chalta hai. Fix: method ko strict gap $∣ λ_{1} ∣ > ∣ λ_{2} ∣$ chahiye; ties (ya ek complex conjugate pair) ko shifts ya block methods chahiye. Trap B — tumne $c_{1} = 0$ se shuru kiya. Agar tumhara seed $x_{0}$ mein $v_{1}$ ingredient zero hai, toh $v_{1}$ ke along amplify karne ke liye kuch nahi hai — bracket mein survive karne ke liye koi $c_{1} v_{1}$ term hi nahi hai. Exact arithmetic mein ye fail hota hai. Practice mein, ek random seed mein almost certainly $c_{1} \neq = 0$ hota hai, aur rounding noise bhi ek tiny $v_{1}$ crumb re-inject karta hai jo phir grow karta hai.

Step 6 — Degenerate sign: agar $λ_{1}$ negative ho toh?

KYA. Maano champion negative hai, jaise $λ_{1} = - 4$ . Toh $λ_{1}^{k} = (- 4)^{k}$ har step sign flip karta hai: $- 4, + 16, - 64, \dots$

YE PHIR BHI KYUN KAAM KARTA HAI. Humne sirf direction ki parwah ki, aur $v_{1} \to - v_{1}$ ka flip ek hi line hai, bas doosri taraf point kar raha hai. Toh normalized arrow $+ v_{1}$ aur $- v_{1}$ ke beech alternate karta hai — ye abhi bhi $v_{1}$ axis pe lock ho jaata hai, bas arrowhead ping-pong karta hai.

PICTURE. Seed arrow steps $k = 1, 2, 3, 4$ pe dikhaya gaya: ye $v_{1}$ line pe snap karta hai lekin alternate head-forward / head-backward karta hai. Line mil gayi; sirf arrowhead ka side oscillate karta hai.

Step 7 — Convergence speed ek do-ghodi ki race hai

KYA. Champion ke baad, sabse dheere marne wala term runner-up $v_{2}$ hai, kyunki $r_{2} = ∣ λ_{2} / λ_{1} ∣$ 1 ke sabse kareeb ratio hai. Direction mein error aisa shrink hota hai: $error_{k} \propto \frac{λ _{2}}{λ _{1}}^{k} .$ Yahi linear convergence hai: har step error ko same fixed factor $r_{2}$ se multiply karta hai.

GAP KYUN MATTER KARTA HAI. Agar $λ_{2}$ $λ_{1}$ se bahut neeche hai (chhota $r_{2}$ ), error jaldi collapse ho jaata hai — thode steps. Agar $λ_{2}$ almost $λ_{1}$ ke barabar hai (r_2 1 ke kareeb), har step barely help karta hai — bahut dheema. Poori speed ek cheez pe hinge karti hai: top two eigenvalues ke beech ka gap.

PICTURE. Do seeds convergence tak run karte hain: ek matrix big gap ke saath ( $r_{2} = 0.2$ , error crash down ho jaata hai), ek small gap ke saath ( $r_{2} = 0.9$ , error crawl karta hai). Same method, wildly different pace.

Recall Aur zyada is par

Yahan linear rate hi wajah hai kyun shifting aur inverse iteration exist karte hain — wo jaanboojhkar ek bada gap manufacture karte hain. Linear speed ko peetchhne wale methods ke liye Rayleigh Quotient Iteration aur QR Algorithm notes dekho. Poori tarah mein use ki gayi eigen-ingredients mein clean split exactly ek Spectral Decomposition hai; $λ_{i}$ ki sorting Characteristic Polynomial se aati hai jiske roots ye hain.

Ek-picture summary

Ek frame mein poori kahani: ek seed arrow $x_{0}$ eigen-ingredients ka mix hai; $A$ se har pass champion $v_{1}$ ko sabse zyada scale karta hai, toh kuch passes ke baad (normalized) arrow $v_{1}$ line pe swing ho jaata hai — jabki runner-up ratio $r_{2} = ∣ λ_{2} / λ_{1} ∣$ quietly set karta hai ki ye swing kitni fast hoti hai.

Recall Feynman retelling — poora walkthrough plain words mein

Ek stretchy rubber sheet imagine karo jisme kuch secret "stretch lines" hain. Zyaadatar directions mein ek dot ko push karne se wo drag bhi hota hai aur uski heading bhi twist hoti hai. Lekin secret lines ke along sirf stretch hota hai — koi twist nahi. Wo eigenvectors hain, aur har ek kitna hard stretch karta hai wo uska eigenvalue hai.

Koi bhi starting dot lo. Uske arrow ko tod do ki har secret line ka kitna-kitna is mein hai. Ab ise sheet ke through baar baar push karo. Har push har ingredient ko uske apne stretch se multiply karta hai. Sabse strong stretch line sabse hard kheenchti hai, toh kuch pushes ke baad dot almost exactly us ek line ke saath slide kar raha hota hai — har doosra ingredient kuch nahi reh jaata kyunki ek fraction-under-one, khud se kai baar multiply hoke, ghayab ho jaata hai.

Do cheezein ise kharab kar sakti hain: agar do lines equally hard stretch karti hain toh koi clear winner nahi hota aur dot kabhi settle nahi hota; aur agar tumhara starting dot strongest line ka zero hai, toh amplify karne ke liye kuch nahi (halaanki noise ka ek speck usually tumhein bacha leta hai). Agar sabse strong stretch negative hai, dot abhi bhi line dhundh leta hai — bas har push side-to-side flip karta hai. Aur ye saari cheez ek number pe depend karti hai slow ya fast hone ke liye: runner-up ka stretch champion ke kitna kareeb hai. Bada gap, fauran jawaab; near tie, bahut dheema. Wo top two stretches ke beech ki akeli race power method ka dhadakta dil hai.