Eigenvalue computation — power method, inverse iteration: Foundations

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

Parent note padhne se pehle, aapko usmein aane wale har symbol ki poori samajh honi chahiye. Hum unhe ek-ek karke build karte hain, har ek pichle ke upar. Kuch bhi assume nahi kiya gaya hai.

1. Ek vector — numbers ki list wala ek arrow

Stacked notation $(y x)$ bas numbers ka ek column hai. Upar se neeche padhte hue: pehla number = horizontal step, doosra = vertical step.

Figure — Eigenvalue computation — power method, inverse iteration

Topic ko yeh kyun chahiye. Har method — power method, inverse iteration — ek kahani hai ek arrow ke saath kya hota hai jab aap use bar-bar ek matrix ko feed karte hain. Arrow nahi, toh kahani nahi.

Hum kyun care karte hain: parent note har step ko normalize karta hai ( $x_{k + 1} = y_{k + 1} /∥ y_{k + 1} ∥$ ). Ek arrow ko uski apni length se divide karna uski direction rakhta hai lekin uski length exactly $1$ par reset kar deta hai — warna baar-baar stretching numbers ko infinity tak blow kar deti.

2. Ek matrix — stretching machine

Ek $2 \times 2$ matrix ke liye rule yeh hai: $(a c b d) (y x) = (c x + d y a x + b y) .$

Ise kaise padhen: upar wala output number top row $(a, b)$ ko arrow $(x, y)$ ke across slide karke aur pairs ko multiply-then-add karke aata hai: $a \cdot x + b \cdot y$ . Bottom row ke liye bhi aise hi.

Topic ko yeh kyun chahiye. $A$ wahi object hai jiske eigenvalues hum chahte hain. Sab kuch " $A$ apply karo" ya " $A$ undo karo" par reduce hota hai.

3. Eigen-pairs — woh arrows jo matrix NAHI turn karti

Jyadaatar arrows $A$ ko feed karne par rotate ho jaate hain. Lekin kuch special arrows usi direction mein bahar aate hain, bas lambe ya chote ho jaate hain. Wahi yahan ke stars hain.

Greek letter $λ$ ("lambda") stretch factor ka bas ek naam hai. Equation $A v = λ v$ kehti hai: machine ka $v$ par action, simply number $λ$ se multiply karne jaisa hi hai.

$λ$ ke signs padhna — sab cases:

$λ > 1$ : same direction, lamba.
$λ = 1$ : unchanged (fixed arrow).
$0 < λ < 1$ : same direction, chota.
$λ = 0$ : origin par collapse (matrix is arrow ko flat kar deti hai).
$λ < 0$ : opposite direction mein flip hota hai, phir $∣ λ ∣$ se scale hota hai.

$∣ \cdot ∣$ bars ka matlab absolute value hai — number ka size, sign ignore karke. Parent note eigenvalues ko $∣ λ ∣$ se rank karta hai kyunki use kitni stretch ki parwah hai, naa ki kis taraf jaati hai.

Topic ko yeh kyun chahiye. Core promise — "repeated multiplication sabse zyada stretched direction ko amplify karta hai" — tab hi sense banata hai jab aap jaano kaun si direction sabse zyada stretch hoti hai. Woh hai dominant eigenvector $v_{1}$ .

4. Ek basis — kisi bhi arrow ko eigenvectors ke mix mein likhna

Toh koi bhi seed arrow eigen-ingredients mein split ho jaata hai: $x_{0} = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{n} v_{n} .$ Numbers $c_{i}$ $x_{0}$ ke andar har eigenvector ki amount (coefficients) hain. Ek smoothie sochein: $x_{0}$ drink hai, $v_{i}$ fruits hain, $c_{i}$ aapne kitna daala.

Topic ko yeh kyun chahiye. Poora power-method derivation is coordinate system mein rehta hai. Kyunki $A$ har $v_{i}$ par simply act karta hai (bas $λ_{i}$ se multiply karo), $x_{0}$ ko eigen-parts mein split karna $A^{k} x_{0}$ compute karna easy banata hai: $A^{k} x_{0} = c_{1} λ_{1}^{k} v_{1} + \dots + c_{n} λ_{n}^{k} v_{n} .$ Har ingredient ko bas uska apna stretch factor $k$ ki power mein milta hai.

5. Exponent $k$ aur ratio $(\frac{λ _{2}}{λ _{1}})^{k}$

Magic lever ratio $\frac{λ _{2}}{λ _{1}}$ hai. Kyunki $∣ λ_{2} ∣ < ∣ λ_{1} ∣$ , is fraction ka absolute value 1 se kam hai. Size mein 1 se chota koi bhi number, badhte power $k$ par, $0$ ki taraf shrink karta hai:

ratio $= 0.5 \Rightarrow 0.5, 0.25, 0.125, \dots \to 0$ fast.
ratio $= 0.95 \Rightarrow$ shrinks, lekin dheere (convergence crawl karti hai).
ratio $\to 1 \Rightarrow$ barely shrinks — do sabse bade eigenvalues almost tied hain aur method stall ho jaata hai.

