# Generalized ASOR and Modified ASOR Methods for Saddle Point Problems

Authors: Zhengge Huang; Ligong Wang; Zhong Xu; Jingjing Cui
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Recently, the accelerated successive overrelaxation- (SOR-) like (ASOR) method was proposed for saddle point problems. In this paper, we establish a generalized accelerated SOR-like (GASOR) method and a modified accelerated SOR-like (MASOR) method, which are extension of the ASOR method, for solving both nonsingular and singular saddle point problems. The sufficient conditions of the convergence (semiconvergence) for solving nonsingular (singular) saddle point problems are derived. Finally, numerical examples are carried out, which show that the GASOR and MASOR methods have faster convergence rates than the SOR-like, generalized SOR (GSOR), modified SOR-like (MSOR-like), modified symmetric SOR (MSSOR), generalized symmetric SOR (GSSOR), generalized modified symmetric SOR (GMSSOR), and ASOR methods with optimal or experimentally found optimal parameters when the iteration parameters are suitably chosen.


---

## Body

## 1. Introduction

Consider the following large and sparse saddle point problem:(1)
A
u
=
A
B
-
B
T
0
x
y
=
p
-
q
,where A
∈
R
m
×
m is a symmetric positive definite matrix, B
∈
R
m
×
n, p
∈
R
m, and q
∈
R
n (m
≥
n). It follows that the linear system (1) is nonsingular when B is of full column rank and singular when B is rank deficient [1].The saddle point problem (1) is important and arises in a variety of scientific and engineering applications, such as mixed finite element approximation of elliptic partial differential equations, optimal control, computational fluid dynamics, weighted least-squares problems, electronic networks, and computer graphics; see [1–4] and references therein.When the linear system (1) is nonsingular, a number of iterative methods and their numerical properties have been discussed to approximate the unique solution of nonsingular saddle point problem (1) in the literatures, such as SOR-like methods [5–11], Uzawa-type methods [5, 12–18], Hermitian and skew-Hermitian splitting (HSS) methods and their variants [2, 19–24], restrictively preconditioned conjugate gradient (RPCG) methods [25, 26], and preconditioned Krylov subspace iteration methods [27–29].In the case ofB in (1) being rank deficient, we call the linear system (1) a singular saddle point problem. For this case, various kinds of relaxation iteration methods have also been established. In [30–34], the authors applied the inexact Uzawa methods for singular saddle point problems.Recently, Njeru and Guo [35] developed an accelerated SOR-like (ASOR) method for the nonsingular saddle point problem (1) and numerical experiments results show that the convergence rate of the ASOR method is faster than the convergence rates of the SOR-like, GSSOR, and GSOR methods when the parameters are suitably chosen. It can be described as follows.For the coefficient matrix of the saddle point problem (1), Njeru and Guo [35] made the following splitting:(2)
A
=
D
-
L
-
U
,where (3)
D
=
α
A
0
0
Q
,
L
=
-
A
0
B
T
1
2
Q
,
U
=
α
A
-
B
0
1
2
Q
,with α
>
0, ω
≠
0, and Q
∈
R
n
×
n is a symmetric positive definite matrix. The iteration for ASOR method [35] is thus described by the algorithm below.The ASOR Method. Given initial vectors x
(
0
)
∈
R
m and y
(
0
)
∈
R
n and two real relaxation factors α
>
0 and ω
≠
0, for k
=
0,1
,
2
,
…, until the iteration sequence {
(
x
(
k
)
T
)
,
(
y
(
k
)
T
)
} converges to the exact solution of the saddle point problem (1), compute(4)
x
k
+
1
=
α
α
+
ω
x
k
-
ω
α
+
ω
A
-
1
B
y
k
-
p
,
y
k
+
1
=
y
k
+
2
ω
2
-
ω
Q
-
1
B
T
x
k
+
1
-
q
.In addition, the authors in [35] obtained the experimentally found optimal parameters by using trial and error method in different cases, and the experimentally found optimal values for α and ω are very close to(5)
α
=
μ
m
a
x
μ
m
i
n
8
μ
m
i
n
+
μ
m
a
x
,
ω
=
2
μ
m
i
n
μ
m
a
x
+
1
μ
m
i
n
+
μ
m
a
x
2
,where μ
m
a
x and μ
m
i
n are the maximum and minimum eigenvalues of the matrix Q
-
1
B
T
A
-
1
B, respectively.In this paper, based on the ASOR method, by adding the new parameters, the generalized ASOR (GASOR) method and the modified ASOR (MASOR) method are proposed to solve the nonsingular and the singular saddle point problem (1). We discuss the convergence properties of the GASOR and MASOR methods for solving nonsingular saddle point problems and the semiconvergence properties of the GASOR and MASOR methods for solving singular saddle point problems, respectively. In addition, the choice of the relaxation parameters of the GASOR and MASOR methods is discussed in Section 4. Numerical examples are implemented to illustrate the effectiveness of the GASOR and MASOR methods with appropriate parameters for both nonsingular and singular saddle point problems.The rest of this paper is organized as follows. In Section2, we propose the GASOR method for solving nonsingular and singular saddle point problem (1) and discuss the convergence (semiconvergence) properties of the GASOR method for solving nonsingular (singular) saddle point problems. The MASOR method is proposed and convergence (semiconvergence) properties of the MASOR method for solving nonsingular (singular) saddle point problems are derived in Section 3. The analysis of the optimal convergence factors of two new methods is presented in Section 4. In Section 5, numerical experiments are provided to examine the feasibility and effectiveness of the GASOR and MASOR methods for solving both nonsingular and singular saddle point problems. Finally, some conclusions are drawn.


## 2. The Generalized ASOR Method for Saddle Point Problems

### 2.1. The Generalized ASOR Method

In this section, we propose the generalized ASOR (GASOR) method for solving the saddle point problem (1). The GASOR method with appropriate parameters has the faster convergence rate than those of SOR-like [8], GSOR [5], MSOR-like [9], and ASOR [35] methods with optimal or experimentally found optimal parameters for nonsingular saddle point problems. For the coefficient matrix of the augmented system (1), we make the splitting of A as in (2).Letω and τ be two nonzero reals, let I
m
∈
R
m
×
m and I
n
∈
R
n
×
n be the m-by-m and the n-by-n identity matrices, respectively, and(6)
Ω
=
ω
I
m
0
0
τ
I
n
.Then, we consider the following generalized ASOR iteration scheme for solving the saddle point problem (1):(7)
x
k
+
1
y
k
+
1
=
M
α
,
ω
,
τ
x
k
y
k
+
D
-
Ω
L
-
1
Ω
p
-
q
,where M
α
,
ω
,
τ is the iteration matrix of the GASOR method and its form as follows:(8)
M
α
,
ω
,
τ
=
D
-
Ω
L
-
1
I
-
Ω
D
+
Ω
U
=
α
+
ω
A
0
-
τ
B
T
2
-
τ
2
Q
-
1
α
A
-
ω
B
0
2
-
τ
2
Q
=
1
α
+
ω
A
-
1
0
2
τ
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
2
2
-
τ
Q
-
1
α
A
-
ω
B
0
2
-
τ
2
Q
=
α
α
+
ω
I
m
-
ω
α
+
ω
A
-
1
B
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
I
n
-
2
τ
ω
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
B
.Then, we have the following algorithmic description of the GASOR method.The GASOR Method. Given initial vectors x
(
0
)
∈
R
m and y
(
0
)
∈
R
n and three real relaxation factors α
>
0 and ω
,
τ
≠
0, for k
=
0,1
,
2
,
…, until the iteration sequence {
(
x
(
k
)
T
)
,
(
y
(
k
)
T
)
} converges to the exact solution of the saddle point problem (1), compute(9)
x
k
+
1
=
α
α
+
ω
x
k
-
ω
α
+
ω
A
-
1
B
y
k
-
p
,
y
k
+
1
=
y
k
+
2
τ
2
-
τ
Q
-
1
B
T
x
k
+
1
-
q
.Note that the GASOR method involves three parametersα, ω, and τ. Since(10)
D
-
Ω
L
=
α
+
ω
A
0
-
τ
B
T
2
-
τ
2
Q
,then the matrix (
D
-
Ω
L
) is invertible if and only if(11)
α
+
ω
≠
0
,
τ
≠
2
,by the definiteness of A and Q.Note that the GASOR method withτ
=
ω reduces to the ASOR method proposed by Njeru and Guo [35].


### 2.2. Convergence of the GASOR Method

Lemma 1.
Suppose thatμ is an eigenvalue of matrix Q
-
1
B
T
A
-
1
B, if λ satisfies(12)
λ
-
1
2
-
τ
α
-
α
λ
-
λ
ω
=
2
λ
τ
ω
μ
,and then λ is an eigenvalue of iteration matrix M
α
,
ω
,
τ. Conversely, if λ is an eigenvalue of M
α
,
ω
,
τ such that λ
≠
1, τ
≠
2, λ
≠
α
/
(
α
+
ω
), and μ satisfy (12), then μ is a nonzero eigenvalue of matrix Q
-
1
B
T
A
-
1
B.Proof.
Letλ be an eigenvalue of M
α
,
ω
,
τ and let (
x
T
,
y
T
)
T be the corresponding eigenvector. Then we have(13)
M
α
,
ω
,
τ
x
y
=
λ
x
y
.Equation (13) can be written as(14)
α
A
-
ω
B
0
1
-
τ
2
Q
x
y
=
λ
α
+
ω
A
0
-
τ
B
T
1
-
τ
2
Q
x
y
,which is equivalent to(15)
α
-
α
λ
-
λ
ω
A
x
=
ω
B
y
,
(16)
λ
-
1
2
-
τ
2
Q
y
=
λ
τ
B
T
x
.Inasmuch as α
-
α
λ
-
λ
ω
≠
0, we obtain(17)
x
=
ω
α
-
α
λ
-
λ
ω
A
-
1
B
yfrom (15). Substituting (17) into (16), we have(18)
λ
-
1
2
-
τ
2
y
=
λ
τ
ω
α
-
α
λ
-
λ
ω
Q
-
1
B
T
A
-
1
B
yby the definiteness of Q.
Ifμ satisfies (12), then we have(19)
Q
-
1
B
T
A
-
1
B
y
=
μ
y
.If y
=
0, then from (17) this leads to x
=
0, which is a contradiction that (
x
T
,
y
T
)
T is an eigenvector. Thus, y
≠
0, and therefore μ is an eigenvalue of Q
-
1
B
T
A
-
1
B. Furthermore, let λ
=
1; from (15) and (16), we have α
A
x
-
ω
B
y
=
(
α
+
ω
)
A
x and τ
B
T
x
=
0. Thus, x
=
-
A
-
1
B
y by ω
≠
0 and the definiteness of A, which yields that B
T
A
-
1
B
y
=
0. However A is positive definite, so is A
-
1, which implies that B
y
=
0 and then x
=
-
A
-
1
B
y
=
0 and y
=
0 by B which is full column rank. This contradicts the assumption that (
x
T
,
y
T
)
T is an eigenvector as well. Therefore, combining (12) and the assumptions τ
≠
2, λ
≠
α
/
(
α
+
ω
) results in μ
≠
0; that is, μ is a nonzero eigenvalue of the matrix Q
-
1
B
T
A
-
1
B.
We can prove the second assertion by reversing the process.One may easily show that for the special caseτ
=
ω the GASOR method reduces to the ASOR method derived in [35].Lemma 2 (see [36]).
Both roots of the real quadratic equationx
2
-
b
x
+
c
=
0 are less than one in modulus if and only if|
c
|
<
1 and |
b
|
<
1
+
c.Theorem 3.
LetA and Q be symmetric positive definite, and let B be full column rank. Assume that all eigenvalues μ of Q
-
1
B
T
A
-
1
B are real and positive. Then, the GASOR method is convergent for all α, ω, and τ such that(20)
ω
τ
μ
m
a
x
2
-
τ
<
2
α
+
ω
,
ω
>
0
,
α
>
0
,
0
<
τ
<
2
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Proof.
After some manipulations on Lemma1, we have(21)
α
+
ω
τ
-
2
λ
2
+
ω
+
2
α
2
-
τ
-
2
τ
ω
μ
λ
+
α
τ
-
2
=
0
.Changing the above equation into x
2
-
b
x
+
c
=
0, we find(22)
λ
2
+
2
τ
ω
μ
α
+
ω
2
-
τ
-
2
α
+
ω
α
+
ω
λ
+
α
α
+
ω
=
0
,where(23)
b
=
2
α
+
ω
α
+
ω
-
2
τ
ω
μ
α
+
ω
2
-
τ
,
c
=
α
α
+
ω
.By Lemma 2, |
λ
|
<
1 if and only if(24)
α
α
+
ω
<
1
,
(25)
2
α
+
ω
α
+
ω
-
2
τ
ω
μ
α
+
ω
2
-
τ
<
α
α
+
ω
+
1
.It follows from (24) that(26)
ω
>
0
,
-
2
α
<
ω
.It is obvious that (26) holds true by α
>
0 and ω
>
0. From (25), we get(27)
0
<
ω
τ
μ
2
-
τ
<
2
α
+
ω
.Since ω
>
0, τ
>
0, and μ is an real and positive eigenvalue of matrix Q
-
1
B
T
A
-
1
B, we have(28)
0
<
τ
<
2
,
ω
τ
μ
2
-
τ
<
2
α
+
ω
.However,(29)
ω
τ
μ
2
-
τ
≤
ω
τ
μ
m
a
x
2
-
τ
.We obtain that if the conditions (20) are satisfied, the GASOR method is convergent.From (21), we get the following corollary.Corollary 4.
LetA and Q be symmetric positive definite, let and B be full column rank. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
ω
,
τ are given by λ
=
α
/
(
α
+
ω
) or(30)
λ
=
1
2
2
α
+
ω
α
+
ω
-
2
ω
τ
μ
2
-
τ
α
+
ω
±
2
ω
τ
μ
2
-
τ
α
+
ω
-
2
α
+
ω
α
+
ω
2
-
4
α
α
+
ω
.


