Jacobi vs. Gauss-Seidel: convergence I know that for tridiagonal matrices the two iterative methods for linear system solving, the Gauss-Seidel method and the Jacobi one, either both converge or neither converges, and the Gauss-Seidel method converges twice as fast as the Jacobi one. Are there theorems relating the convergence speeds of these two methods when the system's matrix is not tridiagonal?
 A: Yes.  From pg. 233 of A Friendly Introduction to Numerical Analysis by Brian Bradie, we have the following:
Theorem.  Suppose $A$ is a an $n \times n$ matrix.  If $ a_{ii} > 0$ for each $i$ and $a_{ij} \leq 0$ whenever $ i \neq j$, then one and only one of the following statements holds:


*

*$0 \leq \rho (T_{gs}) < \rho (T_{jac}) < 1$

*$1 < \rho (T_{jac}) < \rho (T_{gs})$

*$\rho (T_{jac}) = \rho (T_{gs}) = 0$

*$\rho (T_{jac}) =\rho (T_{gs}) = 1$
where $T$ is the iteration matrix that arises for each method, and  $\rho (T)$ denotes the spectral radius of $T$.
Thus, for this larger class of matrices, the methods converge and diverge together.  When they converge, Gauss-Seidel converges faster; when they diverge, Gauss-Seidel again does so faster.
If you want the proof of this, Bradie cites the following sources:
A. Ralston and P. Rabinowitz, A First Course in Numerical Analysis, 2nd edition, McGraw-Hill, New York, 1978.
D. M. Young, Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.
