Visual walkthrough — Iterative methods — Jacobi, Gauss-Seidel, convergence

4.8.20 · D2 · Maths › Numerical Methods › Iterative methods — Jacobi, Gauss-Seidel, convergence

---

Step 0 — Woh words jo hum use karenge (kuch bhi assumed nahi)

Kisi bhi formula se pehle, teen seedhi baatein.

• Ek system $A\mathbf{x}=\mathbf{b}$ bas kai seedhi-line equations hain jo ek saath sach honi chahiye. Unka milne ka point true solution hai, jise hum ${\mathbf{x}}^{\ast }$ kehte hain (star ka matlab hai "woh asli jawab jo hum dhoondh rahe hain").
• Ek guess ${\mathbf{x}}^{(k)}$ koi bhi point hai jo hum jawab ke roop mein propose karte hain. Upar laga chhota $(k)$ ek step counter hai, power nahi — ${\mathbf{x}}^{(0)}$ hamara pehla guess hai, ${\mathbf{x}}^{(1)}$ uske baad wala, aur isi tarah aage.
• Error ${\mathbf{e}}^{(k)}={\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast }$ woh arrow hai jo true answer se hamare current guess ki taraf point karta hai. Agar woh arrow simat ke kuch nahi reh jaata, toh hamara guess jawab par aa gaya.

Figure dekho: kala dot ${\mathbf{x}}^{\ast }$ hai, khula dot hamara guess hai, aur laal arrow error ${\mathbf{e}}^{(k)}$ hai. Neeche sab kuch ek hi sawaal hai: woh laal arrow step-to-step kaise badalata hai?

---

Step 1 — Problem ko rewrite karo taaki "new" akela left side pe baithe

KYA. Hum $A$ ko ek aasaan part $M$ aur ek bachi hui part $N$ mein tod dete hain, taaki $A=M-N$ ho, aur hum insist karte hain ki $M$ woh matrix ho jise hum sasti tarike se undo (invert) kar sakein.

KYUN. Hum $A$ ko saste mein invert nahi kar sakte — yahi wajah hai ki humne Gaussian Elimination chhoda. Lekin agar $M$ diagonal ya triangular hai, toh "$M\mathbf{y}=\text{kuch}$" solve karna trivial hai. Toh hum saari mushkil cheezein right side par dhakka dete hain, jahan woh ek purane guess ko multiply karti hain jiske numbers hamare paas pehle se hain.

Exact statement se shuru karo aur split substitute karo:

$$A\mathbf{x}=\mathbf{b}⟺\underset{\text{yeh hai }A}{\underbrace{(M-N)}}\mathbf{x}=\mathbf{b}⟺\underset{\text{aasaan piece}}{\underbrace{M\mathbf{x}}}=\underset{\text{bachi hui + data}}{\underbrace{N\mathbf{x}+\mathbf{b}}}.$$

Term by term padhte hain: $M\mathbf{x}$ woh part hai jise hum turant solve kar sakte hain; $N\mathbf{x}$ "coupling" hai jise hum purane guess se feed karenge; $\mathbf{b}$ fixed data vector hai. Ab right side ko purane guess ${\mathbf{x}}^{(k)}$ par freeze karo aur left side se naya guess ${\mathbf{x}}^{(k+1)}$ niklo:

$$M{\mathbf{x}}^{(k+1)}=N{\mathbf{x}}^{(k)}+\mathbf{b}.$$

PICTURE. Figure mein "conveyor belt" dikhti hai: purana guess right box mein jaata hai, $N$ se multiply hota hai aur $\mathbf{b}$ se nudge hota hai, phir $M$ undo hota hai aur naya guess bahar aata hai.

---

Step 2 — Ek step karne wali single machine ka naam rakho: $T$

KYA. Dono sides par $M$ undo karo. Isse ek poora step ek single multiply-and-shift mein simat jaata hai.

KYUN. Hum woh machine dekhna chahte hain jo kisi bhi guess ko agla guess banati hai, kyunki us ek machine ka study hamein lambe run ke baare mein sab kuch bata deta hai.

$${\mathbf{x}}^{(k+1)}=\underset{\text{ise kehte hain }T}{\underbrace{M^{-1}N}}{\mathbf{x}}^{(k)}+\underset{\text{ise kehte hain }\mathbf{c}}{\underbrace{M^{-1}\mathbf{b}}}.$$