Topic ko yeh kyun chahiye. Yahi shrinking exactly wajah hai ki har non-dominant ingredient mar jaata hai, sirf $v_{1}$ bachta hai. Is ratio ki size hi convergence speed hai — dekho Convergence Rates.

6. Inverse $A^{- 1}$ aur $A y = x$ solve karna

Yahan $I$ identity matrix hai — diagonal par 1's, baaki 0's — "do-nothing" machine ( $I x = x$ ).

Key fact jo parent use karta hai: agar $A v = λ v$ toh $A^{- 1} v = \frac{1}{λ} v$ . Same eigenvector, reciprocal eigenvalue. $\times 3$ stretch undo karna matlab $\times \frac{1}{3}$ shrink — same direction.

$2 \times 2$ inverse formula (parent ke worked example mein use hota hai): $(a c b d)^{- 1} = \frac{1}{a d - b c} (d - c - b a) .$ Number $a d - b c$ determinant $det$ hai — ek single number jo measure karta hai ki matrix area ko kitna scale karti hai. Agar $det = 0$ toh machine area ko nothing par flatten kar deti hai aur undo nahi ho sakti ( $A^{- 1}$ exist nahi karta).

7. Shift $A - σ I$

Ek ruler slide karne ki picture banaiye: agar eigenvalues marks ${1.4, 3.6}$ par hain aur aap $σ = 1.3$ se shift karo, toh woh ${0.1, 2.3}$ par move ho jaate hain. Jise aapne target kiya woh ab tiny hai — aur invert karne ke baad, tiny enormous ban jaata hai, toh woh dominate karta hai. Yahi Rayleigh Quotient Iteration ka engine hai aur parent ka "koi bhi eigenvalue dhundho" wala trick hai.

8. Rayleigh quotient $\frac{x ^{⊤} A x}{x ^{⊤} x}$

Yahan do naye pieces hain: dot product aur transpose $⊤$ .

Toh $x^{⊤} x = x_{1}^{2} + x_{2}^{2} = ∥ x ∥^{2}$ : apne aap se dot kiya gaya arrow uski length-squared deta hai.

Topic ko yeh kyun chahiye. Yeh eigenvalue ka number jo bhi arrow aapke paas hai usse padh leta hai — " $λ$ -meter." Dekho Rayleigh Quotient Iteration.

Prerequisite map

Yeh sab parent mein jaata hai: the topic note. Deeper machinery Characteristic Polynomial, Spectral Decomposition, aur QR Algorithm mein hai.

Equipment checklist

Apne aap ko test karo — right side cover karo.

(2 3)

ko arrow ki tarah draw kar sakta hoon

3 right, 2 upar jao; arrowhead point (3,2) par.

∥ (4 3) ∥

compute kar sakta hoon

3^{2} + 4^{2} = 25 = 5

(2113) (0 1)

multiply kar sakta hoon

Row-by-row: top

2 \cdot 1 + 1 \cdot 0 = 2

, bottom

1 \cdot 1 + 3 \cdot 0 = 1

, giving

(1 2)

A v = λ v

ka matlab words mein bata sakta hoon

A

arrow

v

ko number

λ

se scale karta hai bina use turn kiye.

Jaanta hoon

∣ λ ∣

kisse rank karta hai

Stretch ka absolute size, sign ignore karke; dominant wala sabse bada hota hai.

Ek vector ko eigen-ingredients mein split kar sakta hoon

x_{0} = c_{1} v_{1} + \dots + c_{n} v_{n}

, weights

c_{i}

= har eigenvector ki amount.

Jaanta hoon

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

kyun

Ratio ka size

< 1

hai; aisa koi bhi number growing power par zero ki taraf shrink karta hai.

A^{- 1}

ka eigenvalue jaanta hoon

1/ λ

, same eigenvector.

Jaanta hoon

A y = x

kyun solve karte hain

A^{- 1}

form karne ki jagah

Inverting costly aur unstable hai; LU se solve karna sasta aur stable hai.

(0.7 1 1 1.7)

invert kar sakta hoon

det = 0.7 \cdot 1.7 - 1 \cdot 1 = 0.19

; inverse

= \frac{1}{0.19} (1.7 - 1 - 1 0.7)

Jaanta hoon shift

σ

eigenvalues ke saath kya karta hai

Har ek ko

λ_{i} - σ

par slide karta hai, same eigenvectors.

Dot product

x^{⊤} y

compute kar sakta hoon

Matching entries multiply karo aur add karo:

x_{1} y_{1} + x_{2} y_{2}

A

ke liye

x = (0 1)

ka Rayleigh quotient compute kar sakta hoon

\frac{x ^{⊤} A x}{x ^{⊤} x} = \frac{2}{1} = 2

Recall Har step normalize karna kyun zaroori hai?

Iske bina, dominant factor $λ_{1}^{k}$ arrow ki length ko infinity tak explode kar deta hai (ya zero par vanish kar deta hai agar $∣ λ_{1} ∣ < 1$ ). $∥ y ∥$ se divide karna direction rakhta hai — jo hum care karte hain — jabki length ko 1 par pin karta hai.