Exercises — Iterative methods — Jacobi, Gauss-Seidel, convergence

Kya karte hain: diagonal $D$ mein copy karo, below-diagonal entries (negate karke) $L$ mein, aur above-diagonal entries (negate karke) $U$ mein. $D=\left(\begin{array}{ccc}5& 0& 0\\ 0& 4& 0\\ 0& 0& 6\end{array}\right).$ $A$ ke below-diagonal entries hain $a_{21}=1,a_{32}=-3$. Kyunki $A$ ka strictly-lower part $-L$ hai, hum set karte hain $L=-\left(\begin{array}{ccc}0& 0& 0\\ 1& 0& 0\\ 0& -3& 0\end{array}\right)=\left(\begin{array}{ccc}0& 0& 0\\ -1& 0& 0\\ 0& 3& 0\end{array}\right)$. Above-diagonal entries hain $a_{12}=-2,a_{23}=-1$, toh $U=-\left(\begin{array}{ccc}0& -2& 0\\ 0& 0& -1\\ 0& 0& 0\end{array}\right)=\left(\begin{array}{ccc}0& 2& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}\right)$. Check: $D-L-U=\left(\begin{array}{ccc}5& -2& 0\\ 1& 4& -1\\ 0& -3& 6\end{array}\right)=A.$ ✓

• Row 1: $|5|>|-2|+|0|=2$ ✓
• Row 2: $|4|>|1|+|-1|=2$ ✓
• Row 3: $|6|>|0|+|-3|=3$ ✓ Saari rows pass karti hain, toh $A$ SDD hai. Parent ke sufficient condition se, Jacobi aur Gauss-Seidel dono kisi bhi start se converge karte hain.

$T_J=D^{-1}(L+U)$ Jacobi hai; $T_{GS}=(D-L{)}^{-1}U$ Gauss-Seidel hai. Difference: Jacobi sirf $D$ invert karta hai (saari purani values ek saath use hoti hain); Gauss-Seidel poora lower-triangular $D-L$ invert karta hai, matlab yeh abhi-abhi update hue components ko usi sweep mein absorb karta hai.

Jacobi har row ko apne variable ke liye rearrange karta hai, sirf purani values use karke: $x=\frac{12-2y}{10},y=\frac{6-x}{5}.$

• $k=1$ ($(0,0)$ se): $x=\frac{12-0}{10}=1.2000$, $y=\frac{6-0}{5}=1.2000$. Toh ${\mathbf{x}}^{(1)}=(1.2000,1.2000)$.
• $k=2$ ($(1.2,1.2)$ se): $x=\frac{12-2(1.2)}{10}=\frac{9.6}{10}=0.9600$, $y=\frac{6-1.2}{5}=\frac{4.8}{5}=0.9600$. Toh ${\mathbf{x}}^{(2)}=(0.9600,0.9600)$. $(1,1)$ ke aas-paas aa rahe hain.

Gauss-Seidel $y$-equation mein fresh $x$ use karta hai: $x=\frac{12-2y_{\text{old}}}{10},y=\frac{6-x_{\text{new}}}{5}.$

• $k=1$: $x=\frac{12-0}{10}=1.2000$; phir $y=\frac{6-1.2}{5}=0.9600$. Toh ${\mathbf{x}}^{(1)}=(1.2000,0.9600)$.
• $k=2$: $x=\frac{12-2(0.96)}{10}=\frac{10.08}{10}=1.0080$; phir $y=\frac{6-1.008}{5}=0.9984$. Toh ${\mathbf{x}}^{(2)}=(1.0080,0.9984)$. Jacobi ke $(0.9600,0.9600)$ se compare karo: Gauss-Seidel already $0.008$ ke andar hai — clearly faster.

$A{\mathbf{x}}^{(2)}=\left(\begin{array}{c}10(1.008)+2(0.9984)\\ 1.008+5(0.9984)\end{array}\right)=\left(\begin{array}{c}12.0768\\ 6.0\end{array}\right).$ $\mathbf{r}=\mathbf{b}-A{\mathbf{x}}^{(2)}=\left(\begin{array}{c}12\\ 6\end{array}\right)-\left(\begin{array}{c}12.0768\\ 6.0\end{array}\right)=\left(\begin{array}{c}-0.0768\\ 0\end{array}\right).$ Yaad karo $\Vert \mathbf{r}{\Vert }_{\infty }$ = sabse bada absolute component = $\max (|-0.0768|,|0|)=0.0768$. Kyunki $0.0768>0.05$, hum abhi stop nahi karte — ek aur sweep chahiye.

