# Some Results on Preconditioned Mixed-Type Splitting Iterative Method

Authors: Guangbin Wang; Fuping Tan
Journal: Advances in Numerical Analysis
 (2013)

---

## Abstract

We present a preconditioned mixed-type splitting iterative method for solving the linear systemAx=b, where A is a Z-matrix. And we give some comparison theorems to show that the rate of convergence of the preconditioned mixed-type splitting iterative method is faster than that of the mixed-type splitting iterative method. Finally, we give one numerical example to illustrate our results.


---

## Body

## 1. Introduction

For solving linear system,(1)Ax=b,
where A is an n×n square matrix and x and b are n-dimensional vectors, the basic iterative method is
(2)Mxk+1=Nxk+b,k=0,1,…,
where A=M-N and M is nonsingular. Thus, (2) can be written as
(3)xk+1=Txk+c,k=0,1,…,
where T=M-1N and c=M-1b.Assuming thatA has unit diagonal entries, let A=I-L-U, where I is the identity matrix and -L and -U are strictly lower and strictly upper triangular parts of A, respectively.Transform the original system (1) into the preconditioned form as follows:
(4)PAx=Pb.Then, we can define the basic iterative scheme as follows:(5)Mpxk+1=Npxk+Pb,k=0,1,…,
where PA=Mp-Np and Mp is nonsingular. Thus, the equation above can also be written as
(6)xk+1=Txk+c,k=0,1,…,
where T=Mp-1Np and c=Mp-1Pb.In paper [1], Cheng et al. presented the mixed-type splitting iterative method as follows:
(7)(D+D1+L1-L)xk+1=(D1+L1+U)xk+b,(D+D1+L1-L)xk+11(D1U)xkk=0,1,2…,
with the following iterative matrix:
(8)T=(D+D1+L1-L)-1(D1+L1+U),
where D1 is an auxiliary nonnegative diagonal matrix, L1 is an auxiliary strictly lower triangular matrix, and 0≤L1≤L.In this paper, we will establish the preconditioned mixed-type splitting iterative method with the preconditionersPα=I+αL, Pβ=I+βU, and Pαβ=I+αL+βU for solving linear systems. And we obtain some comparison results which show that the rate of convergence of the preconditioned mixed-type splitting iterative method with Pαβ is faster than that of the preconditioned mixed-type splitting iterative method with Pα or Pβ. Finally, we give one numerical example to illustrate our results.


## 2. Preconditioned Mixed-Type Splitting Iterative Method