### 2.3. Semiconvergence of the GASOR Method for Singular Saddle Point Problems

For singular saddle point problems, in [37], Wang and Zhang studied the accelerated HSS (AHSS) method first put forward by Bai and Golub in [20] for solving singular saddle point problems; Yang and Wu [38] proposed the Uzawa-HSS method and applied it for singular saddle point problems [39]. Recently, Miao and Cao [40] studied the semiconvergence of the generalized local HSS method established by Zhu [41] for singular saddle point problems; Zhou and Zhang [42] discussed the semiconvergence of the GMSSOR method which derived by Zhang et al. in [43] for singular saddle point problems. In the sequel, Chen and Ma [44] presented a generalized shift-splitting preconditioner and investigated this preconditioner for singular saddle point problems [45]. For more literatures on this theme, one can refer to [46, 47] and references therein.In this section, by using the idea of [42], we assume that B in (1) is rank deficient; that is, r
a
n
k
(
B
)
<
n; that is, A in (1) is singular. In addition, we will discuss the semiconvergence region for parameters α, ω, and τ in the GASOR method for solving the singular saddle point problem (1). The GASOR method has a faster convergence rate than the ones of the GSSOR [48], MSSOR [49], and GMSSOR [42, 43] methods for singular saddle point problems when optimal or experimentally found optimal parameters are chosen for them.We first recollect some needed known results about stationary iterative methods for singular linear systems. We denote the range and the null space of the matrixA by R
(
A
) and N
(
A
), respectively. The smallest nonnegative integer i such that rank
⁡
(
A
i
)
=
r
a
n
k
(
A
i
+
1
) is called the index of A and is denoted by i
=
i
n
d
e
x
(
A
). For a matrix A
∈
C
m
×
m, the splitting A
=
M
-
N is a nonsingular splitting if M is nonsingular. Let T
=
M
-
1
N and c
=
M
-
1
b, then solving linear systems A
x
=
b is equivalent to considering the following iterative scheme:(31)
x
k
+
1
=
T
x
k
+
c
.When A is singular, the semiconvergence about the iteration scheme (31) is precisely described in [50, 51].Definition 5 (see [51]).
For any initial vectorz
(
0
), the iteration scheme (31) is semiconvergence to a solution z
∗ of A
x
=
b if and only if the iteration matrix T is semiconvergent. Moreover, it holds that z
∗
=
(
I
-
T
)
D
c
+
[
I
-
(
I
-
T
)
(
I
-
T
)
D
]
z
(
0
), where I is the identity matrix with appropriate size and (
I
-
T
)
D denotes the Drazin inverse of I
-
T.Definition 6 (see [42]).
The pseudospectral radius of matrixT is defined as(32)
V
T
=
max
⁡
λ
∣
λ
∈
σ
T
∖
1
,where σ
(
T
) stands for the spectrum of matrix T.Lemma 7 (see [52]).
The iteration (31) is semiconvergent, if and only if the following conditions hold:(1)
i
n
d
e
x
(
I
-
T
)
=
1.
(2)
V
(
T
)
<
1.Theorem 8.
LetA and Q be symmetric positive definite, and let B be rank deficient. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
ω
,
τ are 1, λ
=
α
/
(
α
+
ω
), and the remainder eigenvalues are the roots of the quadratic equation (21).Proof.
In order to seek for the eigenvalues ofM
α
,
ω
,
τ, we need to solve d
e
t
(
λ
I
-
M
α
,
ω
,
τ
)
=
0:(33)
λ
I
-
M
α
,
ω
,
τ
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
λ
-
1
I
n
+
2
τ
ω
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
B
.If λ
=
α
/
(
α
+
ω
), we have(34)
λ
I
-
M
α
,
ω
,
τ
=
0
ω
α
+
ω
A
-
1
B
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
-
ω
α
+
ω
I
n
+
2
τ
ω
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
B
=
0
ω
α
+
ω
A
-
1
B
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
-
ω
α
+
ω
I
n
=
-
2
τ
α
2
-
τ
α
+
ω
A
-
1
B
Q
-
1
B
T
0
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
-
ω
α
+
ω
I
n
=
-
2
τ
α
2
-
τ
α
+
ω
m
-
ω
α
+
ω
n
A
-
1
B
Q
-
1
B
T
.Notice that Q is symmetric positive definite and therefore rank
⁡
(
A
-
1
B
Q
-
1
B
T
)
=
rank
⁡
(
B
Q
-
1
B
T
)
=
rank
⁡
(
B
T
)
=
rank
⁡
(
B
)
<
n. As A
-
1
B
Q
-
1
B
T is an m
×
m (m
≥
n) matrix, we have A
-
1
B
Q
-
1
B
T
=
0, which implies that α
/
(
α
+
ω
) is an eigenvalue of M
α
,
ω
,
τ. If λ
≠
α
/
(
α
+
ω
), after some elementary transformation of matrix, the following holds:(35)
λ
I
-
M
α
,
ω
,
τ
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
=
λ
-
α
α
+
ω
m
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
.Suppose that rank
⁡
(
B
)
=
n
-
k
(
k
>
0
). Notice that A and Q are symmetric and positive definite, so rank
⁡
(
Q
-
1
B
T
A
-
1
B
)
=
rank
⁡
(
B
T
A
-
1
B
)
=
rank
⁡
(
B
). Then, Q
-
1
B
T
A
-
1
B has at least k eigenvalues 0, and we denote them by μ
n
-
k
+
1
=
μ
n
-
k
+
2
=
⋯
=
μ
n
=
0. Let V
∈
R
n
×
n be an orthogonal matrix such that V
T
Q
-
1
B
T
A
-
1
B
V
=
R, where R is an upper triangular matrix, whose diagonal elements are composed of the eigenvalues of Q
-
1
B
T
A
-
1
B. Then, we have(36)
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
=
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
=
V
T
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
V
=
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
R
=
∏
i
=
1
n
λ
-
1
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
μ
i
=
λ
-
1
k
∏
i
=
1
n
-
k
λ
-
1
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
μ
i
;that is,(37)
λ
I
-
M
α
,
ω
,
τ
=
λ
-
α
α
+
ω
m
λ
-
1
k
∏
i
=
1
n
-
k
λ
-
1
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
μ
i
.Thus, M
α
,
ω
,
τ has at least k eigenvalues 1 and m eigenvalues α
/
(
α
+
ω
). After some calculations, we obtain (21) by λ
-
1
+
2
τ
ω
λ
/
[
(
α
+
ω
)
λ
-
α
]
(
2
-
τ
)
μ
i
=
0, which means that the remainder eigenvalues of M
α
,
ω
,
τ are the roots of (21). This proof is completed.Lemma 9 (see [33]).
i
n
d
e
x
(
I
-
Ω
-
1
(
D
-
Ω
L
)
)
=
1 holds if and only if, for any 0
≠
Y
∈
R
(
A
), Y
∉
N
(
A
(
D
-
Ω
L
)
-
1
Ω
).Lemma 10.
LetA and Q be symmetric positive definite, let B be rank deficient, and ω
≠
0 and τ
≠
2. Then, i
n
d
e
x
(
I
-
M
α
,
ω
,
τ
)
=
1.Proof.
LetX
=
(
x
T
,
y
T
)
T, where x
∈
R
m and y
∈
R
n such that(38)
Y
=
A
X
=
A
B
-
B
T
0
x
y
=
A
x
+
B
y
-
B
T
x
≠
0
.To prove i
n
d
e
x
(
I
-
M
α
,
ω
,
τ
)
=
1, it is sufficient to prove A
M
1
-
1
Y
≠
0 by Lemma 9, where M
1
-
1
=
(
D
-
Ω
L
)
-
1
Ω. Now we give the proof for A
M
1
-
1
Y
≠
0 by contradiction. Suppose A
M
1
-
1
Y
=
0. Let U
=
(
u
T
,
v
T
)
T satisfy A
U
=
0, where u
∈
R
m and v
∈
R
n. Then,(39)
A
U
=
A
B
-
B
T
0
u
v
=
0
0
.So we can get A
u
+
B
v
=
0 and -
B
T
u
=
0. From A
u
+
B
v
=
0, we obtain u
=
-
A
-
1
B
v, and B
T
A
-
1
B
v
=
0. Since A is positive definite and so is A
-
1, which results in B
v
=
0, thus u
=
0. Hence,(40)
N
A
=
s
p
a
n
0
φ
,
w
h
e
r
e
B
φ
=
0
.Then, there exists a vector φ
0 such that(41)
M
1
-
1
Y
=
0
φ
0
,
B
φ
0
=
0
,which yields that(42)
Y
=
M
1
0
φ
0
=
α
+
ω
ω
A
0
-
B
T
2
-
τ
2
τ
Q
0
φ
0
=
0
2
-
τ
2
τ
Q
φ
0
.Making use of (38) and (42), we have B
φ
0
=
-
2
τ
/
(
2
-
τ
)
B
Q
-
1
B
T
x
=
0. Notice that Q is positive definite, so is Q
-
1; then B
T
x
=
0, which implies that φ
0
=
-
2
τ
/
(
2
-
τ
)
Q
-
1
B
T
x
=
0. Hence,(43)
Y
=
M
1
0
φ
0
=
0
,which is a contradiction to Y
≠
0. Thus, A
M
1
-
1
Y
≠
0. This proof is completed.By Lemma10, we have proved that i
n
d
e
x
(
I
-
M
α
,
ω
,
τ
)
=
1, which satisfies the condition (1) in Lemma 7. Next, we need to prove the condition (2) in Lemma 7.By Theorem8, we see that the eigenvalues of M
α
,
ω
,
τ are 1, α
/
(
α
+
ω
) and the remainder eigenvalues are the roots of the quadratic equation (21). By Definition 6 and Lemma 7, we need to consider the eigenvalues of M
α
,
ω
,
τ except 1.Lemma 11.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, V
(
M
α
,
ω
,
τ
)
<
1 for all α, ω, and τ such that(44)
ω
τ
μ
m
a
x
2
-
τ
<
2
α
+
ω
,
ω
>
0
,
α
>
0
,
0
<
τ
<
2
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Proof.
Combining Lemma2 and (21), we know that V
(
M
α
,
ω
,
τ
)
<
1 if and only if(45)
α
α
+
ω
<
1
,
2
α
+
ω
α
+
ω
-
2
τ
ω
μ
α
+
ω
2
-
τ
<
α
α
+
ω
+
1
.Using the same technique as the proof of Theorem 3, the conditions (44) are obtained. This completes our proof of Lemma 11.Based on Definition6 and Lemmas 10 and 11, we can establish the sufficient conditions of the semiconvergence for the GASOR method.Theorem 12.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, the GASOR method is semiconvergent for all α, ω, and τ such that(46)
ω
τ
μ
m
a
x
2
-
τ
<
2
α
+
ω
,
ω
>
0
,
α
>
0
,
0
<
τ
<
2
,where μ
m
a
x is the maximum nonzero eigenvalue of Q
-
1
B
T
A
-
1
B.


