A note of generalized shift-splitting preconditionersfor nonsymmetric saddle point problems

張理濤，谷同祥，孟慧麗

(1.鄭州航空工業(yè)管理學(xué)院 理學(xué)院， 河南 鄭州 450015；2.北京應(yīng)用物理與計算數(shù)學(xué)研究所 計算物理實(shí)驗(yàn)室，北京 100088；3.河南師范大學(xué) 計算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007)

A note of generalized shift-splitting preconditionersfor nonsymmetric saddle point problems

Recently, CAO et al introduced a generalized shift-splitting preconditioner for saddle point problems with nonsymmetric positive definite (1,1)-block. In this paper, we establish a parameterized shift-splitting preconditioner for solving the large sparse augmented systems of linear equations. Furthermore, we obtain some useful properties of the new preconditioned saddle point matrix, which has the intersection with the generalized shift-splitting preconditioner.

nonsymmetric saddle point problem; parameterized shift-splitting; convergence; preconditioner; eigenvalue

0 Introduction

Consider the following 2×2 block saddle point problems

(1)

In recent years, there has been a surge of interest in the saddle point problem of the form (1), and a large number of stationary iterative methods have been proposed. For example, SANTOS et al[6]studied preconditioned iterative methods for solving the singular augmented system withA=I. YUAN et al[7-8]proposed several variants of SOR method and preconditioned conjugate gradient methods for solving general augmented system (1) arising from generalized least squares problems whereAcan be symmetric and positive semidefinite， andBcan be ranked deficiently. The SOR-like method requires less arithmetic work per iteration step than other methods, but it requires choosing an optimal iteration parameter in order to achieve a comparable rate of convergence. GOLUB et al[9]presented SOR-like algorithms for solving system (1). DARVISHI et al[10]studied SSOR method to solve the augmented systems. BAI et al[11-12,14]presented GSOR method, parameterized Uzawa (PU) and the inexact parameterized Uzawa (PIU) methods for solving systems (1). ZHANG et al[15]showed the generalized symmetric SOR method for augmented systems. PENG et al[16]studied unsymmetric block overrelaxation-type methods for saddle point. BAI et al[17-21,23]presented splitting iteration methods such as Hermitian and skew-Hermitian splitting (HSS) iteration scheme and its preconditioned variants, Krylov subspace methods such as preconditioned conjugate gradient (PCG), preconditioned MINRES (PMINRES) and restrictively preconditioned conjugate gradient (RPCG) iteration schemes, and preconditioning techniques related to Krylov subspace methods such as HSS, block-diagonal, block-triangular and constraint preconditioners and so on. WANG et al[23]and CHEN et al[13]studied some general approaches about the relaxed splitting iteration methods. WU et al[24]presented the modified SSOR (MSSOR) method for the augmented systems.

Shift-splitting technique has been studied in many papers for solving the system of linear equations. For example, BAI et al[25]presented a regularized conjugate gradient method for symmetric positive definite system of linear equations by shifting and contracting the spectrum of the coefficient matrix. BAI et al[26]proposed a shift-splitting preconditioner for non-Hermitian positive definite matrices. The numerical results showed that the shift-splitting technique is very effective for ill-conditioned and non-Hermitian positive definite systems of linear equations. CAO et al[27]introduced a shift-splitting preconditioner and a local shift-splitting preconditioner for saddle point problems (1). Moreover, the authors studied some properties of the local shift-splitting preconditioned matrix and presented numerical experiments of a model Stokes problem to show the effectiveness of the proposed preconditioners. CHEN et al[28]presented a generalized shift-splitting preconditioner for saddle point problems with symmetric positive definite (1, 1)-block and gave theoretical analysis and numerical experiments. Recently, CAO et al[29]introduced a class of generalized shift-splitting preconditioners with two shift-parameters for nonsymmetric saddle point problems with nonsymmetric positive definite (1,1) block, and gave theoretical analysis and numerical experiments. Moreover, both theoretical and numerical results are very interesting.

For large, sparse or structure matrices, iterative methods are an attractive option. In particular, Krylov subspace methods apply techniques that involve orthogonal projections onto subspaces of the form

The conjugate gradient method (CG), minimum residual method (MINRES) and generalized minimal residual method (GMRES) are common Krylov subspace methods. The CG method is used for symmetric, positive definite matrices, MINRES for symmetric and possibly indefinite matrices and GMRES for unsymmetric matrices[30].

