# Comparison Results on Preconditioned GAOR Methods for Weighted Linear Least Squares Problems

Authors: Guangbin Wang; Yanli Du; Fuping Tan
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We present preconditioned generalized accelerated overrelaxation methods for solving weighted linear least square problems. We compare the spectral radii of the iteration matrices of the preconditioned and the original methods. The comparison results show that the preconditioned GAOR methods converge faster than the GAOR method whenever the GAOR method is convergent. Finally, we give a numerical example to confirm our theoretical results.


---

## Body

## 1. Introduction

Consider the weighted linear least squares problem(1.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.This problem has been discussed in many books and articles. In order to solve it, one has to solve a nonsingular linear system as(1.2)Hy=f,
where
(1.3)H=(I-B1UCI-B2)
is an invertible matrix with
(1.4)B1=(bij)p×p,B2=(bij)(n-p)×(n-p),C=(cij)(n-p)×p,U=(uij)p×(n-p).Yuan proposed a generalized SOR (GSOR) method to solve linear system (1) in [1]; afterwards, Yuan and Jin [2] established a generalized AOR (GAOR) method to solve linear system (1). In [3, 4], authors studied the convergence of the GAOR method for solving the linear system Hy=f. In [3], authors studied the convergence of the GAOR method when the coefficient matrices are consistently ordered matrices and gave the regions of convergence. In [4], authors studied the convergence of the GAOR method for diagonally dominant coefficient matrices and gave the regions of convergence.In order to solve the linear system (1.2) using the GAOR method, we split H as
(1.5)H=I-(00-C0)-(B1-U0B2).Then, forω≠0, one GAOR method can be defined by
(1.6)y(k+1)=Lr,ωy(k)+ωg,k=0,1,2,…,
where
(1.7)Lr,ω=(I0rCI)-1[(1-ω)I+(ω-r)(00-C0)+ω(B1-U0B2)]=((1-ω)I+ωB1-ωUω(r-1)C-ωrCB1(1-ω)I+ωB2+ωrCU)
is the iteration matrix and
(1.8)g=(I0-rCI)f.In order to decrease the spectral radius ofLr,ω, an effective method is to precondition the linear system (1.2), namely,
(1.9)PH=(I-B1*U*C*I-B2*),
then the preconditioned GAOR method can be defined by
(1.10)y(k+1)=Lr,ω*y(k)+ωg*,k=0,1,2,…,
where
(1.11)Lr,ω*=((1-ω)I+ωB1*-ωU*ω(1-r)C*-ωrC*B1*(1-ω)I+ωB2*+ωrC*U*),g*=(I0-rC*I)Pf.In [5], authors presented three kinds of preconditioners for preconditioned modified accelerated overrelaxation method to solve systems of linear equations. They showed that the convergence rate of the preconditioned modified accelerated overrelaxation method is better than that of the original method, whenever the original method is convergent.This paper is organized as follows. In Section2, we give some important definition and the known results as the preliminaries of the paper. In Section 3, we propose three preconditioners and give the comparison theorems between the preconditioned and original methods. These results show that the preconditioned GAOR methods converge faster than the GAOR method whenever the GAOR method is convergent. In Section 4, we give an example to confirm our theoretical results.


## 2. Preliminaries

We need the following definition and results.Definition 2.1.
LetA=(aij)n×n and B=(bij)n×n. We say A≥B if aij≥bij for all i,j=1,2,…,n.
This definition can be carried over to vectors by identifying them withn×1 matrices.
In this paper,ρ(·) denotes the spectral radius of a matrix.Lemma 2.2 (see [6]).
LetA∈Rn×n be nonnegative and irreducible. Then(i)
Ahas a positive real eigenvalue equal to its spectral radius ρ(A);(ii)
forρ(A), there corresponds an eigenvector x>0.Lemma 2.3 (see [7]).
LetA∈Rn×n be nonnegative and irreducible. If
(2.1)0≠αx≤Ax≤βx,αx≠Ax,Ax≠βx,
for some nonnegative vector x, then α<ρ(A)<β and x is a positive vector.


## 3. Comparison Results

We consider the preconditioned linear system(3.1)H~y=f~,
where H~=(I+S~)H and f~=(I+S~)f with
(3.2)S~=(S000),S is a p×p matrix with 1<p<n.We takeS as follows:
(3.3)S1=(0α2b12⋯00β2b210⋱00⋮⋱⋮⋱⋮00⋱0αpbp-1,p00⋯βpbp,p-10),S2=(0α2b12⋯αpb1pβ2b210⋯0⋮⋮⋱⋮βpbp10⋯0).Now, we obtain two preconditioned linear systems with coefficient matrices(3.4)H~i=(I-[B1-Si(I-B1)](I+Si)UCI-B2),fori=1,2,
where
(3.5)B1-S1(I-B1)=(b11+α2b21b12⋯b1p+α2b2pb12b21+α3b23b31-β2b21(1-b11)⋯b2p+β2b1pb21+α3b3pb23⋮⋮⋮bp-1,1+βp-1bp-1,p-2bp-2,1+αpbp-1,pbp1⋯bp-1,p+βp-1bp-1,p-2bp-2,p+αpbp-2,pbp-1,p-2bp1+βpbp-1,1bp,p-1⋯bpp+βpbp,p-1bp-1,p),B1-S2(I-B1)=(b11+α2b12b21+⋯+αpb1pbp1⋯b1p+α2b12b2p+⋯+αpb1p(1-bpp)b21-β2b21(1-b11)⋯b2p+β2b21b1p⋮⋱⋮bp1-βpbp1(1-b11)⋯bpp+βpbp1b1p).We splitH~i (i=1,2) as
(3.6)H~i=I-(00-C0)-([B1-Si(I-B1)]-(I+Si)U0B2),fori=1,2,
then the preconditioned GAOR methods for solving (3.1) are defined as follows
(3.7)y(k+1)=Lr,ω(i)y(k)+ωg~,k=0,1,2,…,
where
(3.8)Lr,ω(i)=((1-ω)I+ω[B1-Si(I-B1)]-ω(I+Si)Uω(r-1)C-ωrC[B1-Si(I-B1)](1-ω)I+ωB2+ωrC(I+Si)U)
are iteration matrices and
(3.9)g~=(I0-rCI)f~.Now, we give comparison results between the preconditioned GAOR methods defined by (3.7) and the corresponding GAOR method defined by (1.6).Theorem 3.1.
LetLr,ω,Lr,ω(1) be the iteration matrices associated with the GAOR and preconditioned GAOR methods, respectively. If the matrix H in (1.2) is irreducible with C≤0, U≤0, B1≥0, B2≥0, 0<ω≤1, 0≤r<1, bi,i+1>0, bi+1,i>0 for some i∈{2,…,p}, when 0≤bii<1(i∈{2,…,p}),
(3.10)0<αi<bi-1,i-2bi-2,i+bi-1,i(1-bi-2,i-2)bi-1,i-2[(1-bii)(1-bi-2,i-2)-bi,i-2bi-2,i]fori∈{3,…,p},α2<11-b22,0<βi<bi,i-1(1-bi+1,i+1)+bi-1,ibi+1,i-1bi,i-1[(1-bi-1,i-1)(1-bi+1,i+1)-bi-1,i+1bi+1,i-1]fori∈{2,…,p-1},βp<11-bpp,
or when bii≥1, αi>0, βi>0(i∈{2,…,p}), then either
(3.11)ρ(Lr,ω(1))<ρ(Lr,ω)<1
or
(3.12)ρ(Lr,ω(1))>ρ(Lr,ω)>1.Proof.
By direct operation, we have(3.13)Lr,ω=((1-ω)I+ωB1-ωU-ω(1-r)C(1-ω)I+ωB2)+ωr(00-CB1CU).
Since0<ω≤1, 0≤r<1, C≤0, U≤0, B1≥0, B2≥0, then
(3.14)(00-CB1CU)≥0
and Lr,ω is nonnegative. Since H is irreducible, from (3.13), it is easy to see that the matrix Lr,ω is nonnegative and irreducible.
Similarly, we can prove that the matrixLr,ω(1) is a nonnegative and irreducible matrix.
By Lemma2.2, there is a positive vector x such that
(3.15)Lr,ωx=λx,
where λ=ρ(Lr,ω). Since the matrix H is nonsingular, λ≠1. Hence, we get either λ>1 or λ<1.
Now, from (3.15) and by the definitions of Lr,ω and Lr,ω(1), we have
(3.16)Lr,ω(1)x-λx=(Lr,ω(1)-Lr,ω)x=(-ωS1(I-B1)-ωS1UωrCS1(I-B1)ωrCS1U)x=(S10-rCS10)(-ω(I-B1)-ωU00)x=(S10-rCS10)(-ω(I-B1)-ωUω(r-1)C-ωrCB1-ωI+ωB2+ωrCU)x=(S10-rCS10)(Lr,ω-I)x=(λ-1)(S10-rCS10)x.
Sincebi,i+1>0, bi+1,i>0 for some i∈{2,…,p}, when 0≤bii<1 (i∈{2,…,p}),
(3.17)0<αi<bi-1,i-2bi-2,i+bi-1,i(1-bi-2,i-2)bi-1,i-2[(1-bii)(1-bi-2,i-2)-bi,i-2bi-2,i]fori∈{3,…,p},α2<11-b22,0<βi<bi,i-1(1-bi+1,i+1)+bi-1,ibi+1,i-1bi,i-1[(1-bi-1,i-1)(1-bi+1,i+1)-bi-1,i+1bi+1,i-1]fori∈{2,…,p-1},βp<11-bpp,
or when bii≥1, αi>0, βi>0 (i∈{2,…,p}), then S1≥0 and S1≠0. So we have (S10-rCS10)x≥0, (S10-rCS10)x≠0.
Ifλ<1, then Lr,ω(1)x-λx≤0, Lr,ω(1)x-λx≠0.
By Lemma2.3, the inequality (3.11) is proved.
Ifλ>1, then Lr,ω(1)x-λx≥0, Lr,ω(1)x-λx≠0.
By Lemma2.3, the inequality (3.12) is proved.Theorem 3.2.
LetLr,ω,Lr,ω(2) be the iteration matrices associated with the GAOR and preconditioned GAOR methods, respectively. If the matrix H in (1.2) is irreducible with C≤0, U≤0, B1≥0, B2≥0, 0<ω≤1, 0≤r<1, bi,1>0, b1,i>0 for some i∈{2,3,…,p}, when 0≤b11<1, 0<βi<1/(1-b11),
(3.18)0<αi<b1i+α2b12b2i+⋯αi-1b1,i-1bi-1,i+αi+1b1,i+1bi+1,i+⋯+αpb1pbpib1i(1-bii),i∈{2,3,…,p}
or when b11≥1, αi>0, βi>0, i∈{2,3,…,p}, then either
(3.19)ρ(Lr,ω(2))<ρ(Lr,ω)<1
or
(3.20)ρ(Lr,ω(2))>ρ(Lr,ω)>1.
By the analogous proof of Theorem3.1, we can prove Theorem 3.2.


## 4. Numerical Example

Now, we present an example to illustrate our theoretical results.Example 4.1.
The coefficient matrixH in (1.2) is given by
(4.1)H=(I-B1UCI-B2),
where B1=(bij(1))p×p, B2=(bij(2))(n-p)×(n-p), C=(cij)(n-p)×p, and U=(uij)p×(n-p) with
(4.2)bii(1)=110×(i+1),i=1,2,…,p,bij(1)=130-130×j+i,i<j,i=1,2,…,p-1,j=2,…,p,bij(1)=130-130×(i-j+1)+i,i>j,i=2,…,p,j=1,2,…,p-1,bii(2)=110×(p+i+1),i=1,2,…,n-p,bij(2)=130-130×(p+j)+p+i,i<j,i=1,2,…,n-p+1,j=2,…,n-p,bij(2)=130-130×(i-j+1)+p+i,i>j,i=,2,…,n-p,j=1,2,…,n-p-1,cij=130×(p+i-j+1)+p+i-130,i=1,2,…,n-p,j=1,2,…,p,uij=130×(p+j)+i-130,i=1,2,…,p,j=1,2,…,n-p.
Table1 displays the spectral radii of the corresponding iteration matrices with some randomly chosen parameters r, ω, p. The randomly chosen parameters αi and βi satisfy the conditions of two theorems.
From Table1, we see that these results accord with Theorems 3.1-3.2.Table 1
The spectral radii of the GAOR and preconditioned GAOR iteration matrices.
n
ω
r
p
ρ
ρ
1
ρ
2
5
0.95
0.7
3
0.1450
0.1384
0.1348
10
0.9
0.85
5
0.2782
0.2726
0.2695
15
0.95
0.8
5
0.3834
0.3808
0.3796
20
0.75
0.65
10
0.6350
0.6317
0.6297
25
0.7
0.55
8
0.7872
0.7861
0.7855
30
0.65
0.55
16
0.9145
0.9136
0.9130
40
0.6
0.5
10
1.1426
1.1433
1.1436
50
0.6
0.5
10
1.3668
1.3683
1.3691
Whereρ=ρ(Lr,ω), ρ1=ρ(Lr,ω(1)), ρ2=ρ(Lr,ω(2)).



---

*Source: 563586-2012-09-26.xml*