For the linear system (1), we consider its preconditioned form as follows:
(9)PαβAx=Pαβb,
with the preconditioner Pαβ=I+αL+βU; that is,
(10)Aαβx=bαβ.We apply the mixed-type splitting iterative method to it and have the corresponding preconditioned mixed-type splitting iterative method as follows:(11)(Dαβ+D1+L1-Lαβ)xk+1=(D1+L1+Uαβ)xk+bαβ,(Dαβ+D1+L1-Lαβ)xk+1=(D12Uαβ)xkk=0,1,2,…,
that is,
(12)xk+1=(Dαβ+D1+L1-Lαβ)-1(D1+L1+Uαβ)xk+(Dαβ+D1+L1-Lαβ)-1bαβ,k=0,1,2⋯,
So, the iterative matrix is
(13)T~=(Dαβ+D1+L1-Lαβ)-1(D1+L1+Uαβ),
where Dαβ, -Lαβ, and -Uαβ are the diagonal, strictly lower, and strictly upper triangular matrices obtained from Aαβ, D1 is an auxiliary nonnegative diagonal matrix, L1 is an auxiliary strictly lower triangular matrix, and 0≤L1≤Lαβ.If we chooseβ=0, we have the following corresponding iterative matrix:
(14)T-=(Dα+D1+L1-Lα)-1(D1+L1+Uα).
And if we choose α=0, we have the following corresponding iterative matrix:
(15)T^=(Dβ+D1+L1-Lβ)-1(D1+L1+Uβ).If we choose certain auxiliary matrices, we can get the classical iterative methods as follows.(1)
The PSOR method is(16)D1=1r(1-r)Dαβ,L1=0,L~r=(Dαβ-rLαβ)-1[(1-r)Dαβ+rUαβ].(2)
The PAOR method is(17)D1=1w(1-w)Dαβ,L1=1w(w-r)Lαβ,L~rw=(Dαβ-rLαβ)-1[(1-w)Dαβ+(w-r)Lαβ+wUαβ].We need the following definitions and results.Definition 1 (see [2]).
A matrixA is a Z-matrix if aij≤0, for all i,j=1,2,…n, such that i≠j. A matrix A is an L-matrix if aii>0,i=1,2,…n, and aij≤0, for all i,j=1,2,…n, such that i≠j.Definition 2 (see [2]).
A matrixA is an M-matrix if A is a nonsingular Z-matrix, and A-1≥0.Definition 3 (see [2, 3]).
LetM,N∈Rn,n. Then, A=M-N is called a regular splitting if M-1≥0 and N≥0; A=M-N is called an M-splitting if M is an M-matrix, N≥0.Lemma 4 (see [2]).
LetA≥0 be an irreducible matrix. Then,(1)
A has a positive real eigenvalue equal to its spectral radius;(2)
toρ(A), there corresponds an eigenvector x>0;(3)
ρ(A) is a simple eigenvalue of A.Lemma 5 (see [4]).
LetA be a nonnegative matrix. Then,(1)
ifαx≤Ax for some nonnegative vector x, x≠0, then α≤ρ(A);(2)
ifAx≤βx for some positive vector x, then ρ(A)≤β. Moreover, if A is irreducible and if 0≠αx≤Ax≤βx for some nonnegative vectors x, then
(18)α≤ρ(A)≤β.Lemma 6 (see [5]).
LetA=M-N be an M-splitting of A. Then, ρ(M-1N)<1 if and only if A is a nonsingular M-matrix.Lemma 7 (see [6, 7]).
LetA be a Z-matrix. Then, A is a nonsingular M-matrix if and only if there is a positive vector x such that Ax≥0.Lemma 8 (see [8]).
LetA=M-N be a regular splitting of A. Then, the splitting is convergent if and only if A-1≥0.Lemma 9 (see [9]).
LetA and B be two n×n nonsingular lower triangular L-matrices. If A≥B, then B-1≥A-1≥0.


## 3. Convergence Analysis and Comparison Results

