Eigenvalue computation — power method, inverse iteration: Exercises

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

Poore page mein hamaari workhorse matrix yeh hai: $A = (2113), λ_{1, 2} = \frac{5 \pm 5}{2} \approx 3.6180, 1.3820.$ Ise hum baar baar use karte hain taaki tum usi matrix ko alag-alag sawalon ka jawab dete dekh sako.

Shuru karne se pehle, plain words mein chaar reminders:

Ek eigenpair $(λ, v)$ satisfy karta hai $A v = λ v$ : matrix sirf $v$ ko stretch karti hai, kabhi rotate nahi karti. Dekho Spectral Decomposition.
Identity matrix $I$ ek "kuch-nahi-karta" matrix hai: $I v = v$ har vector $v$ ke liye (2D mein, $I = (1001)$ ). Humein yeh isliye chahiye kyunki " $A$ minus ek number $σ$ " ka koi matlab nahi — tum ek number ko ek matrix se subtract nahi kar sakte — isliye hum $σ$ ke copies of the do-nothing matrix subtract karte hain, likha jaata hai $A - σ I$ , jiska seedha matlab hai "har diagonal entry se $σ$ subtract karo."
Kisi vector $x$ ka Rayleigh quotient yeh number hai $μ = \frac{x ^{⊤} A x}{x ^{⊤} x}$ — isko aise padho: "agar $x$ ek eigenvector hota, toh uska stretch factor kya hota?" Dekho Rayleigh Quotient Iteration.
Normalize ka matlab hai: ek vector ko uski length $∥ x ∥ = x_{1}^{2} + x_{2}^{2} + \dots$ se divide karo taaki uski length $1$ ho jaaye. Hum yeh har step pe karte hain taaki numbers explode na karein.

Poora page ek picture mein. Algebra se pehle, us geometry ko dekho jisme yeh exercises rehte hain. Neeche ka figure hamaara unit vector dikhata hai jo $x_{0} = (0 1)$ se shuru hota hai (seedha daayein point karta hua) aur step by step red dominant-eigenvector line ki taraf swing karta hai. Dashed quarter-circle unit vectors ka set hai (length exactly 1), aur angle marks $θ_{k}$ dikhate hain ki har step red line se angle ko kitna kam karta hai. Har L1–L3 exercise basically yeh sawaal hai: "kaali arrow red line tak kitni tezi se pahunchi, aur main stretch factor ko usse kaise padhunga?" Jab tum calculate karo toh yeh picture dimag mein rakhna.

Figure — Eigenvalue computation — power method, inverse iteration

Do cheezein notice karo jo tum baad mein numerically verify karoge: (1) har kaali arrow pichli wali se red line ke zyada paas padti hai, aur (2) consecutive arrows ke beech ke gaps chhote hote jaate hain — woh shrinking hi Exercise 3.1 ka linear convergence hai.

L1 — Recognition

Exercise 1.1 (L1)

Inn vectors mein se kaun sa $A = (2113)$ ka eigenvector hai, aur kis eigenvalue ke saath? $u = (0 1), w = (1.618 1) .$

Recall Solution 1.1

WHAT karna hai: ek eigenvector woh hai jahan $A v$ sirf $v$ ka ek plain multiple aata hai — same direction, bas scaled.

$u$ test karo: $A u = (2113) (0 1) = (1 2)$ . Kya $(1 2)$ , $(0 1)$ ka multiple hai? Nahi — doosri entry $0$ se $1$ ho gayi. Isliye $u$ eigenvector NAHI hai.

$w$ test karo: $A w = (1 \cdot 1 + 3 \cdot 1.618 2 \cdot 1 + 1 \cdot 1.618) = (5.854 3.618)$ . Kya yeh $(1.618 1)$ ka multiple hai? Pehli entries ka ratio check karo: $3.618/1 = 3.618$ . Doosra check karo: $5.854/1.618 = 3.618$ . Same factor → haan! $A w = 3.618 w$ .

Answer: $w$ ek eigenvector hai eigenvalue $\approx 3.618 = λ_{1}$ ke saath; $u$ nahi hai.

Exercise 1.2 (L1)

Power method $A v = λ v$ ko $A^{- 1} v = ? v$ aur $(A - σ I) v = ? v$ mein convert karta hai. Blanks ko words mein bharo.

Recall Solution 1.2

$A v = λ v$ se shuru karo.

