Error analysis of direct methods of matrix inversion

《Error analysis of direct methods of matrix inversion》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ErrorAnalysisofDirectMethodsofMatrixInversion*J.H.WILKINSONNationalPhysicalLaboratory,Teddington,EnglandIntroduction1.Inordertoassesstherelativeeffectivenessofmethodsofinvertingamatrixitisusefultohaveaprioriboundsfortheerrorsinthecomputedinverses.Inthispaperwedeterminesucherrorboundsforanum

2、berofthemosteffectivedirectmethods.Toillustratefullythetechniqueswehaveused,someoftheanalysishasbeendoneforfloating-pointcomputationandsomeforfixed-point.Inallcasesithasbeenassumedthatthecomputationhasbeenperformedusingaprecisionoftbinaryplaces,thoughitshouldbeappreciatedthatonacom-puterwhi

3、chhasbothfixedandfloating-pointfacilitiesthenumberofpermissibledigitsinafixed-pointnumberisgreaterthanthenumberofdigitsinthemantissaofafloating-pointnumber.Thetechniquesusedforanalyzingfloating-pointcomputationareessentiallythoseof[8],andafamiliaritywiththatpaperisassumed.2.Theerrorboundsar

4、emostconvenientlyexpressedintermsofvectorandmatrixnorms,andthroughoutwehaveusedtheEuclideanvectornormandthespectralmatrixnormexceptwhenexplicitreferenceismadetothecontrary.ForconveniencethemainpropertiesofthesenormsaregiveninSection9.Inarecentpaper[7]weanalyzedtheeffectoftheroundingerrorsma

5、deinthesolutionoftheequationsAx=b(2.1)byGaussianeliminationwithinterchanges"pivotingforsize".Weshowedthatthecomputedsolutionwastheexactsolutionof(A+E)x=-b+~b(2.2)andthatwecouldobtainboundsforEand8bprovidedassumptionsweremadeabouttheratioofthemaximumelementofthesuccessivereducedmatricestothe

6、maximumelementofA.Allthemethodswediscussinthispaperdependonthe(1)(2)(~)successivetransformationoftheoriginalmatrixAintomatricesA,A,,(k)(8)(1)(k)AsuchthateachAisequivalenttoAandthefinalAistriangular.Anessentialrequirementinanapriomanalysisofanyofthemethods,isaboundforthequantityr,definedby(s

7、)R=maxla~3I(s=1,...,k)(2.3)max[a~)I*ReceivedMarch,1961.281282J.H.WILKINSONFormethodsbaseduponGaussianeliminationwehavebeenabletoobtainareasonableupperboundforgeneralunsymmetricmatricesonlywhenpivotingforsizeisusedateachstage.Thisboundisfarfromsharp,butdo