Accelerated RHSS Iteration Method for Stabilized Saddle-Point Problems ()
1. Introduction
Consider the stabilized saddle-point problem
(1)
where
is a Hermitian positive definite matrix,
is a Hermitian positive semidefinite matrix,
is rectangular matrix,
is the complex conjugate transpose of E and
and
. In addition, the null spaces of the matrices C and E do not overlap, i.e.,
, then in accordance with [1], we know that the stabilized saddle-point problem (1) admits a unique solution; see also [2] and its reference therein. For stabilized saddle-point problem, it has a broad background in scientific computing and engineering applications. For example, it frequently appears in Navier-Stokes equations, finite element methods, regularized and weighted least-squares problems. For more details, see [3] [4] [5] [6] [7].
When
, the stabilized saddle-point problem (1) degenerated into standard saddle-point problem. Benzi and Golub [8] proposed the Hermitian and skew-Hermitian splitting (HSS) iteration method to solve the standard saddle-point problem. This iteration method is a direct generalization of the HSS iteration method initially proposed in [9]. To improve the convergence rate of the HSS iteration method, Bai, Golub and Pan [10] proposed the preconditioned HSS (PHSS) iteration method, and then Bai and Golub [11] proposed the accelerated HSS (AHSS) iteration method by calculating the HSS iteration sequence with different parameters. Bai and Benzi [12] proposed the regularized Hermitian and skew-Hermitian splitting (RHSS) iteration method to solve the standard saddle-point problem. The biggest highlight is that the condition number of iterative systems can be improved by regularizing the matrix. In addition, Behzadi and Abdollahi [13] combined the AHSS iteration method and the RHSS iteration method to build the accelerated RHSS (ARHSS) iteration method for the standard saddle-point linear system, and experimental results show that the ARHSS iteration method is better than the HSS iteration method and the RHSS iteration method.
Recently, based on the regularized Hermitian and skew-Hermitian splitting of the stabilized saddle-point matrix A in (1):
(2)
where
is a Hermitian positive semidefinite matrix and
is a non-negative constant. Bai [2] extended the RHSS iteration method for the standard saddle-point problem to the stabilized saddle-point problem as follows:
(3)
where I is the identity matrix and
is a positive constant. And Bai proved the RHSS iteration method converges unconditionally to the exact solution of the stabilized saddle-point problem (1). Numerical results on stabilized saddle-point problems in [2] show that the RHSS iteration method significantly outperforms the Hermitian and skew-Hermitian splitting iteration method in iteration counts and computing times.
In this paper, inspired by Behzadi and Abdollahi [13] and Bai [2], we know that the accelerated RHSS iteration method has advantages over the HSS iteration method and the RHSS iteration method on the standard saddle-point problem. So we extend the accelerated RHSS iteration method for the standard saddle-point problem to the stabilized saddle-point problem, and establish the ARHSS iteration method for the stabilized saddle-point problem. Then we confirm the convergence of the ARHSS iteration method. Finally, experimental results show that the ARHSS iteration method is more effective than the HSS iteration method and the RHSS iteration method for the stabilized saddle-point problem (1).
The remainder of this work is organized as follows. In Section 2, we propose the ARHSS iteration method for the stabilized saddle-point problem (1). In Section 3, we give the convergence property of the ARHSS iteration method. In Section 4, A numerical experiment is given to show the effectiveness of the method. In Section 5, we end the paper with some brief conclusions.
2. The ARHSS Iteration Method
In this section, we derive the ARHSS iteration method for solving (1). Let
be a Hermitian positive semidefinite matrix and
be a prescribed non-negative parameter. Then we can split the stabilized saddle-point matrix
in (1), and obtain the regularized Hermitian and skew-Hermitian (RHS) splitting:
(4)
By applying the regularized Hermitian and Skew-Hermitian (RHS) splitting to (4), we then obtain the iteration scheme
where
with
and
positive constants.
By iterating alternatively between these two fixed-point systems as
and
or in their blockwise forms
(5)
and
(6)
So, we obtain the ARHSS iteration method for solving the stabilized saddle-point problem (1) as follows:
The ARHSS iteration method. Let
and
be positive constants,
be a non-negative constant and
be a Hermitian positive semidefinite matrix. Give an initial guess
, for
until the iteration sequence
converges, compute the next iterate
according to following procedure:
(i) solve for
from the linear subsystem
(ii) compute
and
(iii) solve for
from the linear subsystem
(iv) compute
3. The Convergence Property of the ARHSS Iteration Method
In this section we prove the unconditional convergence of the ARHSS iteration method. We know that calculating the spectral radius of the iterative matrix
is the easiest way to prove the convergence of ARHSS iteration method. From (5) and (6), we easily know
can be equivalently rewritten as
where
and
To prove the convergence of the ARHSS iteration method, we first introduce a lemma.
Lemma 3.1. ( [2], Theorem 3.1) For the stabilized saddle-point problem (1), the RHSS iteration method (3) converges unconditionally to the exact solution of the stabilized saddle-point problem (1).
In the following theorem, we prove the unconditional convergence of the ARHSS iteration method.
Theorem 3.2. For the stabilized saddle-point problem (1), assume that
is Hermitian positive definite,
is Hermitian positive semidefinite and
satisfies
. Let
be prescribed positive constant,
be a given non-negative constant and
be a given Hermitian positive semidefinite matrix. Then it holds that
, i.e., the ARHSS iteration method converges unconditionally to the exact solution of the stabilized saddle-point problem (1).
Proof. There are two cases to consider.
Case I: If
, according to the ARHS splitting, we obtain
(7)
and
(8)
where
. Since
is Hermitian positive semidefinite matrix, relations (7) and (8) are exactly the RHS splitting of A. By Lemma 3.1, this split converges to the exact solution of the saddle point linear system (1).
Case II: If
, according to the ARHS splitting, we obtain
(9)
and
(10)
where
. Since
is Hermitian positive semidefinite matrix, the relations (9) and (10) are exactly the RHS splitting of A. By Lemma 3.1, this split converges to the exact solution of the saddle point linear system (1). The desired result holds by Case I and Case II. Therefore, we complete the proof.
4. Numerical Experiment
In this section, a numerical example is given to illustrate the effectiveness of the ARHSS iteration method for the stabilized saddle-point problem (1). We compare the number of iteration steps (denoted as IT) and computing times in seconds (denoted as CPU) of the ARHSS iteration method with the HSS iteration method and the RHSS iteration method. All our tests are started from the initial vector
. All iterations are terminated as the current residuals satisfy
or the number of iterations steps exceeds 5000. In addition, all the computations were implemented in MATLAB [version 9.1.0.441655 (R2016b)] in double precision on a personal computer with 1.60 GHZ central processing unit [Intel(R) Core(TM)i5-5250U] and 4.00 GB memory.
Example 4.1. ( [2], Example 4.3) Consider the nonlinear image restoration problem
(11)
where
and
represent the observed and the original images,respectively,
denotes a nonlinear point spread function and
is a blurring matrix. When this regularized nonlinear least-squares problem (11) is solved by the Gauss-Newton iteration method,at each step for the currently available approximant
,we need to solve a linear system of the form
to obtain the next approximant,where
is a diagonal matrix with its diagonal entries being given by
This linear system can be equivalently reformulated into the stabilized saddle-point problem (1),in which
and
In actual computations we set
and
and take
,
with
. Here,the notation “:”is a standard MATLAB symbol used in indicating a row vector of the form
for which
and
are the first and the last elements,
is a prescribed increment such that
is its multiple and k is a non-negative integer ranging from 0 to
.
For this example we have
, so that the dimension of the stabilized saddle-point matrix
is
. Note that the Toeplitz matrix E is highly ill-conditioned with rapidly decaying singular values so that it is almost rank-deficient, especially when the problem size p becomes sufficiently large. Besides, we take the regularization matrix to be
Taking Q into (5) and (6), we get
and
So, in the specific algorithms, the parameter
does not need to be determined. In our experiments, let the parameter
be taken as the optimal value of [ [2], Example 4.3], and the optimal values of the parameters
and
can be determined by experience and trial runs. For example, first, suppose the ranges of
and
are
, and then divide it into 100 equal parts. Second, fix parameter
to a certain value in
, and then find the corresponding optimal parameter
by trial runs. Third, using the second step method, fix parameter
to a certain value in
, and then find the corresponding optimal parameter
by trial runs. Finally, we choose the best parameters
and
through experience and trial runs.
In Table 1, we list the best parameters
and regularization parameter
for the three iteration methods including HSS, RHSS and ARHSS with different mesh number p. Through these optimal parameters, we list the experimental results of the three methods in Table 2. The experimental results show that compared with HSS and RHSS, the ARHSS iteration method takes the least CPU and the smallest IT to converge to the solution of (11).
Table 1. Optimal parameter and regularization parameter.
5. Conclusion
For stabilized saddle-point problem, we extend the accelerated RHSS iteration method for the standard saddle-point problem to the stabilized saddle-point problem. The convergence property of the ARHSS iteration method is carefully studied, and the numerical result illustrates that the ARHSS is more effective for the stabilized saddle-point problem. In this paper, optimal iteration parameters can only be determined experimentally. So, how to establish practical formulas for computing the optimal iteration parameters is worth further study.