A GENERALIZATION OF YOUNG’S THEOREM

Saadat Moussavi

University of Wisconsin – Oshkosh

Abstract. The well known “SOR” method is obtained from a one–part splitting of the system matrix A, using one parameter ω.

M. Sisler introduced a new method by using one parameter for the lower triangular matrix L. Later he combined the above two methods to get a two parametric method [7], [8], and [9].

D. Young considered yet another two parametric method. The two parameters weight the diagonal of a positive–definite and consistently ordered 2–cyclic matrix [6]. Removing Young’s hypothesis that both parameters are in the interval (0, 1], we generalized his theorem.

1. Introduction. To find the solution vector x to the linear system Ax = b, where A is a sparse n × n matrix and b is a given n–vector of complex n–space, usually A is not easy to invert. Therefore, one seeks an easy–to–invert part of A, say A_{0}. Hence

(1.1)  A = A_{0} − A_{1}

or equivalently,

(1.2)  A = A_{0}(I − A_{0}^{−1}A_{1}) = A_{0}(I − B)

where B = A_{0}^{−1}A_{1} is called the iteration matrix. Relation (1.1) is called an additive splitting which defines the {x_{k}} for an arbitrary fixed x_{0} via,

A_{0}x_{k+1} − A_{1}x_{k} = b k = 0, 1, 2, …

or equivalently

\begin{aligned}x_{k+1} & = A_{0}^{−1}A_{1}x_{k} + A_{0}^{−1}b k = 0, 1, 2, … \\ x_{k+1} & = Bx_{k} + A_{0}^{−1}b k = 0, 1, 2, … \end{aligned}

Looking at relation (1.1), it is clear that if {x_{k}} converges at all, it must converge to x_{sol} = A^{−1}b (vector solution), where Ax_{sol} = b. Relation (1.2) shows that {x_{k}} converges to x_{sol} = A^{−1}b for each x_{0} if and only if ρ(B) < 1, where ρ(B) is the spectral radius of B [1,6]. Use relation (1.2) to measure the asymptotic convergence R_{∞} of the sequence {x_{k}} where R_{∞} is defined by R_{∞} = − log ρ(B) which carries information on how fast the sequence {x_{k}} converges. In fact, \frac{1}{R_{∞}} asymptotically represents the number of iterations that suffice to produce one additional decimal place of accuracy in x_{k}’s.

The above splitting is called stationary since there is no altering of parameter from iteration to iteration. It is called one part splitting since each x_{k+1} depends only on one previous vector x_{k}.

Examples of one–part stationary splitting are represented in the following important iteration methods.

\underline{JACOBI}: Choose

A_{0} = D , A_{1} = L + U .

Then

B_{jacobi} = B_{j} = D^{−1}(L + U)

where D is the diagonal part of A and −L, −U are strictly lower and upper triangular parts of A, respectively.

\underline{S.O.R.}: The Successive Overrelaxation (SOR) method was developed independently by Frankel [2] and Young [3], [4] in 1950. Choose

A_{0} = \frac{1}{ω} D − L , A_{1} = (\frac{1}{ω} − 1)D + U .

Then

(1.3)  B = B_{ω} = (D − ωL)^{−1}((1 − ω)D + ωU) .

\underline{MSOR}: The Modified Successive Overrelaxation (MSOR) method was first considered by Devogelaere [5] in 1958. Here is how it works. Consider the matrix A in the following form

A = ( \begin{matrix}D_{1} & M \\ N & D_{2} \end{matrix} )

where D_{1} and D_{2} are square non–singular matrices. Use ω for the “red” equations corresponding to D_{1} and ω′ for the “black” equations corresponding to D_{2} then

A_{0} = ( \begin{matrix}\frac{1}{ω} D_{1} & 0 \\ N & \frac{1}{ω′} D_{2} \end{matrix} )

and

A_{1} = A_{0} − A = ( \begin{matrix}(\frac{1}{ω} − 1)D_{1} & −M \\ 0 & (\frac{1}{ω′} − 1)D_{2} \end{matrix} )

Therefore, iteration matrix B_{(ω,ω′)} is defined by