Dono sides ko $A^{- 1}$ se multiply karo: $v = λ A^{- 1} v$ , isliye $A^{- 1} v = \frac{1}{λ} v$ . Eigenvector unchanged rehta hai; eigenvalue flip hokar $1/ λ$ ho jaata hai.
$A v = λ v$ se $σ v$ subtract karo: $(A - σ I) v = (λ - σ) v$ (yaad raho $I$ do-nothing matrix hai, isliye $σ I v = σ v$ ). Eigenvector unchanged; eigenvalue $- σ$ se slide karta hai.

Yeh single fact — eigenvectors dono operations mein survive karte hain, eigenvalues predictably transform hote hain — inverse aur shifted iteration ka poora engine hai.

L2 — Application

Exercise 2.1 (L2)

$A$ pe $x_{0} = (0 1)$ se do power-method steps chalao. $x_{1}, x_{2}$ (normalized) aur Rayleigh estimates $μ_{0}, μ_{1}, μ_{2}$ report karo, consistent rule $μ_{k} = x_{k}^{⊤} A x_{k}$ use karke (har $x_{k}$ ki length 1 hai).

Recall Solution 2.1

Convention (inconsistency theek karna): Rayleigh estimate usi normalized vector se belong karta hai jo hum abhi hold kar rahe hain. Isliye $μ_{k} = x_{k}^{⊤} A x_{k}$ same index $k$ ke liye. Hum ek $μ$ per vector report karte hain: $μ_{0}$ for $x_{0}$ , $μ_{1}$ for $x_{1}$ , $μ_{2}$ for $x_{2}$ .

WHY har Rayleigh quotient se pehle normalize karein: do reasons. (1) Numbers tame rehte hain. Rescaling ke bina, $A^{k} x_{0}$ grow karta hai $λ_{1}^{k} \approx 3.61 8^{k}$ jaisa aur overflow ho jaata hai; length $∥ y_{k} ∥$ se divide karne se har $x_{k}$ unit circle pe rehta hai. (2) Quotient formula simple ho jaata hai. Jab $∥ x_{k} ∥ = 1$ hota hai toh denominator $x_{k}^{⊤} x_{k} = 1$ , isliye $μ_{k} = x_{k}^{⊤} A x_{k}$ mein koi division nahi lagti — jo number tum compute karte ho wahi estimate hai.

WHY Rayleigh quotient dominant eigenvalue pe converge karta hai: jaise kaali arrow red line ki taraf swing karti hai (shuruwaat ka figure dekho), $x_{k} \to v_{1}$ , isliye $A x_{k} \to λ_{1} x_{k}$ . Isse quotient mein dalo: $μ_{k} = x_{k}^{⊤} A x_{k} \to x_{k}^{⊤} (λ_{1} x_{k}) = λ_{1} (x_{k}^{⊤} x_{k}) = λ_{1}$ . Isliye arrow jitna zyada red ke paas hoga, $μ_{k}$ utna hi $λ_{1} = 3.618$ ke paas hoga — jo exactly woh monotone climb hai $2.00 \to 3.00 \to 3.50$ jo hum neeche compute karte hain.

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

Step 1 — WHAT karte hain: $A$ lagao, phir length 1 pe rescale karo. WHY: $A$ vector ko dominant direction ki taraf tilt karta hai; rescaling growth ko remove karta hai taaki sirf direction bachti hai. $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}$ : pehle $A x_{1} = (0.8944 + 3 ( 0.4472 ) 2 ( 0.8944 ) + 0.4472) = (2.2361 2.2361)$ , phir $μ_{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)$ , phir $μ_{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)$ , aur $μ_{0} = 2.00, μ_{1} = 3.00, μ_{2} = 3.50$ — ek clean monotone climb $λ_{1} = 3.618$ ki taraf.

Exercise 2.2 (L2)

Chhoti eigenvalue target karte hue ek shifted-inverse step karo: $σ = 1.3$ , $x_{0} = (0 1)$ . $(A - σ I) y = x_{0}$ solve karo, normalize karo, aur Rayleigh estimate do.

Recall Solution 2.2

WHAT karna hai: unknown $y$ ke liye linear system $(A - σ I) y = x_{0}$ solve karo — inverse matrix mat banao. Yahi LU Decomposition ka message hai: $M y = x_{0}$ ke liye $y$ find karne ke liye, $M$ ko ek baar factor karo aur forward/back-substitution chalao, kabhi $M^{- 1}$ mat banao.

