Iterative methods for linear systems

IterativeMethodsforLinearSystemsHowardC.Elman1DepartmentofComputerScienceandInstituteforAdvancedComputerStudiesUniversityofMarylandCollegePark,[e-mail]overviewofsomeoftheimportanttechniquesusedtosolvelinearsystemsofequationsAx=b(1)byiterativemethods.Weconsidermethodsbasedontwogeneralideas,splittingsofthecoecientmatrix,leadingtostationaryiterativemethods,andKrylovsubspacemethods.Thesetwoideascanalsobecombinedtoproducepreconditionediterativemethods.Inaddition,weoutlinesomeconvergenceresultsforusingthemethodsconsideredtosolvetwoclassesofmodelproblemsarisingfromellipticpartialdierentialequations.Inx1,weintroducethebasicideasofstationaryiterativemethodsandconsiderseveralpartic-ularexamplesofsuchmethods:theJacobi,Gauss-Seidel,SORandSSORmethods.Weoutlinesomeresultsonconvergenceofthesemethods,forbothgeneralmatricesandthosewithspe-cialstructure.Inx2,wegiveanoverviewofKrylovsubspacemethodsforsystemswherethecoecientmatrixissymmetric.Theseincludetheconjugategradientmethodforsymmetricpositive-denitesystems,andseveralgeneralizatonsofthistechniqueforthesymmetricinde-nitecase.Inx3,weexaminetheuseofKrylovsubspacemethodsfornonsymmetricproblems.Thisisanactiveareaofcurrentresearch,andwehighlightGMRES,themostpopularmethodincurrentuse,togetherwiththeQMRmethod,oneofseveralnewideasbeingstudied.Inx4,wepresentseveralpreconditioningtechniquesthatcanbeusedincombinationwithKrylovsubspacemethods.Ouremphasishereismethodssuchasincompletefactorizationsthataredenedpurelyintermsofthealgebraicstructureofthecoecientmatrix.Inx5,weoutlinetheconvergencepropertiesofthemethodspresentedfortwoclassesofmodelproblems,thediscretePoissonequa-tion,whichissymmetricpositive-denite,andthediscreteconvection-diusionequation,whichisnonsymmetric.Finally,inx6,wepresentabriefdiscussionofseveralimportanttopicsthatwehavenotconsideredhere.Beforeproceeding,weintroduceseveralpointsofnotation.WewillassumethatAisanonsingularrealmatrixofordern.Allthemethodsconsideredgenerateasequenceofiteratesx(k)thatareintendedtoconvergetox=A1b.Theyallrequireastoppingcriterionthatcanbeusedtodeterminewhentheiterateissucientlyaccurate.Wewillnotaddressthisquestioninanydetail,excepttonotethattheresidualr(k)=bAx(k)iseasilycomputable;acommonlyusedstoppingcriterionistorequirethattherelativeresidualkr(k)k=kbkbesmallerthansometolerance,wherek:kissomevectornorm.Throughoutthischapter,wewilluse(v;w)torepresenttheEuclideaninnerproductPnj=1vjwj,andkvk2=(v;v)1=2todenotetheEuclidean1ThisworkwassupportedbytheU.S.ArmyResearchOceundergrantDAAL-0392-G-0016,andbytheNationalScienceFoundationundergrantsASC-8958544andCCR-8818340.1norm.Manyofthemethodsunderconsiderationcomputethisnormoftheresidual,kr(k)k,aspartoftheiteration.Essentiallyalloftheresultspresentedherecarryovertocomplexsystemsofequationswherecomplexinnerproductsareusedinplaceofrealinnerproducts.1.StationaryMethods.Inthissection,wegiveabriefoverviewofstationarymethodsforsolving(1).Methodsofthistype,suchasrelaxationmethods,werethemostwidelyusedexamplesofiterativemethodswhenlargecomputersrstbecameavailable.(See[79,80]forahistoricalperspective.)Tosomeextent,theyarenowsomewhatlesspopularthanthemethodsdiscussedinxx2and3,althoughtheeasewithwhichtheycanimplementedandtheirusesinthecontextofpreconditionerscontinuetomakethemanimportanttopicofstudy.1.1.BasicPrinciples.AsplittingofthecoecientmatrixAisarepresentationofAintheformA=MN:(2)Theproblem(1)isthenequivalenttoMx=Nx+b.Thissuggests,fornonsingularM,thestationarymethodforconstructingasequenceofapproximatesolutionsto(1),x(k+1)=M1Nx(k)+M1b:(3)Here,x(0)isa(possiblyarbitrary)initialguessforthesolution.The\classicalJacobi,Gauss-Seidelandsuccessiveoverrelaxationmethods[74,78]areexamplesofsuchmethods.Lete(k)=xx(k)denotetheerroratthek’thstep.Wesaythatthemethod(3)iscon-vergentiflimk!1e(k)=0.Notethate(k)=Gke(0),whereG=M1Nistheiterationmatrix.Consequently,foranyconsistentmatrixnormkk,theerrorsatiseske(k)k=kGke(0)kkGkkke(0)k;(4)andthenormoftheerrortendstozeroifkGkk!0.Unfortunately,itisusuallydiculttoderiveanalyticboundsonkGkk,andanalysisofiterativemethodstypicallymakesuseofthefollowingresult[74].Theorem1.1.ThenormkGkk!0ifandonlyif(G)1.Moreover,kGkkc(k)(G)kwherec(k)isapolynomialink.Here,(G)=maxfjj:isaneigenvalueofGg.Thatis,themethodisconvergentforarbitraryinitialguessesprovidedthatthelargesteigenvalueoftheiterationmatrixhasmoduluslessthanone.Thesecondassertionstatesthatconvergenceisinsomesensecharacterizedbythiseigenvalue.Inparticular,ifourgoalistomakeke(k)k=ke(0)kforsomesmall,thenfrom(4),itissucienttoperformenoughiterationssuchthatkGkk.Inlightofthetheorem,thissuggeststhatkshouldsatisfyloglogc(k)+klog(G)klog(G)forlargek;i.e.kjlogj=jlog(G)j(5)2iterationswillsuce.Wewillconsiderexamplesofstationarymethodsusingavariantofthecomputation(3).WehaveMx(k+1)=Nx(k)+b=Mx(k)+b(MN)x(k);sothatx(k+1)=x(k)+M1r(k):(6)Thisexpressiondeterminesanimplementionthatautomaticallyprovidestheresidualvector,r(k),whichisoftenusedinthestoppingcriterionforaniterativemethod