Worked examples — Iterative methods — Jacobi, Gauss-Seidel, convergence

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

Scenario matrix

Yeh har case class hai jo Jacobi / Gauss-Seidel problem tumhare saamne phenk sakti hai. Neeche har worked example mein us cell ka tag hai jo woh cover karta hai.

Pehle ek decision tree banate hain taaki tum jaano ki jab koi matrix saamne aaye toh kaunsa lever kheenchna hai. (Aakhri box mein ek acronym hai: SOR = Successive Over-Relaxation, Gauss-Seidel ka ek accelerated cousin — ek fallback jab sirf reordering se $\rho$ kaaboo mein na aaye.)

Case A — SDD, dono methods converge karte hain

Step 1 — update rules likho. Kyun? Har equation ka matlab hai "apni diagonal wali variable ke liye solve karo." $x=\frac{6-y}{4},y=\frac{7-x}{3}.$

Step 2 — Jacobi sirf PURANI values use karta hai. Yeh step kyun? Jacobi poore purane vector ko freeze karta hai, phir sab kuch ek saath update karta hai.

• $k=1$: $x=\frac{6-0}{4}=1.5$, $y=\frac{7-0}{3}=2.3333$.
• $k=2$: $x=\frac{6-2.3333}{4}=0.9167$, $y=\frac{7-1.5}{3}=1.8333$.
• $k=3$: $x=\frac{6-1.8333}{4}=1.0417$, $y=\frac{7-0.9167}{3}=2.0278$.

Step 3 — Gauss-Seidel $y$ ke andar NAYA $x$ use karta hai. Yeh step kyun? Jab tak hum $y$ compute karte hain, ek better $x$ already available hai — waste kyon karein.

• $k=1$: $x=\frac{6-0}{4}=1.5$; $y=\frac{7-1.5}{3}=1.8333$.
• $k=2$: $x=\frac{6-1.8333}{4}=1.0417$; $y=\frac{7-1.0417}{3}=1.9861$.
• $k=3$: $x=\frac{6-1.9861}{4}=1.0035$; $y=\frac{7-1.0035}{3}=1.9988$.

Verify: GS 3 sweeps ke baad $(1.0035,1.9988)$ hai — error $\approx 0.004$. Jacobi $(1.0417,2.0278)$ hai — error $\approx 0.05$. GS forecast ke anusaar $\approx 10\times$ kareeb hai. $(1,2)$ ko originals mein daalo: $4(1)+2=6$ ✓, $1+3(2)=7$ ✓.

Case B — $\rho (T_J)$ se speed forecast karo

Forecast: SDD ($|2|>|-1|$ dono rows mein) toh converge karega; sawaal yeh hai ki kitni tezi se.

Step 1 — $T_J=D^{-1}(L+U)$ banao. Kyun? Parent note ne prove kiya tha ${\mathbf{e}}^{(k)}=T_J^k{\mathbf{e}}^{(0)}$ (jahan ${\mathbf{e}}^{(k)}$ upar define kiya gaya error vector hai); error ka anjaam poori tarah $T_J$ mein hai. $D=\left(\begin{array}{cc}2& 0\\ 0& 2\end{array}\right),L+U=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),T_J=\frac{1}{2}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$

Step 2 — $T_J$ ke eigenvalues. Yeh step kyun? $\rho (T_J)=\max |\lambda |$ har step ka shrink factor hai. $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ ke eigenvalues $\pm 1$ hain, toh $T_J$ ke $\lambda =\pm \frac{1}{2}$ hain.

Step 3 — rate padho. $\rho (T_J)=\frac{1}{2}<1$. Interpretation: har sweep error $\Vert {\mathbf{e}}^{(k)}\Vert$ ki length roughly half kar deta hai. Ek decimal digit gain karne ke liye ($10\times$) lagbhag ${\log }_{10}(1/2{)}^{-1}\approx 3.3$ sweeps chahiye.

Verify: $\det (T_J-\lambda I)={\lambda }^2-\frac{1}{4}=0\Rightarrow \lambda =\pm \frac{1}{2}$ ✓. $\rho =0.5$ — ek sweep error half kar dega; yahi "kareeb aana" hum Ex 1 ke SDD systems mein dekh chuke hain.

Upar ki figure forecast ko visual banati hai: $\rho =0.5$ (green) ke saath error length $\Vert {\mathbf{e}}^{(k)}\Vert$ har sweep mein half hoti hai aur zero mein gir jaati hai, jabki $\rho \approx 2.449$ wale matrix (red, agla case) mein error multiply hota hai har sweep mein aur phatt jaata hai. Yellow dashed line starting error size mark karti hai.

