Stein-Rosenberg theorem

The Stein-Rosenberg theorem, proved in 1948, states that under certain premises, the Jacobi method and the Gauss-Seidel method are either both convergent, or both divergent. If they are convergent, then the Gauss-Seidel is asymptotically faster than the Jacobi method.

Statement

Let $A=(a_{ij})\in {ℝ}^{n\times n}$. Let $\rho (X)$ be the spectral radius of a matrix $X$. Let $T_J=D^{-1}(L+U)$ and $T_1=(D-L{)}^{-1}U$ be the matrix splitting for the Jacobi method and the Gauss-Seidel method respectively.

Theorem: If $a_{ij}\le 0$ for $i\ne j$ and $a_{ii}>0$ for $i=1,\dots ,n$. Then, one and only one of the following mutually exclusive relations is valid:

1. $\rho (T_J)=\rho (T_1)=0$.
2. $0<\rho (T_1)<\rho (T_J)<1$.
3. $1=\rho (T_J)=\rho (T_1)$.
4. $1<\rho (T_J)<\rho (T_1)$.

Proof and applications

The proof uses the Perron-Frobenius theorem for non-negative matrices. Its proof can be found in Richard S. Varga's 1962 book Matrix Iterative Analysis.

In the words of Richard Varga:

the Stein-Rosenberg theorem gives us our first comparison theorem for two different iterative methods. Interpreted in a more practical way, not only is the point Gauss-Seidel iterative method computationally more convenient to use (because of storage requirements) than the point Jacobi iterative matrix, but it is also asymptotically faster when the Jacobi matrix

$T_J$

is non-negative

Employing more hypotheses, on the matrix $A$, one can even give quantitative results. For example, under certain conditions one can state that the Gauss-Seidel method is twice as fast as the Jacobi iteration.