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

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

1. ${\displaystyle \rho (T_{J})=\rho (T_{1})=0}$.
2. ${\displaystyle 0<\rho (T_{1})<\rho (T_{J})<1}$.
3. ${\displaystyle 1=\rho (T_{J})=\rho (T_{1})}$.
4. ${\displaystyle 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.^[1]

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 ${\displaystyle T_{J}}$ is non-negative

Employing more hypotheses, on the matrix ${\displaystyle 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.^[2]

References

1. Varga, Richard S. (1962). Matrix Iterative Analysis. ISBN 978-3-540-66321-8. OL 5858659M.
2. "Theorem of Stein and Rosenberg". eklausmeier.goip.de. 2023-06-06.