# Convergence of GAOR Iterative Method with Strictlyα Diagonally Dominant Matrices

Authors: Guangbin Wang; Hao Wen; Ting Wang
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

We discuss the convergence of GAOR method for linear systems with strictlyα diagonally dominant matrices. Moreover, we show that our results are better than ones of Darvishi and Hessari (2006), Tian et al. (2008) by using three numerical examples.


---

## Body

## 1. Introduction

Sometimes we have to solve the following linear system:(1.1)Hy=f,
where(1.2)H=(I-B1DCI-B2)
is invertible. Yuan proposed a generalized SOR(GSOR) method to solve linear system (1.1) in [1]; afterwards, Yuan and Jin [2] established a generalized AOR(GAOR) method to solve linear system (1.1) as follows:(1.3)y(k+1)=Lω,ry(k)+ωk,
where(1.4)Lω,r=(1-ω)I+ωJ+ωrK,k=(I0-rCI)f,J=(B1-D-CB2),K=(00C(I-B1)CD)=(0C)(I-B1D).In [2–4], some people studied the convergence of GAOR method for solving linear systems Hy=f. In [2], Yuan and Jin studied the convergence of GAOR method and show that the GAOR method is better than the GSOR method under certain conditions. In [3], Darvishi and Hessari studied the convergence of GAOR method for diagonally dominant coefficient matrices and gave the regions of convergence. In [4], Tian et al. studied the convergence of GAOR method for strictly diagonally dominant coefficient matrices and gave the regions of convergence.Sometimes, the coefficient matrices of linear systemsHy=fare not strictly diagonally dominant. In this paper, we will discuss the convergence of GAOR method for linear systems Hy=f with strictly α diagonally dominant matrices which need not to be strictly diagonally dominant.Throughout this paper, we denote the set of all complex matrices byCn×n, the spectral radius of iterative matrix Lω,r by ρ(Lω,r). And (1.5)N={1,2,…,n},Ri(A)=∑j≠i|aij|,Si(A)=∑j≠i|aji|,i,j∈N.Definition 1.1 (see [5]).
LetA=(aij)∈Cn×n. If there exists α∈[0,1],
(1.6)|aii|≥αRi(A)+(1-α)Si(A)(∀i∈N)
holds, then we call A as αdiagonally dominant and denote it asA∈D0(α). If all the inequalities are strict, then we denote it asA∈D(α).Obviously, ifAis a strictly diagonally dominant matrix (A∈SD), then A∈D(α). But not vice versa.In [3], Darvishi and Hessari obtained the following result.Theorem 1.2.
LetH∈SDand assume that ω≥r≥0. Then the sufficient condition for convergence of the GAOR method is
(1.7)0<ω<21+max⁡i{Ji+rKi},
where Ji andKi are the i-row sums of the modulus of the entries of J and K, respectively.In [4], Tian et al. obtained the following result.Theorem 1.3.
IfH∈SD, then the sufficient conditions for the convergence of the GAOR method are either(i)
0≤r≤1 and 0<ω≤1 or(ii)
|r|≤mini{(1-Ji)/Ki} and 0<ω<2/(1+maxi(J+rK)i).This work is organized as follows. In Section2, we obtain bound for the spectral radius of the iterative matrix Lω,r of GAOR iterative method. In Section 3, we present two convergence theorems of GAOR method. In Section 4, we present three numerical examples to show that our results are better than ones of Theorems 1.2 and 1.3.


## 2. Upper Bound of the Spectral Radius ofLω,r

