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

True. Since ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}$, the error dies for all ${\mathbf{e}}^{(0)}$ exactly when $T^k\to 0$. Diagonalizing $T=P\Lambda P^{-1}$ gives $T^k=P{\Lambda }^k{P}^{-1}$ with ${\Lambda }^k=\mathrm{diag}({\lambda }_i^k)$, and every ${\lambda }_i^k\to 0$ iff every $|{\lambda }_i|<1$, i.e. $\rho (T)<1$ (figure s01). This is the one non-negotiable law.

True. SDD is a sufficient condition guaranteeing $\rho (T)<1$ for both methods (the Gershgorin picture, figure s02, shows why), for any starting guess. It is a gift, not a requirement.

False. SDD is sufficient, not necessary. A non-SDD matrix can still have $\rho (T)<1$; the only honest test is the spectral radius itself.

False. It is usually faster (fresher data), and for many model problems $\rho (T_{GS})=\rho (T_J{)}^2$, but there exist matrices where Jacobi converges while Gauss-Seidel diverges and vice-versa. "Usually," never "always."

False. $T=M^{-1}N$ is built only from $A$'s splitting. The vector $\mathbf{b}$ only enters the constant term $\mathbf{c}=M^{-1}\mathbf{b}$, which affects where you converge, not whether you converge.

False. The asymptotic error shrinks by a factor $\approx \rho (T)$ per step, so smaller $\rho$ means faster. $\rho =0.1$ crushes the error tenfold each sweep; $\rho =0.99$ barely moves it.

False. At $\rho (T)=1$ the error component along the dominant eigenvector neither grows nor shrinks — it sits on the unit circle (figure s01) and never reaches the origin. You need strict $\rho (T)<1$.

True. Both touch every nonzero of $A$ once, so each sweep is $O(\text{nnz})$. GS's advantage is fewer sweeps, not cheaper sweeps.

True. ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}\to 0$ for any ${\mathbf{e}}^{(0)}$, since $T^k\to 0$. A good guess only reduces the number of steps, not the fate.

True in spirit. Row permutation changes which entries sit on the diagonal, which can turn a non-SDD matrix SDD (parent Example 3). It changes $A$'s splitting, hence $T$, hence $\rho$.

Error. Both formulas divide by $a_{ii}$; a zero diagonal entry gives division by zero on step one. Fix: permute rows first to place nonzeros on the diagonal.

Error. Reading lower-index terms from the old vector is Jacobi. GS must overwrite $x_i$ in place so later components in the same sweep see the fresh value.

Error. That is Gauss-Seidel (recall $M=D-L$, $N=U$). Jacobi uses $M=D$, giving $T_J=D^{-1}(L+U)$. The mix-up swaps which method you're actually running.

Error. $\rho$ is the maximum absolute eigenvalue; one small eigenvalue tells you nothing. Another eigenvalue could be $2.5$ (outside the unit circle). You must bound all of them.

Error (of effort, not logic). SDD already guarantees convergence via Gershgorin — the eigenvalue computation is wasted work. The whole point of the SDD shortcut is to avoid eigenvalues (see Eigenvalues and Eigenvectors).

Error. The convention is $A=D-L-U$, so $-L$ is the strictly lower part; hence $L$ holds the negatives of the below-diagonal entries. Getting the sign wrong flips terms in $T$.

Error. Strict dominance needs a strict inequality $>$ in every row. Equality is only "weakly" diagonally dominant (a Gershgorin disk that just touches the origin) and does not by itself guarantee convergence.

Because the error recurrence ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}$ multiplies the error by $T$ alone each step; the constant $\mathbf{c}=M^{-1}\mathbf{b}$ cancels out of the error equation when you subtract the true-solution identity ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$.

Diagonalizing $T=P\Lambda P^{-1}$ gives $T^k=P{\Lambda }^k{P}^{-1}$, and ${\lambda }_i^k\to 0$ requires each $|{\lambda }_i|<1$. The determinant (a product) or trace (a sum) can be small even when one eigenvalue exceeds 1, which alone causes divergence.

GS injects freshly-updated components immediately, so information propagates across the vector within a single sweep. This typically lowers $\rho (T_{GS})$ below $\rho (T_J)$, needing fewer sweeps for the same accuracy.

Elimination costs $\approx \frac{2}{3}{n}^3$ and destroys sparsity (fill-in). For huge Sparse Matrices each iterative sweep is only $O(\text{nnz})\approx O(n)$, so many cheap steps beat one crushing direct solve.

If $|a_{ii}|$ dominates its row, each variable $x_i$ is governed mainly by its own equation, so updating it perturbs the others only weakly — the coupling that could amplify errors is too small to let $\rho (T)$ reach 1. Geometrically, Gershgorin's disks stay small and clear of the unit circle.

Rewriting $A\mathbf{x}=\mathbf{b}$ as $\mathbf{x}=T\mathbf{x}+\mathbf{c}$ makes the true solution a fixed point ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$; iterating the map converges when the map is contractive, which for linear maps means $\rho (T)<1$.

SOR blends the GS update with an over-relaxation factor $\omega >1$ that pushes each step further along its direction, and a well-chosen $\omega$ can shrink $\rho (T)$ below the Gauss-Seidel value, accelerating convergence.

The clean argument $T^k=P{\Lambda }^k{P}^{-1}$ fails, but the theorem still holds: $T^k\to 0⟺\rho (T)<1$ via the Jordan form, where polynomial-in-$k$ factors appear but are crushed by $|\lambda {|}^k$ when $|\lambda |<1$.

$D=[a]$, $L=U=0$, so $T=0$ and $\rho (T)=0$: it "converges" in one step to $x=b/a$ — provided $a\ne 0$, which is the trivial edge of the divide-by-diagonal rule.

Then ${\mathbf{e}}^{(0)}=0$, so ${\mathbf{e}}^{(k)}=T^k\cdot 0=0$ for all $k$: you sit exactly on the answer. A stopping test $\Vert {\mathbf{x}}^{(1)}-{\mathbf{x}}^{(0)}\Vert <\epsilon$ triggers immediately.

Perfectly possible. $\rho (T)<1$ guarantees eventual decay, but non-normal $T$ can cause transient growth in early sweeps; the norm may rise briefly before the asymptotic $\approx \rho (T)$ rate takes over.

Consecutive iterates barely move each step, so the difference looks tiny while the true error is still large — you may stop prematurely far from ${\mathbf{x}}^{\ast }$. Checking the residual $\Vert \mathbf{b}-A{\mathbf{x}}^{(k)}\Vert$ guards against this.

Gauss-Seidel still converges (SPD is its own sufficient condition), even though the SDD shortcut does not apply. This is a headline example of "SDD fails yet convergence holds."

Jacobi uses only the old vector, so every $x_i^{(k+1)}$ computes independently and in parallel; Gauss-Seidel's in-place updates are inherently sequential, trading parallel speed for fewer sweeps — a real design tension in Finite Difference Methods for PDEs.