Jump to content

Stein-Rosenberg theorem

From Wikipedia, the free encyclopedia

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

[edit]

Let . Let be the spectral radius of a matrix . Let and be the matrix splitting for the Jacobi method and the Gauss-Seidel method respectively.

Theorem: If for and for . Then, one and only one of the following mutually exclusive relations is valid:

  1. .
  2. .
  3. .
  4. .

Proof and applications

[edit]

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 is non-negative

Employing more hypotheses, on the matrix , 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

[edit]
  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.