# Block Preconditioned SSOR Methods forH-Matrices Linear Systems

Authors: Zhao-Nian Pu; Xue-Zhong Wang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We present a block preconditioner and consider block preconditioned SSOR iterative methods for solving linear systemAx=b. When A is an H-matrix, the convergence and some comparison results of the spectral radius for our methods are given. Numerical examples are also given to illustrate that our methods are valid.


---

## Body

## 1. Introduction

For the 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 for solving (1) 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, c=M-1b.Let us consider the following partition ofA:
(4)A=(A11A12⋯A1mA21A22⋯A2m⋮⋮⋱⋮Am1Am2⋯Amm),
where the blocks Aii∈Cni×ni, i=1,…,m, are nonsingular and n1+n2+⋯+nm=n.Usually we splitA into
(5)A=D-L-U,
where D=diag(A11,…,Amm), -L and -U are strictly block lower and strictly block upper triangular parts of A, respectively. Let 0<ω<2, and
(6)M=1ω(2-ω)(D-ωL)D-1(D-ωU),N=1ω(2-ω)((1-ω)D+ωL)D-1((1-ω)D+ωU).
Then, the iteration matrix of the SSOR method for A is given by
(7)ℒω=M-1N=(D-ωU)-1D(D-ωL)-1×((1-ω)D+ωL)D-1×((1-ω)D+ωU).Transforming the original system (1) into the preconditioned form
(8)PAx=Pb,
then we can define the basic iterative scheme:
(9)Mpxk+1=Npxk+Pb,k=0,1,…,
where PA=Mp-Np and Mp is nonsingular. Thus (9) can also be written as
(10)xk+1=Txk+c,k=0,1,…,
where T=Mp-1Np,c=Mp-1Pb. Similar to the original system (1), we call the basic iterative methods corresponding to the preconditioned system the preconditioned iterative methods.WhenA is an M-matrix, Alanelli and Hadjidimosin [1] considered the preconditioner P=Q+S, where Q=diag(L11-1,I22,…,Imm) and S is given by
(11)S=(O11O12⋯O1m-A21L11-1O22⋯O2m⋮⋮⋱⋮-Am1L11-1Om2⋯Omm),
with L11 being the lower triangular matrix in the LU triangular decomposition of A11.We consider the preconditionerP1=I+S1, where (12)I+S1=(I11-α1A11-1A1sI22-α2A22-1A2t⋱⋱-αmAmm-1AmuImm).Let(13)P1A=(I+S1)(D-L-U)=D~-L~-U~,
where D~, -L~ and -U~ are block diagonally, strictly block lower, and strictly block upper triangular parts of P1A, respectively. If D~ is nonsingular, then (D~-ωL~)-1 and (D~-ωU~)-1 exist and it is possible to define the SSOR iteration matrix for P1A. Namely,
(14)ℒ~ω=(D~-ωU~)-1D~(D~-ωL~)-1×((1-ω)D~+ωL~)D~-1((1-ω)D~+ωU~).Alanelli and Hadjidimos in [1] showed that the preconditioned Gauss-Seidel, the preconditioned SOR, and the preconditioned Jacobi methods with preconditioner P are better than original methods. Our work in the presentation is to prove convergence of the block preconditioned SSOR method with preconditioner P1 and give some comparison results of the spectral radius for the case when A is an H-matrix.Let|A| denote the matrix whose elements are the moduli of the elements of the given matrix. We call 〈A〉=(a-ij) to comparison matrix if a-ij=|aij| for i=j, if a-ij=-|aij| for i≠j. For (4), under the previous definition, we have
(15)〈A〉=(〈A11〉-|A12|⋯-|A1m|-|A21|〈A22〉⋯-|A2m|⋮⋮⋱⋮-|Am1|-|Am2|⋯〈Amm〉).
Let 〈A〉=〈D〉-|L|-|U|, where 〈D〉, -|L|, and -|U| are block diagonally, strictly block lower, and strictly block upper triangular parts of 〈A〉, respectively.Notice that the preconditioner of the matrix〈A〉 corresponding to P1 is P2=I+S2; namely, (16)I+S2=(I11|α1|〈A11〉-1|A1s|I22|α2|〈A22〉-1|A2t|⋱⋱|αm|〈Amm〉-1|Amu|Imm).LetP2〈A〉=(I+S2)〈A〉=D--L--U-, where D-, -L-, and -U- are block diagonally, strictly block lower, and strictly block upper triangular parts of P2〈A〉, respectively.IfD- is nonsingular, then (D--ωL-)-1 and (D--ωU-)-1 exist and the SSOR iteration matrix for P2〈A〉 is as follows:
(17)ℒ-ω=(D--ωU-)-1D-(D--ωL-)-1×((1-ω)D-+ωL-)D--1((1-ω)D-+ωU-).