(1.4)  B_{(ω,ω′)} = A_{0}^{−1}A_{1} ( \begin{matrix}(1 − ω)I_{1} & ωF \\ ω′(1 − ω)G & ωω′GF + (1 − ω′)I_{2} \end{matrix} )

where F = −D_{1}^{−1}M and G = −D_{2}^{−1}N. Young [6] has proved that if A is positive definite, then

ρ(B_{ω_{b}}) < \overline{ρ}(B_{(ω,ω′)})

where \overline{ρ}(B_{(ω,ω′)}) is the virtual spectral radius of B_{(ω,ω′)}. Young also showed that B_{1} (Gauss– Seidel iteration matrix) converges faster than MSOR if A is positive definite, 0 < ω ≤ 1 and 0 < ω′ ≤ 1.

In this paper a generalization of Young’s theorem (A is positive definite, 0 < ω ≤ 1 and 0 < ω′ ≤ 1) will be given (Theorem 2.2).

2. Generalized MSOR Method.

\underline{Lemma 2.1}. Let

A = ( \begin{matrix}D_{1} & M \\ N & D_{2} \end{matrix} )

where D_{1} and D_{2} are non–singular matrices. Let ρ(B_{j}) < 1 and assume all the eigenvalues of B_{j} are real. If 0 < ω ≤ 1 or 0 < ω′ ≤ 1, then the eigenvalues of B_{(ω,ω′)} are real.

\underline{Proof}. According to Young [6]

(λ + ω − 1)(λ + ω′ − 1) = λωω′μ^{2}

or equivalently

(2.1)  λ^{2} − (2 − ω − ω′ + ωω′μ^{2})λ + (ω − 1)(ω′ − 1) = 0

If ω = 1 or ω′ = 1 by equation (2.1) it is clear that λ is real. Assume that ω ≠ 1, ω′ ≠ 1 and 0 < ω′ < 1. Let △ be the discriminant of the quadratic equation (2.1), i.e.,

△ = (2 − ω − ω′ + ωω′μ^{2})^{2} − 4(ω − 1)(ω′ − 1)
(2.2)  △ = (1 − ω′μ^{2})^{2}ω^{2} − 2(ω′ − 2ω′μ^{2} + ω′^{2}μ^{2})ω + ω′^{2}

The parabola (2.2) has no x–intercept since the discriminant △′ of equation (2.2) is negative, because

\begin{aligned}△′ & = (ω′ − 2ω′μ^{2} + ω′^{2}μ^{2})^{2} − ω′^{2}(1 − ω′μ^{2}) \\ △′ & = 4ω′^{2}μ^{2}(μ^{2} − 1) + 4ω′^{3}μ^{2}(1 − μ^{2}) . \end{aligned}

Hence

(2.3)  △′ = 4ω′^{2}μ^{2}(1 − μ^{2})(ω′ − 1) .

Now by assumption since ω′ < 1 and μ^{2} < 1, relation (2.3) is negative. Therefore, parabola (2.2) has no x–intercept. But it is known that (1 − ω′μ^{2})^{2} > 0, then △ is always positive which implies that equation (2.1) has real roots. Lemma 2.1 is true for the case 0 < ω ≤ 1, because we can arrange △ as the following

△ = (1 − ωμ^{2})^{2}ω′^{2} − 2(ω − 2ωμ^{2} + ω^{2}μ^{2})ω′ + ω^{2} .
\underline{Theorem 2.2}. Let

A = ( \begin{matrix}D_{1} & M \\ N & D_{2} \end{matrix} )

where D_{1} and D_{2} are non–singular matrices. Assume that all the eigenvalues of B_{j} are real and μ_{1} = ρ(B_{j}) < 1. If 0 < ω ≤ 1 or 0 < ω′ ≤ 1, then

ρ(B_{(ω,ω′)}) ≥ ρ(B_{1}) ,

except for the following special cases. Choose ω and ω′ such that ωω′ > 1 and either

(a)  \frac{1}{ω} + \frac{1}{ω′} < 2 and \frac{(1 − ω)(1 − ω′)}{1 − ωω′} < μ_{1}^{2}

