Preconditioned GAOR Methods for Weighted Linear Least Squares Problems

(1)

Volume 2012, Article ID 563586,9pages doi:10.1155/2012/563586

Research Article

Comparison Results on

Preconditioned GAOR Methods for Weighted Linear Least Squares Problems

Guangbin Wang,

¹

Yanli Du,

¹

and Fuping Tan

²

1Department of Mathematics, Qingdao University of Science and Technology, Qingdao 266061, China

2Department of Mathematics, Shanghai University, Shanghai 200444, China

Correspondence should be addressed to Guangbin Wang,[email protected] Received 18 July 2012; Accepted 26 August 2012

Academic Editor: Zhongxiao Jia

Copyrightq2012 Guangbin Wang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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.

1. Introduction

Consider the weighted linear least squares problem

minx∈RⁿAx−b^TW⁻¹Ax−b, 1.1

whereWis 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

Hyf, 1.2

(2)

where

H

I−B₁ U C I−B₂

1.3

is an invertible matrix with B₁

b_ij

p×p, B₂

b_ij

n−p×n−p, C

c_ij

n−p×p, U

u_ij

p×n−p. 1.4

Yuan proposed a generalized SORGSORmethod to solve linear system1in1;

afterwards, Yuan and Jin2established a generalized AORGAORmethod 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 coeﬃcient matrices are consistently ordered matrices and gave the regions of convergence. In 4, authors studied the convergence of the GAOR method for diagonally dominant coeﬃcient matrices and gave the regions of convergence.

In order to solve the linear system1.2using the GAOR method, we splitHas

HI−

0 0

−C 0

−

B₁ −U 0 B₂

. 1.5

Then, forω /0, one GAOR method can be defined by

y^k1L_r,ωy^kωg, k0,1,2, . . . , 1.6

where

L_r,ω I 0

rC I −1

1−ωI ω−r 0 0

−C 0

ω

B₁ −U 0 B2

1−ωIωB₁ −ωU

ωr−1C−ωrCB1 1−ωIωB2ωrCU

1.7

is the iteration matrix and

g

I 0

−rC I

f. 1.8

In order to decrease the spectral radius ofLr,ω, an eﬀective method is to precondition the linear system1.2, namely,

PH

I−B^∗₁ U^∗ C^∗ I−B₂^∗

, 1.9

(3)

then the preconditioned GAOR method can be defined by

y^k1L^∗_r,ωy^kωg^∗, k0,1,2, . . . , 1.10

where

L^∗_r,ω

1−ωIωB^∗₁ −ωU^∗

ω1−rC^∗−ωrC^∗B₁^∗ 1−ωIωB₂^∗ωrC^∗U^∗

, g^∗

I 0

−rC^∗ I

Pf.

1.11

In5, 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 Section 2, 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×nandB bij_n×n. We sayA≥Bifa_ij≥b_ijfor alli, j1,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.2see6. LetA∈R^n×nbe nonnegative and irreducible. Then iAhas a positive real eigenvalue equal to its spectral radiusρA;

iiforρA, there corresponds an eigenvectorx >0.

Lemma 2.3see7. LetA∈R^n×nbe nonnegative and irreducible. If

0/αx≤Ax≤βx, αx /Ax, Ax /βx, 2.1

for some nonnegative vectorx, thenα < ρA< βandxis a positive vector.

3. Comparison Results

We consider the preconditioned linear system

Hy f, 3.1

(4)

whereH ISHandf ISfwith

S S 0

0 0

, 3.2

Sis ap×pmatrix with 1< p < n.

We takeSas follows:

S1

⎛

⎜⎜

⎝

0 α₂b₁₂ · · · 0 0

β₂b₂₁ 0 . .. 0 0

... . .. ... . .. ...

0 0 . .. 0 αpb_p−1,p

0 0 · · · βpb_p,p−1 0

⎞

⎟⎟

⎠

, S2

⎛

⎜⎜

