# A New Version of the Accelerated Overrelaxation Iterative Method

Authors: Shi-Liang Wu; Yu-Jun Liu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Hadjidimos (1978) proposed a classical accelerated overrelaxation (AOR) iterative method to solve the system of linear equations, and discussed its convergence under the conditions that the coefficient matrices are irreducible diagonal dominant,L-matrices, and consistently orders matrices. In this paper, a new version of the AOR method is presented. Some convergence results are derived when the coefficient matrices are irreducible diagonal dominant, H-matrices, symmetric positive definite matrices, and L-matrices. A relational graph for the new AOR method and the original AOR method is presented. Finally, a numerical example is presented to illustrate the efficiency of the proposed method.


---

## Body

## 1. Introduction

Consider the following linear system:(1)
A
x
=
b
,
where A
∈
R
n
×
n, b
∈
R
n are given and x
∈
R
n is unknown. System of form (1) appears in many applications such as linear elasticity, fluid dynamics, and constrained quadratic programming [1–4]. When the coefficient matrix of the linear system (1) is large and sparse, iterative methods are recommended against direct methods. In order to solve (1) more effectively by using the iterative methods, usually, efficient splittings of the coefficient matrix A are required. For example, the classical Jacobi and Gauss-Seidel iterations are obtained by splitting the matrix A into its diagonal and off-diagonal parts.For the numerical solution of (1), the accelerated overrelaxation (AOR) method was introduced by Hadjidimos in [5] and is a two-parameter generalization of the successive overrelaxation (SOR) method. In certain cases the AOR method has better convergence rate than Jacobi, JOR, Gauss-Seidel, or SOR method [5, 6]. Sufficient conditions for the convergence of the AOR method have been considered by many authors including [6–14]. To improve the convergence rate of the AOR method, the preconditioned AOR (PAOR) method has been considered by many authors including [15–21]. Although Krylov subspace methods [4, 22] are considered as one kind of the important and efficient iterative techniques for solving the large sparse linear systems because these methods are cheap to be implemented and are able to fully exploit the sparsity of the coefficient matrix, Krylov subspace methods are very slow or even fail to converge when the coefficient matrix of (1) is often extremely ill-conditioned and highly indefinite.The purpose of this paper is to present a new version of the accelerated overrelaxation (AOR) method for the linear system (1), which is called the quasi accelerated overrelaxation (QAOR) method. We discuss some sufficient conditions for the convergence of the QAOR method when the coefficient matrices are irreducible diagonal dominant, H-matrices, symmetric positive definite matrices, and L-matrices.The remainder of the paper is organized as follows. In Section2 the QAOR method is derived. In Section 3, some convergence results are given for the QAOR method when the coefficient matrices are irreducible diagonal dominant, H-matrices, symmetric positive definite matrices, and L-matrices. A relational graph for QAOR and AOR is presented in Section 4. Finally, in Section 5 a numerical example is presented to illustrate the efficiency of the proposed method.


## 2. The QAOR Method