$D=3I$, $L+U=\left(\begin{array}{cc}0& -1\\ -1& 0\end{array}\right)$ ($A$ ke off-diagonal entries, kyunki $A=D-L-U$). $T_J=D^{-1}(L+U)=\frac{1}{3}\left(\begin{array}{cc}0& -1\\ -1& 0\end{array}\right)=\left(\begin{array}{cc}0& -\frac{1}{3}\\ -\frac{1}{3}& 0\end{array}\right).$ Yeh eigenvalues kyun hain (characteristic polynomial dikhao): $2\times 2$ matrix ke liye $T_J-\lambda I=\left(\begin{array}{cc}-\lambda & -\frac{1}{3}\\ -\frac{1}{3}& -\lambda \end{array}\right)$, $\det =0$ set karo: $\det =(-\lambda )(-\lambda )-\left(-\frac{1}{3}\right)\left(-\frac{1}{3}\right)={\lambda }^2-\frac{1}{9}=0\Rightarrow \lambda =\pm \frac{1}{3}.$ Toh $\rho (T_J)=\frac{1}{3}<1$ ⇒ converges, aur error har sweep mein $\approx \frac{1}{3}$ factor se shrink hoti hai. Rate as digits per sweep: ek decimal digit matlab error $10$ se divide hona; har sweep $\frac{1}{3}$ se multiply karti hai, toh $m$ sweeps chahiye jahan $(\frac{1}{3}{)}^m\le \frac{1}{10}$, yaani $m\ge \frac{{\log }_{10}10}{{\log }_{10}3}=\frac{1}{{\log }_{10}3}\approx \frac{1}{0.477}\approx 2.1$ sweeps per digit.

Diye gaye $A$ par SDD test: Row 1: $|1|>|\frac{1}{2}|$ ✓; Row 2: $|1|>|\frac{1}{2}|$ ✓. Toh yeh $A$ strictly diagonally dominant hai (barely, lekin strictly), aur sufficient condition se convergence already guaranteed hai. Diye gaye $A$ ke liye $\rho (T_J)$ compute karo: $D=I$, toh $T_J=D^{-1}(L+U)=\left(\begin{array}{cc}0& -\frac{1}{2}\\ -\frac{1}{2}& 0\end{array}\right)$ (off-diagonal entries, $A=D-L-U$ ke according negate kiye). Characteristic polynomial: $T_J-\lambda I=\left(\begin{array}{cc}-\lambda & -\frac{1}{2}\\ -\frac{1}{2}& -\lambda \end{array}\right)$, toh $\det ={\lambda }^2-\left(-\frac{1}{2}\right)\left(-\frac{1}{2}\right)={\lambda }^2-\frac{1}{4}=0\Rightarrow \lambda =\pm \frac{1}{2}.$ Isliye $\rho (T_J)=\frac{1}{2}<1$ ⇒ Jacobi converges (error roughly har sweep mein half hoti hai), SDD guarantee ke consistent. Ab "sufficient not necessary" wala point. Genuinely non-SDD companion $B=\left(\begin{array}{cc}1& 1\\ \frac{1}{4}& 1\end{array}\right)$ lo: Row 1 deta hai $|1|\ngtr |1|$, toh $B$ SDD nahi hai. Iska Jacobi matrix hai $T_J^B=\left(\begin{array}{cc}0& -1\\ -\frac{1}{4}& 0\end{array}\right)$, jahan $T_J^B-\lambda I=\left(\begin{array}{cc}-\lambda & -1\\ -\frac{1}{4}& -\lambda \end{array}\right)$ aur $\det ={\lambda }^2-(-1)\left(-\frac{1}{4}\right)={\lambda }^2-\frac{1}{4}=0\Rightarrow \lambda =\pm \frac{1}{2},$ toh $\rho (T_J^B)=\frac{1}{2}<1$ — SDD fail hone ke baavajood converges. Yahi L3 ka poora lesson hai.

Forecast: Row 1: $|1|<|3|$ — badly non-dominant, likely diverges. $T_J=\left(\begin{array}{cc}0& -3\\ -2& 0\end{array}\right)$ (kyunki $a_{11}=a_{22}=1$). Yeh eigenvalues kyun hain: $T_J-\lambda I=\left(\begin{array}{cc}-\lambda & -3\\ -2& -\lambda \end{array}\right)$, toh $\det ={\lambda }^2-(-3)(-2)={\lambda }^2-6=0\Rightarrow \lambda =\pm \sqrt{6}\approx \pm \mathrm{2.449.}$ Isliye $\rho =\sqrt{6}>1$ ⇒ diverges. ✓ Fix: do rows swap karo aur $\left(\begin{array}{cc}2& 1\\ 1& 3\end{array}\right)$ milega, jo SDD hai ($2>1$, $3>1$) — ab converge karega.