In this paper, based on the generalized shift-splitting preconditioners presented by CAO et al[29], we establish a parameterized shift-splitting preconditioner for saddle point problems with nonsymmetric positive definite (1,1)-block. Furthermore, the preconditioner is based on a parameterized shift-splitting of the saddle point matrix, resulting in an unconditional convergent fixed-point iteration, which has the intersection with the generalized shift-splitting preconditioner. However, the relaxed parameters of the parameterized shift-splitting methods are not optimal and only lie in the convergence region of the method.

1 Parameterized shift-splitting (PSS)preconditioner

Recently, for the coefficient matrix of the augmented system (1), CAO et al[29]make the following splitting:

(2)

where α>0,β>0aretwoconstantsandIis the identity matrix (with appropriate dimension). Based on the iteration methods studied in [27-28], a parameterized shift-splitting of the saddle point matrix A can be constructed as follows:

(3)

where α>0,β>0aretwoconstantsandIis the identity matrix (with appropriate dimension). By this special splitting, the following parameterized shift-splitting method can be defined for solving the saddle point problem (1):

Parameterized shift-splitting (PSS) method Give initial vectorsu0∈Rm+n, and two relaxed parametersα>0 andβ>0. Fork=0,1,2,… until the iteration sequence {uk} converges, we compute

(4)

where α>0,β>0aretwoconstants.Itiseasytoseethattheiterationmatrixoftheparameterizedshift-splittingiterationis

(5)

IfweuseaKrylovsubspacemethodsuchasGMRES(generalizedminimalresidual)methodoritsrestartedvarianttoapproximatethesolutionofthissystemoflinearequations,then

(6)

canbeservedasapreconditioner.WecallthepreconditionerPPSSthe parameterized shift-splitting preconditioner for the nonsymmetric saddle point matrix A.

In every iteration of the parameterized shift-splitting iteration (4) or the preconditioned Krylov subspace method, we need to solve a residual equation

(7)

(8)

(9)

Hence, analogous to algorithm 2.1 in [27], we can derive the following algorithmic version of the generalized shift-splitting iteration method.

Now, we turn to study the convergence of the parameterized shift-splitting iteration for solving nonsymmetric saddle point problems. The iteration method (4) is convergent for every initial guess, if and only ifρ(Γ)<1, whereρ(Γ) denotes the spectral radius of Γ. Letλbe an eigenvalue of Γ and [x*,y*]*be the corresponding eigenvector. Then we have

(10)

or equivalently,

(11)

To get the convergence of the parameterized shift-splitting iteration, we firstly give some lemmas.

Lemma 1 LetAbe a nonsymmetric positive definite matrix, andBhas full row rank. Let Γ be defined as (5) withα>0 andβ>0. Ifλbe an eigenvalue of Γ, thenλ≠±1.

Proof Let [x*,y*]*be the corresponding eigenvector ofλ. Ifλ=1, then from (11) we have

(12)

It is easy to get that the coefficient matrix of (12) is nonsingular. Hence x=0andy=0,whichcontradictstheassumptionthat[x*,y*]*isaneigenvectoroftheiterationmatrixΓ.Soλ≠1.

Now,weprovethatλ≠-1.Ifλ=-1,thenfrom(11)wecanobtain

-2αx+2αβBTy=0, -2βy=0.

(13)

Sinceα>0,β>0, from (13) we getx=0 andy=0, which also contradicts the assumption that [x*,y*]*is an eigenvector of the iteration matrix Γ. Soλ≠-1. This process completes the proof.

Lemma 2 AssumeAbe a nonsymmetric positive definite matrix, andBhas full row rank. Letλbe an eigenvalue of Γ (withα>0 andβ>0) and [x*,y*]*be the corresponding eigenvector withx∈Cnandy∈Cm. Thenx≠0. Moreover, ify=0, then |λ|<1.

Proof Ifx=0, then from (11) we have (1+αβ+λ-λαβ)BTy=0. By lemma 1, we know thatλ≠-1 andα>0,β>0. Thus we haveBTy=0. BecauseBThas full column rank, we gety=0, which contradicts with the assumption that [x*,y*]*is an eigenvector. Thusx≠0. From lemma 2[31], it’s easy to know |λ|≤‖(αI+A)-1(αI-A)‖2.

