# Convergence Analysis of Preconditioned AOR Iterative Method for Linear Systems

Authors: Qingbing Liu; Guoliang Chen
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

M-(H-)matrices appear in many areas of science and engineering, for example, in the solution of the
linear complementarity problem (LCP) in optimization theory and in the solution of large systems
for real-time changes of data in fluid analysis in car industry. Classical (stationary) iterative
methods used for the solution of linear systems have been shown to convergence for this class of
matrices. In this paper, we present some comparison theorems on the preconditioned AOR iterative
method for solving the linear system. Comparison results show that the rate of convergence of the
preconditioned iterative method is faster than the rate of convergence of the classical iterative
method. Meanwhile, we apply the preconditioner to H-matrices and obtain the convergence result.
Numerical examples are given to illustrate our results.


---

## Body

## 1. Introduction

In numerical linear algebra, the theory ofM- and H-matrices is very important for the solution of linear systems of algebra equations by iterative methods (see, e.g., [1–14]). For example, (a) in the linear complementarity problem (LCP) (see [5, Section 10.1] for specific applications), where we are interested in finding a z∈Rn such that z≥0, Mz+q≥0, zT(Mz+q)=0, with M∈Rn×n and q∈Rn given, a sufficient condition for a solution to exist, and to be found by a modification of an iterative method, especially of SOR, is that M is an H-matrix, with mi,i>0, i=1,…,n [15]; (b) in fluid analysis, in the car modeling design [16, 17], it was observed that large linear systems with an H-matrix coefficient A are solved iteratively much faster if A is postmultiplied by a suitable diagonal matrix D, with di,i>0, i=1,…,n, so that AD is strictly diagonally dominant. We consider the following linear system:(1.1)Ax=b,
where A is an n×n square matrix, x and b are two n-dimensional vectors. For any splitting, A=M-N with the nonsingular matrix M, the basic iterative method for solving the linear system (1.1) is as follows:(1.2)xi+1=M-1Nxi+M-1b,i=0,1,2,….Without loss of generality, letA=I-L-U and ai,1≠0, i=2,…,n, where L and U are strictly lower triangular and strictly upper triangular matrices of A, respectively. Then the iterative matrix of the AOR iterative method [18] for solving the linear system (1.1) is(1.3)Tγ,ω=(I-γL)-1[(1-ω)I+(ω-γ)L+ωU],
where ω and γ are nonnegative real parameters with ω≠0.To improve the convergence rate of the basic iterative methods, several preconditioned iterative methods have been proposed in [8, 12, 13, 19–24]. We now transform the original system (1.1) into the preconditioned form(1.4)PAx=Pb,
where P is a nonsingular matrix. The corresponding basic iterative method is given in general by (1.5)xi+1=MP-1NPxi+MP-1Pb,i=0,1,2,…,
where PA=MP-NP is a splitting of PA.Milaszewicz [19] presented a modified Jacobi and Gauss-Seidel iterative methods by using the preconditioned matrix P=I+S, where (1.6)P=(I+S)=[10⋯0-a211⋯0⋮⋮⋱⋮-an10⋯1].The author [19] suggests that if the original iteration matrix is nonnegative and irreducible, then performing Gaussian elimination on a selected column of iteration matrix to make it zero will improve the convergence of the iteration matrix.In 2003, Hadjidimos et al. [4] considered the generalized preconditioner used in this case is of the form(1.7)P(α)=(I+Sα)=[10⋯0-α2a211⋯0⋮⋮⋱⋮-αnan10⋯1],
where α=(α2,…,αn)T∈Rn-1 with αi∈[0,1], i=2,…,n, constants. The selection of α's will be made from the (n-1)-dimensional nonnegative cone Kn-1 in such a way that none of the diagonal elements of the preconditioned matrix Ã=P(α)A vanishes. They discussed the convergence of preconditioned Jacobi and Gauss-Seidel when a coefficient matrix A is an M-matrix.In this paper, we consider the preconditioned linear system of the form(1.8)Ãx=b̃,
where Ã=(I+Sα)A and b̃=(I+Sα)b. It is clear that SαL=0. Thus, we obtain the equality(1.9)Ã=(I+Sα)A=(I+Sα)(I-L-U)=I-SD-L-SL+Sα-U-SU,
where SD,SL, and SU are the diagonal, strictly lower, and strictly upper triangular parts of the matrix SαU, respectively. If we apply the AOR iterative method to the preconditioned linear system (1.8), then we get the preconditioned AOR iterative method whose iteration matrix is(1.10)T̃γ,ω=(D̃-γL̃)-1[(1-ω)D̃+(ω-γ)L̃+ωŨ].This paper is organized as follows. Section2 is preliminaries. Section 3 will discuss the convergence of the preconditioned AOR method and obtain comparison theorems with the classical iterative method when a coefficient matrix is a Z-matrix. In Section 4 we apply the preconditioner to H-matrices and obtain the convergence result. In Section 5 we use numerical examples to illustrate our results.


