On semi-convergence of Hermitian and skew-Hermitian

Computing(2010)89:171–197

DOI10.1007/s00607-010-0101-4

Onsemi-convergenceofHermitianandskew-Hermitiansplittingmethodsforsingularlinearsystems

Zhong-ZhiBai

Received:10August2009/Accepted:7June2010/Publishedonline:6July2010

©Springer-Verlag2010

AbstractForthesingular,non-Hermitian,andpositivesemidefinitesystemsoflinearequations,wederivenecessaryandsuf?cientconditionsforguaranteeingthesemi-convergenceoftheHermitianandskew-Hermitiansplitting(HSS)iterationmethods.Wetheninvestigatethesemi-convergencefactorandestimateitsupperboundfortheHSSiterationmethod.Ifthesemi-convergenceconditionissatis?ed,itisshownthatthesemi-convergencerateisthesameasthatoftheHSSiterationmethodappliedtoalinearsystemwiththecoef?cientmatrixequaltothecompressionoftheoriginalmatrixontherangespaceofitsHermitianpart,thatis,thematrixobtainedfromtheoriginalmatrixbyrestrictingthedomainandprojectingtherangespacetotherangespaceoftheHermitianpart.Inparticular,anupperboundisobtainedintermsofthelargestandthesmallestnonzeroeigenvaluesoftheHermitianpartofthecoef?-cientmatrix.Inaddition,applicationsoftheHSSiterationmethodasapreconditionerforKrylovsubspacemethodssuchasGMRESareinvestigatedindetail,andsev-eralexamplesareusedtoillustratethetheoreticalresultsandexaminethenumericalCommunicatedbyC.C.Douglas.

SupportedbyTheNationalBasicResearchProgram(No.2005CB321702),TheChinaOutstandingYoungScientistFoundation(No.10525102)andTheNationalNaturalScienceFoundation(No.10471146),People’sRepublicofChina.

Z.-Z.Bai

SchoolofMathematicsandComputerScience,GuizhouNormalUniversity,

550001Guiyang,People’sRepublicofChina

Z.-Z.Bai(B)

StateKeyLaboratoryofScienti?c/EngineeringComputing,InstituteofComputational

MathematicsandScienti?c/EngineeringComputing,AcademyofMathematics

andSystemsScience,ChineseAcademyofSciences,P.O.Box2719,

100190Beijing,People’sRepublicofChina

e-mail:bzz@http://wendang.chazidian.com

123

172Z.-Z.BaieffectivenessoftheHSSiterationmethodservedeitherasapreconditionerforGMRESorasasolver.

KeywordsSingularlinearsystem·Non-Hermitianmatrix·Positivesemidefinitematrix·Hermitianandskew-Hermitiansplitting·Splittingiterationmethod·Semi-convergence·Preconditioningmatrix·Krylovsubspacemethod

MathematicsSubjectClassi?cation(2000)

1Introduction

Weconsideraniterativesolutionofthelarge,sparse,non-Hermitianand,possibly,singularsystemoflinearequations

Ax=b,A∈Cn×n,A=A?,andx,b∈Cn,(1.1)65F10·65F50·CR:G1.3

whereA?denotestheconjugatetransposeofthecomplexmatrixA;see[17–19,25].BasedontheHermitianandskew-Hermitian(HS)splitting

A=H(A)+S(A),withH(A)=11(A+A?)andS(A)=(A?A?),22

Baietal.[7]establishedthefollowingHermitianandskew-Hermitiansplitting(HSS)iterationmethodforsolvingthenon-Hermitiansystemoflinearequations(1.1).

TheHSSIterationMethod.Givenaninitialguessx(0)∈Cn,com-putex(k)fork=0,1,2,http://wendang.chazidian.comingthefollowingiterationsch-emeuntil{x(k)}satisfiesthestoppingcriterion:

??(αI+H(A))x(k+)=(αI?S(A))x(k)+b,

(αI+S(A))x(k+1)=(αI?H(A))x(k+)+b,

whereαisagivenpositiveconstantandI∈Cn×ntheiden-titymatrix.