In this section, we obtain upper bound of the spectral radius of iterative matrixLω,r.Theorem 2.1.
LetH∈D(α), thenρ(Lω,r)satisfies the following inequality:
(2.1)ρ(Lω,r)≤max⁡i{|1-ω|+(|ωJ|+|ωrK|)ii+αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|)}.Proof.
Letλbe an arbitrary eigenvalue of iterative matrix Lω,r, then
(2.2)det⁡(λI-Lω,r)=0.
Equation (2.2) holds if and only if
(2.3)det⁡((λ+ω-1)I-ωJ-ωrK)=0.
If (λ+ω-1)I-ωJ-ωrK∈D(α), that is,
(2.4)|λ-(1-ω)-(ωJ+ωrK)ii|>αRi(ωJ+ωrK)+(1-α)Si(ωJ+ωrK),∀i∈N,
where(ωJ+ωrK)iidenotes the diagonal element of matrixωJ+ωrK. From [5], we know that
(2.5)det⁡((λ+ω-1)I-ωJ-ωrK)≠0;
thenλ is not an eigenvalue of iterative matrixLω,r, and when
(2.6)|λ|-|1-ω|-(|ωJ|+|ωrK|)ii>αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|),∀i∈N,λis not an eigenvalue of iterative matrixLω,r.
Whenλ is an eigenvalue of iterative matrix Lω,r, then there exists at least one i(i∈N), such that
(2.7)|λ|-|1-ω|-(|ωJ|+|ωrK|)ii≤αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|),
that is,
(2.8)|λ|≤|1-ω|+(|ωJ|+|ωrK|)ii+αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|).
Hence,
(2.9)ρ(Lω,r)≤max⁡i{|1-ω|+(|ωJ|+|ωrK|)ii+αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|)}.


## 3. Convergence of GAOR Method

In this section, we investigate the convergence of GAOR method to solve linear system (1.1). We assume that His a strictlyαdiagonally dominant coefficient matrix and get some sufficient conditions for the convergence of GAOR method.Theorem 3.1.
LetH∈D(α), then GAOR method is convergent if ω,r satisfy either (I)
0<ω≤1 and
(3.1)|r|<min⁡i1-|J|ii-αRi(|J|)-(1-α)Si(|J|)αRi(|K|)+(1-α)Si(|K|)+|K|iior(II)
1<ω<mini(2/(1+|J|ii+αRi(|J|)+(1-α)Si(|J|))) and
(3.2)|r|<min⁡i2-ω-ω(|J|ii+αRi(|J|)+(1-α)Si(|J|))ω(αRi(|K|)+(1-α)Si(|K|)+|K|ii).Proof.
SinceH∈D(α), then GAOR method is convergent if we haveρ(Lω,r)<1, that is,
(3.3)max⁡i{|1-ω|+(|ωJ|+|ωrK|)ii+αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|)}<1.
Firstly, when0<ω≤1, then
(3.4)1-ω+(|ωJ|+|ωrK|)ii+αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|)<1,∀i∈N.
That is,
(3.5)|J|ii+|r||K|ii+αRi(|J|)+|r|αRi(|K|)+(1-α)Si(|J|)+|r|(1-α)Si(|K|)<1,
which leads to
(3.6)|r|<1-|J|ii-αRi(|J|)-(1-α)Si(|J|)αRi(|K|)+(1-α)Si(|K|)+|K|ii,∀i∈N.
So
(3.7)|r|<min⁡i1-|J|ii-αRi(|J|)-(1-α)Si(|J|)αRi(|K|)+(1-α)Si(|K|)+|K|ii.
Secondly, when1<ω, then
(3.8)ω-1+(|ωJ|+|ωrK|)ii+αRi(|ωJ|+|ωrK|)+(1-α)Si(|ωJ|+|ωrK|)<1,∀i∈N.
That is,
(3.9)ω(|J|ii+|r||K|ii+αRi(|J|)+|r|αRi(|K|)+(1-α)Si(|J|)+|r|(1-α)Si(|K|))<2-ω,
which leads to
(3.10)|r|<2-ω-ω(|J|ii+αRi(|J|)+(1-α)Si(|J|))ω(αRi(|K|)+(1-α)Si(|K|)+|K|ii),∀i∈N.
So
(3.11)|r|<min⁡i2-ω-ω(|J|ii+αRi(|J|)+(1-α)Si(|J|))ω(αRi(|K|)+(1-α)Si(|K|)+|K|ii),
then
(3.12)2-ω-ω(|J|ii+αRi(|J|)+(1-α)Si(|J|))>0,∀i∈N,
so
(3.13)1<ω<min⁡i21+|J|ii+αRi(|J|)+(1-α)Si(|J|).
Thus we complete the proof.Whenr=0, we can get the following theorem.Theorem 3.2.
LetH∈D(α), then ρ(Lω,0)<1 if
(3.14)0<ω<min⁡i21+|J|ii+αRi(|J|)+(1-α)Si(|J|).Proof.
BecauseH∈D(α), from Theorem 1.2, when r=0, we have
(3.15)ρ(lω,r)≤max⁡i{|1-ω|+|ωJ|ii+αRi(|ωJ|)+(1-α)Si(|ωJ|)}<1.
Firstly, when 0<ω≤1,
(3.16)1-ω+ω|J|ii+αωRi(|J|)+(1-α)ωSi(|J|)<1.
That is
(3.17)|J|ii+αRi(|J|)+(1-α)Si(|J|)<1.
Secondly, when 1<ω<2,
(3.18)ω-1+ω|J|ii+αωRi(|J|)+(1-α)ωSi(|J|)<1.
That is
(3.19)ω+ω|J|ii+αωRi(|J|)+(1-α)ωSi(|J|)<2,
which leads to
(3.20)ω<21+|J|ii+αRi(|J|)+(1-α)Si(|J|).
Soωmust satisfy
(3.21)0<ω<min⁡i21+|J|ii+αRi(|J|)+(1-α)Si(|J|).
Thus we complete the proof of Theorem 3.2.