## 2. Preliminaries

We say that a vectorx is nonnegative (positive), denoted x≥0(x>0), if all its entries are nonnegative (positive). Similarly, a matrix B is said to be nonnegative, denoted B≥0, if all its entries are nonnegative or, equivalently, if it leaves invariant the set of all nonnegative vectors. We compare two matrices A≥B, when A-B≥0, and two vectors x≥y(x>y) when x-y≥0(x-y>0). Given a matrix A=(ai,j), we define the matrix |A|=(|ai,j|). It follows that |A|≥0 and that |AB|≤|A||B| for any two matrices A and B of compatible size.Definition 2.1.
A matrixA=(ai,j)∈Rn×n is called a Z-matrix if ai,j≤0 for i≠j. A matrix A is called a nonsingular M-matrix if A is a Z-matrix and A-1≥0.Definition 2.2.
A matrixA is an H-matrix if its comparison matrix 〈A〉=(a¯i,j) is an M-matrix, where a¯i,j is
(2.1)a¯i,i=|ai,i|,a¯i,j=-|ai,j|,i≠j.Definition 2.3 (see [1]).
The splittingA=M-N is called an H-splitting if 〈M〉-|N| is an M-matrix and an H-compatible splitting if 〈A〉=〈M〉-|N|.Definition 2.4.
LetA=(ai,j)∈Rn×n. A=M-N is called a splitting of A if M is a nonsingular matrix. The splitting is called(a)
convergent ifρ(M-1N)<1(b)
regular ifM-1≥0 and N≥0(c)
nonnegative ifM-1N≥0(d)
M-splitting if M is a nonsingular M-matrix and N≥0.Lemma 2.5 (see [1]).
LetA=M-N be a splitting. If the splitting is an H-splitting, then A and M are H-matrices and ρ(M-1N)≤ρ(〈M〉-1|N|)<1. If the splitting is an H-compatible splitting and A is an H-matrix, then it is an H-splitting and thus convergent.Lemma 2.6 (Perron-Frobenius theorem).
LetA≥0 be an irreducible matrix. Then the following hold:(a)
A has a positive eigenvalue equal to ρ(A).(b)
A has an eigenvector x>0 corresponding to ρ(A).(c)
ρ(A) is a simple eigenvalue of A.Lemma 2.7 (see [3, 25]).
LetA=M-N be an M-splitting of A. Then ρ(M-1N)<1(=1) if and only if A is a nonsingular (singular) M-matrix. If A is irreducible, then here is a positive vector x such that M-1Nx=ρ(M-1N)x.Lemma 2.8 (see [5]).
LetA≥0 be a nonnegative matrix. Then the following hold.(a)
IfAx≥βx for a vector x≥0 and x≠0, then ρ(A)≥β.(b)
IfAx≤γx for a vector x>0, then ρ(A)≤γ; moreover, if A is irreducible and if βx≤Ax≤γx, equality excluded, for a vector x≥0 and x≠0, then β<ρ(A)<γ and x>0.


## 3. Convergence Theorems forZ-Matrix

