trigonometric transform splitting methods for real symmetric toeplitz systems zhongyun liu资料.pdf

该【trigonometric transform splitting methods for real symmetric toeplitz systems zhongyun liu资料 】是由【小舍儿】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【trigonometric transform splitting methods for real symmetric toeplitz systems zhongyun liu资料 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..ComputersandMathematicswithApplications()–ContentslistsavailableatScienceDirectComputersandMathematicswithApplicationsjournalhomepage:ate/camwaTrigonometrictransformsplittingmethodsforrealsymmetricToeplitzsystemsZhongyunLiua,*,NianciWua,XiaorongQina,YulinZhangbaSchoolofMathematicsandStatistics,ChangshaUniversityofScienceandTechnology,Changsha410076,PRChinabCentrodeMatemática,UniversidadedoMinho,4710-057Braga,PortugalarticleinfoabstractArticlehistory:InthispaperwestudyefficientiterativemethodsforrealsymmetricToeplitzsystemsbasedReceived7February2017onthetrigonometrictransformationsplitting(TTS)×nToeplitzmatrixAccepted4January2018Aisarealpositiveevenfunction,,wederiveanKeywords:(2003)inwhichalloperationscountsplexoperationswhentheDFTsareemployed,eveniftheToeplitzmatrixIterativemethodsAisrealandsymmetric,-symmetricsplitting(PSS)iterativemethodinBaietal.(2005)andthesymmetricGauss–Seidel(SGS)iterativemethod.?=b()bythetwo-stepsplittingiterationwithalternation,whereb∈RnandA∈Rn×,aToeplitzmatrixAisgeneratedbyafunctionf(x)∈C2π,.,[A]m,k=am?k,where∫π1?ikθak=f(θ)edθ,k=0,±1,±2,...()2π?,putingandengineering,forinstance,imagerestorationstorageproblemsinsignalprocessing,algebraicdifferentialequation,,[1–3]andreferencestherein.*-mailaddresses:liuzhongyun@(),******@().https:///.-1221/?:,etal.,putersandMathematicswithApplications(2018),https:///..:.../ComputersandMathematicswithApplications()–Iterativemethodsforthelinearsystemofequations(),theJacobiandtheGauss–Seideliterations[3,4]splitthematrixAintoitsdiagonalpartD,andstrictlylowertriangularpartLanduppertriangularpartU,respectively,andthegeneralizedconjugategradient(CG)methodandthegeneralizedLanczosmethodsplitsthematrixAintoitsHermitianandskew-Hermitianparts,seeforexample[5]-Hermitiansplitting(HSS)A+A?A?A?A=H+SwithH=andS=.()[5]tosolvethenon-(0).Fork=0,1,2,...until{x(k)}pute{1(αI+H)x(k+2)=(αI?S)x(k)+b(k+1)(k+1)()(αI+S)x=(αI?H)x2+b,,eachiterateoftheHSSiterationalternatesbetweentheHermitianpartHandtheskew-HermitianpartSofthematrixA,analogouslytotheclassicalalternatingdirectionimplicititeration(ADI)introducedbyPeacemanandRachfordforsolvingpartialdifferentialequations,see[4,6].ResultsassociatedtothestationaryiterativemethodwithalternationcanbealsofoundinBenziandSzyld[7].TheoreticalanalysisshowsthattheHSSiteration()convergesunconditionallytotheuniquesolutionofthesystemoflinearequations(),ifthecoefficientmatrixAisanon-,theHSSschemeimmediatelyattractedconsiderableattention,resultinginnumerouspapersdevotedtovariousaspectsofthisnewmethod,seeforinstance[8–17],GuandTianin[16]andChenandJiangin[15](),putationalcostsremainO(n2),becauseeveryn×nToeplitzmatrixAenjoysacirculantandskew-circulantsplittingA=C+S(denotedbyCSCS)whichresultsinthefollowingCSCSiterationproposedbyNgin[18]fornon-(0).Fork=0,1,2,...until{x(k)}pute{1(αI+C)x(k+2)=(αI?S)x(k)+b(k+1)(k+1)()(αI+S)x=(αI?C)x2+b,,thematricesαI±CandαI±Sarecirculantmatricesandskew-circulantmatrices,respectively,whichcanbediagonalizedbythediscreteFouriermatrixFandF?,whereF?=F?with?adiagonalmatrix;seeforexample[2,3,19].Thus,thecostofeachiterationin()isO(plexflopsbyusing8FFTsofn-[18]thatiftherealpartofthegeneratingfunctionfispositive,,().Inparticular,ifthegeneratingfunctionfisrealpositiveeven,,wemayusetheCSCSiterationforsolvingthesystemoflinearequations(),(),,whichisreferredtoastrigonometrictransformsplittingandbrieflydenotedbyTTS,forsolving().,thendiscusstheconvergenceoftheTTSiteration,:,etal.,putersandMathematicswithApplications(2018),https:///..:.../ComputersandMathematicswithApplications()–,notationandpreliminariesusedinthesequel,see[20–22].ransform(DCT)I,thefirstransform(DST)matrixofordernbySI,thesetofalln-dimensionalrealvectorsbyRn,thesetofalln×nTnTn×nrealmatricesbyR,thetransposeofavectorxbyx,thetransposeofamatrixBbyB,theconjugatetransposeofamatrixBbyB?,the2-normby∥·∥2,thevector(1,1,...,1)Tofdimensionnbye,thevector(?1,1,...,(?1)n)Tbyf,the(q?p)×nrestrictionmatrixbyPpqdefinedbyPpq(x1,...,xn)T=(xp,...,xq)Tforp<q,√I2π(m+1)(k+1)[Sn]m,k=sin,m,k=0,1,...,n?1,()n+1n+1√I2πmk[Cn+2]m,k=εkεmcos,m,k=0,1,...,n+1,()n+1nwhere??1,ifj?=0andj?=n+1;εj=1()?√,ifj=0orj=n+√√LetDn+2=diag(1/2,1,...,1,1/2)beadiagonalmatrixofordern+√?2πmk(Cn)m,k=cos(),m,k=1,2,...,+1n+1Thenthematrix√I2πmkn+1Cn+2=Dn+2(cos())m,k=0Dn+2,()n+1n+1whichpossessthefollowingblockstructure?11T1?√2√2e22?√?CI=?√1en+1C?√1f?.()n+2n+1?22n2?1√1fT1(?1)n+1222Letan+2=[a0,a1,...,an+1]T∈Rn+=(λ0,...,λn+1)Tby√Iλ=2(n+1)Dn+2Cn+2Dn+2an+2,()([20,21]).Letλbedefinedasin().ThenarealsymmetricToeplitzmatrixAn=[a|i?j|]n?1admitsasplitting0An=TC+TS,()where11IITC=(C?nΛC?n+R2)andTS=(SnΛSn+R2)()22withΛ=diag(λ,...,λ)andR=λ0eeT+λn++1n+1NotethatbyAnwehaveonlygivenajforj=0,1,...,n?,wehavestillfreedominchoosinganandan+,ifwehavenofurtherinformation,wesetan=an+1=0orwecangetan,an+ordingto().Especially,itisalsopossibletochooseanandan+1suchthatλ0=λn+1=0,and()reducestoAn=1(SIΛSI+C?nΛC?n),forexample,[20](),(0).Fork=0,1,2,...until{x(k)}pute{(k+1)(k)(αI+TC)x2=(αI?TS)x+b1()(αI+TS)x(k+1)=(αI?TC)x(k+2)+b,:,etal.,putersandMathematicswithApplications(2018),https:///..:.../ComputersandMathematicswithApplications()–NotethatwecanreverserolesofthematricesTCandTSintheaboveTTSiterativemethodsothatwemayfirstsolvethesystemoflinearequationswithcoefficientmatrixαI+TSandthensolvethesystemoflinearequationswithcoefficientmatrixαI+()convergestotheuniquesolutionofthesystemoflinearequationsAx=b,-halfstepsateachTTSiterationrequireexactsolutionswiththen×nmatricesαI+TCandαI++TCandαI+TSarerealsymmetricpositivedefinitematriceswithToeplitz-plus-+TCandαI+,theresultingmethodissimilartotheIHSSiterationin[11],,–vectorform,x(k+1)=H(α)x(k)+G(α)b,k=0,1,...,()whereH(α)=(αI+TS)?1(αI?TC)(αI+TC)?1(αI?TS),()istheiterationmatrixoftheTTSiteration()andG(α)=2α(αI+T)?1(αI+T)?,()mayalsoresultfromthesplittingA=M(α)?N(α)ofthecoefficientmatrixA,with?1????M(α)=(αI+TC)(αI+TS)2α.????1N(α)=(αI?TC)(αI?TS)2αWenotethatH(α)=M?1(α)N(α),G(α)=M?1(α)andG(α)A=I?H(α).Ifρ(H(α))?1,thenthespectrumofthepreconditionedmatrixG(α),thepreconditionerG(α)couldbeservedasagoodpreconditioner,referredtoasTTSpreconditioner,forsolvingthelinearsystem()bythepreconditionedconjugategradientmethod(PCG).(αI+TC)?1,(αI+TS)?1,αI?TCandαI?(αI?TC)?????0?C?v?=CI?v?.nn+2?0Thus,(αI?TC)vcanbeeasilyobtainedfrom?????10?(αI?T)v?=CI(2αIn+2?Λn+2)CI?v?,C2n+2n+2?(αI?TC):puteu=CI(0,vT,0)T∈Rn++22:putew=(2αIn+2?Λn+2):putez=+24:putey=1P2,n+1z∈,pute(αI+TC)?,weneedtoembedαI+TCintoan(n+2)×(n+2)matrixMofthefollowingform1II+2(2αIn+2+Λn++2.()2Pleasecitethisarticleinpressas:,etal.,putersandMathematicswithApplications(2018),https:///..:.../ComputersandMathematicswithApplications()–5Asimplebuttediousstraightforwardcalculationshowsthat?T?γ1g1γ2M=?g1αI+TCg2?,()γ2gTγ32with1λ01λn+11λ01(?1)n+1λn+1γ1=α+(+eTΛe+),γ2=(+eTΛf+),n+1424n+1424√1λ01Tλn+11λ0n+1λn+1γ3=α+(+fΛf+),g1=(√e+C?nΛe+√f),n+1424n+122222√n+11λ0n+1(?1)λn+1g2=(√e+C?nΛf+√f).n+122222Clearly,theinverseofMin()canbeeasilysolved,onceαandΛn+(αI+TC)?1fromM?,letuspartitionMin()intothefollowingform?T?[]γ1g1γ2MtM=?gαI+Tg?≡11,1C2tTγ3γ2gTγ32[][]γ2n+1γ1gT1T1(n+1)×(n+1)wheret=∈R,M11=∈+TCIfM11isnonsingular,thenMisofthefollowing2×position[][]M=In+10M11t,tTM?110σ11whereσ=γ3?tTM?1t∈R,plementofthematrixMcorrespondingtothes