## 2.1. The Generalized ASOR Method

In this section, we propose the generalized ASOR (GASOR) method for solving the saddle point problem (1). The GASOR method with appropriate parameters has the faster convergence rate than those of SOR-like [8], GSOR [5], MSOR-like [9], and ASOR [35] methods with optimal or experimentally found optimal parameters for nonsingular saddle point problems. For the coefficient matrix of the augmented system (1), we make the splitting of A as in (2).Letω and τ be two nonzero reals, let I
m
∈
R
m
×
m and I
n
∈
R
n
×
n be the m-by-m and the n-by-n identity matrices, respectively, and(6)
Ω
=
ω
I
m
0
0
τ
I
n
.Then, we consider the following generalized ASOR iteration scheme for solving the saddle point problem (1):(7)
x
k
+
1
y
k
+
1
=
M
α
,
ω
,
τ
x
k
y
k
+
D
-
Ω
L
-
1
Ω
p
-
q
,where M
α
,
ω
,
τ is the iteration matrix of the GASOR method and its form as follows:(8)
M
α
,
ω
,
τ
=
D
-
Ω
L
-
1
I
-
Ω
D
+
Ω
U
=
α
+
ω
A
0
-
τ
B
T
2
-
τ
2
Q
-
1
α
A
-
ω
B
0
2
-
τ
2
Q
=
1
α
+
ω
A
-
1
0
2
τ
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
2
2
-
τ
Q
-
1
α
A
-
ω
B
0
2
-
τ
2
Q
=
α
α
+
ω
I
m
-
ω
α
+
ω
A
-
1
B
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
I
n
-
2
τ
ω
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
B
.Then, we have the following algorithmic description of the GASOR method.The GASOR Method. Given initial vectors x
(
0
)
∈
R
m and y
(
0
)
∈
R
n and three real relaxation factors α
>
0 and ω
,
τ
≠
0, for k
=
0,1
,
2
,
…, until the iteration sequence {
(
x
(
k
)
T
)
,
(
y
(
k
)
T
)
} converges to the exact solution of the saddle point problem (1), compute(9)
x
k
+
1
=
α
α
+
ω
x
k
-
ω
α
+
ω
A
-
1
B
y
k
-
p
,
y
k
+
1
=
y
k
+
2
τ
2
-
τ
Q
-
1
B
T
x
k
+
1
-
q
.Note that the GASOR method involves three parametersα, ω, and τ. Since(10)
D
-
Ω
L
=
α
+
ω
A
0
-
τ
B
T
2
-
τ
2
Q
,then the matrix (
D
-
Ω
L
) is invertible if and only if(11)
α
+
ω
≠
0
,
τ
≠
2
,by the definiteness of A and Q.Note that the GASOR method withτ
=
ω reduces to the ASOR method proposed by Njeru and Guo [35].


## 2.2. Convergence of the GASOR Method

Lemma 1.
Suppose thatμ is an eigenvalue of matrix Q
-
1
B
T
A
-
1
B, if λ satisfies(12)
λ
-
1
2
-
τ
α
-
α
λ
-
λ
ω
=
2
λ
τ
ω
μ
,and then λ is an eigenvalue of iteration matrix M
α
,
ω
,
τ. Conversely, if λ is an eigenvalue of M
α
,
ω
,
τ such that λ
≠
1, τ
≠
2, λ
≠
α
/
(
α
+
ω
), and μ satisfy (12), then μ is a nonzero eigenvalue of matrix Q
-
1
B
T
A
-
1
B.Proof.
Letλ be an eigenvalue of M
α
,
ω
,
τ and let (
x
T
,
y
T
)
T be the corresponding eigenvector. Then we have(13)
M
α
,
ω
,
τ
x
y
=
λ
x
y
.Equation (13) can be written as(14)
α
A
-
ω
B
0
1
-
τ
2
Q
x
y
=
λ
α
+
ω
A
0
-
τ
B
T
1
-
τ
2
Q
x
y
,which is equivalent to(15)
α
-
α
λ
-
λ
ω
A
x
=
ω
B
y
,
(16)
λ
-
1
2
-
τ
2
Q
y
=
λ
τ
B
T
x
.Inasmuch as α
-
α
λ
-
λ
ω
≠
0, we obtain(17)
x
=
ω
α
-
α
λ
-
λ
ω
A
-
1
B
yfrom (15). Substituting (17) into (16), we have(18)
λ
-
1
2
-
τ
2
y
=
λ
τ
ω
α
-
α
λ
-
λ
ω
Q
-
1
B
T
A
-
1
B
yby the definiteness of Q.
Ifμ satisfies (12), then we have(19)
Q
-
1
B
T
A
-
1
B
y
=
μ
y
.If y
=
0, then from (17) this leads to x
=
0, which is a contradiction that (
x
T
,
y
T
)
T is an eigenvector. Thus, y
≠
0, and therefore μ is an eigenvalue of Q
-
1
B
T
A
-
1
B. Furthermore, let λ
=
1; from (15) and (16), we have α
A
x
-
ω
B
y
=
(
α
+
ω
)
A
x and τ
B
T
x
=
0. Thus, x
=
-
A
-
1
B
y by ω
≠
0 and the definiteness of A, which yields that B
T
A
-
1
B
y
=
0. However A is positive definite, so is A
-
1, which implies that B
y
=
0 and then x
=
-
A
-
1
B
y
=
0 and y
=
0 by B which is full column rank. This contradicts the assumption that (
x
T
,
y
T
)
T is an eigenvector as well. Therefore, combining (12) and the assumptions τ
≠
2, λ
≠
α
/
(
α
+
ω
) results in μ
≠
0; that is, μ is a nonzero eigenvalue of the matrix Q
-
1
B
T
A
-
1
B.
We can prove the second assertion by reversing the process.One may easily show that for the special caseτ
=
ω the GASOR method reduces to the ASOR method derived in [35].Lemma 2 (see [36]).
Both roots of the real quadratic equationx
2
-
b
x
+
c
=
0 are less than one in modulus if and only if|
c
|
<
1 and |
b
|
<
1
+
c.Theorem 3.
LetA and Q be symmetric positive definite, and let B be full column rank. Assume that all eigenvalues μ of Q
-
1
B
T
A
-
1
B are real and positive. Then, the GASOR method is convergent for all α, ω, and τ such that(20)
ω
τ
μ
m
a
x
2
-
τ
<
2
α
+
ω
,
ω
>
0
,
α
>
0
,
0
<
τ
<
2
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Proof.
After some manipulations on Lemma1, we have(21)
α
+
ω
τ
-
2
λ
2
+
ω
+
2
α
2
-
τ
-
2
τ
ω
μ
λ
+
α
τ
-
2
=
0
.Changing the above equation into x
2
-
b
x
+
c
=
0, we find(22)
λ
2
+
2
τ
ω
μ
α
+
ω
2
-
τ
-
2
α
+
ω
α
+
ω
λ
+
α
α
+
ω
=
0
,where(23)
b
=
2
α
+
ω
α
+
ω
-
2
τ
ω
μ
α
+
ω
2
-
τ
,
c
=
α
α
+
ω
.By Lemma 2, |
λ
|
<
1 if and only if(24)
α
α
+
ω
<
1
,
(25)
2
α
+
ω
α
+
ω
-
2
τ
ω
μ
α
+
ω
2
-
τ
<
α
α
+
ω
+
1
.It follows from (24) that(26)
ω
>
0
,
-
2
α
<
ω
.It is obvious that (26) holds true by α
>
0 and ω
>
0. From (25), we get(27)
0
<
ω
τ
μ
2
-
τ
<
2
α
+
ω
.Since ω
>
0, τ
>
0, and μ is an real and positive eigenvalue of matrix Q
-
1
B
T
A
-
1
B, we have(28)
0
<
τ
<
2
,
ω
τ
μ
2
-
τ
<
2
α
+
ω
.However,(29)
ω
τ
μ
2
-
τ
≤
ω
τ
μ
m
a
x
2
-
τ
.We obtain that if the conditions (20) are satisfied, the GASOR method is convergent.From (21), we get the following corollary.Corollary 4.
LetA and Q be symmetric positive definite, let and B be full column rank. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
ω
,
τ are given by λ
=
α
/
(
α
+
ω
) or(30)
λ
=
1
2
2
α
+
ω
α
+
ω
-
2
ω
τ
μ
2
-
τ
α
+
ω
±
2
ω
τ
μ
2
-
τ
α
+
ω
-
2
α
+
ω
α
+
ω
2
-
4
α
α
+
ω
.


## 2.3. Semiconvergence of the GASOR Method for Singular Saddle Point Problems