To introduce the QAOR method, firstly, a brief review of the classical AOR method is required.For any splitting,A
=
M
-
N with det
⁡
(
M
)
≠
0, the basic iterative method for solving (1) is
(2)
x
(
i
+
1
)
=
M
-
1
N
x
(
i
)
+
M
-
1
b
,
i
=
0,1
,
…
.
Let
(3)
A
=
D
-
A
L
-
A
U
,
where D is a nonsingular diagonal matrix and A
L and A
U are strictly lower and upper triangular matrices, respectively. Then the classical AOR method in [5] is defined:
(4)
(
D
-
r
A
L
)
x
(
i
+
1
)
=
[
(
1
-
ω
)
D
+
(
ω
-
r
)
A
L
+
ω
A
U
]
x
(
i
)
+
ω
b
,
i
=
1,2
,
…
,
where r is an acceleration parameter and ω is an overrelaxation parameter. Its iterative matrix is
(5)
L
r
,
ω
=
(
D
-
r
A
L
)
-
1
[
(
1
-
ω
)
D
+
(
ω
-
r
)
A
L
+
ω
A
U
]
=
(
I
-
r
L
)
-
1
[
(
1
-
ω
)
I
+
(
ω
-
r
)
L
+
ω
U
]
,
where L
=
D
-
1
A
L and U
=
D
-
1
A
U. Obviously, the iterative matrix of the Jacobi method is L
0,1, the iterative matrix of the Gauss-Seidel method is L
1,1, and the iterative matrix of the successive overrelaxation (SOR) method is L
ω
,
ω.In fact, if we introduce matrices(6)
M
1
=
D
-
r
A
L
,
N
1
=
(
1
-
ω
)
D
+
(
ω
-
r
)
A
L
+
ω
A
U
,
then
(7)
A
=
1
ω
(
M
1
-
N
1
)
,
L
r
,
ω
=
M
1
-
1
N
1
.
Therefore, one can readily verify that the AOR method can be induced by the matrix splitting A
=
(
1
/
ω
)
(
M
1
-
N
1
).To establish the QAOR method, we consider the following matrix splitting of the coefficient matrixA; that is to say,
(8)
M
2
=
(
1
+
ω
)
D
-
r
A
L
,
N
2
=
D
+
(
ω
-
r
)
A
L
+
ω
A
U
.
Then
(9)
A
=
1
ω
(
M
2
-
N
2
)
.
Based on the above matrix splitting (8), the QAOR method is defined as follows:
(10)
(
(
1
+
ω
)
D
-
r
A
L
)
x
(
i
+
1
)
=
[
D
+
(
ω
-
r
)
A
L
+
ω
A
U
]
x
(
i
)
+
ω
b
,
i
=
1,2
,
…
,
and its iterative matrix is
(11)
Q
r
,
ω
=
(
(
1
+
ω
)
D
-
r
A
L
)
-
1
[
D
+
(
ω
-
r
)
A
L
+
ω
A
U
]
=
(
(
1
+
ω
)
I
-
r
L
)
-
1
[
I
+
(
ω
-
r
)
L
+
ω
U
]
.Comparing the QAOR method with the AOR method, it is easy to see that the iteration matrix of the QAOR method is similar to that of the AOR method. Based on this fact, the QAOR method may conserve all the advantages of the AOR method. Ifω
=
r, the QAOR reduces to the QSOR method. The QSOR method is called the KSOR method as well [23, 24].Next, we will discuss some sufficient conditions for the convergence of the QAOR method when the coefficient matrices are irreducible diagonal dominant,H-matrices, symmetric positive definite matrices, and L-matrices.


## 3. Main Results

WhenA is an irreducible matrix with weak diagonal dominance, obviously, both the coefficient matrix A and the corresponding diagonal matrix D are nonsingular. Based on this case, we have the following theorem for the QAOR method.Theorem 1.
IfA is an irreducible matrix with weak diagonal dominance, then the QAOR method converges for all -
1
≤
r
≤
1 and ω
>
0.Proof.
We assume that for the eigenvalueλ of Q
r
,
ω we have |
λ
|
≥
1. For this eigenvalue the relationship below holds:
(12)
det
⁡
(
Q
r
,
ω
-
λ
I
)
=
0
.
By performing a simple series of transformations, we have
(13)
det
⁡
(
W
)
=
0
,
where
(14)
W
=
I
-
r
(
λ
-
1
)
+
ω
λ
-
1
+
λ
ω
L
-
ω
λ
-
1
+
λ
ω
U
.
The coefficients of L and U in (14) are less than one in modulus. To prove this it is sufficient and necessary to prove that
(15)
|
λ
-
1
+
λ
ω
|
≥
|
r
(
λ
-
1
)
+
ω
|
,
|
λ
-
1
+
λ
ω
|
≥
|
ω
|
.
If λ
-
1
=
q
e
i
θ where q and θ are real with 0
<
q
≤
1, then the first inequality in (15) is equivalent to
(16)
(
1
-
r
2
)
(
1
+
q
2
)
-
(
(
1
-
r
2
)
+
(
1
+
r
)
ω
)
2
q
cos
⁡
θ
+
2
ω
+
ω
2
-
ω
2
q
2
+
2
r
ω
q
2
≥
0
,
which holds for r
=
-
1 (in this case, obviously, ω
(
1
-
q
2
)
(
2
+
ω
)
≥
0). Since (
1
-
r
2
)
+
(
1
+
r
)
ω
≥
0, (16) holds for all real θ if and only if it holds for cos
⁡
θ
=
1. Thus, (16) is equivalent to
(17)
(
1
-
r
2
)
(
1
-
q
)
2
+
ω
[
ω
(
1
-
q
2
)
+
2
(
1
-
q
)
(
1
-
r
q
)
]
≥
0
,
which is true. The second inequality in (15) is equivalent to
(18)
(
1
+
ω
)
2
-
2
q
(
1
+
ω
)
cos
⁡
θ
+
q
2
-
ω
2
q
2
≥
0
,
which, for the same reason, must be satisfied for cos
⁡
θ
=
1. Thus, we have
(19)
(
1
+
ω
)
2
+
q
(
1
+
ω
2
)
≥
0
,
which is also true. That is, for all -
1
≤
r
≤
1 and ω
>
0, W is nonsingular which contradicts with det
⁡
(
W
)
=
0. Therefore, ρ
(
Q
r
,
ω
)
<
1.WhenA
=
D
-
A
L
-
A
U is an H-matrix, it follows that ρ
(
|
B
|
)
<
1 with
(20)
B
=
D
-
1
(
A
L
+
A
U
)
=
L
+
U
.Theorem 2.
IfA is an H-matrix and 0
≤
r
≤
ω
(
ω
≠
0
), then the QAOR method converges.Proof.
LetQ
=
(
(
1
+
ω
)
I
-
r
|
L
|
). Then
(21)
|
(
(
1
+
ω
)
I
-
r
L
)
-
1
|
=
1
1
+
ω
|
(
I
-
r
1
+
ω
L
)
-
1
|
=

