Question bank — Iterative methods — Jacobi, Gauss-Seidel, convergence

True. Kyunki ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}$, error tab sabke liye khatam hoga jab $T^k\to 0$. $T=P\Lambda P^{-1}$ diagonalize karne par $T^k=P{\Lambda }^k{P}^{-1}$ milta hai jahan ${\Lambda }^k=\mathrm{diag}({\lambda }_i^k)$, aur har ${\lambda }_i^k\to 0$ tab aur tabhi jab har $|{\lambda }_i|<1$, yaani $\rho (T)<1$ (figure s01). Yeh ek non-negotiable law hai.

True. SDD ek sufficient condition hai jo dono methods ke liye $\rho (T)<1$ guarantee karta hai (Gershgorin picture, figure s02, batata hai kyun), kisi bhi starting guess ke liye. Yeh ek gift hai, requirement nahi.

False. SDD sufficient hai, necessary nahi. Ek non-SDD matrix ka phir bhi $\rho (T)<1$ ho sakta hai; iska ek hi honest test hai — spectral radius khud.

False. Yeh usually faster hota hai (fresher data ki wajah se), aur kaafi model problems mein $\rho (T_{GS})=\rho (T_J{)}^2$ hota hai, lekin aisi matrices bhi exist karti hain jahan Jacobi converge kare aur Gauss-Seidel diverge kare aur vice-versa. "Usually," kabhi "always" nahi.

False. $T=M^{-1}N$ sirf $A$ ki splitting se banta hai. Vector $\mathbf{b}$ sirf constant term $\mathbf{c}=M^{-1}\mathbf{b}$ mein aata hai, jo affect karta hai ki tum kahan converge karte ho, naki karta hai ya nahi.

False. Asymptotic error har step mein $\approx \rho (T)$ factor se sirkata hai, toh chota $\rho$ matlab faster. $\rho =0.1$ har sweep mein error ko dasguna crush karta hai; $\rho =0.99$ muskil se hilata hai.

False. $\rho (T)=1$ par dominant eigenvector ke direction mein error component na badhta hai na ghatta — yeh unit circle par baitha rehta hai (figure s01) aur origin tak kabhi nahi pahunchta. Tumhe strict $\rho (T)<1$ chahiye.

True. Dono $A$ ke har nonzero ko ek baar touch karte hain, toh har sweep $O(\text{nnz})$ ka hai. GS ka faayda kam sweeps mein hai, saste sweeps mein nahi.

True. ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}\to 0$ kisi bhi ${\mathbf{e}}^{(0)}$ ke liye, kyunki $T^k\to 0$. Achha guess sirf steps ki sankhya kam karta hai, result nahi badalta.

Principle mein True. Row permutation ye change karta hai ki diagonal par kaun se entries baithte hain, jo ek non-SDD matrix ko SDD bana sakta hai (parent Example 3). Yeh $A$ ki splitting badalta hai, isliye $T$ badalta hai, isliye $\rho$ badalta hai.

Error. Dono formulas $a_{ii}$ se divide karte hain; zero diagonal entry pehle step par hi division by zero deta hai. Fix: pehle rows permute karo taaki diagonal par nonzeros aa jayein.

Error. Lower-index terms ko purane vector se padhna Jacobi hai. GS ko $x_i$ ko in place overwrite karna chahiye taaki same sweep mein baad ke components fresh value dekh sakein.

Error. Woh Gauss-Seidel hai (yaad karo $M=D-L$, $N=U$). Jacobi $M=D$ use karta hai, jisse $T_J=D^{-1}(L+U)$ milta hai. Yeh mix-up actually swap kar deta hai ki tum kaun sa method run kar rahe ho.

Error. $\rho$ maximum absolute eigenvalue hai; ek chota eigenvalue kuch nahi batata. Koi dusra eigenvalue $2.5$ ho sakta hai (unit circle ke bahar). Tumhe sab ko bound karna hoga.

Error (effort ka, logic ka nahi). SDD pehle se hi Gershgorin ke through convergence guarantee karta hai — eigenvalue computation waste of work hai. SDD shortcut ka poora point hi hai ki eigenvalues se bachna (dekho Eigenvalues and Eigenvectors).

Error. Convention hai $A=D-L-U$, toh $-L$ strictly lower part hai; isliye $L$ mein below-diagonal entries ke negatives hain. Sign galat karne par $T$ ke terms ulat jaate hain.

Error. Strict dominance ke liye har row mein strict inequality $>$ chahiye. Equality sirf "weakly" diagonally dominant hai (ek Gershgorin disk jo origin ko sirf touch karta hai) aur yeh khud convergence guarantee nahi karta.