We first consider the convergence of the iteration matrixT̃γ,ω of the preconditioned linear system (1.8) when the coefficient matrix is a Z-matrix.Particularly, we considerαi=1, i=2,…,n. Define(3.1)A¯=(I+S1)A=(I+S1)(I-L-U)=I-D′-L-L′+S1-U-U′,
where D′,L′, and U′ are diagonal, strictly lower triangular, and strictly upper triangular parts of the matrix S1U, respectively. Then the preconditioned AOR method is expressed as follows: (3.2)T¯γ,ω=(D¯-γL¯)-1[(1-ω)D¯+(ω-γ)L¯+ωU¯],
where D¯=I-D′, L¯=L+L′-S1, and U¯=U+U′ are the diagonal, strictly lower, and strictly upper triangular matrices obtained from A¯, respectively.Lemma 3.1.
LetA=(ai,j)∈Rn×n be a Z-matrix. Then (I+Sα)A is also a Z-matrix.Proof.
SinceÃ=(ãi,j)=(I+Sα)A, we have
(3.3)ãi,j={ai,j,i=1,ai,j-αiai,1a1,j,i=2,…,n.
It is clear that Ã is a Z-matrix for any αi∈[0,1], i=2,…,n.Lemma 3.2.
LetTγ,ω and T̃γ,ω be defined by (1.3) and (1.10). Assume that 0≤γ≤ω≤1(ω≠0,γ≠1). If A is an irreducible Z-matrix with ai1a1i<1, i=2,…,n, for αi∈(0,1), i=2,…,n, then Tγ,ω and T̃γ,ω are nonnegative and irreducible.Proof.
SinceA=I-L-U is irreducible. Then for αi∈(0,1), i=2,…,n, we have that Ã=(I+Sα)A=D̃-L̃-Ũ is also irreducible. Observe that
(3.4)Tγ,ω=(1-ω)I+ω(1-γ)L+ωU+T,
where T is a nonnegative matrix. As A is an irreducible Z-matrix and ω≠0, γ≠1, it is easy to show that Tγ,ω is nonnegative and irreducible. By assumption, D̃,L̃,andŨ are all nonnegative and thus T̃γ,ω is nonnegative. Observe that T̃γ,ω can be expressed as
(3.5)T̃γ,ω=(1-ω)I+ω(1-γ)D̃-1L̃+ωD̃-1Ũ+T̃,
where T̃ is a nonnegative matrix. Since ω≠0, γ≠1, and Ã is irreducible, ω(1-γ)D̃-1L̃+ωD̃-1Ũ is irreducible. Hence, T̃γ,ω is irreducible from (3.5).Our main result in this section is as follows.Theorem 3.3.
LetTγ,ω and T̃γ,ω be defined by (1.3) and (1.10). Assume that 0≤γ≤ω≤1(ω≠0,γ≠1). If A is an irreducible Z-matrix with ai1a1i<1, i=2,…,n, for αi∈(0,1), i=2,…,n, then(a)
forαi∈(0,1), ρ(T̃γ,ω)<ρ(Tγ,ω)<1 if ρ(Tγ,ω)<1;(b)
forαi∈[0,1], ρ(T̃γ,ω)=ρ(Tγ,ω)=1 if ρ(Tγ,ω)=1;(c)
forαi∈(0,1), ρ(T̃γ,ω)>ρ(Tγ,ω)>1 if ρ(Tγ,ω)>1.Proof.
LetA=I-L-U be irreducible. It is clear that I-γL is an M-matrix and (1-ω)I+(ω-γ)L+ωU≥0. So A=(I-γL)-[(1-ω)I+(ω-γ)L+ωU] is an M-splitting of A. From Lemma 2.7, there exists a positive vector x such that
(3.6)Tγ,ωx=λx,
where λ denotes the spectral radius of Tγ,ω. Observe that Tγ,ω=(I-γL)-1[(1-ω)I+(ω-γ)L+ωU]; we have
(3.7)[(1-ω)I+(ω-γ)L+ωU]x=λ(I-γL)x,
which is equivalent to
(3.8)(λ-1)(I-γL)x=ω(L+U-I)x.
Let SαU=SD+SL+SU, where SD,SL, and SU are the diagonal, strictly lower, and strictly upper triangular parts of SαU, respectively. It is clear that SαL=0, so
(3.9)Ã=D̃-L̃-Ũ=(I-SD)-(L+SL-Sα)-(U+SU),
where
(3.10)D̃=I-SD,L̃=L+SL-Sα,Ũ=U+SU.
From (3.8) and (3.10), we have
(3.11)T̃γ,ωx-λx=(D̃-γL̃)-1[(1-ω)D̃+(ω-γ)L̃+ωŨ-λ(D̃-γL̃)]x=(D̃-γL̃)-1[(1-ω-λ)D̃+(ω-γ+λγ)L̃+ωŨ]x=(D̃-γL̃)-1[(1-ω-λ)(I-SD)+(ω-γ+λγ)(L+SL-Sα)+ω(U+SU)=(D̃-γL̃)-1[(1-ω-λ)I+(ω-γ+λγ)L+ωU-(1-ω-λ)SD+(ω-γ+λγ)SL-(ω-γ+λγ)Sα+ωSU]x=(D̃-γL̃)-1[(λ-1)SD+ωSD+(λ-1)γSL+ωSL+ωSU-(ω-γ+λγ)Sα]x=(D̃-γL̃)-1[(λ-1)SD+(λ-1)γSL+ωSαU-ωSα+ωSαL-(λ-1)γSα]x=(D̃-γL̃)-1[(λ-1)SD+(λ-1)γSL-(λ-1)γSα+ωSα(U+L-I)]x=(D̃-γL̃)-1[(λ-1)SD+(λ-1)γSL-(λ-1)γSα+(λ-1)Sα(I-γL)]x=(D̃-γL̃)-1[(λ-1)SD+(λ-1)γSL-(λ-1)γSα+(λ-1)Sα]x=(λ-1)(D̃-γL̃)-1[SD+(1-γ)Sα+γSL]x.
Since ai,1a1,i<1, i=2,…,n, then D̃-γL̃ is an M-matrix. Notice that SD≥0,Sα≥0, and SL≥0. If λ<1, then from (3.11), we have T̃γ,ωx≤λx. As x>0, Lemma 2.8 implied that ρ(T̃γ,ω)≤λ=ρ(Tγ,ω). For the case of λ=1 and λ>1, T̃γ,ωx=λx and T̃γ,ωx≥λx are obtained from (3.11), respectively. Hence, Theorem 3.3 follows from Lemmas 2.8 and 3.2.We next consider the case ofαi=1, i=2,…,n; the convergence theorem is given as follows see [26, 27].Theorem 3.4.
LetTγ,ω and T¯γ,ω be defined by (1.3) and (1.10). Assume that A is an irreducible Z-matrix and A(2:n,2:n) is an irreducible submatrix of A deleting the first row and the first column. Then for 0≤γ≤ω≤1(ω≠0,γ≠1) and ai1a1i<1, i=2,…,n, we have(a)
ρ(T¯γ,ω)<ρ(Tγ,ω)<1 if ρ(Tγ,ω)<1;(b)
ρ(T¯γ,ω)=ρ(Tγ,ω)=1 if ρ(Tγ,ω)=1;(c)
ρ(T¯γ,ω)>ρ(Tγ,ω)>1 if ρ(Tγ,ω)>1.Proof.
LetA=I-L-U be irreducible. It is clear that I-γL is an M-matrix and (1-ω)I+(ω-γ)L+ωU≥0. So A=(I-γL)-[(1-ω)I+(ω-γ)L+ωU] is an M-splitting of A. From Lemma 2.7, there exists a positive vector x such that
(3.12)Tγ,ωx=λx,
where λ denotes the spectral radius of Tγ,ω. Observe that Tγ,ω=(I-γL)-1[(1-ω)I+(ω-γ)L+ωU]; we have
(3.13)[(1-ω)I+(ω-γ)L+ωU]x=λ(I-γL)x,
which is equivalent to
(3.14)(λ-1)(I-γL)x=ω(L+U-I)x.
Similar to the proof of the equality (3.11), we have
(3.15)T¯γ,ωx-λx=(D¯-γL¯)-1[(1-ω)D¯+(ω-γ)L¯+ωU¯-λ(D¯-γL¯)]x=(D¯-γL¯)-1[(1-ω-λ)D¯+(ω-γ+λγ)L¯+ωU¯]x.
Since D¯=I-D′, L¯=L+L′-S1, and U¯=U+U′, then we have
(3.16)T¯γ,ωx-λx=(λ-1)(D¯-γL¯)-1(D′+γL′+(1-γ)S1)x.
By computation, we have
(3.17)T¯γ,ω=(1-ω)I+ω(1-γ)D¯-1L¯+ωD¯-1U¯+H¯=[1-ωT¯1,20T¯2,2],
where H¯ is a nonnegative matrix, T¯1,2≥0 is a 1×(n-1) matrix, and T¯2,2≥0 is an (n-1)×(n-1) matrix. As A is irreducible, then at least one a1,i≠0 and T¯1,2 is nonzero. Since A(2:n,2:n) is irreducible, it is clear that A¯(2:n,2:n) is irreducible. Since ω≠0 and γ≠1, from (3.17), we have that T¯2,2 is irreducible. Let
(3.18)u=(D¯-γL¯)-1(D′+γL′+(1-γ)S1)x,v=(D¯-γL¯)-1u.
From (3.18), and x>0, we know that u≥0, and the first component of u is zero. Hence v≥0 and its first component is zero. Let
(3.19)x=(x1x2),v=(0v2),
where x1∈R1>0, x2∈Rn-1>0, and v2∈Rn-1≥0 being a nonzero vector. From (3.16) and (3.17), we have
(3.20)T¯γ,ωx-λx=(λ-1)v.
That is,
(3.21)(1-ω)x1+T¯1,2x2=λx1,(3.22)T¯2,2x2-λx2=(λ-1)v2.
If λ<1, from (3.22) and v2 is a nonzero vector, we have
(3.23)T¯2,2x2<λx2,(λ-1)v2≠0.
Since T¯2,2 is irreducible, from Lemma 2.8, we have
(3.24)ρ(T¯2,2)<λ.
Since x2>0 and T¯1,2 is a nonzero nonnegative vector, from (3.21), we have (1-ω)x1<λx1. Namely,
(3.25)1-ω<λ.
It is clear that ρ(T¯γ,ω)=max{1-ω,ρ(T¯2,2)}. Hence, we have
(3.26)ρ(T¯γ,ω)<λ.
For the case of λ>1, T¯2,2x2≥λx2 is obtained from (3.22) and equality is excluded. Hence ρ(T¯γ,ω)>λ follows from Lemma 2.8 and T¯2,2 is irreducible. Since A=(I-γL)-[(1-ω)I+(ω-γ)L+ωU] is an M-splitting of A, from Lemma 2.7, we know that λ=1 if and only if A is a singular M-matrix. So A¯=(I+S1)A is a singular M-matrix. Since A¯=(D¯-γL¯)-[(1-ω)D¯+(ω-γ)L¯+ωU¯] is an M-splitting of A¯; from Lemma 2.7 again, we have T¯γ,ω=1, which completes the proof.In Theorem3.4, if we let ω=γ, then can obtain some results about SOR method. For the similarity of proof of the Theorem 3.4, we only give the convergence result of the SOR method.Theorem 3.5.
LetTω and T¯ω be defined by (1.3) and (1.10). Assume that A is an irreducible Z-matrix and A(2:n,2:n) is an irreducible submatrix of A deleting the first row and the first column. Then for 0≤ω≤1(ω≠0) and ai1a1i<1, i=2,…,n, we have(a)
ρ(T¯ω)<ρ(Tω)<1 if ρ(Tω)<1;(b)
ρ(T¯ω)=ρ(Tω)=1 if ρ(Tω)=1;(c)
ρ(T¯ω)>ρ(Tω)>1 if ρ(Tω)>1.


## 4. AOR Method forH-Matrix

In this Section, we will considerAOR method for H-matrices. For convenience, we still use some notions and definitions in Section 2.Lemma 4.1 (see [7]).
LetA be an H-matrix with unit diagonal elements, defining the matrices SD≐diag(0,α2a2,1a1,2,…,αnan,1a1,n) and SαU≐SD+SL+SU, where SL and SU are the strictly lower and strictly upper triangular components of SαU, respectively; then Ã=(I+Sα)A=Mα-Nα, Mα=I-SD-L-SL+Sα, and Nα=U+SU. Let u=(u1,…,un)T be a positive vector such that 〈A〉u>0; assume that ai1≠0 for i=2,…,n, and
(4.1)αi′=ui-∑j=2i-1|ai,j|uj-∑j=i+1n|ai,j|uj+|ai,1|u1|ai,1|∑j=1n|a1,j|uj;
then αi′>1 for i=2,…,n and for 0≤αi<αi′, the splitting Ã=Mα-Nα is an H-splitting and ρ(Mα-1Nα)<1 so that the iteration (1.3) converges to the solution of (1.1).Lemma 4.2.
LetA=(ai,j) be an H-matrix, and let α′=min{αi′},i=2,…,n, where αi′ is defined as Lemma 4.1. Then for any α∈[0,α′],Ã=(I+Sα)A is also an H-matrix.Proof.
The conclusion is easily obtained by Lemma4.1 [7].Lemma 4.3.
Let0≤γ≤ω≤1(ω≠0,γ≠1). Then Ã=M̃-Ñ is an H-compatible splitting.Proof.
Let〈Ã〉=(a¯i,j) and 〈M̃〉-|Ñ|=(bi,j), where M̃=(1/ω)(D̃-γL̃) and Ñ=(1/ω)[(1-ω)D̃+(ω-γ)L̃+ωŨ]. Since
(4.2)ãi,j={ai,j,i=1,ai,j-αiai,1a1,j,i=2,…,n,
we have that(a)
ifi=j, then
(4.3)a¯i,j=|1-αiai,1a1,i|,bi,j=1ω[|1-αiai,1a1,i|-(1-ω)|1-αiai,1a1,i|]=|1-αiai,1a1,i|;(b)
ifi≠j, then
(4.4)a¯i,j=-|ai,j-αiai,1a1,j|,
since 〈M̃〉-|N|=(1/ω)〈D̃-γL̃〉-(1/ω)|(1-ω)D̃+(ω-γ)L̃+ωŨ|; observe that if i<j, we have
(4.5)bi,j=1ω(0-ω|-ai,j+αiai,1a1,j|)=-|aij-αiai,1a1,j|.
if i>j, we have
(4.6)bi,j=1ω[-|γ(ai,j-αiai,1a1,j)|-(ω-γ)|-ai,j+αiai,1a1,j|]=-|ai,j-αiai,1a1,j|; Hence, we have 〈Ã〉=〈M̃〉-|Ñ|, that is, Ã=M̃-Ñ is an H-compatible splitting.Theorem 4.4.
Let the assumption of Lemma4.2 holds. Then for any α∈[0,α′] and 0≤γ≤ω≤1(ω≠0,γ≠1), we have ρ(T̃γ,ω)<1.Proof.
By Lemmas2.5, 4.2, and 4.3, the conclusion is easily obtained.


## 5. Numerical Examples

In this Section, we give three numerical examples to illustrate the results obtained in Sections3 and 4.Example 5.1.
Consider an×n matrix of A of the form
(5.1)A=[1c1c2c3c1⋯c31c1c2⋱c1c2c3⋱⋱⋱c3c1⋱⋱1c1c2c3⋱c2c31c1⋮c3c1c2c31],
where c1=-2/n, c2=-1/n+1, and c3=-1/n+2. It is clear that the matrix A satisfies the assumptions of Theorem 3.3. Numerical results for this matrix A are given in Table 1.Table 1
Spectral radius of the iteration matricesρ(Tγ,ω) and ρ(T¯γ,ω) with different values of ω and γ for Example 5.1.
ωγρ(Tγ,ω)ρ(T¯γ,ω)ωγρ(Tγ,ω)ρ(T¯γ,ω)0.40.10.99830.98400.80.70.99520.95590.40.40.99800.98150.80.80.99490.95290.50.20.99770.97900.90.70.99460.95040.50.40.99750.97680.90.90.99380.94310.60.40.99700.972210.80.99360.94110.60.60.99660.968910.90.99310.9367We consider Example5.1; if we let c1=-2/n, c2=0, and c3=-1/n+2, it is clear to show that A is an M-matrix. The initial approximation of x0 is taken as a zero vector, and b is chosen so that x=(1,2,…,n)T is the solution of the linear system (1.1). Here ∥xk+1-xk∥/∥xk+1∥≤10-6 is used as the stopping criterion.All experiments were executed on a PC using MATLAB programming package.In order to show that the preconditionedAOR method is superior to the basic AOR method. We consider ω=γ=1, that is, the AOR method is reduced to the Gauss-Seidel method. In Table 2, we report the CPU time (T) and the number of iterations (IT) for the basic and the preconditioned Gauss-Seidel method. Here GS represents the restarted Gauss-Seidel method; the preconditioned restarted Gauss-Seidel method is noted by PGS.Table 2
CPU time and the iteration number of the basic and the preconditioned Gauss-Seidel method for Example5.1.
nIT  (GS)CPU  (GS)IT  (PGS)CPU  (PGS)602320.07802290.0780903400.20303370.20301204460.50004430.43801505514.57805484.54701806559.59306529.500021075836.719075530.0470Example 5.2.
Consider the two-dimensional convection-diffusion equation(5.2)-Δu+∂u∂x+2∂u∂y=f
in the unit squire Ω with Dirichlet boundary conditions see [28].
When the central difference scheme on a uniform grid withN×N interior nodes (N2) is applied to the discretization of the convection-diffusion equation (3.5), we can obtain a system of linear equations (1.1) of the coefficient matrix
(5.3)A=I⊗P+Q⊗I,
where ⊗ denotes the Kronecker product,
(5.4)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.
It is clear that the matrixA is an M-matrix, so it is an H-matrix. Numerical results for this matrix A are given in Table 3.
From Table3, for αi∈[0,αi′), it can be seen that the convergence rate of the preconditioned Gauss-Seidel iterative method (ω=γ=1) is faster than the other preconditioned iterative method for H-matrices. And iteration numbers are not changed by the change of αi; the iteration time slightly changed by the change of αi. However, it is difficult to select the optical parameters αi and this needs a further study.Table 3
CPU time and the iteration number with various values ofαi for Example 5.2.
nαi=0.5αi=0.8αi=1αi=1.2αi=2αi=0641111110.06010.04880.05870.05240.05010.0629811111110.05220.05040.05320.05240.05690.06351001111110.05770.05470.04860.05550.05630.0663Example 5.3.
We consider a symmetric Toeplitz matrix(5.5)Tn=[abc⋯bbab⋯ccba⋯b⋮⋮⋮⋱⋮bcb⋯a],
where a=1, b=1/n, and c=1/n-2. It is clear that Tn is an H-matrix. The initial approximation of x0 is taken as a zero vector, and b is chosen so that x=(1,2,…,n)T is the solution of the linear system (1.1). Here ∥xk+1-xk∥/∥xk+1∥≤10-6 is used as the stopping criterion see [29].
All experiments were executed on a PC using MATLAB programming package.
We get Table4 by using the preconditioner P(α). We report the CPU time (T) and the number of iterations (IT) for the basic and the preconditioned AOR method. Here AOR represents the restarted AOR method; the preconditioned restarted AOR method is noted by PAOR.Table 4
CPU time and the iteration number of the basic and the preconditioned AOR method for Example5.3.
nωγIT  (AOR)T  (AOR)IT  (PAOR)T  (PAOR)900.90.5150.3196110.03901200.90.5150.1526100.03061800.90.5150.1407110.10962100.90.5150.2575110.19203000.90.5151.2615100.77094000.90.5153.2573112.3241Remark 5.4.
In Example5.3, we let αi>1, i=2,…,n-1. From Table 4, if αi is appropriate, the convergence of the preconditioned AOR iterative method can be improved. However, it is difficult to select the optical parameters αi and this needs a further study.



---

*Source: 341982-2010-07-08.xml*