1
1
+
ω
|
I

+
r
1
+
ω
L
+

r
2
(
1
+
ω
)
2
L
2

+
⋯
+

r
n
-
1
(
1
+
ω
)
n
-
1
L
n
-
1
|
≤
1
1
+
ω
(
I
+
r
1
+
ω
|
L
|
+
r
2
(
1
+
ω
)
2
|
L
|
2
+
⋯
+
r
n
-
1
(
1
+
ω
)
n
-
1
|
L
|
n
-
1
)
=
(
(
1
+
ω
)
I
-
r
|
L
|
)
-
1
=
Q
-
1
.
Let R
=
I
+
(
ω
-
r
)
|
L
|
+
ω
|
U
|. Then
(22)
|
I
+
(
ω
-
r
)
L
+
ω
U
|
≤
I
+
(
ω
-
r
)
|
L
|
+
ω
|
U
|
.
Obviously, we have
(23)
|
Q
r
,
ω
|
=
|
(
(
1
+
ω
)
I
-
r
L
)
-
1
×
(
I
+
(
ω
-
r
)
L
+
ω
U
)
(
(
1
+
ω
)
I
-
r
L
)
-
1
|
≤
Q
-
1
R
,
which implies
(24)
ρ
(
Q
r
ω
)
≤
ρ
(
Q
-
1
R
)
.
ρ
(
Q
-
1
R
)
<
1 if and only if
(25)
Q
-
R
=
(
1
+
ω
)
I
-
r
|
L
|
-
(
I
+
(
ω
-
r
)
|
L
|
+
ω
|
U
|
)
=
ω
(
I
-
|
B
|
)
is a monotone matrix. Since A is an H-matrix, then ω
(
I
-
|
B
|
) is a monotone matrix. Therefore it is completed.Let(26)
Q
-
=
1
ω
(
(
1
+
ω
)
D
-
r
A
L
)
,
R
-
=
1
ω
(
D
+
(
ω
-
r
)
A
L
+
ω
A
U
)
.
When A
=
D
-
A
L
-
A
U is symmetric positive definite, obviously, Q
- is nonsingular. It is easy to see that
(27)
A
=
Q
-
-
R
-
,
Q
r
,
ω
=
Q
-
-
1
R
-
.
In this case, the QAOR method converges if M
=
Q
-
+
Q
-
T
-
A is positive definite [2]. By the simple computations, we have
(28)
M
=
2
+
ω
ω
D
+
ω
-
r
ω
(
A
L
+
A
U
)
.
That is to say, the QAOR method converges if
(29)
D
-
1
/
2
M
D
-
1
/
2
=
2
+
ω
ω
I
+
ω
-
r
ω
D
-
1
/
2
(
A
L
+
A
U
)
D
-
1
/
2
is positive definite. Let μ
i
(
i
=
1,2
,
…
,
n
) be eigenvalues of D
-
1
/
2
(
A
L
+
A
U
)
D
-
1
/
2. The left in (29) is positive definite if and only if
(30)
2
+
ω
ω
+
ω
-
r
ω
μ
i
>
0
,
i
=
1,2
,
…
,
n
.
Since D
-
1
/
2
(
A
L
+
A
U
)
D
-
1
/
2 and D
-
1
(
A
L
+
A
U
)
=
B are similar, then both have the same eigenvalues. Let μ
=
min
⁡
i
μ
i. If the following inequality is satisfied
(31)
(
2
+
ω
)
+
(
ω
-
r
)
μ
>
0
,
for
ω
>
0
,
then the QAOR method converges. Therefore, we have the following theorem.Theorem 3.
Assume thatA
=
D
-
A
L
-
A
U is symmetric positive definite. Let μ
i
(
i
=
1,2
,
…
,
n
) be eigenvalues of B
=
D
-
1
(
A
L
+
A
U
), μ
=
min
⁡
i
μ
i, and 0
≤
r
≤
ω
(
ω
≠
0
). If
(32)
(
2
+
ω
)
+
(
ω
-
r
)
μ
>
0
,
then the QAOR method converges.WhenA
=
D
-
A
L
-
A
U is an L-matrix, the following theorem is derived.Theorem 4.
IfA is an L-matrix and 0
≤
r
≤
ω
(
ω
≠
0
), then the QAOR method converges for ρ
(
L
0,1
)
<
1.Proof.
Assume thatλ
=
ρ
(
Q
r
,
ω
)
≥
1. Based on our assumptions, we easily get that
(33)
I
+
(
ω
-
r
)
L
+
ω
U
≥
0
,
(34)
(
(
1
+
ω
)
I
-
r
L
)
-
1
=
1
1
+
ω
(
I
-
r
1
+
ω
L
)
-
1
=
1
1
+
ω
[
I
+
r
1
+
ω
L
+
r
2
(
1
+
ω
)
2
L
2
+
⋯
+
r
n
-
1
(
1
+
ω
)
n
-
1
L
n
-
1
]
≥
0
.
Thus, for the iteration matrix Q
r
,
ω we have
(35)
Q
r
,
ω
=
(
(
1
+
ω
)
I
-
r
L
)
-
1
[
I
+
(
ω
-
r
)
L
+
ω
U
]
≥
0
.
That is, Q
r
,
ω is a nonnegative matrix. If x
≠
0 is the corresponding eigenvector, we have
(36)
Q
r
,
ω
x
=
λ
x
,
which is equivalent to
(37)
(
ω
-
r
+
r
λ
ω
L
+
U
)
x
=
λ
-
1
+
λ
ω
ω
x
.
From (37), we have
(38)
λ
-
1
+
λ
ω
ω
≤
ρ
(
ω
-
r
+
r
λ
ω
L
+
U
)
.
Obviously, (
ω
-
r
+
r
λ
)
/
ω
≥
1. Therefore,
(39)
0
≤
ω
-
r
+
r
λ
ω
L
+
U
≤
ω
-
r
+
r
λ
ω
(
L
+
U
)
=
ω
-
r
+
r
λ
ω
L
0,1
.
Combining (38) with (39), we have
(40)
λ
-
1
+
λ
ω
≤
(
ω
-
r
+
r
λ
)
ρ
(
L
0,1
)
.
By simple manipulation, we have
(41)
ρ
(
L
0,1
)
≥
λ
-
1
+
λ
ω
ω
-
r
+
r
λ
≥
1
.
If ρ
(
L
0,1
)
<
1, then
(42)
λ
-
1
+
λ
ω
ω
-
r
+
r
λ
<
1
,
which implies λ
<
1 so that if ρ
(
L
0,1
)
<
1 then so does the QAOR method.Further, we have the following theorem.Theorem 5.
LetA
=
D
-
A
L
-
A
U be an L-matrix and λ
=
ρ
(
Q
r
,
ω
). If 0
≤
r
≤
ω
(
ω
≠
0
), then
(43)
λ
-
1
+
λ
ω
ω
=
ρ
(
ω
-
r
+
r
λ
ω
L
+
U
)
.Proof.
Based on Theorem4, obviously, here it is need to prove
(44)
λ
-
1
+
λ
ω
ω
≥
ρ
(
ω
-
r
+
r
λ
ω
L
+
U
)
.
Let ρ
(
(
(
ω
-
r
+
r
λ
)
/
ω
)
L
+
U
)
=
a. There exists a nonzero vector y
≥
0 such that
(45)
[
ω
-
r
+
r
λ
ω
L
+
U
]
y
=
a
y
,
which is equivalent to
(46)
(
(
1
+
ω
)
I
-
λ
(
1
+
ω
)
r
1
+
ω
a
L
)
-
1
×
[
I
+
(
ω
-
r
)
L
+
ω
U
]
y
=
ω
a
+
1
1
+
ω
y
.
Let
(47)
T
=
(
(
1
+
ω
)
I
-
λ
(
1
+
ω
)
r
1
+
ω
a
L
)
-
1
[
I
+
(
ω
-
r
)
L
+
ω
U
]
.
Obviously, (
ω
a
+
1
)
/
(
1
+
ω
)
≤
ρ
(
T
). Since λ
-
1
+
λ
ω
≤
ω
a, we have
(48)
(
(
1
+
ω
)
I
-
λ
(
1
+
ω
)
r
1
+
ω
a
L
)
-
1
≤
(
(
1
+
ω
)
I
-
r
L
)
-
1
,
which implies T
≤
Q
r
,
ω. Therefore, we have
(49)
ω
a
+
1
1
+
ω
≤
ρ
(
T
)
≤
ρ
(
Q
r
,
ω
)
=
λ
.
That is to say,
(50)
a
≤
λ
-
1
+
λ
ω
ω
,
which is completed.Some remarks on (43) are given as follows.(i)
Obviously,λ
≥
1
/
(
1
+
ω
). If λ
=
1, then ρ
(
B
)
=
1.
(ii)
Ifλ
=
1
/
(
1
+
ω
), then ρ
(
B
)
=
0. In fact, we have
(51)
0
=
ρ
(
ω
-
r
+
r
(
1
/
(
1
+
ω
)
)
ω
L
+
U
)
=
ρ
(
(
1
-
r
1
+
ω
)
L
+
U
)
≥
(
1
-
r
1
+
ω
)
ρ
(
B
)
.
(iii)
0
<
ρ
(
B
)
<
1 if and only if 1
/
(
1
+
ω
)
<
λ
<
1. In this case, from (43) we have
(52)
(
ω
-
r
)
ρ
(
B
)
+
1
1
+
ω
-
r
ρ
(
B
)
≤
λ
≤
ω
ρ
(
B
)
+
1
1
+
ω
.
(iv)
ρ
(
B
)
>
1 if and only if λ
>
1.


