您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > Iterative methods for linear systems
IterativeMethodsforLinearSystemsHowardC.Elman1DepartmentofComputerScienceandInstituteforAdvancedComputerStudiesUniversityofMarylandCollegePark,MD20742elman@cs.umd.eduThischaptercontainsanoverviewofsomeoftheimportanttechniquesusedtosolvelinearsystemsofequationsAx=b(1)byiterativemethods.Weconsidermethodsbasedontwogeneralideas,splittingsofthecoe cientmatrix,leadingtostationaryiterativemethods,andKrylovsubspacemethods.Thesetwoideascanalsobecombinedtoproducepreconditionediterativemethods.Inaddition,weoutlinesomeconvergenceresultsforusingthemethodsconsideredtosolvetwoclassesofmodelproblemsarisingfromellipticpartialdi erentialequations.Inx1,weintroducethebasicideasofstationaryiterativemethodsandconsiderseveralpartic-ularexamplesofsuchmethods:theJacobi,Gauss-Seidel,SORandSSORmethods.Weoutlinesomeresultsonconvergenceofthesemethods,forbothgeneralmatricesandthosewithspe-cialstructure.Inx2,wegiveanoverviewofKrylovsubspacemethodsforsystemswherethecoe cientmatrixissymmetric.Theseincludetheconjugategradientmethodforsymmetricpositive-de nitesystems,andseveralgeneralizatonsofthistechniqueforthesymmetricinde -nitecase.Inx3,weexaminetheuseofKrylovsubspacemethodsfornonsymmetricproblems.Thisisanactiveareaofcurrentresearch,andwehighlightGMRES,themostpopularmethodincurrentuse,togetherwiththeQMRmethod,oneofseveralnewideasbeingstudied.Inx4,wepresentseveralpreconditioningtechniquesthatcanbeusedincombinationwithKrylovsubspacemethods.Ouremphasishereismethodssuchasincompletefactorizationsthatarede nedpurelyintermsofthealgebraicstructureofthecoe cientmatrix.Inx5,weoutlinetheconvergencepropertiesofthemethodspresentedfortwoclassesofmodelproblems,thediscretePoissonequa-tion,whichissymmetricpositive-de nite,andthediscreteconvection-di usionequation,whichisnonsymmetric.Finally,inx6,wepresentabriefdiscussionofseveralimportanttopicsthatwehavenotconsideredhere.Beforeproceeding,weintroduceseveralpointsofnotation.WewillassumethatAisanonsingularrealmatrixofordern.Allthemethodsconsideredgenerateasequenceofiteratesx(k)thatareintendedtoconvergetox=A 1b.Theyallrequireastoppingcriterionthatcanbeusedtodeterminewhentheiterateissu cientlyaccurate.Wewillnotaddressthisquestioninanydetail,excepttonotethattheresidualr(k)=b Ax(k)iseasilycomputable;acommonlyusedstoppingcriterionistorequirethattherelativeresidualkr(k)k=kbkbesmallerthansometolerance,wherek:kissomevectornorm.Throughoutthischapter,wewilluse(v;w)torepresenttheEuclideaninnerproductPnj=1vjwj,andkvk2=(v;v)1=2todenotetheEuclidean1ThisworkwassupportedbytheU.S.ArmyResearchO ceundergrantDAAL-0392-G-0016,andbytheNationalScienceFoundationundergrantsASC-8958544andCCR-8818340.1norm.Manyofthemethodsunderconsiderationcomputethisnormoftheresidual,kr(k)k,aspartoftheiteration.Essentiallyalloftheresultspresentedherecarryovertocomplexsystemsofequationswherecomplexinnerproductsareusedinplaceofrealinnerproducts.1.StationaryMethods.Inthissection,wegiveabriefoverviewofstationarymethodsforsolving(1).Methodsofthistype,suchasrelaxationmethods,werethemostwidelyusedexamplesofiterativemethodswhenlargecomputers rstbecameavailable.(See[79,80]forahistoricalperspective.)Tosomeextent,theyarenowsomewhatlesspopularthanthemethodsdiscussedinxx2and3,althoughtheeasewithwhichtheycanimplementedandtheirusesinthecontextofpreconditionerscontinuetomakethemanimportanttopicofstudy.1.1.BasicPrinciples.Asplittingofthecoe cientmatrixAisarepresentationofAintheformA=M N:(2)Theproblem(1)isthenequivalenttoMx=Nx+b.Thissuggests,fornonsingularM,thestationarymethodforconstructingasequenceofapproximatesolutionsto(1),x(k+1)=M 1Nx(k)+M 1b:(3)Here,x(0)isa(possiblyarbitrary)initialguessforthesolution.The\classicalJacobi,Gauss-Seidelandsuccessiveoverrelaxationmethods[74,78]areexamplesofsuchmethods.Lete(k)=x x(k)denotetheerroratthek’thstep.Wesaythatthemethod(3)iscon-vergentiflimk!1e(k)=0.Notethate(k)=Gke(0),whereG=M 1Nistheiterationmatrix.Consequently,foranyconsistentmatrixnormk k,theerrorsatis eske(k)k=kGke(0)k kGkkke(0)k;(4)andthenormoftheerrortendstozeroifkGkk!0.Unfortunately,itisusuallydi culttoderiveanalyticboundsonkGkk,andanalysisofiterativemethodstypicallymakesuseofthefollowingresult[74].Theorem1.1.ThenormkGkk!0ifandonlyif (G)1.Moreover,kGkk c(k) (G)kwherec(k)isapolynomialink.Here, (G)=maxfj j: isaneigenvalueofGg.Thatis,themethodisconvergentforarbitraryinitialguessesprovidedthatthelargesteigenvalueoftheiterationmatrixhasmoduluslessthanone.Thesecondassertionstatesthatconvergenceisinsomesensecharacterizedbythiseigenvalue.Inparticular,ifourgoalistomakeke(k)k=ke(0)k forsomesmall ,thenfrom(4),itissu cienttoperformenoughiterationssuchthatkGkk .Inlightofthetheorem,thissuggeststhatkshouldsatisfylog logc(k)+klog (G) klog (G)forlargek;i.e.k jlog j=jlog (G)j(5)2iterationswillsu ce.Wewillconsiderexamplesofstationarymethodsusingavariantofthecomputation(3).WehaveMx(k+1)=Nx(k)+b=Mx(k)+b (M N)x(k);sothatx(k+1)=x(k)+M 1r(k):(6)Thisexpressiondeterminesanimplementionthatautomaticallyprovidestheresidualvector,r(k),whichisoftenusedinthestoppingcriterionforaniterativemethod
本文标题:Iterative methods for linear systems
链接地址:https://www.777doc.com/doc-3710105 .html