Stein-Rosenberg theorem

Key takeaways

Stein-Rosenberg theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Stein-Rosenberg theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Stein-Rosenberg theorem from memory before moving on to harder problems.

Reference excerpt

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 i j ) ∈ R n × n {\displaystyle A=(a_{ij})\in \mathbb {R} ^{n\times n}} . Let ρ ( X ) {\displaystyle \rho (X)} be the spectral radius of a matrix X {\displaystyle X} . Let T J = D − 1 ( L + U ) {\displaystyle T_{J}=D^{-1}(L+U)} and T 1 = ( D − L ) − 1 U {\displaystyle T_{1}=(D-L)^{-1}U} be the matrix splitting for the Jacobi method and the Gauss-Seidel method respectively. Theorem: If a i j ≤ 0 {\displaystyle a_{ij}\leq 0} for i ≠ j {\displaystyle i\neq j} and a i i > 0 {\displaystyle a_{ii}>0} for i = 1 , … , n {\displaystyle i=1,\ldots ,n} . Then, one and only one of the following mutually exclusive relations is valid:

ρ ( T J ) = ρ ( T 1 ) = 0 {\displaystyle \rho (T_{J})=\rho (T_{1})=0} .

0 < ρ ( T 1 ) < ρ ( T J ) < 1 {\displaystyle 0<\rho (T_{1})<\rho (T_{J})<1} .

1 = ρ ( T J ) = ρ ( T 1 ) {\displaystyle 1=\rho (T_{J})=\rho (T_{1})} .

1 < ρ ( T J ) < ρ ( T 1 ) {\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. 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 {\displaystyle T_{J}} is non-negative

Employing more hypotheses, on the matrix A {\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.

References

Worked examples

Example 1 — a first encounter with Stein-Rosenberg theorem

Start with the simplest possible case. Write down what Stein-Rosenberg theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Stein-Rosenberg theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Stein-Rosenberg theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Stein-Rosenberg theorem

In research: Stein-Rosenberg theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Stein-Rosenberg theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Stein-Rosenberg theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Numerical linear algebra, Relaxation (iterative methods), Theorems in linear algebra, so understanding it makes those chapters shorter.
In everyday life: Look for Stein-Rosenberg theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Stein-Rosenberg theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Stein-Rosenberg theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Stein-Rosenberg theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Stein-Rosenberg theorem in simple terms?

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.

Why does Stein-Rosenberg theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Stein-Rosenberg theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Stein-Rosenberg theorem.