Whenthecoef?cientmatrixA∈Cn×nispositivedefinite,i.e.,itsHermitianpartH(A)∈Cn×nisHermitianpositivedefinite,Baietal.provedin[7]thattheHSSiterationconvergesunconditionallytotheexactsolutionofthesystemoflinearequa-tions(1.1),withtheboundontherateofconvergenceaboutthesameasthatoftheconjugategradientmethodwhenappliedtotheHermitianmatrixH(A):indeedbythemixing-upeffectdescribedin[14,Sect.2.1.3]thegivenboundsofconvergenceratescouldbeverypessimistic,asalreadyobservedin[7].Moreover,anupperboundofthecontractionfactorisobtainedintermsofthelargestandthesmallestnonzeroeigen-valuesofH(A).NumericalexperimentshaveshownthattheHSSiterationmethodisef?cientandrobustforsolvingnon-Hermitianpositivedefinitelinearsystems.Whenthecoef?cientmatrixA∈Cn×nisnonsingularandpositivesemidefinite,i.e.,itsHermitianpartH(A)∈Cn×nisHermitianpositivesemidefinite,Baietal.[5]11123

Onsemi-convergenceofHSSmethod173provedthattheHSSiterationisconvergentifandonlyifAdoesnothavea(reducing)eigenvalueoftheform?ξwithξ∈Rand?theimaginaryunit,orequivalently,thenullspaceofH(A),denotedasnull(H(A)),doesnotcontainaneigenvectorofS(A).Thisresultimmediatelyleadstoanecessaryandsuf?cientconditionforguaranteeingtheunconditionalconvergenceoftheHSSiterationmethodwhenitisusedtosolvethesaddle-pointproblem

??

Ax≡BE??EC??????????yf=≡b,zg

whereB∈Cp×pispositivedefinite,C∈Cq×qisHermitianpositivesemidefinite,E∈Cp×qisoffullcolumnrank,andp≥q.NotethattheconvergencetheoremgiveninBenziandGolub[12]isaspecialcaseofthisresult;seealso[3,10]andreferencestherein.

Inthispaper,wegiveanecessaryandsuf?cientconditionforanarbitrarysingu-lar,non-Hermitian,andpositivesemidefinitelinearsystemsothattheHSSiterationmethodwillleadtoasemi-convergentiterationsequence.Inparticular,thisresultimmediatelygivesanecessaryandsuf?cientconditionforguaranteeingthesemi-convergenceoftheHSSiterationmethodappliedtothesaddle-pointproblemofasingularandpositivesemidefinitecoef?cientmatrix.Wetheninvestigatethesemi-convergencefactorandestimateitsupperboundfortheHSSiterationmethod.Itisshownthatthesemi-convergencerateoftheHSSiterationmethodisaboutthesameasthatoftheconjugategradientmethodappliedtothesymmetrizedlinearsystemofthecoef?cientmatrixbeingH(A).Moreover,anupperboundofthesemi-conver-gencefactorisobtainedintermsofthelargestandthesmallestnonzeroeigenvaluesofH(A).Inaddition,weinvestigatethepreconditioningpropertyoftheHSSpre-conditionerinducedfromtheHSSiterationmethodand,inparticular,wediscussthesemi-convergencebehavioroftheHSS-preconditionedGMRESmethod.Severalexamplesarisingfromthe?nitedifferencediscretizationsofsecond-orderdifferentialequationsofperiodicboundaryconditionsareusedtoillustratethetheoreticalresultsandexaminethecomputationaleffectivenessoftheHSSiterationmethodservedeitherasapreconditionerforGMRESorasasolver.

2Notationsandconcepts

ForamatrixW∈Cn×n,rank(W)andindex(W)areusedtorepresentitsrankandindex,respectively.FortwomatricesA1andA2ofsuitabledimensions,weuseA1⊕A2todenotetheirdirectsum,i.e.,

??

A1⊕A2=A10

0A2??.

AssumethatamatrixA∈Cn×ncanbesplitas

A=M?N,(2.2)

123