Term by term: $M^{-1}$ hai "aasaan part undo karo"; $M^{-1}N=T$ hai iteration matrix — woh fixed multiplier jo har step par lagti hai; $M^{-1}\mathbf{b}=\mathbf{c}$ ek constant offset hai jo kabhi nahi badalti. Toh har method (Jacobi, Gauss-Seidel, SOR) ek hi shape ka hai:

$${\mathbf{x}}^{(k+1)}=T{\mathbf{x}}^{(k)}+\mathbf{c}.$$

PICTURE. Step 1 ke do boxes ek labelled box $T$ mein merge ho jaate hain, upar se ek chhota constant $\mathbf{c}$ add hota hai.

---

Step 3 — Sach subtract karo taaki guess nahi, error dekhein

KYA. Saccha jawab ${\mathbf{x}}^{\ast }$ ek fixed point hai: use andar daalo toh wahi waapas milta hai. Toh woh bhi usi rule ko maanta hai, ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$.

KYUN. Constant $\mathbf{c}$ cheezein cluttered kar deta hai. Agar hum guess ki equation mein se truth ki equation subtract karein, $\mathbf{c}$ cancel ho jaata hai aur hum sirf error arrow ke liye ek saaf law ke saath bacha jaate hain.

$$\begin{array}{rcl}{\mathbf{x}}^{(k+1)}& =& T{\mathbf{x}}^{(k)}+\mathbf{c}\\ -({\mathbf{x}}^{\ast }& =& T{\mathbf{x}}^{\ast }+\mathbf{c})\\ \underset{={\mathbf{e}}^{(k+1)}}{\underbrace{{\mathbf{x}}^{(k+1)}-{\mathbf{x}}^{\ast }}}& =& T\underset{={\mathbf{e}}^{(k)}}{\underbrace{({\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast })}}.\end{array}$$

$\mathbf{c}$ dono rows mein identically aaya, isliye gayab ho gaya. Jo bacha woh hairaan karne wala simple hai:

$$\boxed{{\mathbf{e}}^{(k+1)}=T{\mathbf{e}}^{(k)}.}$$

Har symbol: ${\mathbf{e}}^{(k+1)}$ agla step ka error arrow hai; $T$ wahi machine hai jaise pehle; ${\mathbf{e}}^{(k)}$ is step ka error arrow hai. Error usi identical machine $T$ se guzarta hai.

PICTURE. Wahi $T$ box, lekin ab laal error arrow andar jaata hai aur ek (umeedan chhota) laal error arrow bahar aata hai.

---

Step 4 — Unroll karo: error hai $T$ jo $k$ baar lagayi gayi

KYA. Boxed law ko baar baar lagaao, poori tarah shuruat tak.

KYUN. Hum kisi bhi step par error ka formula chahte hain initial error ke terms mein, taaki hum pooch sakein "kya woh marta hai?"

$${\mathbf{e}}^{(1)}=T{\mathbf{e}}^{(0)},{\mathbf{e}}^{(2)}=T{\mathbf{e}}^{(1)}=T^2{\mathbf{e}}^{(0)},\dots \boxed{{\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}.}$$

Yahan $T^k$ ka matlab hai "machine $k$ baar lagaao" (ab ek sachchi matrix power). Toh convergence ka poora sawaal ek matrix power ke baare mein ek sawaal ban jaata hai:

Kya $T^k{\mathbf{e}}^{(0)}\to 0$ jaata hai jab $k\to \infty$, har possible starting error ${\mathbf{e}}^{(0)}$ ke liye?

PICTURE. $T$-boxes ki ek chain; laal error arrow har box mein chhota hota jaata hai — ya, agar hum badkismat hain, bada.

---

Step 5 — $T$ ko uske khud ke natural directions (eigenvectors) se dekho