⎜⎝

0 α₂b₁₂ · · · αpb1p

β2b21 0 · · · 0 ... ... . .. ... βpbp1 0 · · · 0

⎞

⎟⎟

⎟⎠. 3.3

Now, we obtain two preconditioned linear systems with coeﬃcient matrices

H_i

I−B1−SiI−B1 ISiU

C I−B₂

, fori1,2, 3.4

where

B1−S1I−B1

⎛

⎜⎜

⎝

b₁₁α₂b₂₁b₁₂ · · · b1pα₂b2pb₁₂ b21α3b23b31−β2b211−b11 · · · b2pβ2b1pb21α3b3pb23

... ... ...

b_p−1,1β_p−1b_p−1,p−2b_p−2,1αpb_p−1,pb_p1 · · · b_p−1,pβ_p−1b_p−1,p−2b_p−2,pαpb_p−2,pb_p−1,p−2

b_p1β_pb_p−1,1b_p,p−1 · · · b_ppβ_pb_p,p−1b_p−1,p

⎞

⎟⎟

⎠ ,

B₁−S₂I−B₁

⎛

⎜⎜

⎜⎝

b₁₁α₂b₁₂b₂₁· · ·α_pb_1pb_p1 · · · b_1pα₂b₁₂b_2p· · ·α_pb_1p 1−b_pp b₂₁−β₂b₂₁1−b₁₁ · · · b_2pβ₂b₂₁b_1p

... . .. ...

b_p1−β_pb_p11−b₁₁ · · · b_ppβ_pb_p1b_1p

⎞

⎟⎟

⎟⎠.

3.5

We splitH_ii1,2as

H_iI−

0 0

−C 0

−

B1−S_iI−B₁ −IS_iU

0 B2

, fori1,2, 3.6

(5)

then the preconditioned GAOR methods for solving3.1are defined as follows

y^k1Lⁱ_r,ωy^kωg, k0,1,2, . . . , 3.7

where

Lⁱ_r,ω

1−ωIω

B₁−Si

I−B₁

−ωISiU

ωr−1C−ωrCB1−SiI−B1 1−ωIωB2ωrCISiU

3.8

are iteration matrices and

g

I 0

−rC I

f. 3.9

Now, we give comparison results between the preconditioned GAOR methods defined by3.7and the corresponding GAOR method defined by1.6.

Theorem 3.1. LetLr,ω, L¹_r,ωbe the iteration matrices associated with the GAOR and preconditioned GAOR methods, respectively. If the matrixHin1.2is irreducible withC≤0,U≤0,B₁≥0,B₂≥0, 0< ω≤1, 0≤r <1,b_i,i1>0,b_i1,i>0 for somei∈ {2, . . . , p}, when 0≤b_ii <1i∈ {2, . . . , p},

0< α_i< b_i−1,i−2b_i−2,ib_i−1,i1−b_i−2,i−2

b_i−1,i−21−bii1−b_i−2,i−2−b_i,i−2b_i−2,i fori∈

3, . . . , p

, α₂< 1 1−b22

, 0< β_i< b_i,i−11−b_i1,i1 b_i−1,ib_i1,i−1

b_i,i−11−bi−1,i−11−bi1,i1−bi−1,i1b_i1,i−1 fori∈

2, . . . , p−1

, β_p< 1 1−bpp,

3.10

or whenb_ii≥1,α_i>0,β_i>0 i∈ {2, . . . , p}, then either

ρ L¹r,ω

< ρLr,ω<1 3.11

or

ρ L¹_r,ω

> ρLr,ω>1. 3.12

Proof. By direct operation, we have

L_r,ω

1−ωIωB₁ −ωU

−ω1−rC 1−ωIωB2

ωr

0 0

−CB1 CU

. 3.13

(6)

Since 0< ω≤1, 0≤r <1,C≤0,U≤0,B1≥0,B2≥0, then

0 0

−CB1 CU

≥0 3.14