For singular saddle point problems, in [37], Wang and Zhang studied the accelerated HSS (AHSS) method first put forward by Bai and Golub in [20] for solving singular saddle point problems; Yang and Wu [38] proposed the Uzawa-HSS method and applied it for singular saddle point problems [39]. Recently, Miao and Cao [40] studied the semiconvergence of the generalized local HSS method established by Zhu [41] for singular saddle point problems; Zhou and Zhang [42] discussed the semiconvergence of the GMSSOR method which derived by Zhang et al. in [43] for singular saddle point problems. In the sequel, Chen and Ma [44] presented a generalized shift-splitting preconditioner and investigated this preconditioner for singular saddle point problems [45]. For more literatures on this theme, one can refer to [46, 47] and references therein.In this section, by using the idea of [42], we assume that B in (1) is rank deficient; that is, r
a
n
k
(
B
)
<
n; that is, A in (1) is singular. In addition, we will discuss the semiconvergence region for parameters α, ω, and τ in the GASOR method for solving the singular saddle point problem (1). The GASOR method has a faster convergence rate than the ones of the GSSOR [48], MSSOR [49], and GMSSOR [42, 43] methods for singular saddle point problems when optimal or experimentally found optimal parameters are chosen for them.We first recollect some needed known results about stationary iterative methods for singular linear systems. We denote the range and the null space of the matrixA by R
(
A
) and N
(
A
), respectively. The smallest nonnegative integer i such that rank
⁡
(
A
i
)
=
r
a
n
k
(
A
i
+
1
) is called the index of A and is denoted by i
=
i
n
d
e
x
(
A
). For a matrix A
∈
C
m
×
m, the splitting A
=
M
-
N is a nonsingular splitting if M is nonsingular. Let T
=
M
-
1
N and c
=
M
-
1
b, then solving linear systems A
x
=
b is equivalent to considering the following iterative scheme:(31)
x
k
+
1
=
T
x
k
+
c
.When A is singular, the semiconvergence about the iteration scheme (31) is precisely described in [50, 51].Definition 5 (see [51]).
For any initial vectorz
(
0
), the iteration scheme (31) is semiconvergence to a solution z
∗ of A
x
=
b if and only if the iteration matrix T is semiconvergent. Moreover, it holds that z
∗
=
(
I
-
T
)
D
c
+
[
I
-
(
I
-
T
)
(
I
-
T
)
D
]
z
(
0
), where I is the identity matrix with appropriate size and (
I
-
T
)
D denotes the Drazin inverse of I
-
T.Definition 6 (see [42]).
The pseudospectral radius of matrixT is defined as(32)
V
T
=
max
⁡
λ
∣
λ
∈
σ
T
∖
1
,where σ
(
T
) stands for the spectrum of matrix T.Lemma 7 (see [52]).
The iteration (31) is semiconvergent, if and only if the following conditions hold:(1)
i
n
d
e
x
(
I
-
T
)
=
1.
(2)
V
(
T
)
<
1.Theorem 8.
LetA and Q be symmetric positive definite, and let B be rank deficient. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
ω
,
τ are 1, λ
=
α
/
(
α
+
ω
), and the remainder eigenvalues are the roots of the quadratic equation (21).Proof.
In order to seek for the eigenvalues ofM
α
,
ω
,
τ, we need to solve d
e
t
(
λ
I
-
M
α
,
ω
,
τ
)
=
0:(33)
λ
I
-
M
α
,
ω
,
τ
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
λ
-
1
I
n
+
2
τ
ω
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
B
.If λ
=
α
/
(
α
+
ω
), we have(34)
λ
I
-
M
α
,
ω
,
τ
=
0
ω
α
+
ω
A
-
1
B
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
-
ω
α
+
ω
I
n
+
2
τ
ω
2
-
τ
α
+
ω
Q
-
1
B
T
A
-
1
B
=
0
ω
α
+
ω
A
-
1
B
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
-
ω
α
+
ω
I
n
=
-
2
τ
α
2
-
τ
α
+
ω
A
-
1
B
Q
-
1
B
T
0
-
2
τ
α
2
-
τ
α
+
ω
Q
-
1
B
T
-
ω
α
+
ω
I
n
=
-
2
τ
α
2
-
τ
α
+
ω
m
-
ω
α
+
ω
n
A
-
1
B
Q
-
1
B
T
.Notice that Q is symmetric positive definite and therefore rank
⁡
(
A
-
1
B
Q
-
1
B
T
)
=
rank
⁡
(
B
Q
-
1
B
T
)
=
rank
⁡
(
B
T
)
=
rank
⁡
(
B
)
<
n. As A
-
1
B
Q
-
1
B
T is an m
×
m (m
≥
n) matrix, we have A
-
1
B
Q
-
1
B
T
=
0, which implies that α
/
(
α
+
ω
) is an eigenvalue of M
α
,
ω
,
τ. If λ
≠
α
/
(
α
+
ω
), after some elementary transformation of matrix, the following holds:(35)
λ
I
-
M
α
,
ω
,
τ
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
=
λ
-
α
α
+
ω
m
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
.Suppose that rank
⁡
(
B
)
=
n
-
k
(
k
>
0
). Notice that A and Q are symmetric and positive definite, so rank
⁡
(
Q
-
1
B
T
A
-
1
B
)
=
rank
⁡
(
B
T
A
-
1
B
)
=
rank
⁡
(
B
). Then, Q
-
1
B
T
A
-
1
B has at least k eigenvalues 0, and we denote them by μ
n
-
k
+
1
=
μ
n
-
k
+
2
=
⋯
=
μ
n
=
0. Let V
∈
R
n
×
n be an orthogonal matrix such that V
T
Q
-
1
B
T
A
-
1
B
V
=
R, where R is an upper triangular matrix, whose diagonal elements are composed of the eigenvalues of Q
-
1
B
T
A
-
1
B. Then, we have(36)
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
=
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
=
V
T
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
Q
-
1
B
T
A
-
1
B
V
=
λ
-
1
I
n
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
R
=
∏
i
=
1
n
λ
-
1
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
μ
i
=
λ
-
1
k
∏
i
=
1
n
-
k
λ
-
1
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
μ
i
;that is,(37)
λ
I
-
M
α
,
ω
,
τ
=
λ
-
α
α
+
ω
m
λ
-
1
k
∏
i
=
1
n
-
k
λ
-
1
+
2
τ
ω
λ
α
+
ω
λ
-
α
2
-
τ
μ
i
.Thus, M
α
,
ω
,
τ has at least k eigenvalues 1 and m eigenvalues α
/
(
α
+
ω
). After some calculations, we obtain (21) by λ
-
1
+
2
τ
ω
λ
/
[
(
α
+
ω
)
λ
-
α
]
(
2
-
τ
)
μ
i
=
0, which means that the remainder eigenvalues of M
α
,
ω
,
τ are the roots of (21). This proof is completed.Lemma 9 (see [33]).
i
n
d
e
x
(
I
-
Ω
-
1
(
D
-
Ω
L
)
)
=
1 holds if and only if, for any 0
≠
Y
∈
R
(
A
), Y
∉
N
(
A
(
D
-
Ω
L
)
-
1
Ω
).Lemma 10.
LetA and Q be symmetric positive definite, let B be rank deficient, and ω
≠
0 and τ
≠
2. Then, i
n
d
e
x
(
I
-
M
α
,
ω
,
τ
)
=
1.Proof.
LetX
=
(
x
T
,
y
T
)
T, where x
∈
R
m and y
∈
R
n such that(38)
Y
=
A
X
=
A
B
-
B
T
0
x
y
=
A
x
+
B
y
-
B
T
x
≠
0
.To prove i
n
d
e
x
(
I
-
M
α
,
ω
,
τ
)
=
1, it is sufficient to prove A
M
1
-
1
Y
≠
0 by Lemma 9, where M
1
-
1
=
(
D
-
Ω
L
)
-
1
Ω. Now we give the proof for A
M
1
-
1
Y
≠
0 by contradiction. Suppose A
M
1
-
1
Y
=
0. Let U
=
(
u
T
,
v
T
)
T satisfy A
U
=
0, where u
∈
R
m and v
∈
R
n. Then,(39)
A
U
=
A
B
-
B
T
0
u
v
=
0
0
.So we can get A
u
+
B
v
=
0 and -
B
T
u
=
0. From A
u
+
B
v
=
0, we obtain u
=
-
A
-
1
B
v, and B
T
A
-
1
B
v
=
0. Since A is positive definite and so is A
-
1, which results in B
v
=
0, thus u
=
0. Hence,(40)
N
A
=
s
p
a
n
0
φ
,
w
h
e
r
e
B
φ
=
0
.Then, there exists a vector φ
0 such that(41)
M
1
-
1
Y
=
0
φ
0
,
B
φ
0
=
0
,which yields that(42)
Y
=
M
1
0
φ
0
=
α
+
ω
ω
A
0
-
B
T
2
-
τ
2
τ
Q
0
φ
0
=
0
2
-
τ
2
τ
Q
φ
0
.Making use of (38) and (42), we have B
φ
0
=
-
2
τ
/
(
2
-
τ
)
B
Q
-
1
B
T
x
=
0. Notice that Q is positive definite, so is Q
-
1; then B
T
x
=
0, which implies that φ
0
=
-
2
τ
/
(
2
-
τ
)
Q
-
1
B
T
x
=
0. Hence,(43)
Y
=
M
1
0
φ
0
=
0
,which is a contradiction to Y
≠
0. Thus, A
M
1
-
1
Y
≠
0. This proof is completed.By Lemma10, we have proved that i
n
d
e
x
(
I
-
M
α
,
ω
,
τ
)
=
1, which satisfies the condition (1) in Lemma 7. Next, we need to prove the condition (2) in Lemma 7.By Theorem8, we see that the eigenvalues of M
α
,
ω
,
τ are 1, α
/
(
α
+
ω
) and the remainder eigenvalues are the roots of the quadratic equation (21). By Definition 6 and Lemma 7, we need to consider the eigenvalues of M
α
,
ω
,
τ except 1.Lemma 11.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, V
(
M
α
,
ω
,
τ
)
<
1 for all α, ω, and τ such that(44)
ω
τ
μ
m
a
x
2
-
τ
<
2
α
+
ω
,
ω
>
0
,
α
>
0
,
0
<
τ
<
2
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Proof.
Combining Lemma2 and (21), we know that V
(
M
α
,
ω
,
τ
)
<
1 if and only if(45)
α
α
+
ω
<
1
,
2
α
+
ω
α
+
ω
-
2
τ
ω
μ
α
+
ω
2
-
τ
<
α
α
+
ω
+
1
.Using the same technique as the proof of Theorem 3, the conditions (44) are obtained. This completes our proof of Lemma 11.Based on Definition6 and Lemmas 10 and 11, we can establish the sufficient conditions of the semiconvergence for the GASOR method.Theorem 12.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, the GASOR method is semiconvergent for all α, ω, and τ such that(46)
ω
τ
μ
m
a
x
2
-
τ
<
2
α
+
ω
,
ω
>
0
,
α
>
0
,
0
<
τ
<
2
,where μ
m
a
x is the maximum nonzero eigenvalue of Q
-
1
B
T
A
-
1
B.


## 3. The Modified ASOR Method for Saddle Point Problems

### 3.1. The Modified ASOR Method

To obtain the new iteration methods for saddle point problems, some authors added new parameters in the existing methods and got the better methods [11, 20, 53]. Based on the preconditioned HSS (PHSS) method derived by Bai et al. [2], Bai and Golub [20] and Li et al. [53] by using this method obtained the AHSS and parameterized preconditioned HSS (PPHSS) methods, respectively. This idea motivates us to propose the modified ASOR (MASOR) method for solving the saddle point problem (1) by making another splitting for the coefficient matrix of the saddle point problem (1) as follows:(47)
A
=
D
-
L
-
U
,where (48)
D
=
α
A
0
0
Q
,
L
=
-
A
0
B
T
β
Q
,
U
=
α
A
-
B
0
1
-
β
Q
,with α
>
0 and Q
∈
R
n
×
n is a symmetric positive definite matrix. Let ω be nonzero real and let β be real. Then, we consider the following modified ASOR iteration scheme for solving the saddle point problem (1):(49)
x
k
+
1
y
k
+
1
=
M
α
,
β
,
ω
x
k
y
k
+
ω
D
-
ω
L
-
1
p
-
q
,where M
α
,
β
,
ω is the iteration matrix of the MASOR method and its form as follows:(50)
M
α
,
β
,
ω
=
D
-
ω
L
-
1
1
-
ω
D
+
ω
U
=
α
+
ω
A
0
-
ω
B
T
1
-
ω
β
Q
-
1
α
A
-
ω
B
0
1
-
ω
β
Q
=
1
α
+
ω
A
-
1
0
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
1
1
-
ω
β
Q
-
1
α
A
-
ω
B
0
1
-
ω
β
Q
=
α
α
+
ω
I
m
-
ω
α
+
ω
A
-
1
B
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
I
n
-
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
.Then, the algorithmic description of the MASOR method is as follows.The MASOR Method. Given initial vectors x
(
0
)
∈
R
m and y
(
0
)
∈
R
n and three real relaxation factors α
>
0, ω
≠
0, and β is a real number, for k
=
0,1
,
2
,
…, until the iteration sequence {
(
x
(
k
)
T
)
,
(
y
(
k
)
T
)
} converges to the exact solution of the saddle point problem (1), compute(51)
x
k
+
1
=
α
α
+
ω
x
k
-
ω
α
+
ω
A
-
1
B
y
k
-
p
,
y
k
+
1
=
y
k
+
ω
1
-
ω
β
Q
-
1
B
T
x
k
+
1
-
q
.Note that the MASOR method involves three parametersα, ω, and β. Since(52)
D
-
ω
L
=
α
+
ω
A
0
-
ω
B
T
1
-
ω
β
Q
,then the matrix (
D
-
ω
L
) is invertible if and only if(53)
α
+
ω
≠
0
,
ω
β
≠
1
,by the definiteness of A and Q.Note that the MASOR method withβ
=
1
/
2 reduces to the ASOR method proposed by Njeru and Guo [35].