$D=2I$, $L=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$, $U=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$. Jacobi: $T_J=\frac{1}{2}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$. Yeh eigenvalues kyun hain: $T_J-\lambda I=\left(\begin{array}{cc}-\lambda & \frac{1}{2}\\ \frac{1}{2}& -\lambda \end{array}\right)$, toh $\det ={\lambda }^2-\frac{1}{4}=0\Rightarrow \lambda =\pm \frac{1}{2}$, toh $\rho (T_J)=\frac{1}{2}$. Gauss-Seidel: $D-L=\left(\begin{array}{cc}2& 0\\ -1& 2\end{array}\right)$, $(D-L{)}^{-1}=\frac{1}{4}\left(\begin{array}{cc}2& 0\\ 1& 2\end{array}\right)$. $T_{GS}=(D-L{)}^{-1}U=\frac{1}{4}\left(\begin{array}{cc}2& 0\\ 1& 2\end{array}\right)\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)=\left(\begin{array}{cc}0& \frac{1}{2}\\ 0& \frac{1}{4}\end{array}\right).$ Yeh eigenvalues kyun hain: $T_{GS}$ upper-triangular hai, toh uske eigenvalues diagonal par baithe hain — $0$ aur $\frac{1}{4}$ (formally $\det \left(\begin{array}{cc}-\lambda & \frac{1}{2}\\ 0& \frac{1}{4}-\lambda \end{array}\right)=(-\lambda )(\frac{1}{4}-\lambda )=0$). Isliye $\rho (T_{GS})=\frac{1}{4}$. Wakai $\rho (T_{GS})=\frac{1}{4}={\left(\frac{1}{2}\right)}^2=\rho (T_J{)}^2$ ✓ — Gauss-Seidel yahan do guna tezi se converge karta hai (digits ke terms mein).

Rows: $5x-2y=3$, $x+4y-z=6$, $-3y+6z=3$. Gauss-Seidel, order mein, hamesha newest available use karte hue:

• $x=\frac{3+2y_{\text{old}}}{5}=\frac{3+0}{5}=0.6000$.
• $y=\frac{6-x_{\text{new}}+z_{\text{old}}}{4}=\frac{6-0.6+0}{4}=\frac{5.4}{4}=1.3500$.
• $z=\frac{3+3y_{\text{new}}}{6}=\frac{3+3(1.35)}{6}=\frac{7.05}{6}=1.1750$. Toh ${\mathbf{x}}^{(1)}=(0.6000,1.3500,1.1750)$.

Fixed-point equation ko iteration se subtract karo: ${\mathbf{x}}^{(k+1)}-{\mathbf{x}}^{\ast }=T({\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast })\Rightarrow {\mathbf{e}}^{(k+1)}=T{\mathbf{e}}^{(k)}\Rightarrow {\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}.$ Koi bhi induced (operator) norm lo aur sub-multiplicativity $\Vert T\mathbf{v}\Vert \le \Vert T\Vert \Vert \mathbf{v}\Vert$ baar baar use karo: $\Vert {\mathbf{e}}^{(k)}\Vert =\Vert T^k{\mathbf{e}}^{(0)}\Vert \le \Vert T{\Vert }^k\Vert {\mathbf{e}}^{(0)}\Vert .$ Agar $\Vert T\Vert <1$ toh yeh already ${\mathbf{e}}^{(k)}\to 0$ force karta hai. Lekin $\Vert T\Vert$ $1$ se zyada ho sakta hai jabki iteration phir bhi converge kare: sharp fact yeh hai ki ${\lim }_{k\to \infty }\Vert T^k{\Vert }^{1/k}=\rho (T)$ (Gelfand's formula). Isliye $T^k\to 0⟺\rho (T)<1$, kisi bhi single norm se independent. Norm bound ek convenient sufficient handle hai; $\rho (T)<1$ exact truth hai.

Over-relax ($\omega >1$) kyun? Gauss-Seidel solution ki taraf ek "safe" step leta hai. Agar successive corrections baar baar usi same direction mein point karte hain — jo smooth SPD problems mein hota hai, jahan error ek slowly-decaying eigenvector se dominate hoti hai — toh har safe step systematically bahut chhota hota hai. Correction ko $\omega >1$ se multiply karna usi consistent direction mein aage extrapolate karta hai, toh hum remaining distance kam sweeps mein cover karte hain. $\omega =1$ set karne par plain Gauss-Seidel milta hai; $\omega <1$ ("under-relaxation") step chhota karta hai, sirf tab useful jab Gauss-Seidel overshoot kare. Convergence range (Ostrowski–Reich): symmetric positive-definite $A$ ke liye, SOR iteration converge karta hai if and only if $0<\omega <2.$ Us band ke bahar extrapolation itna zyada overshoot karta hai ki $\rho (T_{\omega })\ge 1$ aur error badh'ti hai. Andar ek single optimal ${\omega }^{\star }\in (1,2)$ hai jo $\rho (T_{\omega })$ minimize karta hai; 2D model-Laplacian grid ke liye, ${\omega }^{\star }\to 2$ jaata hai jab mesh refine hoti hai, jo Gauss-Seidel ke upar ek dramatic speedup deta hai. Aisi large sparse systems exactly woh hain jahan iterating Gaussian Elimination ko beat karta hai — unke origin ke liye Finite Difference Methods for PDEs dekho aur per-sweep cost $O(n)$ ke paas kyun rehti hai iske liye Sparse Matrices dekho.

$\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)$ par kaun faster hai, aur kitna? Gauss-Seidel: $\rho (T_{GS})=\frac{1}{4}$ vs Jacobi $\rho (T_J)=\frac{1}{2}$, toh ${\rho }_{GS}={\rho }_J^2$ — har sweep mein do gune zyada correct digits.

$\rho (T)<1$ (spectral radius ek se kam); SDD sirf ek sufficient shortcut hai.