or

(b)  μ_{1}^{2} > \frac{(ω + ω′ − 2) + \sqrt{M}}{2(1 + ωω′)}

where M = ω^{2} + ω′^{2} + ωω′(−6 − 4ωω′ + 4ω + 4ω′).

\underline{Proof}.

(i) Suppose 0 < ω ≤ 1 and 0 < ω′ ≤ 1 (Young’s theorem [6]). (A new proof is given which is easier than Young’s. Use this proof to extend Young’s theorem). In relation (2.1)

λ^{2} − (2 − ω − ω′ + ωω′μ^{2})λ + (ω − 1)(ω′ − 1) = 0

By assumption 0 < ω ≤ 1 and 0 < ω′ ≤ 1 therefore,

(2.4)  b(μ) = 2 − ω − ω′ + ωω′μ^{2} > 0

and

(2.5)  λ_{i} = \frac{b(μ_{i}) ± \sqrt{b^{2}(μ_{i}) − 4(ω − 1)(ω′ − 1)}}{2} .

Because all λ_{i}’s are real, by Lemma 2.1 the spectral radius of B_{(ω,ω′)} is given by

(2.6)  ρ(B_{(ω,ω′)}) = \frac{b(μ_{1}) + \sqrt{b^{2}(μ_{1}) − 4(ω − 1)(ω′ − 1)}}{2} .

Thus,

\frac{b(μ_{1}) + \sqrt{b^{2}(μ_{1}) − 4(ω − 1)(ω′ − 1)}}{2} > μ_{1}^{2}

(2.7)  \sqrt{b^{2}(μ_{1}) − 4(ω − 1)(ω′ − 1)} > 2μ_{1}^{2} − b(μ_{1})

since 0 < ω ≤ 1 and 0 < ω′ ≤ 1

(2.8)  \frac{1}{ω} + \frac{1}{ω′} > 1

or

ω + ω′ > ωω′
(2.9)  ω + ω′ − 2 > ωω′ − 2 > μ_{1}^{2}(ωω′ − 2)

relation (2.9) holds because μ_{1}^{2} < 1. Therefore,

−μ_{1}^{2}(ωω′ − 2) + ω + ω′ − 2 > 0

or

2μ_{1}^{2} − (2 − ω − ω′ + μ_{1}^{2}ωω′) > 0 .

Since the right hand side of relation (2.7) is positive, one can square both sides of relation (2.7). Therefore,

b^{2}(μ_{1}) − 4(ω − 1)(ω′ − 1) > 4μ_{1}^{4} − 4μ_{1}^{2}b(μ_{1}) + b^{2}(μ_{1})

(1 − ωω′)μ_{1}^{4} − (2 − ω − ω′)μ_{1}^{2} + (ω − 1)(ω′ − 1) < 0 (2.10) (μ_{1}^{2} − 1)((1 − ωω′)μ_{1}^{2} − (ω − 1)(ω′ − 1)) < 0 . (2.11)

In this case one can show that

(2.12)  \frac{(1 − ω)(1 − ω′)}{1 − ωω′} < 1

holds since

\frac{1}{ω} + \frac{1}{ω′} > 2 .

One has also the following relation

(2.13)  \frac{(1 − ω)(1 − ω′)}{1 − ωω′} < μ_{1}^{2}

because clearly

\begin{aligned}ω′ − 1 + μ_{1}^{2}ω′ & < ω′ − 1 + μ_{1}^{2} \\ ω(ω′ − 1 + μ_{1}^{2}ω′) & < ω′ − 1 + μ_{1}^{2} . \end{aligned}

Hence

ωω′ − ω − ω′ + 1 < μ_{1}^{2}(1 − ωω′)

since 1 − ωω′ > 0 which implies

\frac{ωω′ − ω − ω′ + 1}{1 − ωω′} < μ_{1}^{2} .

This shows that inequality (2.13) is true. Thus by inequalities (2.12) and (2.13)

\frac{(1 − ω)(1 − ω′)}{1 − ωω′} < μ_{1}^{2} < 1 .

