IMPROVING COMPARISON RESULTS ON PRECONDITIONED GENERALIZED ACCELERATED OVERRELAXATION METHODS†

Journal of Applied Mathematics & Informatics.
2015.
Jan,
33(1_2):
193-201

- Received : March 19, 2014
- Accepted : June 05, 2014
- Published : January 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

In this paper, we present preconditioned generalized accelerated overrelaxation (GAOR) 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.
AMS Mathematics Subject Classification : 65F10.
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
where
is an invertible matrix with
In order to solve the linear system using the GAOR method, we split H as
Then, for
ω
≠ 0, one GAOR method can be defined by
where
is the iteration matrix and
In order to decrease the spectral radius of the iteration matrix, an effective method is to precondition the linear system (1.1), namely,
then the preconditioned GAOR (PGAOR) method can be defined by
where
This paper is organized as follows. In Section 2, 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 3, we give one example to confirm our theoretical results.
In paper
[3]
, the following preconditioned linear system was considered
where
with
S
is a
p
×
p
matrix with 1 <
p
<
n
. And
S
was taken as follows:
The preconditioned GAOR methods for solving (2.1) are
where
are iteration matrices for
i
= 1, 2, 3.
In paper
[4]
, the preconditioners introduced by Yun are of the form
In this paper, we will consider new preconditioners
where
S_{i}
are defined as above and
Then
The preconditioned GAOR methods for solving
are defined as follows
where for
i
= 1, 2, 3,
Lemma 2.1
(
[1
,
2]
).
Let A
∈
R
^{n×n}
be nonnegative and irreducible.Then
Theorem 2.1.
Let
be the iteration matrices associated of the GAOR and preconditioned GAOR methods, respectively. If the matrix H is irreducible with D
≤ 0,
E
≤ 0,
B
≥ 0,
C
≥ 0,
b_{i,i}
_{+1}
> 0,
b_{i}
_{+1,}
_{i}
> 0,
c_{i,i}
_{+1}
> 0,
c_{i}
_{+1,}
_{i}
> 0
for some i
∈ {1, 2, · · · ,
p
− 1}, 0 <
ω
≤ 1, 0 ≤
r
< 1,
then either
or
Proof
. Since 0 <
ω
≤ 1, 0 ≤
r
< 1,
D
≤ 0,
E
≤ 0,
B
≥ 0,
C
≥ 0, it is easy to prove that both
and
L_{r,ω}
are irreducible and non-negative. By Lemma 2.1, there is a positive vector
x
such that
L_{r,ω}x
=
λx
, where
λ
=
ρ
(
L_{r,ω}
). Then
Since
b_{i,i}
_{+1}
> 0,
b_{i}
_{+1,}
_{i}
> 0,
c_{i,i}
_{+1}
> 0,
c_{i}
_{+1,}
_{i}
> 0 then
S
_{1}
> 0,
V
_{1}
> 0 and
If
λ
< 1, then
By Lemma 2.1, we get
If
λ
> 1, then
By Lemma 2.1, we get
□
By the analogous proof of Theorem 2.1, we can prove the following two theorems.
Theorem 2.2.
Let
be the iteration matrices associated of the GAOR and preconditioned GAOR methods, respectively. If the matrix H is irreducible with D
≤ 0,
E
≤ 0,
B
≥ 0,
C
≥ 0,
b_{i,i}
_{+1}
> 0,
b_{i}
_{+1,}
_{i}
> 0,
c_{i,i}
_{+1}
> 0,
c_{i}
_{+1,}
_{i}
> 0
for some i
∈ {1, 2, · · · ,
p
− 1}, 0 <
ω
≤ 1, 0 ≤
r
< 1,
then either
Theorem 2.3.
Let
be the iteration matrices associated of the GAOR and preconditioned GAOR methods, respectively. If the matrix H is irreducible with D
≤ 0,
E
≤ 0,
B
≥ 0,
C
≥ 0,
b_{i,i}
_{+1}
> 0,
b_{i}
_{+1,}
_{i}
> 0,
c_{i,i}
_{+1}
> 0,
c_{i}
_{+1,}
_{i}
> 0
for some i
∈ {1, 2, · · · ,
p
− 1}, 0 <
ω
≤ 1, 0 ≤
r
< 1,
then either
Theorem 2.4.
Under the assumptions of Theorem 2.1, then either
or
Proof
. By Lemma 2.1, there is a positive vector
x
,such that
where
λ
=
ρ
(
L_{r,ω}
). Then
Under the conditions of Theorem 2.1, we know that
Thus
Then
□
By the analogous proof of Theorem 2.4, we can prove the following one theorem.
Theorem 2.5.
Under the assumptions of Theorem 2.1, then either
or
Theorem 2.6.
Under the assumptions of Theorem 2.1, then either
or
Proof
. By Lemma 2.1, there is a positive vector
x
,such that
where
Then
By assumptions,
V
_{1}
> 0. Hence we obtain the following results.
If
λ
< 1, then
By Lemma 2.1, we get
If λ > 1, then
By Lemma 2.1, we get
□
By the analogous proof of Theorem 2.6, we can prove the following two theorems.
Theorem 2.7.
Let
be the iteration matrices associated of the GAOR and preconditioned GAOR methods, respectively. If the matrix H is irreducible with D
≤ 0,
E
≤ 0,
B
≥ 0,
C
≥ 0,
b_{i,i}
_{+1}
> 0,
b_{i}
_{+1,}
_{i}
> 0,
c_{i,i}
_{+1}
> 0,
c_{i}
_{+1,}
_{i}
> 0
for some i
∈ {1, 2, · · · ,
p
− 1}, 0 <
ω
≤ 1, 0 ≤
r
< 1,
then either
Theorem 2.8.
Let
be the iteration matrices associated of the GAOR and preconditioned GAOR methods, respectively. If the matrix H is irreducible with D
≤ 0,
E
≤ 0,
B
≥ 0,
C
≥ 0,
b_{i,i}
_{+1}
> 0,
b_{i}
_{+1,}
_{i}
> 0,
c_{i,i}
_{+1}
> 0,
c_{i}
_{+1,}
_{i}
> 0
for some i
∈ {1, 2, · · · ,
p
− 1}, 0 <
ω
≤ 1, 0 ≤
r
< 1,
then either
Example 3.1.
The coefficient matrix
H
in (1.1) is given by
Table 1
displays the spectral radii of the corresponding iteration matrices with some randomly chosen parameters
r, ω, p
. From
Table 1
, we see that these results accord with Theorems 2.1-2.8.
Here
Remark:
In this paper, 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.
Guangbin Wang received his Ph.D from Shanghai University, China in 2004. Since 2004 he has been at Qingdao University of Science and Technology, China. His research interests include numerical linear algebra, matrix theory.
Department of Mathematics, Qingdao University of Science and Technology, Qingdao 266061, China.
e-mail: wguangbin750828@sina.com
Deyu Sun received his BS from Jining University, China in 2012. Since 2012 he has been at Qingdao University of Science and Technology, China. His research interests include numerical linear algebra, matrix theory.
Department of Mathematics, Qingdao University of Science and Technology, Qingdao 266061, China.
e-mail: s2613@126.com