Kyunki error recurrence ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}$ har step mein error ko sirf $T$ se multiply karta hai; constant $\mathbf{c}=M^{-1}\mathbf{b}$ error equation se cancel ho jaata hai jab tum true-solution identity ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$ subtract karte ho.

$T=P\Lambda P^{-1}$ diagonalize karne par $T^k=P{\Lambda }^k{P}^{-1}$ milta hai, aur ${\lambda }_i^k\to 0$ ke liye har $|{\lambda }_i|<1$ chahiye. Determinant (ek product) ya trace (ek sum) chota ho sakta hai tab bhi jab ek eigenvalue 1 se zyada ho, jo akela divergence cause karta hai.

GS freshly-updated components ko turant inject karta hai, toh ek hi sweep mein vector mein information propagate ho jaati hai. Yeh typically $\rho (T_{GS})$ ko $\rho (T_J)$ se neeche le jaata hai, same accuracy ke liye kam sweeps chahiye.

Elimination $\approx \frac{2}{3}{n}^3$ cost karta hai aur sparsity ko destroy karta hai (fill-in). Bade Sparse Matrices ke liye har iterative sweep sirf $O(\text{nnz})\approx O(n)$ ka hai, toh kai saste steps ek crushing direct solve se better hain.

Agar $|a_{ii}|$ apni row ko dominate karta hai, toh har variable $x_i$ mainly apni hi equation se govern hota hai, toh use update karne se doosron par sirf weak perturbation hoti hai — woh coupling jo errors ko amplify kar sakti thi woh itni choti hai ki $\rho (T)$ ko 1 tak pahunchne nahi deti. Geometrically, Gershgorin ke disks chote rehte hain aur unit circle se clear.

$A\mathbf{x}=\mathbf{b}$ ko $\mathbf{x}=T\mathbf{x}+\mathbf{c}$ ke roop mein rewrite karne par true solution ek fixed point ban jaata hai ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$; map ko iterate karna tab converge karta hai jab map contractive ho, jo linear maps ke liye matlab hai $\rho (T)<1$.

SOR GS update ko ek over-relaxation factor $\omega >1$ ke saath blend karta hai jo har step ko uske direction mein aur aage push karta hai, aur ek well-chosen $\omega$ se $\rho (T)$ ko Gauss-Seidel ki value se neeche le ja sakta hai, convergence accelerate karte hue.

Clean argument $T^k=P{\Lambda }^k{P}^{-1}$ fail hota hai, lekin theorem phir bhi hold karta hai: $T^k\to 0⟺\rho (T)<1$ Jordan form ke through, jahan polynomial-in-$k$ factors appear hote hain lekin jab $|\lambda |<1$ ho toh $|\lambda {|}^k$ unhe crush kar deta hai.

$D=[a]$, $L=U=0$, toh $T=0$ aur $\rho (T)=0$: yeh ek step mein $x=b/a$ par "converge" karta hai — provided $a\ne 0$ ho, jo divide-by-diagonal rule ka trivial edge case hai.

Tab ${\mathbf{e}}^{(0)}=0$, toh ${\mathbf{e}}^{(k)}=T^k\cdot 0=0$ sab $k$ ke liye: tum bilkul answer par baithe ho. Stopping test $\Vert {\mathbf{x}}^{(1)}-{\mathbf{x}}^{(0)}\Vert <\epsilon$ immediately trigger ho jaata hai.

Bilkul possible hai. $\rho (T)<1$ eventual decay guarantee karta hai, lekin non-normal $T$ early sweeps mein transient growth cause kar sakta hai; norm briefly badh sakta hai phir asymptotic $\approx \rho (T)$ rate aane se pehle.

Consecutive iterates har step mein barely move karte hain, toh difference chota lagta hai jabki true error abhi bhi bada hai — tum ${\mathbf{x}}^{\ast }$ se door premature stop kar sakte ho. Residual $\Vert \mathbf{b}-A{\mathbf{x}}^{(k)}\Vert$ check karna isse guard karta hai.

Gauss-Seidel phir bhi converge karta hai (SPD apna sufficient condition hai), chahe SDD shortcut apply na ho. Yeh "SDD fail hone par bhi convergence" ka ek headline example hai.

Jacobi sirf purana vector use karta hai, toh har $x_i^{(k+1)}$ independently aur parallel compute hota hai; Gauss-Seidel ke in-place updates inherently sequential hain, jo parallel speed ke badle kam sweeps leta hai — yeh Finite Difference Methods for PDEs mein ek real design tension hai.