6th June 2023, 5 min read

Theorem of Stein and Rosenberg

Original post is here eklausmeier.goip.de/blog/2023/06-06-theorem-of-stein-rosenberg.

This post recaps content from Homer Walker in his handout, and Richard Varga's classic book "Matrix Iterative Analysis".

Below tables show the three standard iterations for solving the linear system $A x = b$ , with $A = (a_{i j}) \in R^{n \times n}$ , and $x, b \in R^{n}$ ; index $i$ is running $i = 1 (1) n$ . Split $A$ into $A = D - L - U$ , where $D$ is a diagonal matrix, $L$ is strictly lowertriangular, $U$ is strictly uppertriangular. $x^{ν}$ is the $ν$ -th iterate.

Jacobi iteration	Gauss-Seidel iteration	SOR
$x_{i}^{ν + 1} = (b_{i} - \sum_{j \neq i} a_{i j} x_{j}^{ν}) / a_{i i}$	$x_{i}^{ν + 1} = (b_{i} - \sum_{j < i} a_{i j} x_{j}^{ν + 1} - \sum_{j > i} a_{i j} x_{j}^{ν}) / a_{i i}$	$x_{i}^{ν + 1} = (1 - ω) x_{i} + \frac{ω}{a_{i i}} (b_{i} - \sum_{j < i} a_{i j} x_{j}^{ν + 1} - \sum_{j > i} a_{i j} x_{j}^{ν})$
$x^{ν + 1} = D^{- 1} [(L + U) x^{ν} + b]$	$x^{ν + 1} = (D - L)^{- 1} (U x^{ν} + b)$	$x^{ν + 1} = (D - ω L)^{- 1} {[(1 - ω) D + ω U] x^{ν} + ω b}$
$T_{J} = D^{- 1} (L + U)$	$T_{1} = (D - L)^{- 1} U$	$T_{ω} = (D - ω L)^{- 1} [(1 - ω) D + ω U]$

The difference between Jacobi and Gauss-Seidel is that the Gauss-Seidel iteration already uses the newly computed elements $x_{j}$ , for $j < i$ . The SOR (Successive Over-Relaxation) does likewise but employs a "damping" or overshooting factor $ω$ in addition to the Gauss-Seidel method. The case $ω = 1$ is the Gauss-Seidel method. $ω > 1$ is called overrelaxation, $ω < 1$ is called underrelaxation.

The iterations from above are called point iterations. If, instead, the $a_{i i}$ are taken as matrices, i.e., solve a linear equation in each iteration step, then the corresponding method is called a block-method.

Above iteration methods can be written as $x^{ν + 1} = T x^{ν} + c$ , with $T \in R^{n \times n}$ . Let $ρ (T)$ be the spectral radius of $T$ .

Theorem. The iterates $x^{ν}$ converge if and only if $ρ (T) < 1$ .

Proof: See "Matrix Iterative Analysis", theorem 1.4 using Jordan normal form, or theorem 5.1 in Auzinger/Melenk (2017) using the equivalence of norms in finite dimensional normed vectorspaces. A copy is here Iterative Solution of Large Linear Systems.

Theorem (Stein-Rosenberg (1948)): If $a_{i j} \leq 0$ for $i \neq j$ and $a_{i i} > 0$ for $i = 1, \dots, n$ . Then, one and only one of the following mutually exclusive relations is valid:

$ρ (T_{J}) = ρ (T_{1}) = 0$ .
$0 < ρ (T_{1}) < ρ (T_{J}) < 1$ .
$1 = ρ (T_{J}) = ρ (T_{1})$ .
$1 < ρ (T_{J}) < ρ (T_{1})$ .

Thus, the Jacobi method and the Gauss-Seidel method are either both convergent, or both divergent. If they are convergent then the Gauss-Seidel is faster than the Jacobi method.

Proof: See §3.3 in "Matrix Iterative Analysis".

From R. 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

Philip Stein born 1890 in Lithuania, graduated in South Africa, died 1974 in London. R.L. Rosenberg was a coworker at the University Technical College of Natal, South Africa.

Theorem. If $A$ is strictly or irreducibly diagonally dominant, then, both the point Jacobi and the point Gauss-Seidel converge for any starting value.