Theorem 1 AssumeA∈Rn×nbe a nonsymmetric positive definite matrix, andB∈Rm×nhas full row rank, and letα,βbe two positive constants. Letρ(Γ) denote the spectral radius of the parameterized shift-splitting iteration matrix. Then it holds that

ρ(Γ)<1, ?α>0,β>0,

(14)

i.e., the parameterized shift-splitting iteration converges to the unique solution of the nonsymmetric saddle point problem (1).

Proof Letλbe an eigenvalue of Γ and [x*,y*]*be the corresponding eigenvector withx∈Cnandy∈Cm. By lemma 1, we obtainλ≠1. Then we can obtain from (11) that

(15)

IfBx=0, then we can obtainy=0. By the second part of lemma 2.3[29], we know that |λ|<1. Substituting (15) into the first equation of (11), we get

(16)

(17)

Let

(18)

(19)

Define

and

Now, according to lemma 2.4[32], we find that both roots of the complex quadratic equation (19) satisfy |λ|<1,ifandonlyif

(20)

Bycomputation,wehave

(21)

and

(22)

whereRe(ξ)andIm(ξ)denotetherealpartandtheimaginarypartofacomplexnumberξ,respectively.Thenweobtain

[((αβ-βa+c+αβc)(αβ+βa+c-αβc)-β2b2)2+(2c+2αβ)2β2b2]/((αβ+βa+c-αβc)2+β2b2)2.

(23)

Ifc>αβ, then it holds that

(2βa(2c-2αβ))((αβ+βa+c-αβc)2+β2b2)+

((αβ-βa+c+αβc)(αβ+βa+c-αβc)-β2b2)2+

(2αβ+2c)2β2b2=

(αβ+βa+c-αβc)2(α2β2-6αβ2a+2βac+β2a2+c2+2αβc-

2α2β2c-αβ2ac-2αβc2-αβ2a+α2β2c2)+β4b4+

2β2b2(α2β2-2αβ2a+2βac+β2a2+c2+2αβc-

2α2β2c-αβ2ac-2αβc2-αβ2a+α2β2c2)<

((αβ+βa+c-αβc)2+2β2b2)(α2β2-2αβ2a+2βac+

β2a2+c2+2αβc-2α2β2c-αβ2ac-2αβc2-αβ2a+α2β2c2)+

β4b4<((αβ+βa+c-αβc)2+2β2b2)(α2β2+2αβ2a+2βac+

β2a2+c2+2αβc-2α2β2c-αβ2ac-2αβc2-αβ2a+α2β2c2)+β4b4=

(αβ+βa+c-αβc)4+2β2b2(αβ+βa+c-αβc)2+β4b4=

((αβ+βa+c-αβc)2+β2b2)2.

(24)

Likewise, the following inequality

(2βa(2αβ-2c))((αβ+βa+c-αβc)2+β2b2)+

((αβ-βa+c+αβc)(αβ+βa+c-αβc)-β2b2)2+

(2αβ+2c)2β2b2<((αβ+βa+c-αβc)2+β2b2)2

(25)

holds true in the casec<αβ. Thus, by combining (24) and (25), we can obtain that (20) holds for allα,β>0. Therefore, we have

ρ(Γ<1), ?α,β>0,

i.e., the generalized shift-splitting iteration (3) converges to the unique solution of the nonsymmetric saddle point problem (1).

Remark 1 Whenα=0, the parameterized shift-splitting preconditioner reduces to the local shift-splitting preconditioner. Moreover, the parameterized shift-splitting preconditioner in this paper and the generalized shift-splitting preconditioner in [28] are two different preconditioning modes. Additionally, they have an intersection.

Remark 2 From theorem 1, we know that the parameterized shift-splitting iteration method is unconditionally convergent.

[1] WRIGHT S. Stability of augmented system factorizations in interior-point methods[J]. SIAM J Matrix Anal Appl,1997,18:191-222.

[2] ELMAN H, SILVESTER D. Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations[J]. SIAM J Sci Comput,1996,17:33-46.

[3] ELMAN H, GOLUB G H. Inexact and preconditioned Uzawa algorithms for saddle point problems[J]. SIAM J Numer Anal,1994,31:1645-1661.

[4] FISCHER B, RAMAGE A, SILVESTER D J, et al. Minimum residual methods for augmented systems[J]. BIT,1998,38:527-543.

[5] ARIOLI M, DUFF I S, de RIJK P P M. On the augmented system approach to sparse least-squares problems[J].Numer Math,1989,55:667-684.