System set up karo. Yahan $M = A - σ I = (0.7 1 1 1.7)$ (har diagonal entry se $σ = 1.3$ subtract karo — yahi $- σ I$ karta hai). Hum solve karte hain: $(0.7 1 1 1.7) (y _{2} y _{1}) = (0 1) .$ Elimination se solve karo (yahi LU under the hood karta hai). Row 1 se: $0.7 y_{1} + y_{2} = 1$ . Row 2 se: $y_{1} + 1.7 y_{2} = 0$ , yaani $y_{1} = - 1.7 y_{2}$ . Row 1 mein substitute karo: $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$ . Toh $y = (- 5.263 8.947)$ — kabhi $M^{- 1}$ compute kiye bina mila, exactly jaise preached.

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

Answer: $x_{1} \approx (0.862, - 0.507)$ , $μ \approx 1.383$ — practically $λ_{2} = 1.382$ ek hi step mein.

L3 — Analysis

Exercise 3.1 (L3)

Hamare $A$ ke liye, power-method error $r^{k}$ ki tarah shrink hoti hai jahan $r = ∣ λ_{2} / λ_{1} ∣$ . $r$ compute karo. Error ko $1000$ ke factor se cut karne ke liye kitne steps chahiye? Isse shuruwaat ke figure mein shrinking arrow-gaps se relate karo.

Recall Solution 3.1

WHY yeh ratio: derivation $λ_{1}^{k}$ ko factor out karta hai, bacha hua component $(λ_{2} / λ_{1})^{k}$ se scale hota hai. Woh bacha hua error hi hai, isliye $k$ steps ke baad uski size $r^{k}$ hai. Dekho Convergence Rates. $r = \frac{1.3820}{3.6180} = 0.3820.$ Humein chahiye $r^{k} \leq 1 0^{- 3}$ . Log lo (log = "mujhe kitni baar multiply karna hoga yahan pahunchne ke liye?"): $k \geq \frac{l n ( 1 0 ^{- 3} )}{l n ( 0.3820 )} = \frac{- 6.9078}{- 0.9622} = 7.18.$ Answer: $r \approx 0.382$ ; teen decimal digits gain karne ke liye roughly $k = 8$ steps. Yeh linear convergence hai — har digit ke liye steps ki fixed number. Shuruwaat ke figure mein, yahi $r = 0.382$ explain karta hai ki har kaali arrow ka red line se angular gap $\sim 0.382$ times pichle gap ke barabar hota hai — arrows visibly red line ke against pile up hoti hain.

Exercise 3.2 (L3)

$λ_{2} = 1.382$ ko target karte hue $σ = 1.3$ ke saath shifted inverse iteration ke liye, rate hai $\frac{λ _{2} - σ}{λ _{1} - σ}$ . Ise compute karo aur Exercise 3.1 se contrast karo.

Recall Solution 3.2

WHY yeh do gaps: shifting aur inverting ke baad, target eigenvalue $λ_{2}$ bada wala $\frac{1}{λ _{2} - σ}$ ban jaata hai, aur nearest competitor $λ_{1}$ hai (doosra sirf ek eigenvalue). Rate "distance to target" aur "distance to competitor" ka ratio hai: $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$ — ek step mein hi $\sim 1.5$ digits gain ho jaate hain, plain power method ke $0.382$ ke comparison mein. $σ$ ko target ke paas choose karna hi inverse iteration ko explosive banata hai: $∣ λ_{2} - σ ∣$ shrink karo aur rate plummet kar jaata hai.

L4 — Synthesis

Exercise 4.1 (L4)

$A$ ka dominant eigenvector $v_{1} \propto (1.618 1)$ hai. Doosra eigenvector $v_{2} \propto (- 0.618 1)$ hai ( $λ_{2} = 1.382$ ka eigenvector). Maano main power method seed $x_{0} = (- 0.618 1)$ se shuru karta hoon — yaani exactly $v_{2}$ direction se. Exact arithmetic mein, power method kahan converge karega, aur kyun? Real computation mein kya rescue karta hai? Shuruwaat ke figure ki geometry use karke explain karo.

Recall Solution 4.1

Check karo ki seed sach mein $v_{2}$ hai: $A (- 0.618 1) = (1 - 1.854 2 - 0.618) = (- 0.854 1.382)$ . Kya woh $λ_{2} (- 0.618 1)$ hai? Compute karo $1.382 \cdot (- 0.618 1) = (- 0.854 1.382)$ . Exact match — isliye $x_{0}$ genuinely $v_{2}$ direction mein hai, $v_{1}$ ke saath zero component ke saath, yaani $c_{1} = 0$ .