### 3.2. Convergence of the MASOR Method

Lemma 13.
Suppose thatμ is an eigenvalue of matrix Q
-
1
B
T
A
-
1
B, if λ satisfies(54)
λ
-
1
1
-
ω
β
α
-
α
λ
-
λ
ω
=
λ
ω
2
μ
,and then λ is an eigenvalue of iteration matrix M
α
,
β
,
ω. Conversely, if λ is an eigenvalue of M
α
,
β
,
ω such that λ
≠
1, ω
β
≠
1, λ
≠
α
/
(
α
+
ω
), and μ satisfy (54), then μ is a nonzero eigenvalue of matrix Q
-
1
B
T
A
-
1
B.Proof.
SinceQ
-
1
B
T
A
-
1
B is nonsingular, μ
≠
0. If λ
=
0 in (54), we obtain 0
≠
-
α
(
1
-
ω
β
)
=
0
=
λ
ω
2
μ, which is a contradiction. Thus, λ
≠
0. In a similar manner, we can prove that λ
≠
α
/
(
α
+
ω
) and λ
≠
1.
We assume thaty is the eigenvector corresponding to μ; thus, y
≠
0. Then by (54), the following holds:(55)
λ
-
1
1
-
ω
β
α
-
α
λ
-
λ
ω
λ
ω
2
y
=
μ
y
,which yields that(56)
λ
-
1
1
-
ω
β
y
=
λ
ω
2
α
-
α
λ
-
λ
ω
Q
-
1
B
T
A
-
1
B
y
.Let x
=
ω
/
(
α
-
α
λ
-
λ
ω
)
A
-
1
B
y; we can deduce that(57)
α
-
α
λ
-
λ
ω
A
x
=
ω
B
y
,and, by setting x into (56), we have(58)
λ
-
1
1
-
ω
β
Q
y
=
λ
ω
B
T
x
.Combining (57) and (58) results in(59)
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
α
x
-
ω
A
-
1
B
y
=
λ
-
1
y
.We rewrite (57) and (59) as follows:(60)
α
α
+
ω
x
-
ω
α
+
ω
A
-
1
B
y
=
λ
x
,
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
x
+
y
-
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
y
=
λ
ywhich is equivalent to(61)
α
α
+
ω
I
m
-
ω
α
+
ω
A
-
1
B
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
I
n
-
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
x
y
=
λ
x
y
.This implies that M
α
,
β
,
ω
x
=
λ
x, where x
=
(
x
T
,
y
T
)
T
≠
0, which means that λ is an eigenvalue of M
α
,
β
,
ω. We can prove the second assertion by revising the process.Theorem 14.
LetA and Q be symmetric positive definite, and let B be full column rank. Assume that all eigenvalues μ of Q
-
1
B
T
A
-
1
B are real and positive. Then, the MASOR method is convergent for all α, ω, and τ such that(62)
ω
2
μ
m
a
x
1
-
ω
β
<
2
2
α
+
ω
,
ω
>
0
,
α
>
0
,
1
-
ω
β
>
0
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Proof.
Equation (54) can be equivalently written as(63)
λ
2
+
ω
2
μ
α
+
ω
1
-
ω
β
-
2
α
+
ω
α
+
ω
λ
+
α
α
+
ω
=
0
.Equation (63) can be expressed as x
2
-
b
x
+
c
=
0, where(64)
b
=
2
α
+
ω
α
+
ω
-
ω
2
μ
α
+
ω
1
-
ω
β
,
c
=
α
α
+
ω
.Applying Lemma 2 to the quadratic equation (63), we know that |
λ
|
<
1 if and only if(65)
α
α
+
ω
<
1
,
2
α
+
ω
α
+
ω
-
ω
2
μ
α
+
ω
1
-
ω
β
<
α
α
+
ω
+
1
.In terms of (65), we derive(66)
ω
>
0
,
-
2
α
<
ω
,
0
<
ω
2
μ
1
-
ω
β
<
2
2
α
+
ω
.Evidently, the first and the second inequalities in (66) hold true for all α
>
0 and ω
>
0. It follows from the third inequality in (66), ω
2
>
0, and μ which is a real and positive eigenvalue of the matrix Q
-
1
B
T
A
-
1
B that(67)
1
-
ω
β
>
0
,
ω
2
μ
1
-
ω
β
<
2
2
α
+
ω
.It is not difficult to verify that(68)
ω
2
μ
1
-
ω
β
≤
ω
2
μ
m
a
x
1
-
ω
β
.Therefore, the proof of this theorem is completed.From (63), we get the following corollary.Corollary 15.
LetA and Q be symmetric positive definite, and let B be be full rank. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
β
,
ω are given by λ
=
α
/
(
α
+
ω
) or(69)
λ
=
1
2
2
α
+
ω
α
+
ω
-
ω
2
μ
α
+
ω
1
-
ω
β
±
ω
2
μ
α
+
ω
1
-
ω
β
-
2
α
+
ω
α
+
ω
2
-
4
α
α
+
ω
.


### 3.3. Semiconvergence of the MASOR Method for Singular Saddle Point Problem

In this section, we assume thatB in (1) is rank deficient and we will discuss the semiconvergence region for parameters ω, α, and β in the MASOR method for solving the singular saddle point problem (1).Theorem 16.
LetA and Q be symmetric positive definite, and let B be rank deficient. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
β
,
ω are 1, λ
=
α
/
(
α
+
ω
), and the remainder eigenvalues are the roots of the quadratic equation (63).Proof.
By simple calculations, we have(70)
λ
I
-
M
α
,
β
,
ω
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
-
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
λ
-
1
I
n
+
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
.If λ
=
α
/
(
α
+
ω
), with the similar manner applied in the proof of Theorem 8, we can prove that |
λ
I
-
M
α
,
β
,
ω
|
=
0, which means that α
/
(
α
+
ω
) is an eigenvalue of M
α
,
β
,
ω. Otherwise, λ
≠
α
/
(
α
+
ω
), after suitable manipulations, gives (71)
λ
I
-
M
α
,
β
,
ω
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
Q
-
1
B
T
A
-
1
B
=
λ
-
α
α
+
ω
m
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
Q
-
1
B
T
A
-
1
B
=
λ
-
α
α
+
ω
m
λ
-
1
I
n
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
Q
-
1
B
T
A
-
1
B
.We assume that rank
⁡
(
B
)
=
n
-
k
(
k
>
0
) and, with a quite similar strategy utilized in Theorem 8, we deduce that (72)
λ
I
-
M
α
,
β
,
ω
=
λ
-
α
α
+
ω
m
∏
i
=
1
n
λ
-
1
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
μ
i
=
λ
-
α
α
+
ω
m
λ
-
1
k
∏
i
=
1
n
-
k
λ
-
1
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
μ
i
,where μ
i
(
i
=
1
,
…
,
n
-
k
) are the eigenvalues of Q
-
1
B
T
A
-
1
B, from which one can see that M
α
,
β
,
ω has at least k eigenvalues 1 and m eigenvalues α
/
(
α
+
ω
). It follows from λ
-
1
+
ω
2
λ
/
[
(
α
+
ω
)
λ
-
α
]
(
1
-
ω
β
)
μ
i
=
0 that (63) holds, which implies that the remainder eigenvalues of M
α
,
β
,
ω are the roots of (63). Thus, the theorem is proved.Lemma 17.
LetA and Q be symmetric positive definite, let B be rank deficient, and ω
≠
0 and ω
≠
1
/
β. Then, i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1.Proof.
We prove this theorem by Lemma9. Let X
=
(
x
T
,
y
T
)
T, with x
∈
R
m and y
∈
R
n such that(73)
Y
=
A
X
=
A
B
-
B
T
0
x
y
=
A
x
+
B
y
-
B
T
x
≠
0
.In order to prove i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1, it remains only to prove A
M
2
-
1
Y
≠
0, where M
2
-
1
=
ω
(
D
-
ω
L
)
-
1. Here and in the sequel, we prove A
M
2
-
1
Y
≠
0 by contradiction. We assume that A
M
2
-
1
Y
=
0. Let F
=
(
f
T
,
g
T
)
T, where f
∈
R
m, g
∈
R
n, and A
F
=
0. That is(74)
A
U
=
A
B
-
B
T
0
f
g
=
0
0
,which results in A
f
+
B
g
=
0 and -
B
T
f
=
0. From A
f
+
B
g
=
0, we deduce that f
=
-
A
-
1
B
g and B
T
A
-
1
B
g
=
0. From the fact that A is positive definite and so is A
-
1, which leads to B
g
=
0, thus f
=
0. Then, we infer that(75)
N
A
=
s
p
a
n
0
φ
,
w
h
e
r
e
B
φ
=
0
.Therefore, there is a vector φ
0 such that(76)
M
2
-
1
Y
=
0
φ
0
,
B
φ
0
=
0
.It follows from (76) that(77)
Y
=
M
2
0
φ
0
=
α
+
ω
ω
A
0
-
B
T
1
-
ω
β
ω
Q
0
φ
0
=
0
1
-
ω
β
ω
Q
φ
0
.Combining (73) with (77) gives B
φ
0
=
-
ω
/
(
1
-
ω
β
)
B
Q
-
1
B
T
x
=
0. Q
-
1 is positive definite as Q is positive definite, and thus B
T
x
=
0, which results in φ
0
=
-
ω
/
(
1
-
ω
β
)
Q
-
1
B
T
x
=
0. Then, Y
=
0 holds, which is in contradiction with (73). So A
M
2
-
1
Y
≠
0. From the above analysis and Lemma 9, it has i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1. This proves the theorem.By Lemma17, we have proved that i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1, which satisfies the condition (1) in Lemma 7. In the sequel, we need to prove condition (2) in Lemma 7.By Theorem16, we see that the eigenvalues of M
α
,
β
,
ω are 1, α
/
(
α
+
ω
) and the remainder eigenvalues are the roots of the quadratic equation (63). By Definition 6 and Lemma 7, we only consider the eigenvalues of M
α
,
β
,
ω except 1.Lemma 18.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, V
(
M
α
,
β
,
ω
)
<
1 for all α, β, and ω such that(78)
ω
2
μ
m
a
x
1
-
ω
β
<
2
2
α
+
ω
,
ω
>
0
,
α
>
0
,
1
-
ω
β
>
0
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Together with Definition6 and Lemmas 17 and 18, we get the following sufficient conditions for the semiconvergence of the MASOR method.Theorem 19.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, the MASOR method is semiconvergent for all α, β, and ω such that(79)
ω
2
μ
m
a
x
1
-
ω
β
<
2
2
α
+
ω
,
ω
>
0
,
α
>
0
,
1
-
ω
β
>
0
,where μ
m
a
x is the maximum nonzero eigenvalue of Q
-
1
B
T
A
-
1
B.


## 3.1. The Modified ASOR Method

