Accurate computation of the smallest eigenvalue of a diagona(4)

s+1e,|η10|≤(φ(n)+2) +O( 2).Bse≥(1+η10)λ

ItfollowsfromLemma2.2that

s+1≤γs≤(1+η9)λ s+1,(1+η10)λ

andhence λ s+1 γs s+1e+η7λ

λ s λλ ≤(βsλ)

(s+1)w i=minu (s)

s, (s),λLetλs+1bethequantitythatiscomputedintheexactarithmeticfromu

v (s)bythe(s+1)-thiterationstepofAlgorithm2.Wehave (s)

u s+minλs+1=λ.w (s+1)u (s).

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

232ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

+1FromTheorem3.1, λ s+1 λs

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

ACCURATECOMPUTATIONOFTHESMALLESTEIGENVALUE233

Table1.Case1:λisill-conditioned

1.0×10 3

1.0×10 6

1.0×10 9

1.0×10 12

1.0×10 18

1.0×10 24

1.0×10 301.1×10 31.15×10 61.2×10 91.3×10 121.5×10 181.7×10 242.0×10 30 ||λ λ|λ λQR|4.7×10 132.06×10 114.7×10 104.9×10 93.5×10 58.0×10 21.7×10 1

Example1.Considerthen×nM-matrixA=(P,e,v),where

(5.1) P= 0

δ00...1001......0000······...······00... 1 0

and

(5.2)v=(0,0,···,0,1 δ),

i.e.A=I P.Letxandybetheunitrightandlefteigenvectorscorrespondingto

1n.λ,thesmallesteigenvalueofA.Itisshownin[11]thatλ=1 δ

Ifδistiny,thenλisill-conditionedsinceyTxisveryclosetozero.Ifδtendsto1,yTxisnotsmallandthusthesmallesteigenvalueiswell-conditioned,butitistiny.

WetestouralgorithmandtheQRalgorithmonbothcasesofsuchM-matrices. andλQRdenotethesmallesteigenvaluescomputedbyInthefollowing,weletλ

Algorithm2andtheQRalgorithmrespectively.

Case1.n=100andδ～0.Table1presentstheresults.Asitshows,Algorithm2computesthesmallesteigenvaluesalmosttofullprecisionnomatterhowsmallδis.Ontheotherhand,theQRalgorithmlosessigni cant guresasδdecreases.Ifδ≤10 24,onlyone gureofthecomputedeigenvalueiscorrect. s λ|/λagainstsinForthisexample,wealsoplotconvergencehistoryof|λ

Figure1(insolidlineforδ=10 3andindottedlineforδ=10 9).Itclearlyshowsthequadraticconvergencepropertyin niteprecisionasdemonstratedbyTheorem4.3.

Case2.n=20andδ～1.WereporttheresultsinTable2.Again,ouralgorithmcancomputeλtofullprecisionnomatterhowtinyitis,whileQRalgorithmhaslowaccuracyasδdecreases.

ThematricesinExample1areverysparse.Nextweconsidertestingondensematrices.

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

234ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

Table2.Case2:λistinyrelativeto A

≥

10

(1 10 6)20

10 9

(1 10 12)20

10 1503.1

3λλ3.3×10 134.2×10 168.6×10 7

dotted-δ=10 9

Example2.Considerthen×nM-matrixA=(P,e,v)de nedby

v=(δ,···,δ,65δ/128,191δ/128)T

and

P= .P1

uTw0

whereP1isofordern 1withalltheo -diagonalentriesequalto1,

u=(0,···,0,δ/128)Tw=(0,···,0,δ/2)T.

Thesmallesteigenvalueofthismatrixisδandthecorrespondingeigenvectoris(1,···,1,1/64)T.

Wetestouralgorithmwithvariousnandδ.Tables3and4reportsthenumericalresultsforn=100andn=1000.Weobservethat,forthesedensematrices,increase either.ofndoesnota ecttheaccuracyofcomputedeigenvalueλ

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

ACCURATECOMPUTATIONOFTHESMALLESTEIGENVALUE235

Table3.100×100densematrix

10 3

10 6

10 9

10 12

10 15014.2×10 162.3×10 6λλ4.9×10 12

Table4.1000×1000densematrix

10

10 6

10 9

10 12

10 152.0×10 162.2×10 1 3λλ2.5×10 108.5×10 161.3×10 4

References

[1]A.AhacandD.Olesky,AstablemethodfortheLUfactorizationofM-matrices,SIAMJ.Alg.Disc.Meth.,7(1986):368-378.MR87i:65035

[2]J.Abate,L.ChoudhuryandW.Whitt,Asymptoticsforsteady-statetailprobabilitiesin

structuredMarkovqueueingmodels,Commun.Statist-StochasticModels,1(1994):99-143.MR95f:60106

[3]A.S.Alfa,J.XueandQ.Ye,EntrywiseperturbationtheoryfordiagonallydominantM-

matriceswithapplications,toappearinNumer.Math.

[4]J.BarlowandJ.Demmel,Computingaccurateeigensystemsofscaleddiagonallydominant

matrices,SIAMJ.Num.Anal.,27(3),(1990):762-791.MR91g:65071

[5]A.BermanandR.Plemmons,Nonnegativematricesinmathematicalscience,Academic

Press,NewYork,1979.MR82b:15013

[6]S.ConteandC.deBoor,ElementarynumericalanalysisThirdedition,NewYork-

Tokyo:McGraw-Hill1980.

[7]J.DemmelandW.Kahan,Accuratesingularvaluesofbidiagonalmatrices,SIAMJ.Sci.

put,11(5)(1990):873-912.MR91i:65072

[8]J.Demmel,AccurateSVDsofstructuredmatrices,LAPACKWorkingNote#130,Dept.of

ComputerScience,Univ.ofTennessee,Oct.1977.

[9]J.Demmel,M.Gu,S.Eisenstat,I.Slapni car,K.Vaseli´candZ.Dram c,Computingthe

singularvaluedecompositionwithhighrelativeaccuracy,LinearAlgebraAppl.299 …… 此处隐藏：3640字，全部文档内容请下载后查看。喜欢就下载吧 ……