## 4. Examples

In the following examples, we give the regions of convergence of GAOR method to show that our results are better than ones of Theorems1.2 and 1.3.Example 4.1.
Let(4.1)H=(113131315613131)=(I-B1DCI-B2).
Obviously,H is not a strictly diagonally dominant matrix, so we cannot use the results of Theorems 1.2 and 1.3. But H∈D(1/2), and
(4.2)J=(0-13-13-130-56-13-130),K=(0000004949718).
By Theorem 3.1, we obtain the following regions of convergence: (I)
0<ω≤1 and |r|<1/10or(II)
1<ω<24/23 and |r|<(2-(23/12)ω)(6/5ω).Example 4.2 (Example 1 of paper [4]).
Let(4.3)H=(113131311313131)=(I-B1DCI-B2).
It is easy to test that H∈D(1/4), and
(4.4)J=(0-13-13-130-13-13-130),K=(000000494929).
By Theorem 3.1, we obtain the following regions of convergence: (I)
0<ω≤1 and |r|<3/4or (II)
1<ω<1.2 and |r|<((18-5ω)/4ω).
In addition,H is a strictly diagonally dominant matrix.
By Theorem1.3, we obtain the following regions of convergence:(I)
0≤r≤1 and 0<ω≤1,(II)
0≤r<0.3and 0<ω<1.2,or(III)
-0.3<r<0 and 0<ω<(18/(15-10r)).
By Theorem1.2, we obtain the following region of convergence:
0≤r≤ω and0<ω<(18/(15+10r)).And we get Figure1, where the regions of convergence got by Theorems 3.1 and 1.3, Theorem 1.2 are bounded by blue lines, red lines, green lines, respectively.Figure 1This figure shows that the regions of convergence got by Theorem3.1 are larger than ones got by Theorems 1.2 and 1.3.Example 4.3.
Consider(4.5)H=(11960⋯⋯⋯⋯0196-1211960⋯⋯⋯0196-196-121196196⋯⋯196196-1960-121196196⋯196196⋮⋮⋮⋮⋮⋮⋮⋮⋮-1960⋯0-121196196196-1960⋯⋯0-121196196-1960⋯⋯⋯0-121196-1960⋯⋯⋯⋯0-121)51×51,
where
(4.6)I-B1=(1196-121),D=(0⋯01961960⋯0196).
Obviously,H is not a strictly diagonally dominant matrix, so we cannot use the results of Theorems 1.2 and 1.3. But H∈D(1/2), and
(4.7)J=(0-1960⋯⋯⋯⋯0-196120-1960⋯⋯⋯0-196196120-196-196⋯⋯-196-1961960120-196-196⋯-196-196⋮⋮⋱⋱⋱⋱⋱⋮⋮1960⋯0120-196-196-1961960⋯⋯0120-196-1961960⋯⋯⋯0120-1961960⋯⋯⋯⋯0120)51×51,K=(0000⋯⋯⋯000000⋯⋯⋯002396-46099216-11920⋯000-499216-196-1921600⋯000-19216⋮⋮⋮⋮⋮⋮⋮⋮⋮-196-1921600⋯000-19216-196-1921600⋯000-19216-196-1921600⋯000-19216-196-1921600⋯000-19216)51×51.
By Theorem 3.1, we obtain the following regions of convergence: (I)
0<ω≤1 and |r|<(2208/3481)or (II)
1<ω<(192/169) and |r|<((18432-16224ω)/3481ω).



---

*Source: 713795-2011-11-15.xml*