andLr,ω is nonnegative. SinceH is irreducible, from3.13, it is easy to see that the matrix L_r,ωis nonnegative and irreducible.

Similarly, we can prove that the matrixL¹_r,ωis a nonnegative and irreducible matrix.

ByLemma 2.2, there is a positive vectorxsuch that

Lr,ωxλx, 3.15

whereλ ρLr,ω. Since the matrixH is nonsingular,λ /1. Hence, we get eitherλ > 1 or λ <1.

Now, from3.15and by the definitions ofLr,ωandL¹r,ω, we have

L¹_r,ωx−λx

L¹_r,ω−L_r,ω x

−ωS1I−B1 −ωS1U ωrCS₁I−B₁ ωrCS₁U

x

S₁ 0

−rCS1 0

−ωI−B₁ −ωU

0 0

x

S₁ 0

−rCS1 0

−ωI−B₁ −ωU ωr−1C−ωrCB₁ −ωIωB₂ωrCU

x

S₁ 0

−rCS1 0

Lr,ω−Ix λ−1

S₁ 0

−rCS1 0

x.

3.16

Sinceb_i,i1>0,b_i1,i>0 for somei∈ {2, . . . , p}, when 0≤b_ii<1i∈ {2, . . . , p},

0< αi< b_i−1,i−2b_i−2,ib_i−1,i1−b_i−2,i−2

b_i−1,i−21−b_ii1−b_i−2,i−2−b_i,i−2b_i−2,i fori∈

3, . . . , p

, α2 < 1 1−b₂₂,

0< βi< b_i,i−11−b_i1,i1 b_i−1,ib_i1,i−1

b_i,i−11−bi−1,i−11−bi1,i1−bi−1,i1b_i1,i−1 fori∈

2, . . . , p−1

, βp< 1 1−bpp,

3.17

(7)

or whenb_ii ≥1,α_i>0,β_i>0i∈ {2, . . . , p}, thenS₁≥0 andS₁/0. So we have _S

1 0

−rCS10

x≥ 0, _S

1 0

−rCS10

x /0.

Ifλ <1, thenL¹r,ωx−λx≤0,L¹r,ωx−λx /0.

ByLemma 2.3, the inequality3.11is proved.

Ifλ >1, thenL¹_r,ωx−λx≥0,L¹_r,ωx−λx /0.

ByLemma 2.3, the inequality3.12is proved.

Theorem 3.2. LetL_r,ω, L²_r,ωbe the iteration matrices associated with the GAOR and preconditioned GAOR methods, respectively. If the matrixH in1.2is irreducible withC ≤ 0,U ≤ 0,B₁ ≥ 0, B2 ≥ 0, 0 < ω ≤ 1, 0 ≤ r < 1,bi,1 > 0,b1,i > 0 for somei ∈ {2,3, . . . , p}, when 0 ≤ b11 < 1, 0< β_i<1/1−b₁₁,

0< α_i< b_1iα₂b₁₂b_2i· · ·α_i−1b_1,i−1b_i−1,iα_i1b_1,i1b_i1,i· · ·α_pb_1pb_pi

b_1i1−b_ii , i∈

2,3, . . . , p 3.18

or whenb₁₁≥1,α_i>0,β_i>0,i∈ {2,3, . . . , p}, then either

ρ L²_r,ω

< ρLr,ω<1 3.19

or

ρ L²_r,ω

> ρLr,ω>1. 3.20

By the analogous proof ofTheorem 3.1, we can proveTheorem 3.2.

4. Numerical Example

Now, we present an example to illustrate our theoretical results.

Example 4.1. The coeﬃcient matrixHin1.2is given by

H

I−B₁ U C I−B2

, 4.1

(8)

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ρL¹r,ω,ρ2ρL²r,ω.

whereB₁ b_ij¹

p×p,B₂ b²_ij

n−p×n−p,C cij_n−p×p, andU uij_p×n−pwith b¹_ii 1