## 4. A Relational Graph for QAOR and AOR

Based on the above discussion, we have(53)
Q
r
,
ω
=
(
(
1
+
ω
)
D
-
r
A
L
)
-
1
[
D
+
(
ω
-
r
)
A
L
+
ω
A
U
]
=
(
(
1
+
ω
)
I
-
r
L
)
-
1
[
I
+
(
ω
-
r
)
L
+
ω
U
]
=
(
I
-
r
1
+
ω
L
)
-
1
[
1
1
+
ω
I
+
ω
-
r
1
+
ω
L
+
ω
1
+
ω
U
]
=
(
I
-
r
1
+
ω
L
)
-
1
×
[
(
1
-
ω
1
+
ω
)
I
+
ω
-
r
1
+
ω
L
+
ω
1
+
ω
U
]
.
Let s
=
ω
/
(
1
+
ω
) and t
=
r
/
(
1
+
ω
). Therefore, we have
(54)
Q
r
,
ω
=
(
I
-
t
L
)
-
1
[
(
1
-
s
)
I
+
(
s
-
t
)
L
+
s
U
]
=
L
t
,
s
.
That is to say, when s
=
ω
/
(
1
+
ω
) and t
=
r
/
(
1
+
ω
), the QAOR method reduces to the AOR method. Based on this case, Figure 1 describes the relationship between the QAOR method and the AOR method.Figure 1
A graph for QAOR and AOR.


