ESOR METHOD WITH DIAGONAL PRECONDITIONERS FOR SPD LINEAR SYSTEMS†

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

- Received : May 17, 2014
- Accepted : September 20, 2014
- Published : January 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

In this paper, we propose an extended SOR (ESOR) method with diagonal preconditioners for solving symmetric positive definite linear systems, and then we provide convergence results of the ESOR method. Lastly, we provide numerical experiments to evaluate the performance of the ESOR method with diagonal preconditioners.
AMS Mathematics Subject Classification : 65F10.
where
A
= (
a_{ij}
) ∈ ℝ
^{n}
^{×}
^{n}
is a symmetric positive definite (SPD) matrix. The basic iterative method
[6
,
7]
for solving the linear system (1) can be expressed as
where
x
_{0}
is an initial vector and
A
=
M
−
N
is a splitting of
A
. To improve the convergence rate of the basic iterative method, the original linear system (1) is usually transformed into the following preconditioned linear system
where
P
is called a preconditioner. Then the preconditioned iterative method
[1
,
2
,
3
,
5
,
8]
for solving the linear system (3) is
where
x
_{0}
is an initial vector and
PA
=
M_{p}
−
N_{p}
is a splitting of
PA
. It is well known that the necessary and sufficient condition for the iterative method (4) to converge for any
x
_{0}
is
(see
[6
,
7]
).
Throughout the paper, we assume that
A
=
D
−
L
−
U
, where
D
= diag(
A
) is the diagonal matrix, and
L
and
U
are strictly lower triangular and strictly upper triangular matrices, respectively. For a vector
x
∈ ℝ
^{n}
, ∥
x
∥
_{2}
denotes
ℓ
_{2}
-norm of
x
and
x
^{∗}
denotes the conjugate transpose of
x
. For a square matrix
B
,
ρ
(
B
) denotes the spectral radius of
B
.
In this paper, we only consider diagonal preconditioners P which are diagonal matrices. Recently, Tarazaga and Cuellar
[4]
proposed two diagonal preconditioners which were obtained by minimizing the norm of the iteration matrix using the Frobenius norm and the infinity norm. The diagonal preconditioner
P_{F}
obtained by minimizing the Frobenius norm is given by
where
a_{i}
stands for the
i
th row of the matrix
A
. The diagonal preconditioner
P_{I}
obtained by minimizing the infinity norm is given by
P_{I}
=
αI
, where
and
I
denotes the identity matrix of order
n
. It was shown in
[4]
that
ρ
(
I
−
P_{F}A
) < 1 and
ρ
(
I
−
P_{I}A
) < 1 when
A
is a strictly diagonal dominant matrix with positive diagonal elements.
We now propose an
extended SOR (ESOR) method
with diagonal preconditioner
P
for solving the preconditioned linear system (3), which is defined by
where
ω
> 0 is a relaxation parameter. If we rearrange the equation (6), then the ESOR method can be rewritten as
where
H_{P}
=
I
−
ω
(
P
^{−1}
−
ωL
)
^{−1}
A
and
B_{P}
=
ω
(
P
^{−1}
−
ωL
)
^{−1}
. The
H_{P}
is called the
iteration matrix
for the ESOR method with diagonal preconditioner
P
. It is easy to see that the ESOR method reduces to the SOR method if
P
=
D
^{−1}
. In this respect, the ESOR method can be viewed as an extension of the SOR method.
This paper is organized as follows. In Section 2, we provide convergence results of the ESOR method with diagonal preconditioners including the
P_{F}
and
P_{I}
proposed in
[4]
. In Section 3, we provide numerical experiments to evaluate the performance of the ESOR method with diagonal preconditioners. Lastly, some conclusions are drawn.
Theorem 2.1.
Let A
= (
a_{ij}
) =
D
−
L
−
U be a symmetric positive definite matrix and P
= (
p_{ij}
)
be a diagonal matrix with positive diagonal elements. If
then the ESOR method with the diagonal preconditioner P converges for any x
_{0}
.
Proof
. Notice that
a_{ii}
> 0 for all
i
,
U
=
L^{T}
and
It is sufficient to show that
ρ
(
H_{P}
) < 1. Assume that
H_{P}x
=
λx
, where
x
is a nonzero vector. Then, one obtains
By premultiplying
x
^{∗}
on both sides of equation (8),
Since
A
is positive definite, it can be easily shown that
λ
≠ 1. Taking the complex conjugate transpose on both sides of equation (9),
Adding two equations (9) and (10), one obtains
Let
Then
E
is a diagonal matrix whose diagonal element is given by
for every
i
. Since
for all
i
, every diagonal element of
E
is positive and so
E
is positive definite. Hence, (11) implies that
By simple calculation, one easily obtains |
λ
| < 1. Hence, the proof is complete.
□
Since the ESOR method with
P
=
D
^{−1}
becomes the SOR method, the following well-known property is immediately obtained from Theorem 2.1.
Corollary 2.2
(
[6]
).
Let A
=
D
−
L
−
U be a symmetric positive definite matrix. If
0 <
ω
< 2,
then the SOR method converges for any x
_{0}
.
Corollary 2.3.
Let A
= (
a_{ij}
) =
D
−
L
−
U be a symmetric positive definite matrix. If
then the ESOR method with P
=
P_{F} converges for any x
_{0}
.
Proof
. Since
the proof is directly obtained from Theorem 2.1. □
Corollary 2.4.
Let A
= (
a_{ij}
)
be a symmetric positive definite matrix. If
0 <
ω
< 2,
then the ESOR method with P
=
P_{F} converges for any x
_{0}
.
Proof
. Since
Hence, this corollary follows from Corollary 2.3. □
Corollary 2.5.
Let A
= (
a_{ij}
)
be a symmetric strictly diagonally dominant or irreducibly diagonally dominant matrix with positive diagonal elements. If
then the ESOR method with P
=
P_{F} converges for any x
_{0}
.
Proof
. Since a symmetric strictly diagonally dominant or irreducibly diagonally dominant matrix with positive diagonal elements is positive definite, this corollary follows from Corollary 2.3. □
Corollary 2.6.
Let A
= (
a_{ij}
) =
D
−
L
−
U be a symmetric positive definite matrix. If A is strictly diagonally dominant and
then the ESOR method with P
=
P_{I} converges for any x
_{0}
.
Proof
. Note that
From Theorem 2.1, the ESOR method with
P
=
P_{I}
converges when
Since
the proof is complete. □
the upper bound of ω in Corollary 2.6 is greater than 1.
Corollary 2.7.
Let A be a symmetric strictly diagonally dominant matrix with positive diagonal elements. If
then the ESOR method with P
=
P_{I} converges for any x
_{0}
.
Corollary 2.8.
Let A
= (
a_{ij}
) =
D
−
L
−
U be a symmetric positive definite matrix with D
=
βI, where β is a positive constant. If A is strictly diagonally dominant, then the ESOR method with P
=
P_{I} is the same as the SOR method which converges for any x
_{0}
when
0 <
ω
< 2.
Proof
.
Since D
=
βI
, ∥
A
∥
_{∞}
+ sg(
A
) = 2
β
. It follows that
P_{I}
=
β
^{−1}
I
=
D
^{−1}
. Thus, the ESOR method with
P
=
P_{I}
is the same as the SOR method. From Corollary 2.2, the ESOR method with
P
=
P_{I}
converges when 0 <
ω
< 2. □
P_{F}
) and ESOR(
P_{I}
) stand for the ESOR methods with diagonal preconditioners
P_{F}
and
P_{I}
, respectively. Bold numbers in
Tables 1
to
4
refer to the optimal performances for 3 different iterative methods. The first example considers the SPD matrix with constant diagonal and nonpositive off-diagonal entries.
Example 3.1.
Consider the two dimensional Poisson’s equation
with the Dirichlet boundary condition on ∂Ω. When the central difference scheme on a uniform grid with
m
×
m
interior node is applied to the discretization of the equation (13), we obtain a linear system
Ax
=
b
whose coefficient matrix
A
∈ ℝ
^{n}
^{×}
^{n}
is given by
where ⊗ denotes the Kronecker product,
n
=
m
^{2}
,
P
= tridiag(−1, 4,−1) and
Q
= tridiag(−1, 0,−1) are
m
×
m
tridiagonal matrices. Note that this matrix
A
is a symmetric irreducibly diagonally dominant matrix. It is easy to compute that
and
α
= 0.25. Since
A
has a constant diagonal (i.e.,
D
= 4
I
), ESOR method with
P_{I}
is the same as SOR method from Corollary 2.7. Numerical results for Example 3.1 with
n
= 10
^{2}
or
n
= 15
^{2}
are provided in
Table 1
.
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.1.
The second example considers the randomly generated SPD matrix with negative off-diagonal entries.
Example 3.2.
Consider the SPD matrix
A
∈ ℝ
^{n}
^{×}
^{n}
which is generated by using the following Matlab functions:
Notice that
and
α
≈ 0.1220 for
n
= 100 or 0.1235 for
n
= 200. Numerical results for Example 3.2 with
n
= 100 or
n
= 200 are provided in
Table 2
.
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.2.
The third example considers the randomly generated SPD matrix with positive off-diagonal entries.
Example 3.3.
Consider the SPD matrix
A
∈ ℝ
^{n}
^{×}
^{n}
which is generated by using the following Matlab functions:
Notice that
for
n
= 100 or 2.0001 for
and
α
≈ 0.8366 for
n
= 100 or 0.9100 for
n
= 200. Numerical results for Example 3.3 with
n
= 100 or
n
= 200 are provided in
Table 3
.
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.3.
The last example considers the randomly generated SPD matrix whose offdiagonal entries contain both positive and negative numbers. More specifically, each of positive and negative entries takes 50% of all off-diagonal entries.
Example 3.4.
Consider the SPD matrix
A
∈ ℝ
^{n}
^{×}
^{n}
which is generated by using the following Matlab functions:
Notice that
for
n
= 100 or 2.0002 for
and
α
≈ 0.8037 for
n
= 100 or 0.8900 for
n
= 200. Numerical results for Example 3.4 with
n
= 100 or
n
= 200 are provided in
Table 4
.
Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.4.
P_{F}
performs better than the other two methods (see
Tables 3
to
4
). These observations are similar to those of the extended Jacobi method studied in
[4]
. It was also observed that the optimal number of
ω
is greater than 1 for SPD matrices with negative or nonpositive off-diagonal entries, while the optimal number of
ω
is not greater than 1 for SPD matrices containing many positive off-diagonal entries. All of these observations have not been proved theoretically, so further research should be required to prove these observations and find out additional advantages of the ESOR method with diagonal preconditioners.
SeYoung Oh received M.Sc. from Seoul National University and Ph.D at University of Minnesota. Since 1992 he has been at Chungnam National University. His research interests include numerical optimization and biological computation.
Department of Mathematics, Chungnam National University, Daejeon 305-764, Korea
e-mail: soh@cnu.ac.kr
Jae Heon Yun received M.Sc. from Kyungpook National University, and Ph.D. from Iowa State University. He is currently a professor at Chungbuk National University since 1991. His research interests are computational mathematics, iterative method and parallel computation.
Department of Mathematics, College of Natural Sciences, Chungbuk National University, Cheongju 362-763, Korea
e-mail: gmjae@chungbuk.ac.kr
Kyoum Sun Kim is a graduate student in Chungbuk National University. Her research interests are computational mathematics, new homotopy methods for solving functional equations.
Department of Mathematics, Chungbuk National University, Cheongju, 361-763, Korea.
e-mail: giunsun@naver.com

