Eigenvalue computation — power method, inverse iteration

4.8.21 · Maths › Numerical Methods

1. Seed idea: repeated multiplication dominant eigenvector kyun dhundh leta hai

WHAT hum exploit karte hain: Maano $A$ ( $n \times n$ , real) ke eigenvalues hain $∣ λ_{1} ∣ > ∣ λ_{2} ∣ \geq \dots \geq ∣ λ_{n} ∣$ aur eigenvectors $v_{1}, \dots, v_{n}$ ek basis bana rahe hain. $∣ λ_{1} ∣$ strictly sabse bada hai — yahi dominant eigenvalue hai.

HOW derivation hoti hai (scratch se): Koi bhi start vector eigenbasis mein likho: $x_{0} = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{n} v_{n}, c_{1} \neq = 0.$ $A$ ek baar lagao: $A v_{i} = λ_{i} v_{i}$ , to $A x_{0} = c_{1} λ_{1} v_{1} + \dots + c_{n} λ_{n} v_{n} .$ $k$ baar lagao (har baar $A$ , $v_{i}$ ko $λ_{i}$ se multiply karta hai): $A^{k} x_{0} = c_{1} λ_{1}^{k} v_{1} + c_{2} λ_{2}^{k} v_{2} + \dots + c_{n} λ_{n}^{k} v_{n} .$ Ab dominant term $λ_{1}^{k}$ factor out karo — yahi crucial algebraic move hai: $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}] .$

Error ki rate $\frac{λ _{2}}{λ _{1}}^{k}$ se ghatti hai — yeh linear convergence hai, jo do sabse bade eigenvalues ke beech ke gap se control hoti hai.

2. Power Method — algorithm

Vector ko blow up ( $λ_{1}^{k}$ ) ya vanish nahi hone de sakte, isliye har step normalize karte hain.

Rayleigh quotient KYU? Agar $x_{k} \approx v_{1}$ to $A x_{k} \approx λ_{1} x_{k}$ , isliye $\frac{x _{k}^{⊤} A x _{k}}{x _{k}^{⊤} x _{k}} \approx \frac{x _{k}^{⊤} ( λ _{1} x _{k} )}{x _{k}^{⊤} x _{k}} = λ_{1} .$ Yeh $∥ A x_{k} - μ x_{k} ∥$ ko $μ$ ke upar minimize bhi karta hai, matlab yeh current vector ke liye best least-squares eigenvalue hai — isliye accurate hai, chahe $x_{k}$ approximate ho. (Symmetric $A$ ke liye yeh $O (error^{2})$ tak accurate hai.)

Figure — Eigenvalue computation — power method, inverse iteration

3. Sabse chhota eigenvalue dhundhna: inverse iteration

HOW (derivation): $A v_{i} = λ_{i} v_{i}$ se, $A^{- 1} / λ_{i}$ se multiply karo: $A^{- 1} v_{i} = \frac{1}{λ _{i}} v_{i} .$ To $A^{- 1}$ pe power method $v_{n}$ (yani $min ∣ λ ∣$ ka eigenvector) ki taraf converge karta hai, rate $\frac{λ _{n}}{λ _{n - 1}}^{k}$ se.

4. Shifted inverse iteration — koi bhi eigenvalue dhundho

KYU shift karte hain: $(A - σ I)^{- 1}$ ka eigenvalue $\frac{1}{λ _{i} - σ}$ hota hai. Agar $σ$ ko target eigenvalue $λ_{j}$ ke paas choose karo, to $λ_{j} - σ$ bahut chhota hoga, isliye $\frac{1}{λ _{j} - σ}$ bahut bada ho jaayega — yeh sab doosron pe dominate karega. Inverse iteration phir $v_{j}$ ki taraf explosively fast converge karega.

5. 80/20 core

Recall Feynman: ek 12-saal ke bachche ko samjhao

Ek rubber ki stretchy sheet socho. Uspe ek dot push karo aur chhodo — sheet usse us direction mein kheechchti hai jo sabse zyada stretch hoti hai. Yeh push baar baar karo, aur dot hamesha us strongest stretch line pe slip karta rehta hai. Yahi power method hai: sabse strong stretch "biggest eigenvalue" direction hai. Ab rubber ka rule ulta karo taaki weakest stretch strongest ban jaaye — yahi inverse iteration hai, chhota wala dhundhne ke liye. Aur agar koi specific stretch chahiye, to sheet ko "tilt" karo (yani shift karo) taaki tumhara favourite direction strongest ban jaaye, aur woh almost instantly pop out ho jaata hai.

Flashcards

A^{k} x_{0}

kis direction mein converge karta hai?

Dominant eigenvector

v_{1}

ki taraf (sabse bada

∣ λ ∣

), provided

c_{1} \neq = 0

aur

∣ λ_{1} ∣ > ∣ λ_{2} ∣

Derivation mein

λ_{1}^{k}

factor out kyun karte hain?

Taaki ratios

(λ_{i} / λ_{1})^{k} \to 0

expose hon, yeh dikhata hai ki sab non-dominant components decay karte hain.

Power method convergence rate?

Linear,

∣ λ_{2} / λ_{1} ∣^{k}

se governed.

Rayleigh quotient kya hai aur kyun use karte hain?

μ = \frac{x ^{⊤} A x}{x ^{⊤} x}

; kisi bhi given vector ke liye best least-squares eigenvalue estimate, approximate

x

ke liye bhi accurate (symmetric

A

ho to quadratically accurate).

A^{- 1}

ke eigenvalues

A

ke eigenvalues se kaise relate karte hain?

Reciprocals

1/ λ_{i}

; eigenvectors unchanged.

Inverse iteration kya dhundhta hai aur kyun?

A

ka sabse chhota

∣ λ ∣

, kyunki woh

A^{- 1}

ka sabse bada

1/ λ

ban jaata hai.

A y = x

solve kyun karte hain

A^{- 1}

compute karne ke bajaaye?

Sasta aur stable; LU-factor ek baar karo, har step back-substitute karo (

O (n^{2})

O (n^{3})

A - σ I

ke eigenvalues?

λ_{i} - σ

, same eigenvectors.

Shift

σ \approx λ_{j}

inverse iteration kyun fast kar deta hai?

1/ (λ_{j} - σ)

bahut bada ho jaata hai, sab doosron pe dominate karta hai →

v_{j}

ki taraf bahut fast convergence.

Shifted inverse iteration ki convergence rate?

∣ (λ_{j} - σ) / (λ_{m} - σ) ∣^{k}

λ_{m}

σ

ke sabse paas doosra eigenvalue.

Power method shuru karne ki condition?

Seed ka dominant eigenvector ke direction mein nonzero component hona zaroori hai (

c_{1} \neq = 0

Connections

LU Decomposition — har iteration mein $(A - σ I) y = x$ cheaply solve karne ke liye use hota hai.
Characteristic Polynomial — isliye direct eigenvalue formulas $n \geq 5$ ke liye fail karte hain (Abel–Ruffini).
Rayleigh Quotient Iteration — $σ$ ko har step mein current Rayleigh quotient se update karo → cubic convergence.
QR Algorithm — industrial method jo sab eigenvalues compute karta hai.
Spectral Decomposition — eigenbasis expansion $x_{0} = \sum c_{i} v_{i}$ jo derivation ko underpin karta hai.
Convergence Rates — linear vs quadratic vs cubic.