KYA. Ek matrix multiply ko generally picture karna mushkil hai — yeh rotate bhi karta hai aur stretch bhi. Lekin har diagonalizable $T$ ke special directions hote hain, jise eigenvectors ${\mathbf{v}}_i$ kehte hain, jinke along woh sirf stretch karta hai ek number ${\lambda }_i$ se (uska eigenvalue): $T{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$.

KYUN. Yeh exactly is kaam ke liye tool hain. Dekho Eigenvalues and Eigenvectors. Eigenvectors kyun, raw matrix entries kyun nahi? Kyunki ek eigen-direction ke along, $T$ ko sau baar lagaana bas ${\lambda }_i$ se sau baar multiply karna hai — ek scalar jise hum poori tarah samajhte hain. Uljhi hui matrix independent scalars ka ek bag ban jaati hai.

Starting error ko in directions ke combination ke roop mein likho (koi bhi vector aisa likh sakta hai, agar ${\mathbf{v}}_i$ space span karen):

$${\mathbf{e}}^{(0)}=c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2+\cdots +c_n{\mathbf{v}}_n.$$

Numbers $c_i$ kehte hain "error ka kitna hissa direction $i$ ke along point karta hai." Ab ise $T^k$ se hit karo. Har eigen-direction ke along, $T$ bas ${\lambda }_i$ se multiply karta hai, toh $T^k$ ${\lambda }_i^k$ se multiply karta hai:

$${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}=c_1{\lambda }_1^k{\mathbf{v}}_1+c_2{\lambda }_2^k{\mathbf{v}}_2+\cdots +c_n{\lambda }_n^k{\mathbf{v}}_n.$$

Error ka har tukda ${\lambda }_i^k$ se scale hota hai — ek saada number jo $k$-th power tak uthaya gaya.

PICTURE. Error arrow do eigen-arrows ke sum ke roop mein drawn; jab $T$ act karta hai toh har apne $\lambda$ se stretch hota hai.

---

Step 6 — ${\lambda }^k$ kab marta hai? Poora jawab ek number mein

KYA. Har component ka anjaam ${\lambda }_i^k$ se tay hota hai. Koi number jise zyada se zyada high powers tak uthaya jaaye, zero jaata hai iff uski absolute value 1 se neeche hai.

KYUN. Yahi dil ki baat hai. Ek component ke teen cases dekho (figure):

• $|{\lambda }_i|<1$: ${\lambda }_i^k\to 0$. Error ka woh hissa marta hai. ✓
• $|{\lambda }_i|=1$: ${\lambda }_i^k$ hamesha usi size ka rehta hai. Error ruk jaata hai — kabhi converge nahi karta. ✗
• $|{\lambda }_i|>1$: ${\lambda }_i^k$ blast ho jaata hai. Error explode karta hai (diverge). ✗

Poore error ke gaayab hone ke liye, har component marna chahiye. Toh sab $i$ ke liye $|{\lambda }_i|<1$ hona chahiye. Sabse bura (sabse bada) wala bottleneck hai — aur us sabse bade absolute eigenvalue ka ek naam hai.

$$\boxed{\rho (T)<1⟺{\mathbf{e}}^{(k)}\to 0\text{har start ke liye}⟺\text{iteration converge karta hai.}}$$

Aur speed: ek baar chhote components chale jaayein, error sabse bade $\lambda$ se dominate hota hai, toh har step error ko roughly $\rho (T)$ factor se shrink karta hai. Chhota $\rho$ ⇒ zyada fast.

PICTURE. Teen shrinking/steady/growing staircases ${\lambda }^k$ ke teen cases ke liye.

---

Step 7 — Woh degenerate cases jo tum skip nahi kar sakte

KYA & KYUN. Derivation ne kuch cheezein assume ki thi. Yeh raha kya hota hai jab woh fail hoti hain.

• Ek zero diagonal entry, $a_{ii}=0$. Dono methods $a_{ii}$ se divide karte hain, toh $M=D$ (Jacobi) ya $M=D-L$ (Gauss-Seidel) invertible nahi hoga — Step 2 collapse kar jaata hai. Fix: rows ko permute karo taaki diagonal par nonzeros aa jayein $T$ banane se pehle.
• $T$ ka ek repeated eigenvalue hai aur usse diagonalize nahi kiya ja sakta. Step 5 ka clean split fail karta hai. Honest statement phir bhi Spectral Radius use karta hai: $T^k\to 0⟺\rho (T)<1$ abhi bhi hold karta hai (Jordan form ke zariye, jahan ek polynomial-times-${\lambda }^k$ factor phir bhi marta hai jab $|\lambda |<1$ ho). Toh boxed result survive karta hai.
• Boundary $\rho (T)=1$. Error worst direction mein na marta hai na badhta hai — iteration converge nahi karta (yeh cycle ho sakta hai ya drift). Yeh case firmly "fail" side par hai.
• Non-strictly-dominant matrices. Strict diagonal dominance sirf ek sufficient shortcut hai. Ek matrix ise fail kar sakti hai phir bhi $\rho (T)<1$ rakh ke converge kar sakti hai. Eigenvalue test sachcha judge hai.

PICTURE. Ek flowchart-style figure: check $a_{ii}\ne 0$ → $T$ banao → $\rho$ measure karo → verdict.

---

Step 8 — Ek real matrix par dekho (numbers jo tum check kar sako)

KYA. Lo $A=\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)$, classic 1-D finite-difference block ek sparse PDE grid se.