Case C — SDD nahi, yeh diverge karta hai

Forecast: Row 1: $|1|<|2|$ — not dominant. Shak hai: yeh blow up karega.

Step 1 — $T_J$ banao. Kyun? Hamesha usi wajah se — convergence $T_J$ ki property hai, $A$ ki directly nahi. Yahan $a_{11}=a_{22}=1$ toh $D^{-1}=I$: $T_J=D^{-1}(L+U)=\left(\begin{array}{cc}0& -2\\ -3& 0\end{array}\right).$ (Off-diagonals of $A$ hain $2$ aur $3$; $A=D-L-U$ convention mein $L+U$ unke negatives rakhta hai.)

Step 2 — eigenvalues. Kyun? Hume $\rho$ chahiye. Characteristic equation $\det (T_J-\lambda I)={\lambda }^2-6=0$, toh $\lambda =\pm \sqrt{6}\approx \pm 2.449$.

Step 3 — verdict. $\rho (T_J)=\sqrt{6}\approx 2.449>1$. Error har sweep mein $\approx 2.4$ se multiply hota hai ⇒ diverges.

Step 4 — fix. Kyun? Rows swap karne se diagonal par baithne wala coefficient badal jaata hai: $\left(\begin{array}{cc}3& 1\\ 1& 2\end{array}\right),\text{ab }|3|>|1|,|2|>|1|\text{— SDD, converges.}$

Verify: ${\lambda }^2-6=0\Rightarrow \lambda =\pm \sqrt{6}$, $\rho =\sqrt{6}\approx 2.449>1$ ✓ diverges. Swap ke baad $T_J^{\prime }=\left(\begin{array}{cc}0& -1/3\\ -1/2& 0\end{array}\right)$ ke ${\lambda }^2=\frac{1}{6}$, $\rho =1/\sqrt{6}\approx 0.408<1$ ✓ converges.

Case D — SDD nahi, phir bhi CONVERGES

Forecast: Lalach wala (galat) jawaab: "SDD nahi, toh diverges." Chalte hain $\rho$ check karein, kyunki SDD sirf sufficient hai.

Step 1 — $T_J$ banao. Kyun? SDD fail ho gaya, toh shortcut ka koi kaam nahi; hume real criterion compute karna hoga. $a_{11}=a_{22}=1$ ke saath $D^{-1}=I$, aur $L+U$ off-diagonals ke negatives rakhta hai ($2$ upar, $-\frac{1}{4}$ neeche): $T_J=D^{-1}(L+U)=\left(\begin{array}{cc}0& -2\\ \frac{1}{4}& 0\end{array}\right).$

Step 2 — eigenvalues. Zero diagonal wale $2\times 2$ matrix ke liye, $\det (T_J-\lambda I)={\lambda }^2-(\text{dono off-diagonals ka product})$. Yahan product hai $(-2)(\frac{1}{4})=-\frac{1}{2}$, toh $\det (T_J-\lambda I)={\lambda }^2-(-\frac{1}{2})={\lambda }^2+\frac{1}{2}=0$. Toh ${\lambda }^2=-\frac{1}{2}$, $\lambda =\pm i/\sqrt{2}$ — ek complex pair.

Step 3 — magnitudes lo. Yeh step kyun? $\rho$ complex eigenvalues ki absolute value use karta hai: $|\lambda |=\sqrt{(0{)}^2+(1/\sqrt{2}{)}^2}=\frac{1}{\sqrt{2}}\approx 0.707<1$.

Step 4 — verdict. $\rho (T_J)\approx 0.707<1$ ⇒ converges, even though $A$ diagonally dominant nahi hai. Moral: SDD ek friendly sufficient flag hai, abscence mein kabhi death sentence nahi.

Verify: ${\lambda }^2+\frac{1}{2}=0\Rightarrow |\lambda |=1/\sqrt{2}\approx 0.7071<1$ ✓ non-SDD ke bawajood converges.

Case E — diagonal par zero (degenerate)

Forecast: Dono methods $a_{ii}$ se divide karte hain. Yahan $a_{11}=0$ — zero se division. Yeh shuru hone se pehle hi undefined hai.

Step 1 — illegal step pakdo. Kyun? Update $x_1=\frac{1}{a_{11}}(b_1-a_{12}{x}_2)$ mein $\frac{1}{0}$ hai. Ruko.

