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 \mathbb {R} ^{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}\leq 0$ for $i\neq j$ and $a_{ii}>0$ for $i=1,\ldots ,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.