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 [math]\displaystyle{ A=(a_{ij})\in\mathbb{R}^{n\times n} }[/math]. Let [math]\displaystyle{ \rho(X) }[/math] be the spectral radius of a matrix [math]\displaystyle{ X }[/math]. Let [math]\displaystyle{ T_J=D^{-1}(L+U) }[/math] and [math]\displaystyle{ T_1=(D-L)^{-1}U }[/math] be the matrix splitting for the Jacobi method and the Gauss-Seidel method respectively.

Theorem: If [math]\displaystyle{ a_{ij}\le 0 }[/math] for [math]\displaystyle{ i\ne j }[/math] and [math]\displaystyle{ a_{ii} \gt 0 }[/math] for [math]\displaystyle{ i=1,\ldots,n }[/math]. Then, one and only one of the following mutually exclusive relations is valid:

1. [math]\displaystyle{ \rho(T_J) = \rho(T_1) = 0 }[/math].
2. [math]\displaystyle{ 0 \lt \rho(T_1) \lt \rho(T_J) \lt 1 }[/math].
3. [math]\displaystyle{ 1=\rho(T_J)=\rho(T_1) }[/math].
4. [math]\displaystyle{ 1 \lt \rho(T_J) \lt \rho(T_1) }[/math].

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 [math]\displaystyle{ T_J }[/math] is non-negative

Employing more hypotheses, on the matrix [math]\displaystyle{ A }[/math], 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.