To obtain the new iteration methods for saddle point problems, some authors added new parameters in the existing methods and got the better methods [11, 20, 53]. Based on the preconditioned HSS (PHSS) method derived by Bai et al. [2], Bai and Golub [20] and Li et al. [53] by using this method obtained the AHSS and parameterized preconditioned HSS (PPHSS) methods, respectively. This idea motivates us to propose the modified ASOR (MASOR) method for solving the saddle point problem (1) by making another splitting for the coefficient matrix of the saddle point problem (1) as follows:(47)
A
=
D
-
L
-
U
,where (48)
D
=
α
A
0
0
Q
,
L
=
-
A
0
B
T
β
Q
,
U
=
α
A
-
B
0
1
-
β
Q
,with α
>
0 and Q
∈
R
n
×
n is a symmetric positive definite matrix. Let ω be nonzero real and let β be real. Then, we consider the following modified ASOR iteration scheme for solving the saddle point problem (1):(49)
x
k
+
1
y
k
+
1
=
M
α
,
β
,
ω
x
k
y
k
+
ω
D
-
ω
L
-
1
p
-
q
,where M
α
,
β
,
ω is the iteration matrix of the MASOR method and its form as follows:(50)
M
α
,
β
,
ω
=
D
-
ω
L
-
1
1
-
ω
D
+
ω
U
=
α
+
ω
A
0
-
ω
B
T
1
-
ω
β
Q
-
1
α
A
-
ω
B
0
1
-
ω
β
Q
=
1
α
+
ω
A
-
1
0
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
1
1
-
ω
β
Q
-
1
α
A
-
ω
B
0
1
-
ω
β
Q
=
α
α
+
ω
I
m
-
ω
α
+
ω
A
-
1
B
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
I
n
-
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
.Then, the algorithmic description of the MASOR method is as follows.The MASOR Method. Given initial vectors x
(
0
)
∈
R
m and y
(
0
)
∈
R
n and three real relaxation factors α
>
0, ω
≠
0, and β is a real number, for k
=
0,1
,
2
,
…, until the iteration sequence {
(
x
(
k
)
T
)
,
(
y
(
k
)
T
)
} converges to the exact solution of the saddle point problem (1), compute(51)
x
k
+
1
=
α
α
+
ω
x
k
-
ω
α
+
ω
A
-
1
B
y
k
-
p
,
y
k
+
1
=
y
k
+
ω
1
-
ω
β
Q
-
1
B
T
x
k
+
1
-
q
.Note that the MASOR method involves three parametersα, ω, and β. Since(52)
D
-
ω
L
=
α
+
ω
A
0
-
ω
B
T
1
-
ω
β
Q
,then the matrix (
D
-
ω
L
) is invertible if and only if(53)
α
+
ω
≠
0
,
ω
β
≠
1
,by the definiteness of A and Q.Note that the MASOR method withβ
=
1
/
2 reduces to the ASOR method proposed by Njeru and Guo [35].


## 3.2. Convergence of the MASOR Method

Lemma 13.
Suppose thatμ is an eigenvalue of matrix Q
-
1
B
T
A
-
1
B, if λ satisfies(54)
λ
-
1
1
-
ω
β
α
-
α
λ
-
λ
ω
=
λ
ω
2
μ
,and then λ is an eigenvalue of iteration matrix M
α
,
β
,
ω. Conversely, if λ is an eigenvalue of M
α
,
β
,
ω such that λ
≠
1, ω
β
≠
1, λ
≠
α
/
(
α
+
ω
), and μ satisfy (54), then μ is a nonzero eigenvalue of matrix Q
-
1
B
T
A
-
1
B.Proof.
SinceQ
-
1
B
T
A
-
1
B is nonsingular, μ
≠
0. If λ
=
0 in (54), we obtain 0
≠
-
α
(
1
-
ω
β
)
=
0
=
λ
ω
2
μ, which is a contradiction. Thus, λ
≠
0. In a similar manner, we can prove that λ
≠
α
/
(
α
+
ω
) and λ
≠
1.
We assume thaty is the eigenvector corresponding to μ; thus, y
≠
0. Then by (54), the following holds:(55)
λ
-
1
1
-
ω
β
α
-
α
λ
-
λ
ω
λ
ω
2
y
=
μ
y
,which yields that(56)
λ
-
1
1
-
ω
β
y
=
λ
ω
2
α
-
α
λ
-
λ
ω
Q
-
1
B
T
A
-
1
B
y
.Let x
=
ω
/
(
α
-
α
λ
-
λ
ω
)
A
-
1
B
y; we can deduce that(57)
α
-
α
λ
-
λ
ω
A
x
=
ω
B
y
,and, by setting x into (56), we have(58)
λ
-
1
1
-
ω
β
Q
y
=
λ
ω
B
T
x
.Combining (57) and (58) results in(59)
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
α
x
-
ω
A
-
1
B
y
=
λ
-
1
y
.We rewrite (57) and (59) as follows:(60)
α
α
+
ω
x
-
ω
α
+
ω
A
-
1
B
y
=
λ
x
,
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
x
+
y
-
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
y
=
λ
ywhich is equivalent to(61)
α
α
+
ω
I
m
-
ω
α
+
ω
A
-
1
B
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
I
n
-
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
x
y
=
λ
x
y
.This implies that M
α
,
β
,
ω
x
=
λ
x, where x
=
(
x
T
,
y
T
)
T
≠
0, which means that λ is an eigenvalue of M
α
,
β
,
ω. We can prove the second assertion by revising the process.Theorem 14.
LetA and Q be symmetric positive definite, and let B be full column rank. Assume that all eigenvalues μ of Q
-
1
B
T
A
-
1
B are real and positive. Then, the MASOR method is convergent for all α, ω, and τ such that(62)
ω
2
μ
m
a
x
1
-
ω
β
<
2
2
α
+
ω
,
ω
>
0
,
α
>
0
,
1
-
ω
β
>
0
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Proof.
Equation (54) can be equivalently written as(63)
λ
2
+
ω
2
μ
α
+
ω
1
-
ω
β
-
2
α
+
ω
α
+
ω
λ
+
α
α
+
ω
=
0
.Equation (63) can be expressed as x
2
-
b
x
+
c
=
0, where(64)
b
=
2
α
+
ω
α
+
ω
-
ω
2
μ
α
+
ω
1
-
ω
β
,
c
=
α
α
+
ω
.Applying Lemma 2 to the quadratic equation (63), we know that |
λ
|
<
1 if and only if(65)
α
α
+
ω
<
1
,
2
α
+
ω
α
+
ω
-
ω
2
μ
α
+
ω
1
-
ω
β
<
α
α
+
ω
+
1
.In terms of (65), we derive(66)
ω
>
0
,
-
2
α
<
ω
,
0
<
ω
2
μ
1
-
ω
β
<
2
2
α
+
ω
.Evidently, the first and the second inequalities in (66) hold true for all α
>
0 and ω
>
0. It follows from the third inequality in (66), ω
2
>
0, and μ which is a real and positive eigenvalue of the matrix Q
-
1
B
T
A
-
1
B that(67)
1
-
ω
β
>
0
,
ω
2
μ
1
-
ω
β
<
2
2
α
+
ω
.It is not difficult to verify that(68)
ω
2
μ
1
-
ω
β
≤
ω
2
μ
m
a
x
1
-
ω
β
.Therefore, the proof of this theorem is completed.From (63), we get the following corollary.Corollary 15.
LetA and Q be symmetric positive definite, and let B be be full rank. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
β
,
ω are given by λ
=
α
/
(
α
+
ω
) or(69)
λ
=
1
2
2
α
+
ω
α
+
ω
-
ω
2
μ
α
+
ω
1
-
ω
β
±
ω
2
μ
α
+
ω
1
-
ω
β
-
2
α
+
ω
α
+
ω
2
-
4
α
α
+
ω
.


## 3.3. Semiconvergence of the MASOR Method for Singular Saddle Point Problem

In this section, we assume thatB in (1) is rank deficient and we will discuss the semiconvergence region for parameters ω, α, and β in the MASOR method for solving the singular saddle point problem (1).Theorem 16.
LetA and Q be symmetric positive definite, and let B be rank deficient. If μ is an eigenvalue of the matrix Q
-
1
B
T
A
-
1
B, then eigenvalues of the matrix M
α
,
β
,
ω are 1, λ
=
α
/
(
α
+
ω
), and the remainder eigenvalues are the roots of the quadratic equation (63).Proof.
By simple calculations, we have(70)
λ
I
-
M
α
,
β
,
ω
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
-
α
ω
1
-
ω
β
α
+
ω
Q
-
1
B
T
λ
-
1
I
n
+
ω
2
1
-
ω
β
α
+
ω
Q
-
1
B
T
A
-
1
B
.If λ
=
α
/
(
α
+
ω
), with the similar manner applied in the proof of Theorem 8, we can prove that |
λ
I
-
M
α
,
β
,
ω
|
=
0, which means that α
/
(
α
+
ω
) is an eigenvalue of M
α
,
β
,
ω. Otherwise, λ
≠
α
/
(
α
+
ω
), after suitable manipulations, gives (71)
λ
I
-
M
α
,
β
,
ω
=
λ
-
α
α
+
ω
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
Q
-
1
B
T
A
-
1
B
=
λ
-
α
α
+
ω
m
I
m
ω
α
+
ω
A
-
1
B
0
λ
-
1
I
n
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
Q
-
1
B
T
A
-
1
B
=
λ
-
α
α
+
ω
m
λ
-
1
I
n
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
Q
-
1
B
T
A
-
1
B
.We assume that rank
⁡
(
B
)
=
n
-
k
(
k
>
0
) and, with a quite similar strategy utilized in Theorem 8, we deduce that (72)
λ
I
-
M
α
,
β
,
ω
=
λ
-
α
α
+
ω
m
∏
i
=
1
n
λ
-
1
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
μ
i
=
λ
-
α
α
+
ω
m
λ
-
1
k
∏
i
=
1
n
-
k
λ
-
1
+
ω
2
λ
α
+
ω
λ
-
α
1
-
ω
β
μ
i
,where μ
i
(
i
=
1
,
…
,
n
-
k
) are the eigenvalues of Q
-
1
B
T
A
-
1
B, from which one can see that M
α
,
β
,
ω has at least k eigenvalues 1 and m eigenvalues α
/
(
α
+
ω
). It follows from λ
-
1
+
ω
2
λ
/
[
(
α
+
ω
)
λ
-
α
]
(
1
-
ω
β
)
μ
i
=
0 that (63) holds, which implies that the remainder eigenvalues of M
α
,
β
,
ω are the roots of (63). Thus, the theorem is proved.Lemma 17.
LetA and Q be symmetric positive definite, let B be rank deficient, and ω
≠
0 and ω
≠
1
/
β. Then, i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1.Proof.
We prove this theorem by Lemma9. Let X
=
(
x
T
,
y
T
)
T, with x
∈
R
m and y
∈
R
n such that(73)
Y
=
A
X
=
A
B
-
B
T
0
x
y
=
A
x
+
B
y
-
B
T
x
≠
0
.In order to prove i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1, it remains only to prove A
M
2
-
1
Y
≠
0, where M
2
-
1
=
ω
(
D
-
ω
L
)
-
1. Here and in the sequel, we prove A
M
2
-
1
Y
≠
0 by contradiction. We assume that A
M
2
-
1
Y
=
0. Let F
=
(
f
T
,
g
T
)
T, where f
∈
R
m, g
∈
R
n, and A
F
=
0. That is(74)
A
U
=
A
B
-
B
T
0
f
g
=
0
0
,which results in A
f
+
B
g
=
0 and -
B
T
f
=
0. From A
f
+
B
g
=
0, we deduce that f
=
-
A
-
1
B
g and B
T
A
-
1
B
g
=
0. From the fact that A is positive definite and so is A
-
1, which leads to B
g
=
0, thus f
=
0. Then, we infer that(75)
N
A
=
s
p
a
n
0
φ
,
w
h
e
r
e
B
φ
=
0
.Therefore, there is a vector φ
0 such that(76)
M
2
-
1
Y
=
0
φ
0
,
B
φ
0
=
0
.It follows from (76) that(77)
Y
=
M
2
0
φ
0
=
α
+
ω
ω
A
0
-
B
T
1
-
ω
β
ω
Q
0
φ
0
=
0
1
-
ω
β
ω
Q
φ
0
.Combining (73) with (77) gives B
φ
0
=
-
ω
/
(
1
-
ω
β
)
B
Q
-
1
B
T
x
=
0. Q
-
1 is positive definite as Q is positive definite, and thus B
T
x
=
0, which results in φ
0
=
-
ω
/
(
1
-
ω
β
)
Q
-
1
B
T
x
=
0. Then, Y
=
0 holds, which is in contradiction with (73). So A
M
2
-
1
Y
≠
0. From the above analysis and Lemma 9, it has i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1. This proves the theorem.By Lemma17, we have proved that i
n
d
e
x
(
I
-
M
α
,
β
,
ω
)
=
1, which satisfies the condition (1) in Lemma 7. In the sequel, we need to prove condition (2) in Lemma 7.By Theorem16, we see that the eigenvalues of M
α
,
β
,
ω are 1, α
/
(
α
+
ω
) and the remainder eigenvalues are the roots of the quadratic equation (63). By Definition 6 and Lemma 7, we only consider the eigenvalues of M
α
,
β
,
ω except 1.Lemma 18.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, V
(
M
α
,
β
,
ω
)
<
1 for all α, β, and ω such that(78)
ω
2
μ
m
a
x
1
-
ω
β
<
2
2
α
+
ω
,
ω
>
0
,
α
>
0
,
1
-
ω
β
>
0
,where μ
m
a
x is the maximum eigenvalue of Q
-
1
B
T
A
-
1
B.Together with Definition6 and Lemmas 17 and 18, we get the following sufficient conditions for the semiconvergence of the MASOR method.Theorem 19.
LetA and Q be symmetric positive definite, and let B be rank deficient. Then, the MASOR method is semiconvergent for all α, β, and ω such that(79)
ω
2
μ
m
a
x
1
-
ω
β
<
2
2
α
+
ω
,
ω
>
0
,
α
>
0
,
1
-
ω
β
>
0
,where μ
m
a
x is the maximum nonzero eigenvalue of Q
-
1
B
T
A
-
1
B.