1. Introduction

Consider the weighted linear least squares problem
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

2. Comparison results

In paper
[5]
, the preconditioners introduced by Zhou et al. are of the form
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (a):A has a positive real eigenvalue equal to its spectral radius ρ(A).
- (b):for ρ(A) ,there corresponds an eigenvector x> 0.
- (c):if0 ≠αx≤Ax≤βx, αx≠Ax, Ax≠βx for some nonnegative vector x, then α<ρ(A) <β and x is a positive vector.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (1) Ifλ< 1, thenBy Lemma 2.1, we get
- (2) Ifλ> 1, thenBy Lemma 2.1, we get

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. Numerical exampleg

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

Lager Image

PPT Slide

Lager Image

The spectral radii of the GAOR and preconditioned GAOR iteration matrices

PPT Slide

Lager Image

BIO

Berman A.
,
Plemmons R.J.
1994
Nonnegative Matrices in the Mathematical Sciences
SIAM Press
Philadelphia

Varga R.S.
2000
Matrix Iterative Analysis, in: Springer Series in Computational Mathematics, vol. 27
Springer-Verlag
Berlin

Wang G.B.
,
Wang T.
,
Tan F.P.
(2013)
Some results on preconditioned GAOR methods
Appl. Math. Comput.
219
5811 -
5816
** DOI : 10.1016/j.amc.2012.12.021**

Yun J.H.
(2012)
Comparison results on the preconditioned GAOR method for generalized least squares problems
Int. J. Comput. Math.
89
2094 -
2105
** DOI : 10.1080/00207160.2012.702898**

Zhou X.X.
,
Song Y.Z.
,
Wang L.
,
Liu Q.S.
(2009)
Preconditioned GAOR methods for solving weighted linear least squares problems
J. Comput. Appl. Math.
224
242 -
249
** DOI : 10.1016/j.cam.2008.04.034**

Citing 'IMPROVING COMPARISON RESULTS ON PRECONDITIONED GENERALIZED ACCELERATED OVERRELAXATION METHODS†
'

@article{ E1MCA9_2015_v33n1_2_193}
,title={IMPROVING COMPARISON RESULTS ON PRECONDITIONED GENERALIZED ACCELERATED OVERRELAXATION METHODS†}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2015.193}, DOI={10.14317/jami.2015.193}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={WANG, GUANGBIN
and
SUN, DEYU}
, year={2015}
, month={Jan}