## 2. Preliminaries

A matrixA is called nonnegative (positive) if each entry of A is nonnegative (positive). We denote it by A≥0 (A>0). Similarly, for n-dimensional vector x, we can also define x≥0 (x>0). Additionally, we denote the spectral radius of A by ρ(A). AT denotes the transpose of A. A matrix A=(aij) is called a Z-matrix if for any i≠j, aij≤0. A Z-matrix is a nonsingular M-matrixif A is nonsingular and A-1≥0, If 〈A〉 is a nonsingular M-matrix, then A is called an H-matrix. A=M-N is said to be a splitting of A if M is nonsingular, A=M-N is said to be regular if M-1≥0 and N≥0, and weak regular if M-1≥0 and M-1N≥0, respectively.Some basic properties on special matrices introduced previously are given to be used in this paper.Lemma 1 (see [2]).
Let A be aZ-matrix. Then the following statements are equivalent.(a)
Ais an M-matrix.(b)
There is a positive vectorx such that Ax>0.(c)
A-1≥0.(d)
All principal submatrices ofA are M-matrices.(e)
All principal minors are positive.Lemma 2 (see [3, 4]).
LetA be an M-matrix and let A=M-N be a weak regular splitting. Then ρ(M-1N)<1.Lemma 3 (see [2]).
LetA and B be two n×n matrices with 0≤B≤A. Then ρ(B)≤ρ(A).Lemma 4 (see [5]).
IfA is an H-matrix, then |A-1|≤〈A〉-1.Lemma 5 (see [6]).
Suppose thatA1=M1-N1 and A2=M2-N2 are weak regular splitting of monotone matrices A1 and A2, respectively, such that M2-1≥M1-1. If there exists a positive vector x such that 0≤A1x≤A2x, then for the monotone norm associated with x,
(18)∥M1-1N1∥x≤∥M2-1N2∥x.
In particular, if M1-1N1 has a positive Perron vector, then
(19)ρ(M1-1N1)≤ρ(M2-1N2).
Moreover if x is a Perron vector of M1-1N1 and strict inequality holds in (18), then strict inequality holds in (19).Lemma 6.
IfA and B are two n×n matrices, then 〈A-B〉≥〈A〉-|B|.Proof.
It is easy to see that|aij-bij|≥|aij|-|bij|, for i=j, and -|aij-bij|≥-|aij|-|bij|, for i≠j. Therefore, 〈A-B〉≥〈A〉-|B| is true.Lemma 7.
IfA is an H-matrix with unit diagonal elements, then ∥〈A〉-1∥∞>1.Proof.
Let〈A〉=I-B, from 〈A〉 being an M-matrix; then B≥0 and ρ(B)<1, and thus, we have
(20)〈A〉-1=∑K=0∞‍Bk≥I
and then ∥〈A〉-1∥∞>1.


## 3. Convergence Results