Proof: See "Matrix Iterative Analysis" theorem 3.4 cleverly using the Stein-Rosenberg theorem and the Perron-Frobenius theorem. Alternatively, see theorem 5.5 in Auzinger/Melenk (2017). and just using computation.

The Stein-Rosenberg theorem compares Jacobi and Gauss-Seidel iteration under mild conditions. If those conditions are sharpened then quantitative comparisons between Jacobi and Gauss-Seidel iteration can be made. In particular, a relation between the eigenvalues of $T_{J}$ and $T_{ω}$ can be given. Unrelated to Stein-Rosenberg but of general interest for the overrelaxation method is the theorem of Kahan (1958), which says that overrelaxation only converges for $0 < ω < 2$ , if at all. It is a necessary condition not a sufficient one.

Theorem (Kahan (1958)): $ρ (T_{ω}) \geq | ω - 1 |$ . Equality holds only if all eigenvalues of $T_{ω}$ are of modulus $| ω - 1 |$ .

Proof: See "Matrix Iterative Analysis" theorem 3.5.

Theorem (Ostrowski (1954)): Let $A = D - L - L^{*}$ be a Hermitian matrix and $D - ω L$ is nonsingular for $0 \leq ω \leq 2$ . Then, $ρ (T_{ω}) < 1$ if and only if $A$ is positive definite and $0 < ω < 2$ .

Proof: See theorem 3.6 in "Matrix Iterative Analysis". The case $ω = 1$ was first proved by Reich (1949).

Corollary: If $A$ is positive definite then any splitting will converge provided $0 < ω < 2$ .

Proof: See Corollary 2 in §3.4 in "Matrix Iterative Analysis".

Theorem. Let $A = I - L - U$ , where $L + U \geq 0$ irreducible and $ρ (L + U) < 1$ , where $L$ and $U$ are strictly lower and upper triangular matrices. Then $ρ (T_{ω}) < 1$ and underrelaxation with $ω \leq 1$ is not beneficial, i.e., $0 < ω_{1} < ω_{2} \leq 1$ then

0 < ρ (T_{ω_{2}}) < ρ (T_{ω_{1}}) < 1.

Proof: Theorem 3.16 in "Matrix Iterative Analysis" using the Stein-Rosenberg theorem.

The relation between the eigenvalues $λ$ of the overrelaxation method and the Jacobi iteration $μ$ for consistently ordered $p$ -cyclic matrices is

\begin{matrix} (V) & (λ + ω - 1)^{p} = λ^{p - 1} ω^{p} μ^{p} . \end{matrix}

Theorem. Let $A$ be consistently ordered $p$ -cyclic matrix with nonsingular submatrices. If $ω \neq 0$ , $λ$ is a nonzero eigenvalue of $T_{ω}$ and if $μ$ satisfies (V), then $μ$ is an eigenvalue of the block Jacobi matrix. Converseley, if $μ$ is an eigenvalue of $T_{J}$ and $λ$ satisfies (V), then $λ$ is an eigenvalue of $T_{ω}$ .

Proof: See "Matrix Iterative Analysis" theorem 4.3, or Varga's paper "p-Cyclic Matrices: A Generalization Of The Young-Frankel Successive Overrelaxation Scheme", or see local copy.

From R. Varga:

the main result of this section is a functional relationship (V) between the eigenvalues $μ$ of the block Jacobi matrix and the eigenvalues $λ$ of the block successive overrelaxation matrix. That such a functional relationship actually exists is itself interesting, but the importance of this result lies in the fact that it is the basis for the precise determination of the value of $ω$ which minimizes $ρ (T_{ω})$ .

For the special case $p = 2$ we have:

Corollary: The Gauss-Seidel iteration is twice as fast as the Jacobi iteration: $ρ (T_{1}) = ρ (T_{J})^{2} < 1$ . The relaxation factor $ω$ that minimizes $ρ (T_{ω})$ is

ω = \frac{2}{1 + \sqrt{1 - ρ (T_{J})^{2}}} .

For this $ω$ , the spectral radius $ρ (T_{ω}) = ω - 1$ .

So called M-matrices are relevant in the study of iteration methods. See M-matrix.