10×i1, i1,2, . . . , p, b¹_ij 1

30− 1

30×ji, i < j, i1,2, . . . , p−1, j2, . . . , p, b¹_ij 1

30− 1

30×

i−j1

i, i > j, i2, . . . , p, j1,2, . . . , p−1,

b²_ii 1

10×

pi1, i1,2, . . . , n−p, b²_ij 1

30− 1

30× pj

pi, i < j, i1,2, . . . , n−p1, j2, . . . , n−p, b²_ij 1

30− 1

30×

i−j1

pi, i > j, i,2, . . . , n−p, j1,2, . . . , n−p−1,

cij 1

30×

pi−j1

pi− 1

30, i1,2, . . . , n−p, j1,2, . . . , p,

uij 1

30× pj

i− 1

30, i1,2, . . . , p, j1,2, . . . , n−p.

4.2

Table 1displays the spectral radii of the corresponding iteration matrices with some randomly chosen parametersr,ω,p. The randomly chosen parametersαi andβi satisfy the conditions of two theorems.

FromTable 1, we see that these results accord with Theorems3.1-3.2.

Acknowledgments

This work was supported by the National Natural Science Foundation of China Grant no. 11001144and the Science and Technology Program of Shandong Universities of China J10LA06.

(9)

References

1 J.-Y. Yuan, “Numerical methods for generalized least squares problems,” Journal of Computational and Applied Mathematics, vol. 66, no. 1-2, pp. 571–584, 1996.

2 J.-Y. Yuan and X.-Q. Jin, “Convergence of the generalized AOR method,” Applied Mathematics and Computation, vol. 99, no. 1, pp. 35–46, 1999.

3 M. T. Darvishi, P. Hessari, and J. Y. Yuan, “On convergence of the generalized accelerated overrelaxation method,” Applied Mathematics and Computation, vol. 181, no. 1, pp. 468–477, 2006.

4 M. T. Darvishi and P. Hessari, “On convergence of the generalized AOR method for linear systems with diagonally dominant coeﬃcient matrices,” Applied Mathematics and Computation, vol. 176, no. 1, pp. 128–133, 2006.

5 M. T. Darvishi, P. Hessari, and B.-C. Shin, “Preconditioned modified AOR method for systems of linear equations,” International Journal for Numerical Methods in Biomedical Engineering, vol. 27, no. 5, pp. 758–

769, 2011.

6 R. S. Varga, Matrix Iterative Analysis, vol. 27 of Springer Series in Computational Mathematics, Springer, Berlin, Germany, 2000.

7 A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, vol. 9 of Classics in Applied Mathematics, SIAM, Philadelphia, Pa, USA, 1994.

(10)

Submit your manuscripts at http://www.hindawi.com

Hindawi Publishing Corporation

http://www.hindawi.com Volume 2014

Mathematics

^{Journal of}

Hindawi Publishing Corporation http://www.hindawi.com

Differential Equations

International Journal of

Volume 2014

Applied Mathematics^{Journal of}

Mathematical PhysicsAdvances in

Complex Analysis

^{Journal of}

Optimization

^{Journal of}

Combinatorics

Journal of

Function Spaces

Abstract and Applied Analysis

International Journal of Mathematics and Mathematical Sciences

The Scientific World Journal

Discrete Dynamics in Nature and Society

Discrete Mathematics

^{Journal of}

Preconditioned GAOR Methods for Weighted Linear Least Squares Problems

Research Article

Comparison Results on

Preconditioned GAOR Methods for Weighted Linear Least Squares Problems

Guangbin Wang,

Yanli Du,

and Fuping Tan

1. Introduction

2. Preliminaries

3. Comparison Results

4. Numerical Example

Acknowledgments

References

Submit your manuscripts at http://www.hindawi.com

Mathematics

Complex Analysis

Optimization

Combinatorics

Function Spaces

The Scientific World Journal

Discrete Mathematics

Stochastic Analysis