资源描述:
《An Introduction tothe Conjugate Gradient MethodWithout the Agonizing Pain.pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、AnIntroductiontotheConjugateGradientMethodWithouttheAgonizingPainEdition114JonathanRichardShewchukAugust4,1994SchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213AbstractTheConjugateGradientMethodisthemostprominentiterativemethodforsolvingsparsesystemsoflinearequations.Unfort
2、unately,manytextbooktreatmentsofthetopicarewrittenwithneitherillustrationsnorintuition,andtheirvictimscanbefoundtothisdaybabblingsenselesslyinthecornersofdustylibraries.Forthisreason,adeep,geometricunderstandingofthemethodhasbeenreservedfortheelitebrilliantfewwhohavepainstakinglydecodedth
3、emumblingsoftheirforebears.Nevertheless,theConjugateGradientMethodisacompositeofsimple,elegantideasthatalmostanyonecanunderstand.Ofcourse,areaderasintelligentasyourselfwilllearnthemalmosteffortlessly.TheideaofquadraticformsisintroducedandusedtoderivethemethodsofSteepestDescent,ConjugateDi
4、rections,andConjugateGradients.EigenvectorsareexplainedandusedtoexaminetheconvergenceoftheJacobiMethod,SteepestDescent,andConjugateGradients.OthertopicsincludepreconditioningandthenonlinearConjugateGradientMethod.Ihavetakenpainstomakethisarticleeasytoread.Sixty-sixillustrationsareprovided
5、.Denseproseisavoided.Conceptsareexplainedinseveraldifferentways.Mostequationsarecoupledwithanintuitiveinterpretation.SupportedinpartbytheNaturalSciencesandEngineeringResearchCouncilofCanadaundera1967ScienceandEngineeringScholarshipandbytheNationalScienceFoundationunderGrantASC-9318163.The
6、viewsandconclusionscontainedinthisdocumentarethoseoftheauthorandshouldnotbeinterpretedasrepresentingtheofficialpolicies,eitherexpressorimplied,ofNSERC,NSF,ortheU.S.Government.Keywords:conjugategradientmethod,preconditioning,convergenceanalysis,agonizingpainContents1.Introduction12.Notation
7、13.TheQuadraticForm24.TheMethodofSteepestDescent65.ThinkingwithEigenvectorsandEigenvalues95.1.EigendoitifItry::::::::::::::::::::::::::::::::::::::95.2.Jacobiiterations:::::::::::::::::::::::::::::::::::::::115.3.AConcreteExample:::::::::::::::::::::::::::::::::::::