Letei=(1,…,1)T∈Rni, i=1,2,…,m, e=(e1T,…,emT)T, r=(r1T,…,rmT)T=〈A〉-1e, Oi=(0,…,0)T∈Rni, where r and e are partitioned in accordance with the block partitioning of the matrix A, and let
(21)si=∥〈Aii〉-1|Aik|ek∥∞,hi=1si(2∥〈A〉-1∥∞-1),i=1,2,…,m.Theorem 8.
LetA be a nonsingular H-matrix; if |αi|<hi, i=1,2,…,m, then P1A is also an H-matrix.Proof.
FromA being an H-matrix, we have r>0, and rk≤∥〈A〉-1∥∞ek. Let
(22)((P1A)ij)={Aij-αiAii-1AikAkj,i≠j,i,j=1,2,…,m,k≠i,Aii-αiAii-1AikAki,i=j,i,j=1,2,…,m,k≠i.
Then
(23)(〈P1A〉r)i=〈Aii-αiAii-1AikAki〉ri-∑j≠i,km‍|Aij-αiAii-1AikAkj|rj-|Aik-αiAii-1AikAkk|rk≥〈Aii〉ri-|αi||Aii-1||Aik||Aki|ri-∑j≠i,km‍|Aij|-∑j≠i,km‍|αi||Aii-1||Aik||Akj|rj-|Aik|rk-|αi||Aii-1||Aik||Akk|rk≥ei-|αi|〈Aii〉-1|Aik||Aki|ri-∑j≠i,km‍|αi|〈Aii〉-1|Aik||Akj|rj-|αi|〈Aii〉-1|Aik||Akk|rk=ei+|αi|〈Aii〉-1|Aik|×(-∑j≠km‍|Akj|rj-|Akk|rk×+〈Akk〉rk-〈Akk〉rk∑j≠km‍)=ei+|αi|〈Aii〉-1|Aik|(ek-2rk)≥ei-|αi|(2∥〈A〉-1∥∞-1)〈Aii〉-1|Aik|ek≥ei-|αi|si(2∥〈A〉-1∥∞-1)ei>Oi.
Therefore, 〈P1A〉 is an M-matrix, and then P1A is an H-matrix.Theorem 9.
IfA is a nonsingular H-matrix with unit diagonal elements, 0<ω≤1 and |αi|<hi,i=1,2,…,m. Then ρ(ℒ~ω)<1.Proof.
From Theorem8, we know 〈P1A〉=〈D~〉-|L~|-|U~| is an M-matrix; if we let
(24)〈P1A〉=1ω(2-ω)(〈D~〉-ω|L~|)〈D~〉-1(〈D~〉-ω|U~|)-1ω(2-ω)((1-ω)〈D~〉+ω|L~|)〈D~〉-1×((1-ω)〈D~〉+ω|U~|),
then the SSOR iteration matrix for 〈P1A〉 is as follows:
(25)ℒ¨ω=(〈D~〉-ω|U~|)-1〈D~〉(〈D~〉-ω|L~|)-1×((1-ω)〈D~〉+ω|L~|)〈D~〉-1×((1-ω)〈D~〉+ω|U~|).
Since 〈P1A〉 is an M-matrix; we have 〈D~〉, 〈D~〉-ω|L~| and 〈D~〉-ω|U~| are M-matrices; by simple calculation, we obtain that (24) is a weak regular splitting; from Lemma 2, we know that ρ(ℒ¨ω)<1. Since
(26)|ℒ~ω|=|(D~-ωU~)-1D(D~-ωL~)-1×((1-ω)D~+ωL~)D-1((1-ω)D~+ωU~)(D~-ωL~)-1|=|(I-ωD~-1U~)-1(I-ωD~-1L~)-1×((1-ω)I+ωD-1L~)((1-ω)I+ωD~-1U~)(D~-ωL~)-1|≤|(I-ωD~-1U~)-1||(I-ωD~-1L~)-1|×|((1-ω)I+ωD-1L~)||((1-ω)I+ωD~-1U~)|≤(I-ω〈D~〉-1|U~|)-1(I-ω〈D~〉-1|L~|)-1×((1-ω)I+ω〈D~〉-1|L~|)((1-ω)I+ω〈D~〉-1|U~|)=ρ(ℒ¨ω)
then, by Lemma 3, ρ(ℒ~ω)≤ρ(|ℒ~ω|)≤ρ(ℒ¨ω)<1.


## 4. Comparison Results of Spectral Radius

Theorem 10.
LetA be a nonsingular H-matrix with unit diagonal elements, 0<ω≤1 and |αi|<hi,i=1,2,…,m. Then P2〈A〉 is an M-matrix and ρ(ℒ-ω)<1.Proof.
Similar to the proof of Theorems8 and 9, it is easy to get the proof of this theorem.In what follows we will give some comparison results on the spectral radius of preconditioned SSOR iteration matrices with different preconditioner.Let(27)〈A〉=M^-N^=1ω(2-ω)(〈D〉-ω|L|)〈D〉-1(〈D〉-ω|U|)-1ω(2-ω)((1-ω)〈D〉+ω|L|)〈D〉-1×((1-ω)〈D〉+ω|U|),
where
(28)M^=1ω(2-ω)(〈D〉-ω|L|)〈D〉-1(〈D〉-ω|U|),N^=1ω(2-ω)((1-ω)〈D〉+ω|L|)〈D〉-1×((1-ω)〈D〉+ω|U|).
Then the SSOR iteration matrix for 〈A〉 is as follows:
(29)ℒ^ω=M^-1N^=(〈D〉-ω|U|)-1〈D〉(〈D〉-ω|L|)-1×((1-ω)〈D〉+ω|L|)〈D〉-1((1-ω)〈D〉+ω|U|),
and let
(30)P2〈A〉=M--N-=1ω(2-ω)(D--ωL-)D--1(D--ωU-)-1ω(2-ω)((1-ω)D-+ωL-)D--1×((1-ω)D-+ωU-),
where
(31)M-=1ω(2-ω)(D--ωL-)D--1(D--ωU-),N-=1ω(2-ω)((1-ω)D-+ωL-)D--1((1-ω)D-+ωU-).
Then the AOR iteration matrix for P2〈A〉 is (17).Theorem 11.
IfA is a nonsingular H-matrix with unit diagonal elements, 0<ω≤1 and |αi|<hi,i=1,2,…,m. Then ρ(ℒ-ω)≤ρ(ℒ^ω).Proof.
Since〈A〉 is a nonsingular M-matrix, by Theorem 10, P2〈A〉 is a nonsingular M-matrix, and thus 〈A〉 and P2〈A〉 are two monotone matrices.
From〈A〉 and P2〈A〉 being M-matrices, we can get 〈D〉, D-, M^, and M- are M-matrices, together with
(32)((1-ω)I+ω〈D〉-1|L|)〈D〉-1((1-ω)I+ω〈D〉-1|U|)>0,((1-ω)I+ωD--1L-)D--1((1-ω)I+ωD--1U-)>0.
We obtain that 〈A〉=M^-N^ and P2〈A〉=M--N- are two weak regular splittings. By simple calculation, we have
(33)M-=1ω(2-ω)(D--ωL-)D--1(D--ωU-)≤1ω(2-ω)(〈D〉-ω|L|)〈D〉-1(〈D〉-ω|U|)=M^
and thus M--1≥M^-1≥0; letting x=〈A〉-1e>0, then (P2〈A〉-〈A〉)x=(I+S2)e>0; since M--1≥M^-1≥0, we have
(34)M--1(P2〈A〉)x=(I-M--1N-)x≥M^-1〈A〉x=(I-M^-1N^)x.
It follows that
(35)∥M--1N-∥x≤∥M^-1N^∥x.
As〈A〉=M^-N^ is a weak regular splitting, there exists a positive perron vector y; by Lemma 5, the following inequality holds:
(36)ρ(M--1N-)≤ρ(M^-1N^),
that is,
(37)ρ(ℒ-ω)≤ρ(ℒ^ω).WhenA is a nonsingular M-matrix, we have A=〈A〉. If αi>0, i=1,2,…,m, then P2=P1. Furthermore, we have ℒ-ω=ℒ~ω and ℒω=ℒ^ω; therefore, we get the following result.Corollary 12.
LetA be a nonsingular M-matrix with unit diagonal elements, 0<αi<|hi|, i=1,2,…,m, and 0<ω≤1. Then
(38)ρ(ℒ-ω)=ρ(ℒ~ω)≤ρ(ℒ^ω)=ρ(ℒω).Theorem 13.
LetA be a nonsingular H-matrix with unit diagonal elements, 0<ω≤1 and |αi|<hi, i=1,2,…,m. Then ρ(ℒ¨ω)≤ρ(ℒ-ω).Proof .
Let(39)〈P1A〉=1ω(2-ω)(〈D~〉-ω|L~|)〈D~〉-1(〈D~〉-ω|U~|)-1ω(2-ω)((1-ω)〈D~〉+ω|L~|)〈D~〉-1×((1-ω)〈D~〉+ω|U~|).
Then the SSOR iteration matrix for 〈P1A〉 is ℒ¨ω which is defined in the proof of Theorem 9, and let
(40)P2〈A〉=1ω(2-ω)(D--ωL-)D--1(D--ωU-)-1ω(2-ω)((1-ω)D-+ωL-)D--1×((1-ω)D-+ωU-).
Then the SSOR iteration matrix for P2〈A〉 is (17). It is easy to know that the previous two splittings are weak regular splittings. Furthermore, by Lemma 6, we have the following result, for any i, i=1,2,…,m,
(41)〈D~ii〉=〈Aii-αiAii-1AikAki〉≥〈Aii〉-|αi|〈Aii〉-1|Aik||Aki|=〈D-ii〉.
From〈P1A〉 and P2〈A〉 being two M-matrices, we have
(42)0≤〈D~〉-1≤D--1
and then
(43)ℒ¨ω=(〈D~〉-ω|U~|)-1〈D~〉(〈D~〉-ω|L~|)-1×((1-ω)〈D~〉+ω|L~|)〈D~〉-1((1-ω)〈D~〉+ω|U~|)=(I-ω〈D~〉-1|U~|)-1(I-ω〈D~〉-1|L~|)-1×((1-ω)I+ω〈D~〉-1|L~|)((1-ω)I+ω〈D~〉-1|U~|)≤(I-ωD--1|U~|)-1(I-ωD--1|L~|)-1×((1-ω)I+ωD--1|L~|)((1-ω)I+ωD--1|U~|)=ℒ-ω.
Therefore, by Lemma 3, ρ(ℒ¨ω)≤ρ(ℒ-ω).Combining the previous Theorems, we can obtain the following conclusion.Theorem 14.
LetA be a nonsingular H-matrix with unit diagonal elements, 0<ω≤1 and |αi|<hi, i=1,2,…,m. Then
(44)ρ(ℒ~ω)≤ρ(ℒ¨ω)≤ρ(ℒ-ω)≤ρ(ℒ^ω)<1.


## 5. Numerical Example

For randomly generated nonsingularH-matrices for n=100,200,500,1000 with n1=n2=⋯=nm=5, we have determined the spectral radius of the iteration matrices of SSOR method mentioned previously with preconditioner P1. We report the spectral radius of the corresponding iteration matrix by ρ. The m parameters αi, i=1,2,...,m, are taken from the m equal-partitioned points of the interval [0,1]. We take (45)P1=(A11-1A11-1A12O13⋯O1mO21A22-1A11-1A23⋱⋮⋮⋱⋱⋱⋮Om-1,1⋯Om-1,m-2Am-1,m-1-1Am-1,m-1-1Am-1,mAmm-1Am1Om2⋯Om,m-1Amm-1).ForP1, we make two groups of experiments. In Figure 1, we test the relation between ω and ρ, when N=100, ω=0.6, where “×”, “+”, “*”, “·” and “∘” denote the spectral radius of 〈A〉, P2〈A〉, 〈P1A〉, A, and P1A, respectively. In Table 1, the meaning of notations ρ(ℒ~ω), ρ(ℒ-ω), ρ(ℒ¨ω), ρ(ℒ^ω), and ρ(ℒω) denotes the spectral radius of P1A, P2〈A〉, 〈P1A〉, 〈A〉, and A, respectively.Table 1
Comparison of spectral radius with preconditionerP1.
ω
,
r
N
ρ
(
ℒ
~
ω
)
ρ
(
ℒ
-
ω)
ρ
(
ℒ
¨
ω
)
ρ
(
ℒ
^
ω
)
ρ
(
ℒ
ω
)
100
0.5636
0.8635
0.7404
0.8999
0.6288
ω
=
0.8
200
0.6030
0.9195
0.7698
0.9473
0.7059
500
0.6120
0.9751
0.7844
0.9847
0.7103
100
0.3650
0.7906
0.5923
0.8530
0.4770
ω
=
0.6
200
0.4510
0.8832
0.6507
0.9240
0.5769
500
0.4345
0.9730
0.6766
0.9835
0.5609
100
0.2387
0.7512
0.6647
0.8087
0.3602
ω
=
0.9
200
0.3494
0.8491
0.5800
0.9009
0.4899
500
0.3569
0.9561
0.6284
0.9731
0.5019
1000
0.3674
0.9738
0.6316
0.9840
0.5173Figure 1
The relation betweenω and ρ, when N=100, ω=0.6.From Figure1 and Table 1, we can conclude that the spectral radius of the preconditioned SSOR method with preconditioner P1 is the best among others, which further illustrates that, Theorem 14 is true.



---

*Source: 213659-2013-04-04.xml*