WHY yeh fail karta hai: derivation ko chahiye tha $x_{0} = c_{1} v_{1} + c_{2} v_{2}$ with $c_{1} \neq = 0$ . Agar $c_{1} = 0$ , toh $A^{k} x_{0} = c_{2} λ_{2}^{k} v_{2}$ hamesha — yeh $v_{2}$ pe converge karta hai aur $λ_{2}$ report karta hai, $λ_{1}$ nahi. Power method sabse bade present component ko amplify karta hai; agar dominant wala absent hai toh woh use invent nahi kar sakta.

Geometric picture: shuruwaat ke figure mein red line $v_{1}$ hai. Ek seed jo exactly perpendicular eigen-direction $v_{2}$ pe lie karta hai woh ek kaali arrow hai jise $A$ seedha wapas apne aap pe map karta hai — woh kabhi red line ki taraf swing nahi karta, kyunki koi red-line component amplify karne ke liye hai hi nahi. Yeh ek knife-edge balance point hai.

WHAT rescue karta hai: floating-point rounding. Har real multiplication ek tiny error inject karta hai, jisme almost surely $v_{1}$ component nonzero hota hai. Woh $v_{1}$ ka seed phir $r^{- k}$ se amplify hota hai aur eventually takeover kar leta hai — kaali arrow, knife-edge se nudge hoke, phir bhi red line pe slide ho jaati hai. Lesson: ek random seed mein probability 1 ke saath $c_{1} \neq = 0$ hota hai, isliye practice mein hum kabhi worry nahi karte.

Exercise 4.2 (L4)

Tumhe $A$ ka woh eigenvalue chahiye jo $2.5$ ke sabse paas ho. Method design karo, shift choose karo, aur convergence rate predict karo. (Eigenvalues: $1.382, 3.618$ .)

Recall Solution 4.2

WHAT banana hai: $σ = 2.5$ ke saath shifted inverse iteration (shift exactly target region pe rakho).

$λ_{1} - σ = 3.618 - 2.5 = 1.118$ , $λ_{2} - σ = 1.382 - 2.5 = - 1.118$ . Woh equidistant hain! $σ = 2.5$ do eigenvalues ka midpoint hai.
$(A - σ I)^{- 1}$ ke eigenvalues $\frac{1}{1.118}$ aur $\frac{1}{- 1.118}$ hain — equal magnitude, opposite sign. Rate $r = \frac{λ _{2} - σ}{λ _{1} - σ} = 1.$

WHY yeh worst case hai: rate $= 1$ matlab koi convergence nahi — method stall ho jaata hai kyunki koi bhi transformed eigenvalue dominate nahi karta. Fix: shift ko off-center nudge karo, jaise $σ = 2.6$ : tab $λ_{1} - σ = 1.018$ , $λ_{2} - σ = - 1.218$ , aur closer eigenvalue $λ_{1}$ hai, isliye yeh $λ_{1}$ pe rate $1.018/1.218 = 0.836$ se converge karta hai. Answer: $σ$ ko kabhi do eigenvalues ke exactly beech mein mat rakho; jis wale ko chahiye uski taraf bias karo.

L5 — Mastery

Exercise 5.1 (L5)

Prove karo ki hamare symmetric $A$ ke liye, Rayleigh quotient error second order hai: agar $x = v_{1} + ϵ d$ (true unit eigenvector ka ek chhota $ϵ$ perturbation ek unit direction $d ⊥ v_{1}$ mein), toh $μ (x) - λ_{1} = O (ϵ^{2})$ hai, $O (ϵ)$ nahi. Hamare $A$ ke liye $ϵ = 0.1$ ke saath numerically verify karo.

Recall Solution 5.1

WHY symmetry matter karti hai: symmetric $A$ ke liye, eigenvectors orthogonal hote hain, aur $μ (x)$ ek smooth function hai jiska gradient har eigenvector pe vanish karta hai (har eigenvector Rayleigh quotient ka ek critical point hai — yahi Rayleigh Quotient Iteration insight hai). Ek function apne critical point pe sirf quadratically change karta hai.

Proof. $x = v_{1} + ϵ d$ likho 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 )} .$ Numerator expand karo, $A v_{1} = λ_{1} v_{1}$ use karke aur — crucially — symmetry use karke, jo deti hai $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}) .$ Linear-in- $ϵ$ term cancel ho gaya (symmetry ki wajah se $v_{1}^{⊤} A d = λ_{1} v_{1}^{⊤} d = 0$ ki zaroorat thi). Isliye $μ (x) - λ_{1} = O (ϵ^{2})$ . $■$