## 4. The Optimal Convergence Factors of the GASOR and MASOR Methods

According to the theory of iterative methods, the optimal parameters of the GASOR method and MASOR method are as follows:(80)
α
∗
,
ω
∗
,
τ
∗
=
a
r
g
m
i
n
α
,
ω
,
τ
ρ
M
α
,
ω
,
τ
,
(81)
α
∗
,
β
∗
,
ω
∗
=
a
r
g
m
i
n
α
,
β
,
ω
ρ
M
α
,
β
,
ω
,respectively, where the a
r
g
m
i
n
(
α
,
β
,
ω
)
ρ
(
L
α
,
β
,
ω
) denotes such α, β, and ω that the spectral radius of the matrix L
α
,
β
,
ω reaches the minimum.This problem has been discussed in some articles [2, 5, 8, 10, 12, 19]. Golub et al. [8] obtained the optimal parameter of the SOR-like method; Bai et al. and Li and Kong studied the optimal parameters of the GSOR-like and GSOR methods in [5, 10], respectively. Bai [19] discussed the optimal parameters of the HSS-like method and Bai et al. [2] studied the optimal parameters of the PHSS method and so forth. To get the optimal values of α, ω, and τ for the GASOR method and α, β, and ω for the MASOR method, we need to analyze the modulus of eigenvalues of M
α
,
ω
,
τ and M
α
,
β
,
ω, respectively. Based on the proof of Theorems 8 and 16, the matrices M
α
,
ω
,
τ and M
α
,
β
,
ω have m repeated eigenvalues α
/
(
α
+
ω
) and the remainder eigenvalues satisfy (21) and (63), respectively. Note that all the eigenvalues λ of M
α
,
ω
,
τ and M
α
,
β
,
ω are available, which depend on α, β, ω, and τ. The optimal parameters could be obtained by getting the minimum of these eigenvalue functions. However, for most iterative methods, especially with multiple parameters, this work is very complicated. Hence it is very difficult to get the optimal parameters. The parameters in this paper are chosen based on prior experience and trial and error.


## 5. Numerical Experiments