This implies that inequality (2.12) always holds because μ_{1}^{2} − 1 < 0, which means in this case

ρ(B_{(ω,ω′)}) > ρ(B_{1}) .

Of course if we choose (without loss of generality) ω > 1 and ω′ < 1 such that ωω′ < 1 then obviously

\frac{(1 − ω)(1 − ω′)}{1 − ωω′} < 0 .

Hence inequalities (2.13) and (2.12) always hold.

(ii) Assume (without loss of generality) 0 < ω′ ≤ 1 and

0 < ω < \frac{2 − ω′}{1 − ω′μ_{1}^{2}}

such that ωω′ > 1. By this assumption b(μ_{1}) > 0.

\underline{Claim}.

ρ(B_{(ω,ω′)}) > ρ(B_{1})

if and only if inequality (2.11) holds.

\underline{Proof of Claim}.

\frac{1}{ω} + \frac{1}{ω′} < 2

or

ωω′ − ω − ω′ + 1 > 1 − ωω′ .

Hence

\frac{(1 − ω)(1 − ω′)}{1 − ωω′} < 1

since 1 − ωω′ < 0. By assumption

(2.14)  \frac{(1 − ω)(1 − ω′)}{1 − ωω′} < μ_{1}^{2} < 1

which implies that inequality (2.11) be always true. Note that if

\frac{1}{ω} + \frac{1}{ω′} > 2 ,

then μ_{1}^{2} > 1.

(iii) Assume (without loss of generality) ω′ ≤ 1 and

ω ≥ \frac{2 − ω′}{1 − ω′μ_{1}^{2}}

then b(μ_{1}) < 0. Hence,

ρ(B_{(ω,ω′)}) = \frac{−b(μ_{1}) + \sqrt{b^{2}(μ_{1}) − 4(ω − 1)(ω′ − 1)}}{2} .

Suppose that

ρ(B_{(ω,ω′)}) < ρ(B_{1}) ,

then by the same argument in (i)

(2.15)  (1 + ωω′)μ_{1}^{4} + (2 − ω − ω′)μ_{1}^{2} + (ω − 1)(ω′ − 1) > 0 .

Inequality (2.15) holds if and only if either

(2.16)  \frac{(3 − 2\sqrt{2})ω′ + 2(\sqrt{2} − 1)ω′^{2}}{1 + 4ω′ − 4ω′^{2}} < ω < \frac{(3 + 2\sqrt{2})ω′ − 2(\sqrt{2} + 1)ω′^{2}}{1 + 4ω′ − 4ω′^{2}}

or

(2.17)  ω > \frac{(3 + 2\sqrt{2})ω′ − 2(\sqrt{2} + 1)ω′^{2}}{1 + 4ω′ − 4ω′^{2}}

(2.18)  ω < \frac{(3 − 2\sqrt{2})ω′ + 2(\sqrt{2} − 1)ω′^{2}}{1 + 4ω′ − 4ω′^{2}} .

Note that

(2.19)  μ_{1}^{2} > \frac{4ω′^{3} − 2(5 − \sqrt{2})ω′^{2} + 2(2 − \sqrt{2})ω′ + 2}{2(1 + \sqrt{2})ω′^{3} − (3 + 2\sqrt{2})ω′^{2}}

because its denominator is negative and its numerator is positive for 0 < ω′ ≤ 1, hence inequality (2.19) implies that

(2.20)  \frac{(3 + 2\sqrt{2})ω′ − 2(\sqrt{2} + 1)ω′^{2}}{1 + 4ω′ − 4ω′^{2}} < \frac{2 − ω′}{1 − ω′μ_{1}^{2}} .

Then inequality (2.16) and inequality (2.18) cannot hold since it contradicts

ω > \frac{2 − ω′}{1 − ω′μ_{1}^{2}}

so inequality (2.17) always holds. Now that inequality (2.17) holds, inequality (2.15) is true if and only if

(2.21)  μ_{1}^{2} < \frac{−(2 − ω − ω′) − \sqrt{M}}{2(1 + ωω′)} or μ_{1}^{2} > \frac{−(2 − ω − ω′) + \sqrt{M}}{2(1 + ωω′)} .

