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

偶是小鸟
1 ℃
2020-04-16

整理文档很辛苦，赏杯茶钱您下走！

还剩 ... 页未读，继续阅读 >>

免费阅读已结束，点击下载阅读编辑剩下 ... 页

阅读已结束，您可以下载文档离线阅读编辑

资源描述

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.Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthorandshouldnotbeinterpretedasrepresentingtheofﬁcialpolicies,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)undertheﬁlenamequake-papers/painless-conjugate-gradient.ps.APostScriptﬁlecontainingfull-pagecopiesoftheﬁguresherein,suitablefortransparencies,isavailableasquake-papers/painless-conjugate-gradient-pics.ps.MostoftheillustrationswerecreatedusingMathematica.c1994byJonathanRichardShewchuk.Thisarticlemaybefreelyduplicatedanddistributedsolongasnoconsiderationisreceivedinreturn,andthiscopyrightnoticeremainsintact.ThisguidewascreatedtohelpstudentslearnConjugateGradientMethodsaseasilyaspossible.Pleasemailme(jrs@cs.cmu.edu)comments,corrections,andanyintuitionsImighthavemissed;someofthesewillbeincorporatedintoasecondedition.Iamparticularlyinterestedinhearingaboutuseofthisguideforclassroomteaching.Forthosewhowishtolearnmoreaboutiterativemethods,IrecommendWilliamL.Briggs’“AMultigridTutorial”[2],oneofthebest-writtenmathematicalbooksIhaveread.SpecialthankstoOmarGhattas,whotaughtmemuchofwhatIknowaboutnumericalmethods,andprovidedmewithextensivecommentsontheﬁrstdraftofthisarticle.ThanksalsotoJamesEpperson,DavidO’Hallaron,JamesStichnoth,NickTrefethen,andDanielTunkelangfortheircomments.Tohelpyouskipchapters,here’sadependencegraphofthesections:1Introduction2Notation10Complexity13NormalEquations3QuadraticForm4SteepestDescent5Eigenvectors6SDConvergence7ConjugateDire