# Convergence of the GAOR Method for One Subclass ofH-Matrix

Authors: Guangbin Wang; Ting Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We discuss the convergence of the GAOR method to solve linear system which occurred in solving the weighted linear least squares problem. Moreover, we present one convergence theorem of the GAOR method when the coefficient matrix is a strictly doublyα diagonally dominant matrix which is a nonsingular H-matrix. Finally, we show that our results are better than previous ones by using four numerical examples.


---

## Body

## 1. Introduction

Consider the weighted linear least squares problem(1)minx∈Rn(Ax-b)TW-1(Ax-b),
where W is the variance-covariance matrix. The problem has many scientific applications. A typical source is parameter estimation in mathematical modeling.In order to solve it, we have to solve the following linear system:(2)Hy=f,
where
(3)H=(I-B1DCI-B2)
is invertible. For example, in the variance-covariance matrix [1], a generalized SOR (GSOR) method to solve linear system (2) was proposed in [2], afterwards, a generalized AOR (GAOR) method to solve linear system (2) was established in [3] as follows:(4)y(k+1)=Lω,ry(k)+ωk,
where
(5)Lω,r=(1-ω)I+ωJ+ωrK,k=(I0-rCI)f,J=(B1-D-CB2),K=(00C(I-B1)CD)=(0C)(I-B1D).In [4–6], authors studied the convergence of the GAOR method for solving the linear system Hy=f. In [4, 5], authors studied the convergence of the GAOR method for diagonally dominant coefficient matrices and gave the regions of convergence. In [6], authors studied the convergence of the GAOR method for strictly doubly diagonally dominant coefficient matrices and gave the regions of convergence. In [7], authors studied the preconditioned generalized AOR method for solving linear systems. They proposed two kinds of preconditioning that each one contains three preconditioners. They showed that the convergence rate of the preconditioned generalized AOR methods is better than that of the original method, whenever the original method is convergent. In [8], authors presented three kinds of preconditioners for preconditioned modified AOR method to solve systems of linear equations. They showed that the convergence rate of the preconditioned modified AOR method is better than that of the original method, whenever the original method is convergent.Sometimes, the coefficient matrices of linear systemsHy=f are not strictly diagonally dominant or strictly doubly diagonally dominant. In this paper, we will discuss the convergence of the GAOR method when the coefficient matrices are strictly doubly α diagonally dominant.Throughout this paper, we denote thei-row sums of the modulus of the entries of J and K by Ji and Ki, the i-column sums of the modulus of the entries of J and K by Ji′ and Ki′, respectively. And we denote the spectral radius of iterative matrix Lω,r by ρ(Lω,r):
(6)N={1,2,…,n},N1={i∣Ki=0,Ki′=0},N2=N-N1,Ri(A)=∑k≠i|aik|,Ci(A)=∑k≠i|aki|,i,k∈N.Definition 1 (see [9]).
We call matrixA∈Cn×n a strictly diagonally dominant matrix if
(7)|aii|>Ri(A),∀i∈N
and denote A∈SD.
We call matrixA∈Cn×n a strictly doubly diagonally dominant matrix if
(8)|aii||ajj|>Ri(A)Rj(A),∀i,j∈N
and denote A∈SDD.
We call matrixA∈Cn×n a strictly doubly α diagonally dominant matrix if
(9)|aii||ajj|>[αRi(A)+(1-α)Ci(A)]×[αRj(A)+(1-α)Cj(A)],∀i,j∈N,
and denote A∈SDD(α), where α∈[0,1].Obviously, a strictly doubly diagonally dominant matrix is a strictly doublyα diagonally dominant matrix, but not vice versa.For example,(10)A=(114341413414141)∈SDD(12),
but A∉SDD.Lemma 2 (see [9]).
IfA∈SDD(α), then A is a nonsingular H-matrix.In this paper, we study the convergence of the GAOR method for solving the linear systemHy=f for strictly doubly α diagonally dominant coefficient matrices. Firstly, we obtain upper bound for the spectral radius of the matrix Lω,r which is the iterative matrix of the GAOR iterative method. Moreover, we present one convergence theorem of the GAOR method. Finally, we present four numerical examples.


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

