an-introduction-to-the-conjugate-gradient-method-w

AnIntroductiontotheConjugateGradientMethodWithouttheAgonizingPainEdition114JonathanRichardShewchukAugust4,1994SchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213AbstractTheConjugateGradientMethodisthemostprominentiterativemethodforsolvingsparsesystemsoflinearequations.Unfortunately,manytextbooktreatmentsofthetopicarewrittenwithneitherillustrationsnorintuition,andtheirvictimscanbefoundtothisdaybabblingsenselesslyinthecornersofdustylibraries.Forthisreason,adeep,geometricunderstandingofthemethodhasbeenreservedfortheelitebrilliantfewwhohavepainstakinglydecodedthemumblingsoftheirforebears.Nevertheless,theConjugateGradientMethodisacompositeofsimple,elegantideasthatalmostanyonecanunderstand.Ofcourse,areaderasintelligentasyourselfwilllearnthemalmosteffortlessly.TheideaofquadraticformsisintroducedandusedtoderivethemethodsofSteepestDescent,ConjugateDirections,andConjugateGradients.EigenvectorsareexplainedandusedtoexaminetheconvergenceoftheJacobiMethod,SteepestDescent,andConjugateGradients.OthertopicsincludepreconditioningandthenonlinearConjugateGradientMethod.Ihavetakenpainstomakethisarticleeasytoread.Sixty-sixillustrationsareprovided.Denseproseisavoided.Conceptsareexplainedinseveraldifferentways.Mostequationsarecoupledwithanintuitiveinterpretation.SupportedinpartbytheNaturalSciencesandEngineeringResearchCouncilofCanadaundera1967ScienceandEngineeringScholarshipandbytheNationalScienceFoundationunderGrantASC-9318163.Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthorandshouldnotbeinterpretedasrepresentingtheofficialpolicies,eitherexpressorimplied,ofNSERC,NSF,ortheU.S.Government.Keywords:conjugategradientmethod,preconditioning,convergenceanalysis,agonizingpainContents1.Introduction12.Notation13.TheQuadraticForm24.TheMethodofSteepestDescent65.ThinkingwithEigenvectorsandEigenvalues95.1.EigendoitifItry95.2.Jacobiiterations115.3.AConcreteExample126.ConvergenceAnalysisofSteepestDescent136.1.InstantResults136.2.GeneralConvergence177.TheMethodofConjugateDirections217.1.Conjugacy217.2.Gram-SchmidtConjugation257.3.OptimalityoftheErrorTerm268.TheMethodofConjugateGradients309.ConvergenceAnalysisofConjugateGradients329.1.PickingPerfectPolynomials339.2.ChebyshevPolynomials3510.Complexity3711.StartingandStopping3811.1.Starting3811.2.Stopping3812.Preconditioning3913.ConjugateGradientsontheNormalEquations4114.TheNonlinearConjugateGradientMethod4214.1.OutlineoftheNonlinearConjugateGradientMethod4214.2.GeneralLineSearch4314.3.Preconditioning47ANotes48BCannedAlgorithms49B1.SteepestDescent49B2.ConjugateGradients50B3.PreconditionedConjugateGradients51iB4.NonlinearConjugateGradientswithNewton-RaphsonandFletcher-Reeves52B5.PreconditionedNonlinearConjugateGradientswithSecantandPolak-Ribi`ere53CUglyProofs54C1.TheSolutiontoAxbMinimizestheQuadraticForm54C2.ASymmetricMatrixHasnOrthogonalEigenvectors.54C3.OptimalityofChebyshevPolynomials55DHomework56iiAboutthisArticleAnelectroniccopyofthisarticleisavailablebyanonymousFTPtoWARP.CS.CMU.EDU(IPaddress128.2.209.103)underthefilenamequake-papers/painless-conjugate-gradient.ps.APostScriptfilecontainingfull-pagecopiesofthefiguresherein,suitablefortransparencies,isavailableasquake-papers/painless-conjugate-gradient-pics.ps.MostoftheillustrationswerecreatedusingMathematica.c1994byJonathanRichardShewchuk.Thisarticlemaybefreelyduplicatedanddistributedsolongasnoconsiderationisreceivedinreturn,andthiscopyrightnoticeremainsintact.ThisguidewascreatedtohelpstudentslearnConjugateGradientMethodsaseasilyaspossible.Pleasemailme([e-mail])comments,corrections,andanyintuitionsImighthavemissed;someofthesewillbeincorporatedintoasecondedition.Iamparticularlyinterestedinhearingaboutuseofthisguideforclassroomteaching.Forthosewhowishtolearnmoreaboutiterativemethods,IrecommendWilliamL.Briggs’“AMultigridTutorial”[2],oneofthebest-writtenmathematicalbooksIhaveread.SpecialthankstoOmarGhattas,whotaughtmemuchofwhatIknowaboutnumericalmethods,andprovidedmewithextensivecommentsonthefirstdraftofthisarticle.ThanksalsotoJamesEpperson,DavidO’Hallaron,JamesStichnoth,NickTrefethen,andDanielTunkelangfortheircomments.Tohelpyouskipchapters,here’sadependencegraphofthesections:1Introduction2Notation10Complexity13NormalEquations3QuadraticForm4SteepestDescent5Eigenvectors6SDConvergence7ConjugateDire