[6] SANTOS C H, SILVA B P B, YUAN Y F. Block SOR methods for rank deficient least squares problems[J]. J Comput Appl Math,1998,100:1-9.

[7] YUAN J Y. Numerical methods for generalized least squares problems[J]. J Comput Appl Math,1996,66:571-584.

[8] YUAN J Y, IUSEM A N. Preconditioned conjugate gradient method for generalized least squares problems[J]. J Comput Appl Math,1996,71:287-297.

[9] GOLUB G H, WU X, YUAN J Y. SOR-like methods for augmented systems[J]. BIT,2001,55:71-85.

[10] DARVISHI M T, HESSARI P. Symmetric SOR method for augmented systems[J]. Appl Math Comput,2006,183:409-415.

[11] BAI Z Z, PARLETT B N, WANG Z Q. On generalized successive overrelaxation methods for augmented linear systems[J]. Numer Math,2005,102:1-38.

[12] BAI Z Z, WANG Z Q. On parameterized inexact Uzawa methods for generalized saddle point problems[J]. Linear Algebra Appl,2008,428:2900-2932.

[13] CHEN F, JIANG Y L. A generalization of the inexact parameterized Uzawa methods for saddle point problems[J]. Appl Math Comput,2008,206:765-771.

[14] ZHENG B, BAI Z Z, YANG X. On semi-convergence of parameterized Uzawa methods for singular saddle point problems[J]. Linear Algebra Appl,2009,431:808-817.

[15] ZHANG G F, LU Q H. On generalized symmetric SOR method for augmented systems[J]. J Comput Appl Math,2008,1(15):51-58.

[16] PENG X F, LI W. On unsymmetric block overrelaxation-type methods for saddle point[J]. Appl Math Comput,2008,203(2):660-671.

[17] BAI Z Z, YANG X. On HSS-based iteration methods for weakly nonlinear systems[J]. Appl Numer Math,2009,59:2923-2936.

[18] BAI Z Z, GOLUB G H, MICHAEL K N. On inexact hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems[J]. Linear Algebra Appl,2008,428:413-440.

[19] BAI Z Z. Several splittings for non-Hermitian linear systems[J]. Science in China(Ser A): Math,2008,51:1339-1348.

[20] BAI Z Z, GOLUB G H, LU L Z, et al. Block-Triangular and skew-Hermitian splitting methods for positive definite linear systems[J]. SIAM J Sci Comput,2005,26:844-863.

[21] BAI Z Z, GOLUB G H, NG M K. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems[J]. SIAM J Matrix Anal A,2003,24:603-626.

[22] JIANG M Q, CAO Y. On local Hermitian skew-Hermitian splitting iteration methods for generalized saddle point problems[J]. J Comput Appl Math,2009,231:973-982.

[23] WANG L, BAI Z Z. Convergence conditions for splitting iteration methods for non-Hermitian linear systems[J]. Linear Algebra Appl,2008,428:453-468.

[24] WU S L, HUANG T Z, ZHAO X L. A modified SSOR iterative method for augmented systems[J]. J Comput Appl Math,2009,228(1):424-433.

[25] BAI Z Z, ZHANG S L. A regularized conjugate gradient method for symmetric positive definite system of linear equations[J]. J Comput Math,2002,20:437-448.

[26] BAI Z Z, YIN J F, SU Y F. A shift-splitting preconditioner for non-Hermitian positive definite matrices[J]. J Comput Math,2006,24:539-552.

[27] CAO Y, DU J, NIU Q. Shift-splitting preconditioners for saddle point problems[J]. J Comput Appl Math,2014,272:239-250.

[28] CHEN C R, MA C F. A generalized shift-splitting preconditioner for saddle point problems[J]. Appl Math Lett,2015,43:49-55.

[29] CAO Y, LI S, YAO L Q. A class of generalized shift-splitting preconditioners for nonsymmetric saddle point problems[J]. Math Numer Sinica,2015,49:20-27.

[30] VAN der VIRST H A. Iterative Krylov Methods for Large Linear Systems[M]//Cambridge Monographs on Applied and Computational Mathematics. Cambridge: Cambridge University Press,2009.

[31] CAO Y, TAO H R, JIANG M Q. Generalized shift splitting preconditioners for saddle point problems[J]. Math Numer Sinica,2014,36:16-26.