Step 2 — rows permute karo. Yeh step kyun? Equations reorder karne se solution nahi badalta, lekin diagonal par nonzero aa jaata hai: $\left(\begin{array}{cc}3& 1\\ 0& 2\end{array}\right)\mathbf{x}=\left(\begin{array}{c}5\\ 4\end{array}\right).$ Ab $a_{11}=3\ne 0$, $a_{22}=2\ne 0$: division legal. Bonus — yeh SDD bhi hai, toh converge bhi karega.

Step 3 — reordered system solve karo (exact, target paane ke liye). Row 2 se: $2y=4\Rightarrow y=2$. Row 1 se: $3x+2=5\Rightarrow x=1$.

Verify: Original equations: $2y=4\Rightarrow y=2$ ✓ aur $3x+y=5\Rightarrow 3(1)+2=5$ ✓. Permuted diagonal nonzero hai, toh Jacobi ab well-defined hai.

Case F — Jacobi converges lekin Gauss-Seidel diverges

Forecast: Sabko "pata hai" GS faster hai. Dekho kaise fail karta hai.

Step 1 — Jacobi ka $T_J$. Pehle $T_J$ kyun compute karein? Baseline establish karne ke liye. Diagonal sab $1$'s hai toh $D^{-1}=I$, aur $L+U$ saare off-diagonal entries ke negatives rakhta hai: $T_J=D^{-1}(L+U)=\left(\begin{array}{ccc}0& -2& 2\\ -1& 0& -1\\ -2& -2& 0\end{array}\right).$

Step 2 — iski characteristic polynomial ${\lambda }^3$ kyun hai. Yeh step kyun? Hume $\rho (T_J)$ chahiye. $\det (T_J-\lambda I)$ expand karo. Likh ke dekho (pehli row ke along cofactor) toh constant, ${\lambda }^1$, aur ${\lambda }^2$ ke coefficients sab cancel ho jaate hain — trace $0$ hai (kills ${\lambda }^2$), $2\times 2$ principal minors ka sum $0$ hai (kills ${\lambda }^1$), aur $\det T_J=0$ hai (kills constant). Jo bachta hai woh hai $\det (T_J-\lambda I)=-{\lambda }^3$. Toh teeno eigenvalues $0$ hain: $\rho (T_J)=0$. Jacobi zyada se zyada 3 steps mein converge karta hai — kamaal.

Step 3 — Gauss-Seidel ka $T_{GS}=(D-L{)}^{-1}U$. Kyun? GS, $M=D-L$ use karta hai. $A=D-L-U$ se hum padh lete hain $D-L=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 2& 2& 1\end{array}\right),U=\left(\begin{array}{ccc}0& -2& 2\\ 0& 0& -1\\ 0& 0& 0\end{array}\right).$ Lower-triangular $D-L$ ko invert karke multiply karne par milta hai $T_{GS}=(D-L{)}^{-1}U=\left(\begin{array}{ccc}0& -2& 2\\ 0& 2& -3\\ 0& 0& 2\end{array}\right).$ Yeh upper-triangular hai, toh iski eigenvalues diagonal par baithi hain: $0,2,2$. Isliye $\rho (T_{GS})=2>1$: diverges.

Step 4 — moral. Yeh kyun important hai: information ki freshness usually achhi hoti hai lekin guaranteed achhi nahi. Jis order mein tum overwrite karte ho, woh certain error directions ko amplify kar sakta hai.

Verify: $\det (T_J-\lambda I)=-{\lambda }^3$ toh $\rho (T_J)=0$ ✓; aur $T_{GS}$ ke diagonal eigenvalues $0,2,2$ hain toh $\rho (T_{GS})=2>1$ ✓. "Usually faster," kabhi "always converges" nahi. (Safe families ke liye — SPD ya SDD — GS sach mein jeetta hai; yeh pathological counter-example hai.)

Case G — ek real-world word problem (chhota PDE grid)

Forecast: Physics kehti hai heat ek straight line mein spread hoti hai, toh exact answer equally spaced hona chahiye: $7.5,15,22.5$.

Step 1 — structure pehchano. Kyun? Rearrange karne par system matrix hai $A=\left(\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right),\mathbf{b}=\left(\begin{array}{c}0\\ 0\\ 30\end{array}\right).$ Yeh ek sparse tridiagonal system hai — exactly woh jo iterative methods ko pasand hai. Yeh sirf weakly diagonally dominant hai (row 2 mein $|2|=|-1|+|-1|$, equality hai), toh weak dominance akele kuch prove nahi karti; convergence justify karne ke liye hume $\rho (T)$ compute karna hoga.

