Accurate computation of the smallest eigenvalue of a diagona

Abstract. If each off-diagonal entry and the sum of each row of a diagonally dominant M-matrix are known to certain relative accuracy, then its smallest eigenvalue and the entries of its inverse are known to the same order relative accuracy independent of

MATHEMATICSOFCOMPUTATION

Volume71,Number237,Pages217–236

S0025-5718(01)01325-4

ArticleelectronicallypublishedonMay14,2001

ACCURATECOMPUTATIONOFTHESMALLESTEIGENVALUE

OFADIAGONALLYDOMINANTM-MATRIX

ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

Abstract.Ifeacho -diagonalentryandthesumofeachrowofadiagonally

dominantM-matrixareknowntocertainrelativeaccuracy,thenitssmallest

eigenvalueandtheentriesofitsinverseareknowntothesameorderrelative

accuracyindependentofanyconditionnumbers.Inthispaper,wedevise

algorithmsthatcomputethesequantitieswithrelativeerrorsinthemagnitude

ofthemachineprecision.Roundingerroranalysisandnumericalexamplesare

presentedtodemonstratethenumericalbehaviourofthealgorithms.

1.Introduction

DiagonallydominantM-matricesformoneofthemostimportantclassesofmatricesinapplicationsandhavebeenstudiedextensivelyintheliterature;see[5,Chapter6].AmongproblemsofinterestaresolvingalinearsystemAx=band ndingthesmallesteigenvalueofA(correspondingtothePerronrootoftheinverse);see[2,12,21,22].Therearemanywellestablishednumericalmethodsforsolvingsuchproblemsandtheyleadtoabackwardstablesolution,whichhasanerrordependingontheconditionoftheproblem.Forinstance,applyingthe istheQRalgorithmto ndthesmallesteigenvalueλofA,thecomputedoneλeigenvalueofaperturbedmatrixA+Ewith E 2～ A 2(where isthemachine λ|～roundo unit).Then,assumingλisasimpleeigenvalue,weobtain|λ

E 2/y x～ A 2/y xandthustherelativeerrorisgivenby

λ||λ

λ1

ReceivedbytheeditorMarch22,1999and,inrevisedform,March14,2000.

2000MathematicsSubjectClassi cation.Primary65F18,65F05.

Keywordsandphrases.Entrywiseperturbation,diagonaldominantmatrix,M-matrix,eigenvalue.

Researchofthe rstauthorwassupportedbygrantNo.OGP0006854fromNaturalSciencesandEngineeringResearchCouncilofCanada.

ResearchofthesecondauthorwassupportedbyNaturalSciencesFoundationofChinaandAlexandervonHumboldtFoundationofGermany.

ResearchofthethirdauthorwassupportedbygrantsfromUniversityofManitobaResearchDevelopmentFundandNaturalSciencesandEngineeringResearchCouncilofCanadawhilethisauthorwaswithUniversityofManitoba,Winnipeg,Manitoba,Canada.

c2001AmericanMathematicalSociety

217

Abstract. If each off-diagonal entry and the sum of each row of a diagonally dominant M-matrix are known to certain relative accuracy, then its smallest eigenvalue and the entries of its inverse are known to the same order relative accuracy independent of

218ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

relativeto A 2,thentheerrorwillalsobelarge.Thislattercaseistrueevenforsymmetricmatrices.Unfortunately,inmanyapplicationproblems,thesmallesteigenvalueistheoneofinterest(see[3,2,12,22])andthecomputedeigenvaluebythestandardalgorithmsmayhaveloworevennoaccuracy.

Thenumericaldi ly,ifthematrixAisonlyde-terminedtowithinanormwiseperturbationE,thenitseigenvaluescanonlybedeterminedtoalowaccuracyinthesituationsdescribedabove.StartinginaworkbyDemmelandKahan[7]oncomputingthesingularvaluesofabidiagonalma-trix,therehavebeensigni cantworksinthelastdecadetoidentifyspecialclassesofproblemsforwhichthecomputedquantitiesarewelldeterminedbythematri-ces,usuallyunderentrywiseperturbations,andtodevisealgorithmsforcomputingthemtohighrelativeaccuracy.Wereferto[9]and[16]forasummaryofmostofsuchclassesofmatricesandtheliterature.Someofthosethatareknowntobedeterminedtothemachineprecisionarethesingularvaluesofbidiagonalmatrices

[7],thePerronrootofanonnegativematrix[10]andthesteadystatedistributionofaMarkovchain[18].Forthekindofproblemsthatweareinterestedinhere,aperturbationanalysisandanalgorithmhavebeendevelopedin[4]fortheeigen-valuesofsymmetricscaleddiagonaldominantmatricesandin[26]forthesmallesteigenvalueofanM-matrix.Unfortunately,theirperturbationboundsandtherel-ativeerrorsofthecomputedeigenvaluesstilldependoncertainconditionnumbersthatareessentiallyrelatedtothediagonaldominance.

FortheclassofdiagonallydominantM-matrices,however,wehaveshowninarecentwork[3]thatthesmallesteigenvalueandtheentriesofinversearedeter-minedtohighrelativeaccuracybytheo -diagonalentriesandtherowsumsofthematrices,ly,ifsmallrelativeerrorsareintroducedtoeacho -diagonalentryofadiagonallydominantM-matrixAandtothesumofeachrowofAwhichinturndeterminesthecorrespondingdiagonalentry,thenthesmallesteigenvalueandeachentryoftheinversehaverelativeerrorsofthesamemagnitude.Wenotethatinmanyapplications(suchasdiscretizedPDE,Markovchains[2],[12],[21,Chapter3]andelectriccircuits[22]),theo -diagonalentriesandtherowsumsofthema-trixplaytheroleofphysicalparameters,whilethediagonalentriesaretreatedasfunctionsofthemandareredundant(theimportanceofproperlyparametrizingamatrixhasalsobeenshownforsomeotherclassesofmatrices;see[8]).Inthosecases,itismoreappropriatetoconsidertheo -diagonalentriesandtherowsumsasthematrixdata.Indeed,inthiswork,adiagonallydominantM-matrixwillberepresentedbyitso -diagonalentriesandthesumsofitsrowsratherthantheusualrepresentationsbyallentries.

Thus,thenewperturbationtheorysuggeststhatitispossibletocomputethesmallesteigenvalueandtheinverseentriestohighrelativeaccuracy.Itisthepurposeofthepresentpapertodevelopsuchalgorithms.WeshallshowhowtheGaussianeliminationcanbeimplementedtosolveAx=b(withb≥0)sothateachentryofxwillhavehighrelativeaccuracy.TheideausedisanextensionoftheGTH-algorithm[14]forstochasticmatricesandthuswecallitaGTH-likealgorithm.ForcomputingthesmallesteigenvalueofA,weuseashiftedinverseiterationalgorithmsimilartotheonedevelopedin[26]andweshallcarryouttheiterationinsuchawaythatthecomputedapproximateeigenvalueconvergesmonotonicallyandquadraticallyuntilitsrelativeerrorisinthemagnitudeofthe

< …… 此处隐藏：5891字，全部文档内容请下载后查看。喜欢就下载吧 ……