Iterative method
;
Diagonal preconditioner
;
Symmetric positive definite matrix
;
SOR method
;
Extended SOR method

1. Introduction

In this paper, we consider an iterative method for solving the following linear system
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. Convergence results of the ESOR method

In this section, we consider convergence of the ESOR method with diagonal preconditioner for solving the preconditioned linear system (3).
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

3. Numerical experiments

In this section, we provide numerical experiments to evaluate the performance of the ESOR method with diagonal preconditioners. All numerical experiments are carried out using Matlab. In
Tables 1
to
4
, ESOR(
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.1.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.2.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.3.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Spectral radii for iteration matrices of ESOR and SOR methods for Example 3.4.

PPT Slide

Lager Image

4. Conclusions

In this paper, we proposed the ESOR method with diagonal preconditioners and provided its convergence results. Numerical results are in good agreement with the theoretical results provided in Section 2 (see
Tables 1
to
4
). For SPD matrices with negative or nonpositive off-diagonal entries, the ESOR method does not have advantages compared eith the SOR method (see
Tables 1
and
2
). For SPD matrices containing many positive off-diagonal entries, the ESOR method with
BIO

Gunawardena A.
,
Jain S.
,
Snyder L.
(1991)
Modified iterative methods for consistent linear systems
Linear Algebra Appl.
154/156
123 -
143
** DOI : 10.1016/0024-3795(91)90376-8**

Kincaid D.
,
Cheney W.
2002
Numerical Analysis: Mathematics of Scientific Computing
3rd Edition
Brooks/Cole
CA

Saad Y.
1996
Iterative methods for sparse linear systems
PWS Publishing Company
Boston

Tarazaga T.
,
Cuellar D.
(2009)
Preconditioner generated by minimizing norm
Comput. Math. Appl.
57
1305 -
1312
** DOI : 10.1016/j.camwa.2008.10.096**

Usui M.
,
Niki H.
,
Kohno T.
(1994)
Adaptive Gauss Seidel method for linear systems
Intern. J. Computer Math.
51
119 -
125
** DOI : 10.1080/00207169408804271**

Varga R.S.
2000
Matrix iterative analysis
Springer
Berlin

Young D.M.
1971
Iterative solution of large linear systems
Academic Press
New York

Yun J.H.
,
Lim H.J.
,
Kim K.S.
(2014)
Performance comparison of preconditioned iterative methods with direct preconditioners
J. Appl. Math. & Informatics
32
389 -
403
** DOI : 10.14317/jami.2014.389**

Citing 'ESOR METHOD WITH DIAGONAL PRECONDITIONERS FOR SPD LINEAR SYSTEMS†
'

@article{ E1MCA9_2015_v33n1_2_111}
,title={ESOR METHOD WITH DIAGONAL PRECONDITIONERS FOR SPD LINEAR SYSTEMS†}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2015.111}, DOI={10.14317/jami.2015.111}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={OH, SEYOUNG
and
YUN, JAE HEON
and
KIM, KYOUM SUN}
, year={2015}
, month={Jan}