Theorem 10.
LetA be a nonsingular Z-matrix. Assume that D1≥0, 0≤L1≤Lα, α∈[0,1], and T- and T are the iterative matrices given by (14) and (8), respectively. Consider the following.(i)
Ifρ(T)<1, then ρ(T-)<ρ(T)<1.(ii)
LetA be irreducible. Assume that 1-α∑l=1i-1ailalj>0 and aij+∑k=i+1naikakj≤0;
then,one has(1)
ρ(T-)≥ρ(T), if ρ(T)≥1,(2)
ρ(T-)≤ρ(T), if ρ(T)<1.Proof.
Let(19)Mα=Dα+D1+L1-Lα,Nα=D1+L1+Uα,M=I+D1+L1-L,N=D1+L1+U,Eα=(I+αL)(I+D1+L1-L),Fα=(I+αL)(D1+L1+U).
Then, we have(20)A=M-N,Aα=Mα-Nα=Eα-Fα.
(i) Since A is a nonsingular Z-matrix and D1≥0, 0≤L1≤Lα, it is clear that M=I+D1+L1-L is a nonsingular M-matrix and the splitting
(21)A=M-N=(I+D1+L1-L)-(D1+L1+U)
is an M-splitting. Since ρ(T)<1, it follows from Lemma 6 that A is a nonsingular M-matrix. Then, by Lemma 7, there is a positive vector x such that Ax≥0, so Aαx=(I+αL)Ax≥0.
By Lemma7, Aα is also a nonsingular M-matrix.
Obviously, we can get thatDα is a positive diagonal matrix. And from Lα is nonnegative, we know that Mα being a Z-matrix. Since Dα-1Lα≥0 is a strictly lower triangular matrix, so that ρ(Dα-1Lα)=0<1.
So, we have(I+Dα-1D1+Dα-1L1-Dα-1Lα)-1≥0.
Then,Mα-1=(I+Dα-1D1+Dα-1L1-Dα-1Lα)-1Dα-1≥0; hence, Mα is a nonsingular M-matrix.
Forj≠i+1, it is obvious that (Uα)ij=-aij+αaii+1ai+1j≥0. And for j=i+1, we have (Uα)ij=(α-1)aij≥0. Thus, Uα≥0 and Nα≥0.
We have proven thatAα=Mα-Nα and A=M-N are both M-splittings and Eα-1Fα=M-1N, two splittings Aα=Mα-Nα=Eα-Fα are nonnegative.
On the other hand, sinceLα=Dα-I+αD-+L-αL+αL2+αE-, we get
(22)Eα-Mα=(I+αL)(I+D1+L1-L)-(Dα+D1+L1-Lα)=(I+D1+L1-L)+αL(I+D1+L1-L)-(Dα+D1+L1-Lα)=I-L+αL+αLD1+αLL1-αL2-Dα+Lα=I-L+αL+αLD1+αLL1-αL2-Dα+Dα-I+αD-+L-αL+αL2+αE-=α(LD1+LL1+D-+E-)≥0,
which implies that
(23)Aα-1Eα-Aα-1Mα=Aα-1(Eα-Mα)≥0.
Therefore,Aα-1Eα≥Aα-1Mα≥0. So, we have ρ(Mα-1Nα)≤ρ(Eα-1Fα); that is,
(24)ρ(T-)≤ρ(T)<1.
(ii) Let A=I-L-U be irreducible. Since L+U is a nonnegative and irreducible matrix, and according to the proof of Lemma 4 in paper [9], we can obtain that T- and T are nonnegative and irreducible matrices. Thus, from Lemma 4, we know that there exists a positive vector x=(x1,x2⋯xn)T such that Tx=λx, where we denote λ=ρ(T), which is equivalent to
(25)(D1+L1+U)x=λ(I+D1+L1-L)x,(U-λI+λL)x=[(λ-1)D1+(λ-1)L1]x.
Let LU=D-+E-+F-, where D-, E-, and F- are the diagonal, lower triangular, and upper triangular parts of LU, respectively. So,
(26)Aα=Dα-Lα-Uα=(I-αD-)-(L-αL+αL2+αE-)-(U+αF-),
where Dα=I-αD-, Lα=L-αL+αL2+αE-, Uα=U+αF-.
Now, we consider(27)T-x-Tx=(Dα+D1+L1-Lα)-1×(D1+L1+Uα)x-λx=(Dα+D1+L1-Lα)-1×[(D1+L1+Uα)-λ(Dα+D1+L1-Lα)]x=(Dα+D1+L1-Lα)-1×[(D1+L1+U+αF-)-λ(I-αD-+D1+L1-L+αL-αL2-αE-)]x=(Dα+D1+L1-Lα)-1×{αL2[(D1+L1+U)-λ(I+D1+L1-L)]x+[αF-+λ(αD--αL+αL2+αE-)]xαL2}=(Dα+D1+L1-Lα)-1×[αF-+λ(αD--αL+αL2+αE-)]x=(Dα+D1+L1-Lα)-1×[(λ-1)αL(D1+L1)+(λ-1)α(D-+E-)]x=(λ-1)(Dα+D1+L1-Lα)-1×α[LD1+LL1+D-+E-]x.
Since Dα+D1+L1-Lα is an M-matrix, and LD1+LL1+D-+E-≥0, we have the following.(1)
Ifλ≥1, then T-x≥Tx=λx. By Lemma 5, we get ρ(T-)≥ρ(T).(2)
Ifλ<1, then T-x≤Tx=λx. By Lemma 5, we get ρ(T-)≤ρ(T).Theorem 11.
LetA be a nonsingular Z-matrix. Assume that D1≥0, 0≤L1≤Lαβ, α,β∈[0,1], and T~ and T are the iterative matrices given by (13) and (8), respectively. Consider the following.(i)
Ifρ(T)<1, then
(28)ρ(T~)<ρ(T)<1.(ii)
LetA be irreducible. Assume that
(29)1-α∑l=1i-1ailalj-β∑k=i+1naikakj>0,aij+∑k=i+1naikakj≤0;Then, one has (1)
ρ(T~)≥ρ(T) if ρ(T)≥1,(2)
ρ(T~)≤ρ(T) if ρ(T)<1.Proof.
Let(30)Mαβ=Dαβ+D1+L1-Lαβ,Nαβ=D1+L1+Uαβ,M=I+D1+L1-L,N=D1+L1+U,Eα=(I+αL+βU)(I+D1+L1-L),Fα=(I+αL+βU)(D1+L1+U).
Then, we have(31)A=M-N,Aαβ=Mαβ-Nαβ=Eαβ-Fαβ.
(i) By a similar proof of Theorem10, we can prove that Aαβ=Mαβ-Nαβ and A=M-N are both M-splitting and Eαβ-1Fαβ=M-1N, two splittings Aαβ=Mαβ-Nαβ=Eαβ-Fαβ, are nonnegative.
On the other hand, sinceLαβ=Dαβ-I+αD-+βD^+L-αL+αL2+αE-+βE^, we get
(32)Eαβ-Mαβ=(I+αL+βU)(I+D1+L1-L)-(Dαβ+D1+L1-Lαβ)=(I+D1+L1-L)+αL(I+D1+L1-L)+βU(I+D1+L1-L)-(Dαβ+D1+L1-Lαβ)=I-L+αL(I+D1+L1-L)+βU(I+D1+L1-L)-Dαβ+Lαβ=I-L+αL(I+D1+L1-L)+βU(I+D1+L1-L)-Dαβ+Dαβ-I+αD-+βD^+L-αL+αL2+αE-+βE^=β(U-F^)+βU(D1+L1)+α(D-+E-)+αL(D1+L1)≥0,
which implies that
(33)Aαβ-1Eαβ-Aαβ-1Mαβ=Aαβ-1(Eαβ-Mαβ)≥0.
Therefore,Aαβ-1Eαβ≥Aαβ-1Mαβ≥0. So, we have ρ(Mαβ-1Nαβ)≤ρ(Eαβ-1Fαβ); that is,
(34)ρ(T-)≤ρ(T)<1.
(ii) LetAαβ=PαβA=(I+αL+βU)A=I-L-U+αL(I-L-U)+βU(I-L-U)(35)=I-αD--βD^-(L-αL+αL2+αE-+βE^)-(U+αF--βU+βF^+βU2),
where LU=D-+E-+F-, UL=D^+E^+F^, and D-, E-, F-, D^, E^, and F^ are the diagonal, strictly lower, and strictly upper triangular matrices of LU and UL, respectively.
And denoteAαβ=Dαβ-Lαβ-Uαβ; then according to (35), we have
(36)Dαβ=I-αD--βD^,Lα=L-αL+αL2+αE-+βE,^Uαβ=U-βU+βU2+αF-+βF.^
By (25), we have
(37)T~x-λx=(Dαβ+D1+L1-Lαβ)-1×(D1+L1+Uαβ)x-λx=(Dαβ+D1+L1-Lαβ)-1×[(D1+L1+Uαβ)-λ(Dαβ+D1+L1-Lαβ)]x=(Dαβ+D1+L1-Lαβ)-1×[(D1+L1+U+αF--βU+βF^+βU2)-λ(I-αD--βD^+D1+L1-L+αL-αL2-αE--βE^)]x=(Dαβ+D1+L1-Lαβ)-1×{αE^[(D1+L1+U)-λ(I+D1+L1-L)]x+[αF--βU+βF^+βU2+-λ(-αD--βD^+αL-λ(-αL2-αE--αE^)]x}=(Dαβ+D1+L1-Lαβ)-1×[αF--βU+βF^+βU2-λ(-αD--βD^+αL-αL2-αE--αE^)]x=(Dαβ+D1+L1-Lαβ)-1×[αF-+λ(αD--αL+αL2+αE-)-βU+βU2+βF^+λ(βD^+βE^)]x=(λ-1)(Dαβ+D1+L1-Lαβ)-1×[αL(D1+L1)+α(D-+E-)+βU(D1+L1)+β(U-F^)]x=(λ-1)(Dαβ+D1+L1-Lαβ)-1×[(U-F^)(αL+βU)(D1+L1)+α(D-+E-)+β(U-F^)]x.
If aij+∑k=i+1naikakj≤0, then by the proof of Theorem 10, we have U-F^≥0.
Therefore, one has the following.(1)
Ifλ≥1, then T~x-λx≥0 but not equal to 0. Therefore, T~x≥λx. By Lemma 5, we get ρ(T~)≥λ=ρ(T).(2)
Ifλ<1, then T~x-λx≤0 but not equal to 0. Therefore, T~x≤λx. By Lemma 5, we get ρ(T~)≤λ=ρ(T).
Remark. If we choose α=0 in Theorem 11, we have a similar result which is showed by the following corollary.Corollary 12.
LetA be a nonsingular Z-matrix. Assume that D1≥0, 0≤L1≤Lβ, β∈[0,1], and T^ and T are the iterative matrices given by (15) and (8), respectively. Consider the following.(i)
Ifρ(T)<1, then
(38)ρ(T^)<ρ(T)<1.(ii)
LetA be irreducible. Assume that
(39)1-β∑k=i+1naikakj>0,aij+∑k=i+1naikakj≤0;
then, one has(1)
ρ(T^)≥ρ(T) if ρ(T)≥1,(2)
ρ(T^)≤ρ(T) if ρ(T)<1.
Now, one will provide some results to show the relations amongρ(T~), ρ(T-), and ρ(T^).Theorem 13.
LetA=(aij)∈Rn×n be a nonsingular Z-matrix. Let T~ and T- be iterative matrices given by (13) and (14), respectively. Assume that α,β∈[0,1], D1≥0, 0≤L1≤Lαβ. If 1-α∑l=1i-1ailalj-β∑k=i+1naikakj>0 and aij+∑k=i+1naikakj≤0, then(1)
ρ(T~)≥ρ(T-) if ρ(T)≥1;(2)
ρ(T~)≤ρ(T-) if ρ(T)<1.Proof.
SinceDαβ+D1+L1-Lαβ and Dα+D1+L1-Lα are two lower triangular L-matrices with Dαβ+D1+L1-Lαβ≤Dα+D1+L1-Lα, by Lemma 9, we have
(40)(Dαβ+D1+L1-Lαβ)-1≥(Dα+D1+L1-Lα)-1≥0.
By the proof of Theorems10 and 11, we consider
(41)T~x-T-x=T~x-λx-(T-x-λx)=(λ-1)(Dαβ+D1+L1-Lαβ)-1×[(αL+βU)(D1+L1)+αD-+αE-+β(U-F^)]x-(Dα+D1+L1-Lα)-1×[αL(D1+L1)+αD-+αE-]x≥(λ-1)(Dαβ+D1+L1-Lαβ)-1×(βU(D1+L1)+β(U-F^))x.
In view of the proof of Theorem11, we have βU(D1+L1)+β(U-F^)≥0.
Therefore, one has the following.(1)
Ifλ≥1, the right-hand side of the above inequality is more than zero. By Lemma 8, ρ(T~)≥ρ(T-).(2)
Ifλ<1, the right-hand side of the above inequality is more than zero. By Lemma 8, ρ(T~)≤ρ(T-).Theorem 14.
LetA=(aij)∈Rn×n be a nonsingular Z-matrix. Let T~ and T^ be iterative matrices given by (13) and (15), respectively. Assume that α,β∈[0,1], D1≥0, 0≤L1≤Lαβ. If 1-α∑l=1i-1ailalj-β∑k=i+1naikakj>0 and aij+∑k=i+1naikakj≤0,
then(1)
ρ(T~)≥ρ(T^) if ρ(T)≥1,(2)
ρ(T~)≤ρ(T^) if ρ(T)<1.Proof.
SinceDαβ+D1+L1-Lαβ and Dβ+D1+L1-Lβ are two lower triangular L-matrices with Dαβ+D1+L1-Lαβ≤Dβ+D1+L1-Lβ, by Lemma 9, we have
(42)(Dαβ+D1+L1-Lαβ)-1≥(Dβ+D1+L1-Lβ)-1≥0.
By the proof of Corollary12 and Theorem 11, we consider
(43)T~x-T^x=T~x-λx-(T^x-λx)=(λ-1)(Dαβ+D1+L1-Lαβ)-1×[(αL+βU)(D1+L1)+αD-+αE-+β(U-F^)]x-(Dα+D1+L1-Lα)-1×[βU(D1+L1)+β(U-F^)]x≥(λ-1)(Dαβ+D1+L1-Lαβ)-1×(αL(D1+L1)+αD-+αE-)x.
SinceαL(D1+L1)+αD-+αE-≥0, we get the following.(1)
Ifλ≥1, the right-hand side of the above inequality is more than zero. By Lemma 8, ρ(T~)≥ρ(T^).(2)
Ifλ<1, the right-hand side of the above inequality is more than zero. By Lemma 8, ρ(T~)≤ρ(T^).
Remark. The results (theorems and corollaries) in Section 3 are in some sense the generalized Stein-Rosenberg-type theorems like those in the papers [10–13]. The results (theorems and corollaries) in Section 3 are the comparisons of spectral radius of iterative matrices between the mixed-type splitting method and the preconditioned mixed-type splitting method, while the results in the papers [10–13] are the comparisons of spectral radius of iterative matrices between the parallel decomposition-type relaxation method and its special case.


## 4. Numerical Example

Consider the following equation:(44)-Δu+∂u∂x+∂u∂y=f,
in the unit square Ω with Dirichlet boundary conditions.If we apply the central difference scheme on a uniform grid withN×N interior nodes (N2=n) to the discretization of the above equation, we can get a system of linear equations with the coefficient matrix
(45)A=I⊗P+Q⊗I,
where ⊗ denotes the Kronecker product,
(46)P=tridiag(-2+h8,1,-2-h8),Q=tridiag(-1+h4,1,-1-h4)
are N×N tridiagonal matrices, and the step size is h=1/N.We chooseN=5; then A∈R25×25.If we choose(1)
D1=0.45Dα, L1=0.4Lα, α∈[0,0.5],(2)
D1=0.45Dβ, L1=0.4Lβ, β∈[0,0.5],(3)
D1=0.45Dαβ, L1=0.4Lαβ, α=β∈[0,0.5], then we can obtain the following results by Theorems 10–14.Table1 shows that that the rate of convergence of the preconditioned mixed-type splitting method is faster than that of the mixed-type splitting method. And it shows that the rate of convergence of the preconditioned mixed-type splitting method with Pαβ is faster than that of the preconditioned mixed-type splitting method with Pα or Pβ.Table 1
α
(
β
)
ρ
(
T
)
ρ
(
T
-
)
ρ
(
T
^
)
ρ
(
T
~
)
0
0.563691
0.563691
0.563691
0.563691
0.05
0.563691
0.554915
0.554027
0.545537
0.1
0.563691
0.545958
0.544027
0.527441
0.15
0.563691
0.536827
0.533673
0.509401
0.2
0.563691
0.527531
0.522949
0.491418
0.25
0.563691
0.518081
0.511842
0.473488
0.3
0.563691
0.508493
0.500331
0.455608
0.35
0.563691
0.498782
0.488412
0.437775
0.4
0.563691
0.488967
0.476073
0.419983
0.45
0.563691
0.479065
0.463309
0.402227
0.5
0.563691
0.469097
0.450121
0.384541



---

*Source: 512084-2013-12-03.xml*