Split: $D=2I$, aur $L+U=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, toh Jacobi machine hai

$$T_J=D^{-1}(L+U)=\frac{1}{2}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$$

Iske eigenvalues: inner matrix $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ components swap karta hai, toh uske eigenvalues $\pm 1$ hain; half karne par $\lambda (T_J)=\pm \frac{1}{2}$ milta hai. Isliye

$$\rho (T_J)=\frac{1}{2}<1\Rightarrow \text{converge karta hai, error har sweep mein half hota hai.}$$

Contrast karo parent ke diverging example $A=\left(\begin{array}{cc}1& 2\\ 3& 1\end{array}\right)$ se: wahan $\rho (T_J)=\sqrt{6}\approx 2.449>1$, toh laal error arrow barhta hai — exactly Step 6 ki "explode" staircase.

---

Ek-picture summary

Is page ki har cheez ek frame mein: split machine $T$ banata hai (Step 2); sach subtract karne se guess-law error-law ${\mathbf{e}}^{(k+1)}=T{\mathbf{e}}^{(k)}$ ban jaata hai (Step 3); unrolling se ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}$ milta hai (Step 4); eigen-directions matrix power ko scalars ${\lambda }_i^k$ mein badal dete hain (Step 5); aur woh scalars exactly tab marte hain jab sabse bada, $\rho (T)$, 1 se neeche ho (Step 6).

Recall Feynman retelling — ek story ki tarah bolo

Kahin ek sachcha jawab baitha hai, aur ek guess hai jiske saath ek laal arrow answer se guess ki taraf point karta hai. Humne ek machine, $T$, banai jo koi bhi guess leta hai aur naya banata hai. Kyunki sachcha jawab machine se guzarne par wahi rehta hai, use subtract karne par pata chalta hai ki arrow bhi usi machine ko maanta hai: har step mein, laal arrow $T$ se guzarta hai. Yeh $k$ baar karo aur arrow exactly $k$ baar $T$ se guzra hoga. Ab trick: har machine ke favorite directions hote hain jahan woh sirf stretch karta hai, ek factor $\lambda$ se. Arrow ko un directions mein toro; har ek ke along, $k$ steps ka matlab hai $\lambda$ se utne baar multiply karna. 1 se neeche ka number, khud se hamesha multiply hota hua, zero ho jaata hai; 1 se upar wala blast karta hai; 1 ke barabar wala stubborn ho ke wahi baitha rehta hai. Arrow tabhi gayab hota hai jab uske har piece fade ho — toh sabse bada stretch factor, $\rho (T)$, 1 se neeche hona chahiye. Woh single number tay karta hai ki hum jeetenge ya nahi aur kitni jaldi.

Recall Rapid self-check

Error law mein constant $\mathbf{c}$ kyun gayab ho jaata hai? ::: Saccha solution ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$ maanta hai; guess equation mein se ise subtract karne par $\mathbf{c}$ cancel ho jaata hai. Convergence iff kaunsa single number 1 se neeche ho? ::: $\rho (T)$, spectral radius (sabse bada $|\lambda |$). Approximate per-step error shrink factor kya hai? ::: $\rho (T)$ khud. $T$ exist karne se pehle kya fix karna chahiye? ::: Ek zero diagonal entry — rows permute karo taaki $M$ invertible ho.

---

Parent: 4.8.20 Iterative methods — Jacobi, Gauss-Seidel, convergence (Hinglish)