174Z.-Z.BaiwithM∈Cn×nnonsingular.Thenwecanconstructasplittingiterationmethodas

x(k+1)=Tx(k)+c,k=0,1,2,...,(2.3)

whereT=M?1Nistheiterationmatrix,andc=M?1b.Obviously,avectorx∈Cnisasolutionofthelinearsystem(1.1)ifandonlyif(I?T)x=c;see[13,18].

Theconvergenceandsemi-convergenceoftheiterativescheme(2.3)havebeenstudiedextensively;see,e.g.,[11,13,22,24].WhenAissingular,then1isaneigen-valueoftheiterationmatrixT.Moreover,whenthespectralradiusoftheiterationmatrixTisequaltoone,i.e.,ρ(T)=1,thefollowingtwoconditionsarenecessaryandsuf?cientforguaranteeingthesemi-convergenceoftheiterativemethod(2.3):(a)TheelementarydivisorsoftheiterationmatrixTassociatedwithitseigenvalue

μ=1arelinear;(b)Ifμ∈σ(T),thespectrumoftheiterationmatrixT,satisfying|μ|=1,thenμ=1,i.e.,?(T)<1,where

?(T)≡max{|μ||μ∈σ(T),μ=1}.

WeremarkthatforanonsingularmatrixA,thesemi-convergenceconceptofthecor-respondinglyinducedmatrixsplittingoriterationmatrixcoincideswiththestandardconvergenceconcept.

From[13]weknowthatthesplitting(2.2)orthecorrespondingiterationmatrixTiscalledsemi-convergent,iftheiteration(2.3)issemi-convergent.Inthiscase,wede?ne?(T)asthesemi-convergencefactoroftheiteration(2.3).

TheHSSiterationmethodcanberewritteninmatrix-vectorformas

x(k+1)=T(α)x(k)+G(α)b,

where

T(α)=(αI+S(A))?1(αI?H(A))(αI+H(A))?1(αI?S(A))

and

G(α)=2α(αI+S(A))?1(αI+H(A))?1.

Here,T(α)istheiterationmatrixoftheHSSiterationmethod.NotethatT(α)issimilartothematrix

L(α)=(αI+H(A))?1(αI?H(A))(αI+S(A))?1(αI?S(A)).

Infact,(2.4)mayalsoresultfromthesplitting

A=M(α)?N(α)(2.6)(2.5)k=0,1,2,...,(2.4)

123

Onsemi-convergenceofHSSmethod175ofthecoef?cientmatrixA,with

??M(α)=N(α)=1(αI1(αI+H(A))(αI+S(A)),?H(A))(αI?S(A)).

Evidently,theHSSiterationmethodcannaturallyinduceapreconditionerM(α)tothematrixA.ThispreconditioneriscalledastheHSSpreconditioner;see[3,10,12].Forothertypesofpreconditionersaboutanon-Hermitianmatrix,wereferto[15,16,19,25].

3Thesemi-convergenceoftheHSSiterationmethod

We?rstrevealabasicrelationshipbetweenasingularmatrixanditsHermitianandskew-Hermitianparts.

Lemma3.1LetA∈Cn×nbeasingularandpositivesemidefinitematrix,andH(A)andS(A)beitsHermitianandskew-Hermitianparts,respectively.Then

null(A)=null(H(A))∩null(S(A)).

ProofEvidently,

null(H(A))∩null(S(A))?null(A).

Hence,weonlyneedtodemonstratetheinclusionrelationship

null(A)?null(H(A))∩null(S(A)).

Infact,foranx∈null(A)wehave

0=Ax=H(A)x+S(A)x.

Let

x?H(A)x+x?S(A)x=μ+?ν,

withμ,ν∈R.Then

x?H(A)x=μ=0.

SinceH(A)isHermitianpositivesemidefinite,x?H(A)x=0impliesH(A)x=0.Thus,byusing(3.7),weimmediatelygetS(A)x=Ax?H(A)x=0.Hence,x∈null(H(A))∩null(S(A)).????FromLemma3.1,wegetthefollowingconclusion.(3.7)

123