Advanced
IMPROVING COMPARISON RESULTS ON PRECONDITIONED GENERALIZED ACCELERATED OVERRELAXATION METHODS†
IMPROVING COMPARISON RESULTS ON PRECONDITIONED GENERALIZED ACCELERATED OVERRELAXATION METHODS†
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 193-201
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : March 19, 2014
  • Accepted : June 05, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
GUANGBIN WANG
DEYU SUN

Abstract
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.
Keywords
1. Introduction
Consider the weighted linear least squares problem
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is an invertible matrix with
PPT Slide
Lager Image
In order to solve the linear system using the GAOR method, we split H as
PPT Slide
Lager Image
Then, for ω ≠ 0, one GAOR method can be defined by
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the iteration matrix and
PPT Slide
Lager Image
In order to decrease the spectral radius of the iteration matrix, an effective method is to precondition the linear system (1.1), namely,
PPT Slide
Lager Image
then the preconditioned GAOR (PGAOR) method can be defined by
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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.
2. Comparison results
In paper [5] , the preconditioners introduced by Zhou et al. are of the form
PPT Slide
Lager Image
In paper [3] , the following preconditioned linear system was considered
PPT Slide
Lager Image
where
PPT Slide
Lager Image
with
PPT Slide
Lager Image
S is a p × p matrix with 1 < p < n . And S was taken as follows:
PPT Slide
Lager Image
The preconditioned GAOR methods for solving (2.1) are
PPT Slide
Lager Image
where
PPT Slide
Lager Image
are iteration matrices for i = 1, 2, 3.
In paper [4] , the preconditioners introduced by Yun are of the form
PPT Slide
Lager Image
In this paper, we will consider new preconditioners
PPT Slide
Lager Image
PPT Slide
Lager Image
where Si are defined as above and
PPT Slide
Lager Image
Then
PPT Slide
Lager Image
The preconditioned GAOR methods for solving
PPT Slide
Lager Image
are defined as follows
PPT Slide
Lager Image
where for i = 1, 2, 3,
PPT Slide
Lager Image
Lemma 2.1 ( [1 , 2] ). Let A R n×n be nonnegative and irreducible.Then
  • (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.
Theorem 2.1. Let
PPT Slide
Lager Image
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, bi,i +1 > 0, bi +1, i > 0, ci,i +1 > 0, ci +1, i > 0 for some i ∈ {1, 2, · · · , p − 1}, 0 < ω ≤ 1, 0 ≤ r < 1, then either
PPT Slide
Lager Image
or
PPT Slide
Lager Image
Proof . Since 0 < ω ≤ 1, 0 ≤ r < 1, D ≤ 0, E ≤ 0, B ≥ 0, C ≥ 0, it is easy to prove that both
PPT Slide
Lager Image
and Lr,ω are irreducible and non-negative. By Lemma 2.1, there is a positive vector x such that Lr,ωx = λx , where λ = ρ ( Lr,ω ). Then
PPT Slide
Lager Image
Since bi,i +1 > 0, bi +1, i > 0, ci,i +1 > 0, ci +1, i > 0 then S 1 > 0, V 1 > 0 and
PPT Slide
Lager Image
If λ < 1, then
PPT Slide
Lager Image
By Lemma 2.1, we get
PPT Slide
Lager Image
If λ > 1, then
PPT Slide
Lager Image
By Lemma 2.1, we get
PPT Slide
Lager Image
By the analogous proof of Theorem 2.1, we can prove the following two theorems.
Theorem 2.2. Let
PPT Slide
Lager Image
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, bi,i +1 > 0, bi +1, i > 0, ci,i +1 > 0, ci +1, i > 0 for some i ∈ {1, 2, · · · , p − 1}, 0 < ω ≤ 1, 0 ≤ r < 1, then either
PPT Slide
Lager Image
Theorem 2.3. Let
PPT Slide
Lager Image
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, bi,i +1 > 0, bi +1, i > 0, ci,i +1 > 0, ci +1, i > 0 for some i ∈ {1, 2, · · · , p − 1}, 0 < ω ≤ 1, 0 ≤ r < 1, then either
PPT Slide
Lager Image
Theorem 2.4. Under the assumptions of Theorem 2.1, then either
PPT Slide
Lager Image
or
PPT Slide
Lager Image
Proof . By Lemma 2.1, there is a positive vector x ,such that
PPT Slide
Lager Image
where λ = ρ ( Lr,ω ). Then
PPT Slide
Lager Image
Under the conditions of Theorem 2.1, we know that
PPT Slide
Lager Image
Thus
PPT Slide
Lager Image
Then
  • (1) Ifλ< 1, thenBy Lemma 2.1, we get
  • (2) Ifλ> 1, thenBy Lemma 2.1, we get
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
PPT Slide
Lager Image
or
PPT Slide
Lager Image
Theorem 2.6. Under the assumptions of Theorem 2.1, then either
PPT Slide
Lager Image
or
PPT Slide
Lager Image
Proof . By Lemma 2.1, there is a positive vector x ,such that
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Then
PPT Slide
Lager Image
By assumptions, V 1 > 0. Hence we obtain the following results.
If λ < 1, then
PPT Slide
Lager Image
By Lemma 2.1, we get
PPT Slide
Lager Image
If λ > 1, then
PPT Slide
Lager Image
By Lemma 2.1, we get
PPT Slide
Lager Image
By the analogous proof of Theorem 2.6, we can prove the following two theorems.
Theorem 2.7. Let
PPT Slide
Lager Image
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, bi,i +1 > 0, bi +1, i > 0, ci,i +1 > 0, ci +1, i > 0 for some i ∈ {1, 2, · · · , p − 1}, 0 < ω ≤ 1, 0 ≤ r < 1, then either
PPT Slide
Lager Image
Theorem 2.8. Let
PPT Slide
Lager Image
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, bi,i +1 > 0, bi +1, i > 0, ci,i +1 > 0, ci +1, i > 0 for some i ∈ {1, 2, · · · , p − 1}, 0 < ω ≤ 1, 0 ≤ r < 1, then either
PPT Slide
Lager Image
3. Numerical exampleg
Now, we present an example to illustrate our theoretical results.
Example 3.1. The coefficient matrix H in (1.1) is given by
PPT Slide
Lager Image
PPT Slide
Lager Image
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.
The spectral radii of the GAOR and preconditioned GAOR iteration matrices
PPT Slide
Lager Image
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.
BIO
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
References
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