In this section, numerical examples illustrate the superiority of the GASOR and MASOR methods to the ASOR, SOR-like, GSOR, and MSOR-like methods when they are used for solving the nonsingular saddle point problem (1) and show the advantages of the GASOR and MASOR methods over the GSOR, GSSOR, MSSOR, and GMSSOR methods for solving the singular saddle point problem (1). All numerical procedures are carried out using Matlab 6.5 on a personal computer with Intel(R) Pentium(R) CPU G3240T 2.70 GHz, 2.0 G memory and Windows 7 operating system.Example 1.
Consider the Stokes flow problem [2]: find u and w such that (82)
-
μ
Δ
u
+
∇
w
=
f
~
,
i
n
Ω
,
∇
·
u
=
g
~
,
i
n
Ω
,
u
=
0
,
o
n
∂
Ω
,
∫
Ω
w
x
d
x
=
0
,where Ω
=
(
0,1
)
×
(
0,1
)
⊂
R
2, ∂
Ω is the boundary of Ω, μ stands for the viscosity scalar, u
=
(
u
1
T
,
u
2
T
)
T is a vector-valued function representing the velocity, Δ is the componentwise Laplace operator, and w is a scalar function representing the pressure. By discretizing (82) with the upwind scheme as follows [54, 55]:(83)
μ
h
2
4
u
1
i
,
j
-
u
1
i
,
j
+
1
-
u
1
i
,
j
-
1
-
u
1
i
+
1
,
j
-
u
1
i
-
1
,
j
+
1
h
w
i
,
j
-
w
i
-
1
,
j
=
f
1
,
μ
h
2
4
u
2
i
,
j
-
u
2
i
,
j
+
1
-
u
2
i
,
j
-
1
-
u
2
i
+
1
,
j
-
u
2
i
-
1
,
j
+
1
h
w
i
,
j
-
w
i
,
j
-
1
=
f
2
,
-
1
h
u
1
i
,
j
-
u
1
i
-
1
,
j
-
1
h
u
2
i
,
j
-
u
2
i
,
j
-
1
=
-
g
,we obtain the system(84)
A
B
-
B
T
0
u
w
=
f
-
g
,where(85)
A
=
I
⊗
T
+
T
⊗
I
0
0
I
⊗
T
+
T
⊗
I
∈
R
2
p
2
×
2
p
2
,
B
=
I
⊗
F
F
⊗
I
∈
R
2
p
2
×
p
2
,with(86)
T
=
μ
h
2
·
t
r
i
d
i
a
g
-
1,2
,
-
1
∈
R
p
×
p
,
F
=
1
h
·
t
r
i
d
i
a
g
-
1,1
,
0
∈
R
p
×
p
.Here⊗ denotes the Kronecker product, h
=
1
/
(
p
+
1
) is the discretization mesh size, and J
=
t
r
i
d
i
a
g
(
a
,
b
,
c
) denotes a tridiagonal matrix with J
i
+
1
,
i
=
a, J
i
,
i
=
b, and J
i
,
i
+
1
=
c. In addition, we choose the right-hand side vector b so that the exact solution of the saddle point problem (1) is (
1,1
,
…
,
1
)
T
∈
R
m
+
n, where m
=
2
p
2 and n
=
p
2. The preconditioning matrix Q is an approximation of matrix Q
=
B
T
A
-
1
B. Moreover, we choose μ
=
1 in this example. We consider two cases as listed in Table 1.Table 1
Choice of the matrixQ.
Case number
MatrixQ
Description
1
B
T
A
^
-
1
B
A
^
=
t
r
i
d
i
a
g
(
A
)
2
B
T
A
^
-
1
B
A
^
=
diag
⁡
(
A
)All computations for the SOR-like, GSOR, MSOR-like, ASOR, GASOR, and MASOR methods are started from initial vectorx
(
0
)
=
(
x
0
T
,
y
0
T
)
T
=
(
0,0
,
…
,
0
)
T and the iteration is terminated once the current iterate x
(
k
) satisfies(87)
R
E
S
=
f
-
A
x
k
-
B
y
k
2
2
+
g
-
B
∗
x
k
2
2
f
2
2
+
g
2
2
<
1
0
-
9
,or the maximum prescribed number of iterations k
m
a
x
=
15
p is exceeded.In Table2, for various problem sizes p, we list the theoretical optimal iteration parameters of the SOR-like, GSOR, MSOR-like, ASOR, GASOR, and MASOR methods used in our implementations. For the GSOR, SOR-like, and MSOR-like methods, we adopt their optimal parameters as in [5, 8, 9]. In addition, the parameters taken by the ASOR method are the same as in [35], and we choose the parameters of the GASOR and MASOR methods which result in the least numbers of iterations for this numerical example. However, note that the explicit expressions of parameters cannot be obtained, and we only choose them by trial and error. The corresponding convergence factors ρ
∗, ρ
e
x
p, and ρ with various problems size p are also reported in Table 2.Table 2
Parameters for the six methods and the corresponding spectral radii.
Method
p
16
24
32
Case1
SOR-like
ω
∗
0.3657
0.2620
0.2037
ρ
∗
0.7964
0.8591
0.8923
GSOR
ω
∗
0.4429
0.3307
0.2635
τ
∗
0.2854
0.1985
0.1519
ρ
∗
0.7464
0.8181
0.8582
MSOR-like
ω
∗
0.2498
0.1806
0.1412
α
∗
1.7732
1.8315
1.8662
ρ
∗
0.7464
0.8181
0.8582
ASOR
ω
e
x
p
0.2531
0.1817
0.1417
α
e
x
p
0.3300
0.3944
0.4401
ρ
e
x
p
0.7523
0.8274
0.8697
GASOR
α
e
x
p
0.4117
0.3697
0.2799
ω
e
x
p
0.3200
0.1820
0.1000
τ
e
x
p
0.2450
0.1780
0.1400
ρ
0.7657
0.8373
0.8701
MASOR
ω
e
x
p
0.2531
0.1820
0.1002
α
e
x
p
0.319
0.3698
0.2800
β
e
x
p
0.3900
0.3769
3.3550
ρ
0.7737
0.8371
0.8690
Case2
SOR-like
ω
∗
0.2720
0.1915
0.1476
ρ
∗
0.8533
0.8992
0.9232
GSOR
ω
∗
0.3419
0.2489
0.1956
τ
∗
0.2066
0.1423
0.1084
ρ
∗
0.8112
0.8667
0.8969
MSOR-like
ω
∗
0.1873
0.1328
0.1029
α
∗
1.8256
1.8737
1.9009
ρ
∗
0.8112
0.8667
0.8969
ASOR
ω
e
x
p
0.1886
0.1333
0.1031
α
e
x
p
0.3873
0.4509
0.4934
ρ
e
x
p
0.8201
0.8785
0.9095
GASOR
α
e
x
p
0.4400
0.4000
0.4150
ω
e
x
p
0.2400
0.1348
0.1040
τ
e
x
p
0.1780
0.1280
0.1000
ρ
0.8590
0.8942
0.9181
MASOR
ω
e
x
p
0.1886
0.1333
0.1031
α
e
x
p
0.3450
0.3900
0.414
β
e
x
p
0.2090
0.2481
0.2100
ρ
0.8579
0.8941
0.9171In Table3, we present the iteration numbers (IT), CPU times (CPU), and relative residual (RES) of the testing iteration methods with different problem sizes p. In this table, we use the bold numbers to indicate the smallest and the second smallest CPU times and iteration numbers in each column.Table 3
Numerical results for the six methods for Case1 and Case 2, respectively.
Method
p
16
24
32
Case1
SOR-like
IT
131
201
273
CPU
0.3793
2.8314
10.8478
RES
8.76
e
-
010
8.78
e
-
010
9.14
e
-
010
GSOR
IT
100
149
200
CPU
0.2947
2.0845
7.7318
RES
8.87
e
-
010
9.86
e
-
010
9.41
e
-
010
MSOR-like
IT
99
149
201
CPU
0.2813
2.0790
7.6604
RES
7.90
e
-
010
9.49
e
-
010
8.82
e
-
010
ASOR
IT
87
127
172
CPU
0.2559
1.7806
6.5416
RES
1.25
e
-
010
7.52
e
-
010
5.29
e
-
010
GASOR
IT
80
116
154
CPU
0.2279
1.6303
5.8605
RES
6.26
e
-
010
5.14
e
-
010
9.07
e
-
010
MASOR
IT
83
116
157
CPU
0.2396
1.6388
6.0598
RES
5.69
e
-
010
6.85
e
-
010
7.75
e
-
010
Case2
SOR-like
IT
192
292
389
CPU
0.5437
4.2177
15.4625
RES
9.81
e
-
010
9.27
e
-
010
9.91
e
-
010
GSOR
IT
143
215
287
CPU
0.4612
3.0769
11.1054
RES
8.75
e
-
010
9.87
e
-
010
9.15
e
-
010
MSOR-like
IT
143
213
286
CPU
0.4110
2.9643
11.0999
RES
9.36
e
-
010
9.83
e
-
010
9.17
e
-
010
ASOR
IT
125
185
261
CPU
0.3571
2.5767
10.1672
RES
9.80
e
-
010
9.56
e
-
010
5.48
e
-
010
GASOR
IT
108
160
219
CPU
0.3067
2.2436
8.4094
RES
3.83
e
-
010
8.29
e
-
010
8.85
e
-
010
MASOR
IT
110
161
226
CPU
0.3123
2.3058
8.7687
RES
9.62
e
-
010
9.97
e
-
010
4.51
e
-
010As observed in Table2, the convergence factors of the GASOR and MASOR methods are smaller than that of the SOR-like method. We can also see that the spectral radii of the GASOR and MASOR methods in Cases1 and 2 for this example are almost the same as the ones of the GSOR, MSOR-like and ASOR methods, while the GASOR and MASOR methods require much less time and iteration steps to achieve the stopping criterion than other four methods, and the relaxation parameters of the GASOR and MASOR methods are not optimal and only lie in the convergence region of these methods. From the results in Table 3, we see that the SOR-like, GSOR, MSOR-like, ASOR, GASOR, and MASOR methods succeed in achieving the stopping criterion within the largest admissible number of iteration steps in all cases. Moreover, the GASOR method uses the least iteration numbers and CPU times compared with the SOR-like, GSOR, MSOR-like, ASOR, and MASOR methods, and the MASOR method is also superior to the SOR-like, GSOR, MSOR-like, and ASOR methods both in iteration numbers and CPU times especially for large problem size m. Furthermore, we can find that the performance of the GASOR and MASOR methods is almost the same.In order to better understand the numerical results, we have presented graphs ofR
E
S
(
log
⁡
10
) against number of iterations in Table 3 for p
=
16, p
=
24, and p
=
32, respectively, in Figures 1–3. From the three figures, we note that the six methods are convergent while the GASOR and MASOR methods converge faster than other methods. Moreover, it can be seen that the GASOR and MASOR methods at different iteration points have “semilocal convergence” behavior, and thus we can deduce that the parameters chosen by the GASOR and MASOR methods are not optimal and only lie in the convergence regions of these two new methods, which means that the GASOR and MASOR methods may perform better with better choice of optimal parameters. The numerical results in this example show feasibility and effectiveness of the GASOR and MASOR methods for solving nonsingular saddle point problems.Figure 1
The iteration curves of algorithms whenm
=
512 for Case1 and Case2, respectively.Figure 2
The iteration curves of algorithms whenm
=
1152 for Case1 and Case2, respectively.Figure 3
The iteration curves of algorithms whenm
=
2048 for Case1 and Case2, respectively.Example 2.
Consider the singular saddle point problem (1) with coefficient matrix of the matrix blocks [34] (88)
A
=
I
⊗
T
+
T
⊗
I
0
0
I
⊗
T
+
T
⊗
I
∈
R
2
p
2
×
2
p
2
,
B
=
B
^
b
1
b
2
∈
R
2
p
2
×
p
2
+
2
,where(89)
T
=
1
h
2
·
t
r
i
d
i
a
g
-
1,2
,
-
1
∈
R
p
×
p
,
B
^
=
I
⊗
F
F
⊗
I
∈
R
2
p
2
×
p
2
,
b
1
=
B
^
e
0
,
b
2
=
B
^
0
e
,
e
=
1,1
,
…
,
1
∈
R
p
2
/
2
,
F
=
1
h
·
t
r
i
d
i
a
g
-
1,1
,
0
∈
R
p
×
p
,
h
=
1
p
+
1
,and the right-hand side vector b is chosen by b
=
A
e
m
+
n, where(90)
e
m
+
n
=
1,1
,
…
,
1
∈
R
m
+
n
,
m
=
2
p
2
,
n
=
p
2
+
2
.We choose the preconditioning matrix Q
=
diag
⁡
(
B
T
A
-
1
B
). All computations for the GSOR, MSSOR, GSSOR, GMSSOR, GASOR, and MASOR methods are started from initial vector x
(
0
)
=
(
x
0
T
,
y
0
T
)
T
=
(
0,0
,
…
,
0
)
T and the iteration is terminated once the current iterate x
(
k
) satisfies(91)
R
E
S
=
f
-
A
x
k
-
B
y
k
2
2
+
g
-
B
∗
x
k
2
2
f
2
2
+
g
2
2
<
1
0
-
6or the maximum prescribed number of iterations k
m
a
x
=
10
p is exceeded.In Table4, for various problem sizes p, we list the theoretical optimal iteration parameters of the iteration matrices of the GSOR, MSSOR, GSSOR, GMSSOR, GASOR, and MASOR methods for solving singular saddle point problem. For the GSOR, MSSOR, and GSSOR methods, we take their optimal parameters as in [5, 6, 49]. For the GMSSOR method, the parameters are chosen as [42]. Furthermore, we take the parameters of the GASOR and MASOR methods which result in the least numbers of iterations for this numerical example. As mentioned in Example 1, we only choose them by trial and error. Furthermore, the pseudospectral radii of the iteration matrices of these methods are also presented in this table.Table 4
Parameters for the six methods and the corresponding pseudospectral radii.
Method
p
16
24
32
GSOR
ω
∗
0.7896
0.7398
0.6984
τ
∗
1.1050
1.2442
1.3671
ρ
∗
0.4651
0.5650
0.5583
MSSOR
ω
∗
0.45
0.4817
0.47
ρ
∗
0.5500
0.5684
0.6793
GSSOR
ω
∗
1.4587
1.5110
1.5492
τ
∗
0.4100
0.4444
0.4722
ρ
∗
0.4651
0.5650
0.5583
GMSSOR
ω
e
x
p
1.4600
1.5000
1.5400
τ
e
x
p
0.4300
0.4500
0.4700
ρ
e
x
p
0.4876
0.6206
0.6731
GASOR
α
0.2300
0.2840
0.3230
ω
0.7700
0.7160
0.6770
τ
0.7097
0.7654
0.8095
ρ
0.4796
0.5329
0.5683
MASOR
ω
0.7700
0.7160
0.6770
α
0.2300
0.2840
0.3230
β
0.3896
0.5902
0.7418
ρ
0.4796
0.5329
0.5683Comparing the results in Table4, we observe that the pseudospectral radii of the GASOR and MASOR methods are smaller than those of the MSSOR and GMSSOR methods. It also can be seen that the pseudospectral radii of the GASOR and MASOR methods for Example 2 are almost the same as the ones of the GSOR and GSSOR methods. However, the GASOR and MASOR methods outperform the GSOR and GSSOR methods in terms of less CPU times and iteration steps. In Table 5, we present the iteration numbers (IT), CPU times (CPU), and relative residual (RES) of the testing iteration methods with different problem sizes p. In this table, we use the bold numbers to indicate the smallest and the second smallest CPU times and iteration numbers in each column. Dates presented in Table 5 reveal that the GSOR, MSSOR, GSSOR, GMSSOR, GASOR, and MASOR methods succeed in producing high-quality approximate solutions in all cases. The iteration numbers and CPU times of all methods improve with size growing. Moreover, the GASOR and MASOR methods both use the least iteration numbers and CPU times compared with the GSOR, MSSOR, GSSOR, and GMSSOR methods. Furthermore, we can observe that the performance of the GASOR and MASOR methods is the same. It can be seen that the performance of the GASOR and MASOR methods is much better than other methods, but the parameters of these two methods are not the optimal parameters, and other methods take optimal or experimentally found optimal parameters. Hence, it is anticipated that the GASOR and MASOR methods with the optimal parameters would be much better than the other four methods.Table 5
Numerical results for the six methods.
Method
p
16
24
32
GSOR
IT
21
25
27
CPU
0.2679
0.6841
1.6852
RES
2.44
e
-
07
5.65
e
-
07
9.02
e
-
07
MSSOR
IT
25
25
32
CPU
0.3586
0.9891
2.9142
RES
5.21
e
-
07
6.06
e
-
07
9.43
e
-
07
GSSOR
IT
22
25
28
CPU
0.3404
0.9095
2.5249
RES
6.13
e
-
07
7.40
e
-
07
8.19
e
-
07
GMSSOR
IT
21
27
31
CPU
0.4154
1.0380
2.6683
RES
7.57
e
-
07
7.32
e
-
07
9.57
e
-
07
GASOR
IT
20
23
26
CPU
0.2582
0.6273
1.6367
RES
5.98
e
-
07
8.20
e
-
07
4.95
e
-
07
MASOR
IT
20
23
26
CPU
0.2615
0.6802
1.6194
RES
5.98
e
-
07
8.20
e
-
07
4.95
e
-
07In Figure4, the graphs of R
E
S
(
log
⁡
10
) against number of iterations in Table 5 for four different sizes are derived. It clearly shows that the six methods are semiconvergent while the GASOR and MASOR methods converge faster. However, the parameters of the GASOR and MASOR methods are not optimal and only lie in the convergence regions of these two methods.Figure 4
The iteration curves of algorithms forp
=
16, p
=
24, and p
=
32.


## 6. Conclusions

In this paper, we propose two new methods called GASOR and MASOR methods, respectively, and study the convergence and semiconvergence of these two new methods for solving nonsingular and singular saddle point problems, respectively. Numerical results given in Section5 (Tables 1–5 and Figures 1–4) show that the convergence rates of the GASOR and MASOR methods are better than the SOR-like, GSOR, MSOR-like, GSSOR, MSSOR, GMSSOR, and ASOR methods even though they are implemented with the optimal or the experimentally found optimal parameters. Numerical results present the feasibility and effectiveness of the GASOR and MASOR methods for solving both nonsingular and singular saddle point problems.Since the optimal parameters were not used for the GASOR and MASOR methods in the numerical experiments, it is anticipated that the GASOR and MASOR methods with the optimal parameters would be much better than the other methods. Thus, it would be nice if we can find the optimal parameters for which the convergence rates of the GASOR and MASOR methods are best. Future work will include numerical or theoretical studies for finding the optimal values ofα, ω, and τ for the GASOR method and the optimal values of α, β, and ω for the MASOR method.



---

*Source: 5087237-2016-04-14.xml*