资源描述:
《painless conjuage gradient.pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、AnIntroductiontotheConjugateGradientMethodWithouttheAgonizingPainEdition114JonathanRichardShewchukAugust4,1994SchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213AbstractTheConjugateGradientMethodisthemostprominentiterativemethodforsolvingsparsesystemsofl
2、inearequations.Unfortunately,manytextbooktreatmentsofthetopicarewrittenwithneitherillustrationsnorintuition,andtheirvictimscanbefoundtothisdaybabblingsenselesslyinthecornersofdustylibraries.Forthisreason,adeep,geometricunderstandingofthemethodhasbeenreservedfortheelit
3、ebrilliantfewwhohavepainstakinglydecodedthemumblingsoftheirforebears.Nevertheless,theConjugateGradientMethodisacompositeofsimple,elegantideasthatalmostanyonecanunderstand.Ofcourse,areaderasintelligentasyourselfwilllearnthemalmosteffortlessly.Theideaofquadraticformsisi
4、ntroducedandusedtoderivethemethodsofSteepestDescent,ConjugateDirections,andConjugateGradients.EigenvectorsareexplainedandusedtoexaminetheconvergenceoftheJacobiMethod,SteepestDescent,andConjugateGradients.OthertopicsincludepreconditioningandthenonlinearConjugateGradien
5、tMethod.Ihavetakenpainstomakethisarticleeasytoread.Sixty-sixillustrationsareprovided.Denseproseisavoided.Conceptsareexplainedinseveraldifferentways.Mostequationsarecoupledwithanintuitiveinterpretation.SupportedinpartbytheNaturalSciencesandEngineeringResearchCouncilofC
6、anadaundera1967ScienceandEngineeringScholarshipandbytheNationalScienceFoundationunderGrantASC-9318163.Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthorandshouldnotbeinterpretedasrepresentingtheof®cialpolicies,eitherexpressorimplied,ofNSERC,NSF,ortheU.S.
7、Government.Keywords:conjugategradientmethod,preconditioning,convergenceanalysis,agonizingpainContents1.Introduction12.Notation13.TheQuadraticForm24.TheMethodofSteepestDescent65.ThinkingwithEigenvectorsandEigenvalues95.1.EigendoitifItry
8、 95.2.Jacobiiterations