In this section, we obtain upper bound of the spectral radius of the iterative matrixLω,r.Theorem 3.
LetH∈SDD(α), then ρ(Lω,r) satisfies the following inequality:
(11)ρ(Lω,r)≤maxi,ji≠j(×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2|1-ω|+(+(1-α)(|ω|Jj′+|ωr|Kj′)]+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2[(1-α)(|ω|Ji′+|ωr|Ki′)α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2).Proof.
Letλ be an arbitrary eigenvalue of the iterative matrix Lω,r, then
(12)det(λI-Lω,r)=0,
that is,
(13)det((λ+ω-1)I-ωJ-ωrK)=0.
If (λ+ω-1)I-ωJ-ωrK∈SDD(α), then
(14)|λ+ω-1|2>[α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)],i≠j.
From Lemma 2, we know that
(15)(λ+ω-1)I-ωJ-ωrK
is nonsingular, that is
(16)det((λ+ω-1)I-ωJ-ωrK)=det(λI-Lω,r)≠0,
then λ is not an eigenvalue of the iterative matrix Lω,r.However,λ is an eigenvalue of the iterative matrix Lω,r, then there exists at least a couple of i,j∈N(i≠j), such that
(17)|λ+ω-1|2≤[α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)].
That is,
(18)|λ|2-2|1-ω||λ|+(1-ω)2≤[α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)].
It is easy to find that the discriminant of a curve of second order
(19)Δ=4[α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)]≥0,
then the solution of (18) satisfies
(20)|λ|≤|1-ω|+(+(1-α)(|ω|Jj′+|ωr|Kj′)][Kj′α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[{(|ω|Jj′+|ωr|Kj′)}α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2,i≠j.
So, ρ(Lω,r) satisfies the following inequality:
(21)ρ(Lω,r)≤maxi,ji≠j(×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2|1-ω|+(+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2+(1-α)(|ω|Jj′+|ωr|Kj′)][+(1-α)(|ω|Ji′+|ωr|Ki′)α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[{(|ω|Jj′+|ωr|Kj′)}α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2).


## 3. Convergence of the GAOR Method

In this section, we investigate the convergence of the GAOR method to solve linear system (2). We assume that H is a strictly doubly α diagonally dominant coefficient matrix and obtain the regions of convergence of the GAOR method.Theorem 4.
IfH∈SDD(α),
(22)[αJi+(1-α)Ji′][αJj+(1-α)Jj′]<1,∀i,j∈N,i≠j,
then the GAOR method converge if ω,r satisfy either(Ι)
0<ω≤1,
(23)|r|<mini.ji≠j{×(2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1(1-[αJi+(1-α)Ji′][αJj+(1-α)Jj′])×([αJj+(1-α)Jj′][αKi+(1-α)Ki′]+[αJi+(1-α)Ji′][αKj+(1-α)Kj′])-1,(Δ1-[αKi+(1-α)Ki′][αJj+(1-α)Jj′]-[αKj+(1-α)Kj′][αJi+(1-α)Ji′]+Δ1)×(2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1}or(ΙΙ)
(24)1<ω<min{2,mini,ji≠j2-2[αJi+(1-α)Ji′][αJj+(1-α)Jj′]1-[αJi+(1-α)Ji′][αJj+(1-α)Jj′]},|r|<mini.ji≠j{(ω2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1((2-ω)2-ω2[αJi+(1-α)Ji′]×[αJj+(1-α)Jj′])×(ω2[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+ω2[αKj+(1-α)Kj′]×[αJi+(1-α)Ji′])-1,(Δ2-ω2[αKi+(1-α)Ki′][αJj+(1-α)Jj′]-ω2[αKj+(1-α)Kj′][αJi+(1-α)Ji′]+Δ2)×(ω2[αKi+(1-α)Ki′]×[αKj+(1-α)Kj′])-1},where
(25)Δ1={[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+[αKj+(1-α)Kj′][αJi+(1-α)Ji′]}2+4[αKi+(1-α)Ki′][αKj+(1-α)Kj′]×{1-[αJi+(1-α)Ji′][αJj+(1-α)Jj′]},Δ2={ω2[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+ω2[αKj+(1-α)Kj′][αJi+(1-α)Ji′]}2+4ω2[αKi+(1-α)Ki′][αKj+(1-α)Kj′]×{ω2-ω2[αJi+(1-α)Ji′]×[αJj+(1-α)Jj′]-4ω+4}.Proof.
BecauseH∈SDD(α), then the GAOR method converge if
(26)maxi,ji≠j{×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2|1-ω|+(+(1-α)(|ω|Jj′+|ωr|Kj′)][(|ω|Jj′+|ωr|Kj′)α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[{(|ω|Jj′+|ωr|Kj′)}α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2}<1.
That is,
(27)|1-ω|+maxi,ji≠j{+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2(+(1-α)(|ω|Jj′+|ωr|Kj′)][+(1-α)(|ω|Ji′+|ωr|Ki′)α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[{(|ω|Jj′+|ωr|Kj′)}α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)])1/2}<1.
Firstly, when 0<ω≤1, we have
(28)ω2>[α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)].
That is,
(29)|r|2[αKi+(1-α)Ki′][αKj+(1-α)Kj′]+|r|{[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+[αKj+(1-α)Kj′][αJi+(1-α)Ji′]}+[αJi+(1-α)Ji′][αJj+(1-α)Jj′]-1<0.
Then, we have the following conditions.(1)
Wheni,j∈N1, then Ki=Kj=0, Ki′=Kj′=0. From
(30)[αJi+(1-α)Ji′][αJj+(1-α)Jj′]<1,we have
(31)|r|<+∞.(2)
Wheni∈N1, j∈N2 or i∈N2, j∈N1, then
(32)|r|{[αJj+(1-α)Jj′][αKi+(1-α)Ki′]+[αJi+(1-α)Ji′][αKj+(1-α)Kj′]}+[αJi+(1-α)Ji′][αJj+(1-α)Jj′]-1<0.From [αJi+(1-α)Ji′][αJj+(1-α)Jj′]<1, we have
(33)|r|<(1-[αJi+(1-α)Ji′][αJj+(1-α)Jj′])×([αJj+(1-α)Jj′][αKi+(1-α)Ki′]+[αJi+(1-α)Ji′][αKj+(1-α)Kj′])-1.(3)
Wheni,j∈N2, it is easy to prove that the discriminant of a curve of second order of (29) Δ1>0, and then
(34)|r|<(Δ1-[αKi+(1-α)Ki′][αJj+(1-α)Jj′]-[αKj+(1-α)Kj′][αJi+(1-α)Ji′]+Δ1)×(2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1.So, when 0<ω≤1, we have
(35)|r|<mini,ji≠j{×(2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1(1-[αJi+(1-α)Ji′][αJj+(1-α)Jj′])×([αJj+(1-α)Jj′][αKi+(1-α)Ki′]+[αJi+(1-α)Ji′][αKj+(1-α)Kj′])-1,(Δ1-[αKi+(1-α)Ki′][αJj+(1-α)Jj′]-[αKj+(1-α)Kj′][αJi+(1-α)Ji′]+Δ1)×(2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1}.
Secondly, when 1<ω<2, we have
(36)4-4ω+ω2>[(|ω|Ji′+|ωr|Ki′)α(|ω|Ji+|ωr|Ki)+(1-α)(|ω|Ji′+|ωr|Ki′)]×[α(|ω|Jj+|ωr|Kj)+(1-α)(|ω|Jj′+|ωr|Kj′)].
That is,
(37)|r|2ω2[αKi+(1-α)Ki′][αKj+(1-α)Kj′]+|r|ω2{[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+[αKj+(1-α)Kj′][αJi+(1-α)Ji′]}+ω2[αJi+(1-α)Ji′][αJj+(1-α)Jj′]-(ω-2)2<0.
Then we have the following conditions.(1)
Wheni,j∈N1, then Ki=Kj=0, Ki′=Kj′=0. From inequality (37), we have
(38)ω2[αJi+(1-α)Ji′][αJj+(1-α)Jj′]-(ω-2)2<0.From [αJi+(1-α)Ji′][αJj+(1-α)Jj′]<1, we have
(39)1<ω<mini,ji≠j2-2[αJi+(1-α)Ji′][αJj+(1-α)Jj′]1-[αJi+(1-α)Ji′][αJj+(1-α)Jj′],|r|<+∞.(2)
Wheni∈N1, j∈N2 or i∈N2, j∈N1, then Ki=Ki′=0 or Kj=Kj′=0. From inequality (37), we have
(40)|r|{[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+[αKj+(1-α)Kj′][αJi+(1-α)Ji′]}ω2+ω2[αJi+(1-α)Ji′][αJj+(1-α)Jj′]-(ω-2)2<0,so,
(41)|r|<((2-ω)2-ω2[αJi+(1-α)Ji′]×[αJj+(1-α)Jj′])×(ω2[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+ω2[αKj+(1-α)Kj′][αJi+(1-α)Ji′])-1.(3)
Wheni,j∈N2, then Ki>0, Kj>0, Ki′>0, Kj′>0.
It is easy to find that the discriminant of a curve of second order of (37) Δ2>0. Then we have
(42)|r|<(Δ2-ω2[αKi+(1-α)Ki′][αJj+(1-α)Jj′]-ω2[αKj+(1-α)Kj′][αJi+(1-α)Ji′]+Δ2)×(ω2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1.
So, when 1<ω<min{2,mini,j,i≠j((2-2[αJi+(1-α)Ji′][αJj+(1-α)Jj′])/(1-[αJi+(1-α)Ji′][αJj+(1-α)Jj′]))}, we have
(43)|r|<mini,ji≠j{(ω2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1}((2-ω)2-ω2[αJi+(1-α)Ji′][αJj+(1-α)Jj′])×(ω2[αKi+(1-α)Ki′][αJj+(1-α)Jj′]+ω2[αKj+(1-α)Kj′][αJi+(1-α)Ji′])-1,(Δ2-ω2[αKi+(1-α)Ki′][αJj+(1-α)Jj′]-ω2[αKj+(1-α)Kj′][αJi+(1-α)Ji′]+Δ2)×(ω2[αKi+(1-α)Ki′][αKj+(1-α)Kj′])-1}.


## 4. Examples

In this section, we give four numerical examples to show that our results are better than previous ones.Example 1.
Let(44)H=(113131311313131)=(I-B1DCI-B2),
where
(45)I-B1=(113131),I-B2=(1).It is easy to know thatH∈SDD(1/2) and
(46)J=(0-13-13-130-13-13130),K=(000000494929),J1=J2=J3=23,K1=K2=0,K3=109,J1′=J2′=J3′=23,K1′=K2′=49,K3′=29.
So
(47)N1={1,2},N2={3},12JiJj+12Ji′Jj′=49<1,i,j∈N,i≠j.By Theorem4, we obtain the following regions of convergence: (Ι)
0<ω≤1 and |r|<(31-4)/2, or(ΙΙ)
1<ω<6/5 and |r|<(27/4)(1/ω-1/2)2-3/4.In addition,H∈SDD.By Theorem 2 of paper [6], we obtain the following regions of convergence:(Ι)
0<ω≤1 and |r|<3/4, or(ΙΙ)
1<ω<6/5 and |r|<(27/20)((2-ω)/ω)2-3/5.From Figure1, we know that the regions of convergence got by Theorem 4 in this paper (bounded by blue lines) are larger than ones got by Theorem 2 of paper [6] (bounded by green lines). From Example 1 of paper [6], we know that the regions of convergence got by Theorem 2 of paper [6] are larger than ones of paper [4] and paper [5]. So, the regions of convergence got by Theorem 4 in this paper are larger than ones of paper [4–6].Figure 1Example 2.
Let(48)H=(114341413414141)=(I-B1DCI-B2),
where
(49)I-B1=(114141),I-B2=(1).It is easy to know thatH∈SDD(1/2) and
(50)J=(0-14-34-140-34-14-140),K=(000000516516616),J1=J2=1,J3=12,J1′=J2′=12,J3′=32,K1=K2=0,K3=1,K1′=K2′=516,K3′=38.
So,
(51)N1={1,2},N2={3},12JiJj+12Ji′Jj′=58<1,i,j∈N,i≠j.By Theorem4, we obtain the following regions of convergence:(Ι)
0<ω≤1 and |r|<(4/55)(2289-43), or(ΙΙ)
1<ω<4(2-3) and |r|<(8/55)7040(1/ω-1/2)2+529-344/55.But H∉SDD, so we cannot use Theorem 2 of paper [6]. And we cannot use the results of paper [4, 5].Example 3.
Let(52)H=(113160017613130116016131)=(I-B1DCI-B2),
where
(53)I-B1=(11301),I-B2=(116131).Obviously,H∈SDD(1) and
(54)J=(0-13-16000-76-13-1300-160-16-130),K=(0000000013191180016736118).By Theorem4, we obtain the following regions of convergence: (Ι)
0<ω≤1 and |r|<1/3, or(ΙΙ)
1<ω<8-43 and |r|<(4/3)((2-ω)/ω)2-1.Consider the following linear system:(55)Hy=f,
where
(56)H=(113160017613130116016131),f=(32523232),
which has the exact solution
(57)y=(1,1,1,1)T.We choose the initial solutiony0=(0,0,0,0)T. If ω=101/100,r=-1/5, we need 28 iterations to achieve four decimal digits of accuracy in the solution components. If ω=101/100, r=1/5, we need 18 iterations to achieve four decimal digits of accuracy in the solution components. If ω=1/2,r=1/4, we need 22 iterations to achieve four decimal digits of accuracy in the solution components.Example 4.
Consider(58)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(59)I-B1=(1196-121),D=(0⋯⋯01961960⋯0196).
Obviously, H∈SDD(1/2), and
(60)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 Theorem4, we obtain the following regions of convergence: (Ι)
0<ω≤1 and |r|<2208/3481, or(ΙΙ)
1<ω<192/169 and |r|<(18432-16224ω)/3481ω.



---

*Source: 956143-2013-04-16.xml*