[32] HENRICI P. Applied and Computational Complex Analysis[M]. New York: Wiley,1974.

[33] BAI Z Z, GOLUB G H, LI G K. Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two by-two block matrices[J]. SIAM J Sci Comput,2006,28:583-603.

[34] BAI Z Z, GOLUB G H, NG M K. On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations[J]. Numer Linear Algebra Appl,2007,14:319-335.

[35] BAI Z Z, GOLUB G H, PAN J Y. Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems[J]. Numer Math,2004,98:1-32.

[36] BAI Z Z, NG M K. On inexact preconditioners for nonsymmetric matrices[J]. SIAM J Sci Comput,2005,26:1710-1724.

[37] BAI Z Z, NG M K, WANG Z Q. Constraint preconditioners for symmetric indefinite matrices[J]. SIAM J Matrix Anal Appl,2009,31:410-433.

[38] BAI Z Z. Optimal parameters in the HSS-like methods for saddle-point problems[J]. Numer Linear Algebra Appl,2009,16:447-479.

[39] BAI Z Z, GOLUB G H, PAN J Y. Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems[R]//Technical Report SCCM-02-12, Scientific Computing and Computational Mathematics Program. Stanford: Department of Computer Science, Stanford University,2002.

[40] CAO Y, YAO L Q, JIANG M Q. A modified dimensional split preconditioner for generalized saddle point problems[J]. J Comput Appl Math,2013,250:70-82.

[41] CAO Y, YAO L Q, JIANG M Q, et al. A relaxed HSS preconditioner for saddle point problems from meshfree discretization[J]. J Comput Math,2013,31:398-421.

[42] YOUNG D M. Iterative Solution for Large Systems[M]. New York: Academic Press,1971.

[43] ZHANG L T. A new preconditioner for generalized saddle matrices with highly singular(1,1) blocks[J]. Int J Comput Math,2014,91(9):2091-2101.

[44] ZHANG L T, HUANGG T Z, CHENG S H, et al. Convergence of a generalized MSSOR method for augmented systems[J]. J Comput Appl Math,2012,236:1841-1850.

ZHANG Litao1, GU Tongxiang2, MENG Huili3*

(1. College of Science, Zhengzhou University of Aeronautics, Zhengzhou 450015, China; 2. Laboratory of ComputationaryPhysics, Institute of Applied Physics and Computational Mathematics, Beijing 100088, China; 3. College of Computerand Information Engineering, Henan Normal University, Xinxiang 453007, Henan Province, China)

最近，曹等提出了解非對稱正定(1,1)-塊鞍點(diǎn)問題的廣義交替分裂預(yù)處理子.確立了一類參數(shù)交替分裂預(yù)處理子.針對新預(yù)處理鞍點(diǎn)矩陣，取得了一些有意義的性質(zhì)，這與廣義交替分裂預(yù)處理子有交集.

非對稱鞍點(diǎn)問題；參數(shù)化交替分裂；收斂性；預(yù)處理子；特征值

TP 391.7

A

1008-9497(2017)02-168-07

Foundation item:Supported by NSFC(11226337，11501525)； Science Technology Innovation Talents in Universities of Henan Province(16HASTIT040)；Project of Youth Backbone Teachers of Colleges and Universities in Henan Province(2013GGJS-142,2015GGJS-179)； ZZIA Innovation Team Fund(2014TD02)；Natural Science Foundation of Zhengzhou City(141PQYJS560).

10.3785/j.issn.1008-9497.2017.02.008

張理濤1，谷同祥2，孟慧麗3

(1.鄭州航空工業(yè)管理學(xué)院 理學(xué)院， 河南 鄭州 450015；2.北京應(yīng)用物理與計算數(shù)學(xué)研究所 計算物理實(shí)驗(yàn)室，北京 100088；3.河南師范大學(xué) 計算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007)

Received date：April 8, 2016.

About the author:ZHANG Litao(1980-)，ORCID:http://orcid.org/0000-0002-6087-8611, male, PhD, associate professor, the field of interest is computing mathematics, E-mail:litaozhang@163.com.

*Corresponding author, ORCID: http://orcid.org/0000-0002-6476-3678, E-mail:menghuili93@163.com.

解非對稱鞍點(diǎn)問題的廣義交替分裂預(yù)處理子的一個注記.浙江大學(xué)學(xué)報(理學(xué)版),2017,44(2):168-173,190