For ω > 1,

(ω − 1)(ω′ + \frac{1}{ω}) > 0

multiplying by (ω′ − 1),

((ω′ − 1)ω′)ω^{2} − (ω′ − 1)^{2} − (ω′ − 1) < 0 .

This implies −(2 − ω − ω′) − \sqrt{M} < 0. Then the first inequality of (2.21) cannot hold. Hence, inequality (2.15) holds when ω′ < 1,

ω′ > \frac{2 − ω′}{1 − ω′^{2}}

and the second inequality of (2.21) holds (part b).

\underline{Examples}.

(1) Suppose μ_{1}^{2} = 0.5, let ω′ = 0.8 and ω = 1.6, then ωω′ > 1,

\frac{(1 − ω)(1 − ω′)}{1 − ωω′} = 0.428571 < μ_{1}^{2}

and

\frac{1}{ω} + \frac{1}{ω′} < 2 .

Hence, all the conditions of case (a) hold. It follows that the spectral radii

ρ(B_{(ω,ω′)}) < ρ(B_{1})

where

ρ(B_{(ω,ω′)}) = 0.48

and ρ(B_{1}) = 0.5.

(2) Suppose μ_{1}^{2} = 0.5, let ω′ = 0.7 and ω = 1.9, then ωω′ > 1

\frac{(1 − ω)(1 − ω′)}{1 − ωω′} = 1.5 > μ_{1}^{2}

and

\frac{1}{ω} + \frac{1}{ω′} < 2 .

It follows that the spectral radii

ρ(B_{(ω,ω′)}) > ρ(B_{1})

where

ρ(B_{(ω,ω′)}) = 0.5737

and ρ(B_{1}) = 0.5.

(3) Suppose μ_{1}^{2} = 0.7, let ω′ = 0.7 and ω = 2.5, then

\frac{−(2 − ω − ω′) + \sqrt{M}}{2(1 + ωω′)} = 0.66778 < μ_{1}^{2} .

Hence, all the conditions of case (b) hold. It follows that the spectral radii

ρ(B_{(ω,ω′)}) < ρ(B_{1})

where

ρ(B_{(ω,ω′)}) = 0.683

and ρ(B_{1}) = 0.7.

(4) Suppose μ_{1}^{2} = 0.5, let ω′ = 0.7 and ω = 2.1, then

\frac{−(2 − ω − ω′) + \sqrt{M}}{2(1 + ωω′)} = 0.56 > μ_{1}^{2} .

It follows that the spectral radii

ρ(B_{(ω,ω′)}) > ρ(B_{1})

where

ρ(B_{(ω,ω′)}) = 0.61

and ρ(B_{1}) = 0.5.

\underline{References}

1. R. Plemmons and A. Berman, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979.

2. S. P. Frankel, “Convergence Rate of Iterative Treatments of Partial Differential Equations,” Math. Tables Aids Compute., 4 (1950), 65–75, 94, 488, 493.

3. D. Young, “Iterative Methods for Solving Partial Differential Equations of Elliptic Type,” Doctoral Thesis, Harvard University, (1950), Cambridge, Massachusetts.

4. D. Young, “Iterative Methods for Solving Partial Differential Equations of Elliptic Type,” Trans. Amer. Math. Soc., 76 (1954), 92–111, 54, 94, 95, 163, 227, 234, 265, 365.

5. R. Devogelaere, “Over–Relaxation, Abstract,” Amer. Math. Soc. Notices, 5 (1950), 147–273.

6. D. Young, Iterative Solution of Large Linear System of Equations, Academic Press, New York, 1971.

7. M. Sisler, “Uberein Iterationsverfahren fur Zyklische Matrizen,” Apl. Mat., 17 (1972), 225–233.

8. M. Sisler, “Uber die Knvergenenz eines Gewissen Iterationsverfahren fur Zyklische Matrizen,” Apl. Mat., 18 (1973), 89–98.

9. M. Sisler, “Uber die Optimierung einer Zweiparametrigen Iterationsverfahren,” Apl. Mat., 20 (1975), 126–142.