Step 2 — convergence prove karne ke liye $\rho (T_J)$ compute karo. Yeh step kyun? Yahi real WHY hai "yeh converge karta hai" ke peeche. $D=2I$ ke saath, $T_J=D^{-1}(L+U)=\frac{1}{2}\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& 0\end{array}\right).$ Ek $m\times m$ tridiagonal matrix ke liye jisme diagonal par $0$ aur off-diagonal par $1$ ho, eigenvalues exactly known hain: $2\cos \frac{m^{\prime }\pi }{m+1}$ for $m^{\prime }=1,\dots ,m$. Yahan $m=3$, toh woh inner eigenvalues hain $2\cos \frac{\pi }{4},2\cos \frac{2\pi }{4},2\cos \frac{3\pi }{4}=\sqrt{2},0,-\sqrt{2}$. Aage $\frac{1}{2}$ se multiply karo: $T_J$ ke eigenvalues hain $\frac{\sqrt{2}}{2},0,-\frac{\sqrt{2}}{2}$. Sabse badi magnitude $\rho (T_J)=\frac{\sqrt{2}}{2}\approx 0.7071<1$ ⇒ converges (aur Gauss-Seidel, is model matrix ke liye ${\rho }_{GS}={\rho }_J^2=\frac{1}{2}=0.5$ hone se, aur bhi fast hai).

Step 3 — Gauss-Seidel sweeps (average form, freshest neighbour use karo). Yeh step kyun? Har row already $T_i$ ko ek average de rahi hai, toh GS bas "left-to-right latest values use karke averages recompute karo" hai.

• $k=1$: $T_1=\frac{0+0}{2}=0$; $T_2=\frac{0+0}{2}=0$; $T_3=\frac{0+30}{2}=15$.
• $k=2$: $T_1=\frac{0+0}{2}=0$; $T_2=\frac{0+15}{2}=7.5$; $T_3=\frac{7.5+30}{2}=18.75$.
• $k=3$: $T_1=\frac{0+7.5}{2}=3.75$; $T_2=\frac{3.75+18.75}{2}=11.25$; $T_3=\frac{11.25+30}{2}=20.625$.
• $k=4$: $T_1=\frac{0+11.25}{2}=5.625$; $T_2=\frac{5.625+20.625}{2}=13.125$; $T_3=\frac{13.125+30}{2}=21.5625$.

Step 4 — dekho yeh $(7.5,15,22.5)$ ki taraf badh raha hai; har sweep mein steadily climb karta hai, exactly jaisa Step 2 ka $\rho \approx 0.71$ promise kiya tha.

Verify: Exact solution: $(7.5,15,22.5)$ daalo: $2(7.5)-15=0$ ✓, $-7.5+2(15)-22.5=0$ ✓, $-15+2(22.5)=30$ ✓. Units: sab ${}^{\circ }$C mein, endpoints $0$ aur $30$ har interior value ko bracket karte hain ✓.

Case H — exam twist: convergence guarantee karne ke liye value choose karo

Forecast: Bada diagonal = safer. $|c|$ par koi threshold honi chahiye.

Step 1 — har row ke liye SDD inequality likho. Kyun? SDD demand karta hai $|a_{ii}|>{\sum }_{j\ne i}|a_{ij}|$. Yahan har row mein diagonal $c$ hai aur do off-diagonal $1$'s hain: $|c|>1+1=2.$

Step 2 — solve karo. Yeh step kyun? $|c|>2$ ka matlab hai $c>2$ ya $c<-2$.

Step 3 — ek value se sanity-check karo. $c=3$ lo: $T_J=D^{-1}(L+U)=-\frac{1}{3}\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$. Inner matrix $\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$ ke eigenvalues $2,-1,-1$ hain, toh $T_J$ ke $\lambda =-\frac{2}{3},\frac{1}{3},\frac{1}{3}$ hain, $\rho (T_J)=\frac{2}{3}<1$ ✓ converges.

Verify: $|c|>2⟺c\in (-\infty ,-2)\cup (2,\infty )$. $c=3$ ke liye: $\rho (T_J)=\frac{2}{3}\approx 0.667<1$ ✓. Boundary $c=2$ ke liye: $\rho (T_J)=\frac{2}{2}=1$ — converge hone ki guarantee nahi (borderline), jo confirm karta hai ki strict inequality genuinely zaroori hai.

Recall