## 5. Numerical Example

Now let us consider the following example to assess the feasibility and effectiveness of the QAOR iteration method. Suppose thatb
=
A
e
(
e
=
(
1,1
,
…
,
1
)
T
) and the coefficient matrix A of (1) is given by
(55)
A
=
{
a
i
j
=
1
10
j
-
1
20
,
i
>
j
,
a
i
i
=
1
,
a
i
j
=
1
10
(
i
-
j
)
-
1
20
,
i
<
j
.The initial guess for all tests is zero. The tests are performed in MATLAB 7.0. In Tables1 and 2, we list the value of the spectral radius ρ of iterative matrix, the iteration numbers (IT), and CPU's time (CPU) with the different value of w and r when the QAOR (QSOR) iteration is used to solve the linear system (1).Table 1
ρ, IT, and RES of QAOR.
n
w
r
ρ
IT
CPU
8
0.9
0.6
0.575
63
0.015
16
0.95
0.2
0.7188
102
0.056
20
0.9
0.3
0.8068
155
0.084
25
0.8
0.4
0.9198
385
0.156Table 2
ρ, IT, and RES of QSOR.
n
w
ρ
IT
CPU
8
0.9
0.5726
62
0.015
16
0.95
0.6977
94
0.035
20
0.9
0.789
141
0.076
25
0.8
0.9123
352
0.098From Tables1 and 2, the iteration numbers and CPU’s time of QSOR are less than those of QAOR. That is to say, the QAOR iteration is not much better than the QSOR iteration under certain conditions.



---

*Source: 725360-2014-08-26.xml*