Numeric check ( $ϵ = 0.1$ ): $v_{1}$ unit dominant eigenvector lo aur $d$ unit orthogonal direction lo ( $= v_{2}$ ). Form karo $x = v_{1} + 0.1 d$ aur compute karo $μ (x) = \frac{x ^{⊤} A x}{x ^{⊤} x}$ . Result deta hai $μ (x) - λ_{1} \approx - 0.0198$ , jabki vector error $0.1$ hai. Ratio $0.0198/0. 1^{2} \approx 1.98$ — ek clean $O (ϵ^{2})$ (constant $∣ d^{⊤} A d - λ_{1} ∣ = ∣ λ_{2} - λ_{1} ∣ = 2.236$ hai, aur $2.236 \cdot 0. 1^{2} / (1 + 0.01) \approx 0.0221$ hai, order match karta hai). Ek linear error $\sim 0.1$ deta, paanch gunga zyada bada.

Exercise 5.2 (L5)

Transformation rules use karke explain karo ki Rayleigh Quotient Iteration (shift ko har step pe current Rayleigh estimate update karna) symmetric matrices ke liye cubically converge kyun karta hai, aur plain shifted inverse iteration (fixed $σ$ ) sirf linear kyun hai. QR Algorithm aur Characteristic Polynomial se connect karo.

Recall Solution 5.2

Fixed shift (linear): $σ$ constant rehne pe, har step error ko fixed ratio $r = \frac{λ _{j} - σ}{λ _{m} - σ} < 1$ se multiply karta hai. Constant ratio → error $r^{k}$ jaisi → linear. Dekho Convergence Rates.

Adaptive shift (cubic) — poori chain: $σ_{k} = μ (x_{k})$ set karo, current vector ka Rayleigh quotient, aur $ϵ_{k} = ∥ x_{k} - v_{j} ∥$ current vector error ho.

Shift accuracy (Exercise 5.1 se): kyunki Rayleigh quotient symmetric eigenvector pe second-order accurate hai, shift $∣ σ_{k} - λ_{j} ∣ = O (ϵ_{k}^{2})$ ke andar land karta hai true eigenvalue se. Yahi crucial input hai — shift error quadratically small hai, sirf linearly small nahi.
Uss shift ke saath ek inverse-iteration step: transformed target eigenvalue $\frac{1}{λ _{j} - σ _{k}}$ hai, aur nearest competitor $\frac{1}{λ _{m} - σ _{k}}$ hai with $λ_{m}$ fixed distance door. Isliye one-step contraction factor hai: $\frac{λ _{j} - σ _{k}}{λ _{m} - σ _{k}} \approx \frac{O ( ϵ _{k}^{2} )}{O ( 1 )} = O (ϵ_{k}^{2}) .$
Dono ko compound karo: nayi error purani error times contraction factor hai: $ϵ_{k + 1} = ϵ_{k} \cdot O (ϵ_{k}^{2}) = O (ϵ_{k}^{3}) .$ Yahi cubic convergence hai — sahi digits ki sankhya har step mein triple hoti hai (3, 9, 27, …). Engine hai feedback loop: accurate vector → quadratically-accurate shift → quadratically-strong contraction → aur bhi accurate vector.

QR aur characteristic polynomial se concrete link:

QR Algorithm disguise mein shifted inverse iteration hai jo sab eigenvectors pe ek saath chalti hai. Woh Rayleigh-type Wilkinson shifts use karta hai (essentially $σ_{k} =$ current matrix ka ek corner Rayleigh quotient) exactly isi cubic speed ko symmetric problems mein inherit karne ke liye — isiliye practical libraries QR use karti hain, un definitions se nahi jinse humne shuru kiya tha.
Hum Characteristic Polynomial route ( $det (A - λ I) = 0$ ) se bilkul bachte hain: $n \geq 5$ ke liye us polynomial ke koi closed-form roots nahi hain (Abel–Ruffini), aur numerically bhi uske roots coefficient errors ke liye wildly sensitive hain. Iteration polynomial ko sidestep karta hai: har eigenvalue shifting aur solving se mili, aur Rayleigh feedback ise cubically fast banata hai. Slogan: "polynomial root mat karo — shift karo, solve karo, aur Rayleigh ko answer chase karne do."

Recall Poore page ka one-line recap

Power method biggest stretch ride karta hai; inverse iteration chhote ki taraf flip karta hai; shifting kahin bhi aim karta hai; Rayleigh quotient eigenvalue quadratically padhta hai (symmetric case); aur shift ko us quotient ke peeche chase karne dene se cubic speed milti hai — QR Algorithm ka seed.