# On Comparison Theorems for Splittings of  Different Semimonotone Matrices

Authors: Shu-Xin Miao; Yang Cao
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Comparison theorems between the spectral radii of different matrices are useful tools for judging the efficiency of preconditioners. In this paper, some comparison theorems for the spectral radii of matrices arising from proper splittings of different semimonotone matrices are presented.


---

## Body

## 1. Introduction and Preliminaries

LetO be the null matrix with suitable size. The notation A
≥
O
(
A
>
O
) denotes that all entries of matrix A are nonnegative (positive), and in this case matrix A is called nonnegative (positive). For two real m
×
n matrices, A
,
B, A
≥
B  (
A
>
B
) means that A
-
B
≥
O
(
A
-
B
>
O
). The same notation is valid for vectors. A real rectangular m
×
n matrix A is said to be semimonotone if A
†
≥
O [1]; here A
† is the Moore-Penrose inverse of A, that is, the unique matrix which satisfies the Moore-Penrose equation A
A
†
A
=
A, A
†
A
A
†
=
A
†, (
A
A
†
)
T
=
A
A
†, and (
A
†
A
)
T
=
A
†
A (B
T denotes the transpose of B); see [2, 3].Real rectangular linear system of the form(1)
A
x
=
b
,
where A is a real m
×
n matrix and b is a real m-vector, appears in many areas of mathematics. For example, finite difference discretization of partial differential equations with Neumann boundary conditions. Iterative methods for solving (1) can be formulated by the decomposition of A as A
=
U
-
V [4], and the approximation solution of (1) is generated by
(2)
x
(
k
+
1
)
=
U
†
V
x
(
k
)
+
U
†
b
.The decompositionA
=
U
-
V is called a proper splitting if R
(
A
)
=
R
(
U
) and N
(
A
)
=
N
(
U
) [4], where R
(
A
) and N
(
A
) are the range and kernel of A, respectively. Let ρ
(
C
) be the spectral radius of the real square matrix C; then, for the proper splitting A
=
U
-
V, the iterative scheme (2) converges to the minimal norm least square solution x
=
A
†
b of (1) for any initial vector x
0 if and only if ρ
(
U
†
V
)
<
1 [4, Corollary 1]. In this case, we say that the proper splitting A
=
U
-
V is a convergent splitting. Moreover, the fact that U
=
A
+
V is a proper splitting, as A
=
U
-
V is a proper splitting, implies that ρ
(
A
†
V
)
<
1 and I
+
A
†
V is invertible, so we have U
†
=
(
I
+
A
†
V
)
-
1
A
† [1, Theorem 2.2] and U
†
V
=
(
I
+
A
†
V
)
-
1
A
†
V. The next lemma shows the relation between the eigenvalues of U
†
V and A
†
V.Lemma 1 (see [1, Lemma 2.6]).
LetA
=
U
-
V be a proper splitting of real m
×
n matrix A. Let μ
i
,
1
≤
i
≤
s, and λ
j
,
1
≤
j
≤
s, be the eigenvalues of  U
†
V and A
†
V, respectively. Then for every j, we have 1
+
λ
j
≠
0. Also, for every i, there exists j such that μ
i
=
(
λ
j
/
(
1
+
λ
j
)
) and, for every j, there exists i such that λ
j
=
(
μ
i
/
(
1
-
μ
i
)
).For nonnegative matrix, there is a well-known result which is shown next.Lemma 2 (see [5, Theorem 2.21]).
LetA
,
B be n
×
n matrices; if A
≥
B
≥
O, then ρ
(
A
)
≥
ρ
(
B
).Using the notation of nonnegative matrix, the proper regular and proper weak regular splittings, which are the natural extensions of the regular and weak regular splittings of a real square matrix [5, 6], are defined as follows.Definition 3.
For a realm
×
n matrix A, the splitting A
=
U
-
V is called (1)
proper regular splitting if it is a proper splitting such thatU
†
≥
O and V
≥
O [7, Definition 1], [8, Definition 1.2];
(2)
proper weak regular splitting of first type if it is a proper splitting such thatU
†
≥
O and U
†
V
≥
O; proper weak regular splitting of second type if it is a proper splitting such that U
†
≥
O and V
U
†
≥
O [7, Definition 1], [8, Definition 1.2].It should be remarked that Jena et al. [8] only considered proper weak regular splitting of first type; they name it as proper weak regular splitting. The existence of the proper splitting is discussed in [4]; there is an example in [4] to show how to construct such splitting.LetA
=
U
-
V be a proper regular splitting of A; Berman and Plemmons in [4] showed that ρ
(
U
†
V
)
<
1 if and only if A
†
≥
O. Other convergence results of proper regular and/or weak regular splitting can be found in [8, 9]. Comparison theorems between the spectral radii of matrices are useful tools for analyzing the rate of convergence of iterative methods or for judging the efficiency of preconditioners [8, 10–12]. There is also a connection to population dynamics [11]. Some comparison theorems of proper splittings of a semimonotone matrix are established recently in [8, 13].Our basic purpose here is to give a new convergence theorem for proper weak regular splitting of a semimonotone matrix and to derive the comparison theorems of proper regular and proper weak regular splittings of different semimonotone matrices. The condition of new convergence theorem is weaker than that in [8], and the comparison results generalized the corresponding results in [5, 8, 11]. The comparison results can be further used for judging the efficiency of the preconditioners.


