Higham Gaussian elimination

《Higham Gaussian elimination》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AdvancedReviewGaussianeliminationNicholasJ.Higham∗Asthestandardmethodforsolvingsystemsoflinearequations,Gaussianelimination(GE)isoneofthemostimportantandubiquitousnumericalalgorithms.However,itssuccessfulusereliesonunderstandingitsnumericalstabilitypropertiesandhowtoorganizei

2、tscomputationsforefficientexecutiononmoderncomputers.WegiveanoverviewofGE,rangingfromtheorytocomputation.WeexplainwhyGEcomputesanLUfactorizationandthevariousbenefitsofthismatrixfactorizationviewpoint.Pivotingstrategiesforensuringnumericalstabilityaredescribed.Specialpropertieso

3、fGEforcertainclassesofstructuredmatricesaresummarized.HowtoimplementGEinawaythatefficientlyexploitsthehierarchicalmemoriesofmoderncomputersisdiscussed.WealsodescribeblockLUfactorization,correspondingtotheuseofpivotblocksinsteadofpivotelements,andexplainhowiterativerefinementcan

4、beusedtoimproveasolutioncomputedbyGE.OthertopicsareGEforsparsematricesandtheroleGEplaysintheTOP500rankingoftheworld’sfastestcomputers.2011JohnWiley&Sons,Inc.WIREsCompStat20113230–238DOI:10.1002/wics.164INTRODUCTIONThenweturntothenumericalpropertiesofLUfac-torizationanddiscus

5、spivotingstrategiesforensuringaussianelimination(GE)isthestandardmethodnumericalstability.Inthesection‘StructuredMatri-Gforsolvingasystemoflinearequations.Assuch,ces’,wedescribesomespecialresultsthatholdforLUitisoneofthemostubiquitousnumericalalgorithmsfactorizationwhenthemat

6、rixhasparticularproper-andplaysafundamentalroleinscientificcomputation.ties.Computerimplementationisthendiscussed,asGEwasknowntotheancientChinese1andiswellasaversionofGEthatusesblockpivots.Iterativefamiliartomanyschoolchildrenastheintuitivelyrefinement—ameansforimprovingthequal

7、ityofanaturalmethodofeliminatingvariablesfromlinearcomputedsolution—isalsodescribed.equations.GaussuseditinthecontextofthelinearWewillneedthefollowingnotation.Theunitleastsquaresproblem.2–4Undergraduateslearntheroundoff(ormachineprecision)isdenotedbyu;inmethodinlinearalgebrac

8、ourses,whereitisusuallyIEEEdoubleprecisionarithmeticithasthevaluetau