## 2. Main Results

Recall that the proper regular splitting of a semimonotone matrix is a convergent splitting [4, 8]. For proper weak regular splitting of a semimonotone matrix, we have the following convergence theorem.Theorem 4.
LetA
=
U
-
V be a proper weak regular splitting (of any type) of real m
×
n matrix A. If A
†
≥
O and A
†
V
≥
O, then
(3)
ρ
(
V
U
†
)
=
ρ
(
U
†
V
)
=
ρ
(
A
†
V
)
1
+
ρ
(
A
†
V
)
<
1
.Proof.
Note thatA
†
V
≥
O; the proof is essentially analogous to that in [8]. We omit it here.Remark 5.
Jena et al. [8] concluded that, for a proper weak regular splitting of real m
×
n matrix A, the convergence conditions are A
†
≥
O and V
≥
O, so the condition of Theorem 4 is weaker than that in [8]. To see this, let
(4)
A
=
[
2
-
1
0
-
3
2
0
]
,
U
[
2
0
0
-
3
1
0
]
,
V
=
[
0
1
0
0
-
1
0
]
.
Then A is a semimonotone matrix and A
=
U
-
V is a proper weak regular splitting of A. It is easy to see that A
†
V
≥
O and ρ
(
U
†
V
)
=
0.5
<
1, but V
≥
O does not hold.LetA
1 and A
2 be two semimonotone matrices and let A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 be proper splittings of A
1 and A
2, respectively. In what follows, we will present the comparison results between ρ
(
U
1
†
V
1
) and ρ
(
U
2
†
V
2
). The comparison theorems for proper regular splittings are given first.Theorem 6.
LetA
1 and A
2 be two semimonotone matrices and let A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 be proper regular splittings of A
1 and A
2, respectively. If A
2
†
≥
A
1
† and V
2
≥
V
1, then
(5)
ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
)
<
1
.Proof.
AsA
1 and A
2 are semimonotone matrices and A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 are proper regular splittings, it follows from [4] that ρ
(
U
i
†
V
i
)
<
1 for i
=
1,2. Thus all we need to show is ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
).
Fori
=
1,2, note that the matrices A
i
†
V
i are nonnegative; Perron-Frobenius theorem (cf. [5]) states that the spectral radius ρ
(
A
i
†
V
i
) of A
i
†
V
i is an eigenvalue corresponding to a nonnegative eigenvector; then from Lemma 1, (
ρ
(
A
i
†
V
i
)
/
(
1
+
ρ
(
A
i
†
V
i
)
)
)
≥
0 is an eigenvalue of U
i
†
V
i; hence, ρ
(
U
i
†
V
i
)
≥
(
ρ
(
A
i
†
V
i
)
/
(
1
+
ρ
(
A
i
†
V
i
)
)
). Again, by Perron-Frobenius theorem, U
i
†
V
i
≥
O implies existence of a nonnegative vector x  (
x
≠
0
) such that U
i
†
V
i
x
=
ρ
(
U
i
†
V
i
)
x. Then
(6)
A
i
†
V
i
x
=
(
I
-
U
i
†
V
i
)
-
1
U
i
†
V
i
x
=
ρ
(
U
i
†
V
i
)
1
-
ρ
(
U
i
†
V
i
)
x
implies (
ρ
(
U
i
†
V
i
)
/
(
1
-
ρ
(
U
i
†
V
i
)
)
)
≥
0 is an eigenvalue of A
i
†
V
i; hence, ρ
(
A
i
†
V
i
)
≥
(
ρ
(
U
i
†
V
i
)
/
(
1
-
ρ
(
U
i
†
V
i
)
)
); that is, ρ
(
U
i
†
V
i
)
≤
(
ρ
(
A
i
†
V
i
)
/
(
1
+
ρ
(
A
i
†
V
i
)
)
). Therefore, we have
(7)
ρ
(
U
i
†
V
i
)
=
ρ
(
A
i
†
V
i
)
1
+
ρ
(
A
i
†
V
i
)
.
Note that V
1
≥
O; then, A
2
†
≥
A
1
† and V
2
≥
V
1 lead to A
2
†
V
2
≥
A
1
†
V
1
≥
O, and Lemma 2 yields ρ
(
A
1
†
V
1
)
≤
ρ
(
A
2
†
V
2
). Let f
(
λ
)
=
(
λ
/
(
1
+
λ
)
); then, f
(
λ
) is a strictly increasing function for λ
>
0. Hence the inequality ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
) holds.Remark 7.
The assumptionsA
2
†
≥
A
1
† and V
2
≥
V
1 of  Theorem 4 can be weakened as A
2
†
V
2
≥
A
1
†
V
1.For different proper regular splittings of one semimonotone matrixA, the following corollary is obtained.Corollary 8 (see [8, Theorem 3.2]).
LetA be a semimonotone matrix and let A
=
U
1
-
V
1
=
U
2
-
V
2 be two proper regular splittings of A. If V
2
≥
V
1, then
(8)
ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
)
<
1
.When we consider the monotone matrices, we have the following corollaries directly.Corollary 9 (see [11, Theorem 4.2]).
LetA
1 and A
2 be two monotone matrices and let A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 be regular splittings of A
1 and A
2, respectively. If A
2
-
1
≥
A
1
-
1 and V
2
≥
V
1, then
(9)
ρ
(
U
1
-
1
V
1
)
≤
ρ
(
U
2
-
1
V
2
)
<
1
.Corollary 10.
LetA
1 and A
2 be two monotone matrices and let A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 be regular splittings of A
1 and A
2, respectively. If A
2
-
1
V
2
≥
A
1
-
1
V
1, then
(10)
ρ
(
U
1
-
1
V
1
)
≤
ρ
(
U
2
-
1
V
2
)
<
1
.Corollary 11 (see [5, Theorem 3.32]).
LetA be a monotone matrix and let A
=
U
1
-
V
1
=
U
2
-
V
2 be two regular splittings of A. If V
2
≥
V
1, then
(11)
ρ
(
U
1
-
1
V
1
)
≤
ρ
(
U
2
-
1
V
2
)
<
1
.Next the comparison results for proper weak regular splittings are given.Theorem 12.
LetA
1 and A
2 be two semimonotone matrices and let A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 be proper weak regular splittings of the same types of A
1 and A
2, respectively. If A
2
†
V
2
≥
A
1
†
V
1
≥
O, then
(12)
ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
)
<
1
.Proof.
Note thatA
2
†
V
2
≥
A
1
†
V
1
≥
O; from Theorem 4 we have ρ
(
U
i
†
V
i
)
<
1
(
i
=
1,2
). Analogous to the proof of Theorem 6, the desired comparison results are obtained.Theorem 13.
LetA
1 and A
2 be two semimonotone matrices and let A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 be proper weak regular splittings of different types of A
1 and A
2, respectively. Assume that A
1
†
-
A
2
†
≥
O and A
2
†
V
2
≥
O. If U
1
†
-
U
2
†
≥
A
1
†
-
A
2
†, then
(13)
ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
)
<
1
.Proof.
SinceA
2
=
U
2
-
V
2 is a proper weak regular splitting of semimonotone matrix A
2 and A
2
†
V
2
≥
O, it follows from Theorem 4 that ρ
(
U
2
†
V
2
)
<
1. Hence, it suffices to show that ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
).
Assume first thatA
1
=
U
1
-
V
1 is of second type and A
2
=
U
2
-
V
2 is of first type. Note that the splittings A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 are proper splittings; then, U
i
†
U
i
A
i
†
=
A
i
†, U
i
†
A
i
A
i
†
=
U
i
†, for i
=
1,2, and A
1
†
A
1
U
1
†
=
U
1
† and A
1
†
U
1
U
1
†
=
A
1
† (see, e.g., [3, Exercise 1.3(2)]). Using U
1
†
-
U
2
†
≥
A
1
†
-
A
2
† we obtain
(14)
U
2
†
V
2
A
2
†
=
U
2
†
(
U
2
-
A
2
)
A
2
†
=
A
2
†
-
U
2
†
≥
A
1
†
-
U
1
†
=
U
1
†
(
U
1
-
A
1
)
A
1
†
=
U
1
†
V
1
A
1
†
=
A
1
†
V
1
U
1
†
≥
O
.
For U
1
†
V
1
≥
O and U
2
†
V
2
≥
O, by Perron-Frobenius theorem (cf. [5]), there exist two nonzero vectors x
≥
0 and y
≥
0 such that
(15)
V
1
U
1
†
x
=
ρ
(
U
1
†
V
1
)
x
,
y
T
U
2
†
V
2
=
y
T
ρ
(
U
2
†
V
2
)
.
Thus
(16)
ρ
(
U
2
†
V
2
)
y
T
A
2
†
x
=
y
T
U
2
†
V
2
A
2
†
x
≥
y
T
A
1
†
V
1
U
1
†
x
=
ρ
(
U
1
†
V
1
)
y
T
A
1
†
x
.
By assumption A
1
†
≥
A
2
† we obtain
(17)
ρ
(
U
2
†
V
2
)
y
T
A
2
†
x
≥
ρ
(
U
1
†
V
1
)
y
T
A
2
†
x
.
Therefore
(18)
ρ
(
U
1
†
V
1
)
≤
ρ
(
U
2
†
V
2
)
.
The case that A
1
=
U
1
-
V
1 is of first type and A
2
=
U
2
-
V
2 is of second type can be proved in a similar way.
The proof is completed.When considering the monotone matrices, the conditionA
2
-
1
V
2
≥
O for the convergence of weak regular splitting (weak nonnegative splitting in [11]) is not necessary. Hence we have the following corollary.Corollary 14.
LetA
1 and A
2 be two monotone matrices and let A
1
=
U
1
-
V
1 and A
2
=
U
2
-
V
2 be weak regular splittings of different types of A
1 and A
2, respectively. Assume that A
1
-
1
-
A
2
-
1
≥
O. If U
1
-
1
-
U
2
-
1
≥
A
1
-
1
-
A
2
-
1, then
(19)
ρ
(
U
1
-
1
V
1
)
≤
ρ
(
U
2
-
1
V
2
)
<
1
.


## 3. Conclusion

In this paper, a new convergence theorem for proper weak regular splitting of a semimonotone matrix and two comparison theorems for proper weak regular and proper weak regular splittings of different semimonotone matrices are given. The obtained results are improved and/or generalized the previous results. Applying the comparison results to judge the efficiency of the preconditioners for rectangular linear system needs further study.



---

*Source: 329490-2014-07-06.xml*