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

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

226ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

putingthesmallesteigenvalue

Inthissection,weconsiderhowtocomputethesmallesteigenvalueofadi-agonallydominantirreducibleM-matrixA,whichisgivenintherepresentationA=(P,u,v).

4.1.Theinverseiterationalgorithm.ThealgorithmtobedevelopedhereisbasedonthefollowinginverseiterationshiftedbyaRayleighquotientlikeapprox-imationoftheeigenvalue.

ShiftedInverseIteration:

Foragivenu(0)>0,iterativelyde ne

(s)Auλs=min

w(s+1) ∞.

ThisinverseiterationalgorithmwaspresentedbyXuein[26]forM-matrices.

It

stems

from

the

algorithmbyNodain[17]forcomputingthePerronrootofanirreduciblenonnegativematrix.Elsner[10]hasshownthatNoda’salgorithmisquadraticallyconvergent.Thustheaboveeigenvalueisincreasingandquadraticallyconvergent,i.e.,

λs≤λs+1≤λandλ λs+1≤β(λ λs)2,

whereβisaconstantdependingonu(0)andA.Itisnotedin[26]thatλs+1canbecomputedfromλswithoutsubtractionsfollowingtherelation

(s) Aw(s+1)u+min=λλs+1=minsw(s+1)

u(s)>0(thispropertyisalso

observedandusedbyO’Cinneide[20]).Thus,thekeyideaisthatA λsIcanberepresentedwithoutformingthediagonalsas

A λsI=(P,u(s),v(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

ACCURATECOMPUTATIONOFTHESMALLESTEIGENVALUE227

where

v(s)=

=(A λsI)u(s)1

(λs 1w(s)+u(s 1) λsw(s))

w(s)w(s) w(s) ∞=1

≥0.Hence,weshallformA λsIbytherepresentation(P,u(s),v(s))andthensolve(4.1)withAlgorithm1.Inthisprocess,subtractionisencounteredonlyinthecomputationofv(s).Onaccountofpossiblecancellation,wecannotexpectw(s+1)andu(s+1)arecomputedwithsmallentrywiserelativeerror.Fortunately,however,thiswillnota ecttheaccuracyofthecomputedeigenvalue,whichwillbeshowninthelatererroranalysis.

Finally,forthestoppingcriterion,weadopt (s)umaxw(s+1)

u Fors=0,1,2,···etheGTH-likealgorithmtosolve,v(0)=v λ0u.

(P,u(s),v(s))w(s+1)=u(s)

2.

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

w(s+1) ∞

4.Calculatev(s+1)accordingto (s)ui(s+1)(s+1)=uivi

5.Proceeduntil

max w(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

228ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

Remark4.1.ThisalgorithmcanbeadaptedtocomputethesmallesteigenvalueofanarbitraryM-matrixAby rst ndingarepresentation,i.e., ndingapositivevectorusuchthatAu>0.Aftercalculatingv=Au,weapplyAlgorithm2tocomputethesmallesteigenvalueof(P,u,v),where Pistheo -diagonalpartof

A.Asforu,itcanbeobtainedbysolvingthelinearsystemAu=e.Withasmallresidual,wecanexpectAu ,whereu isthecomputedsolution,tobepositive.

4.2.Erroranalysis.Inthissection,wepresentadetailederroranalysisforAl-gorithm2.Again,weadd“hats”tothecomputedintermediatequantities.

Firstnotethattheoretically(intheexactarithmetic),from(A λsI)u(s)=v(s),wehavetherepresentationofAinthes-thiterationstepas

A=(P,u(s),λsu(s)+v(s)).

s,u (s)andv (s)bethecomputedquantitiesatInthe oatingpointarithmetic,letλ

thes-thiteration.Then

su (s),λ (s)+v (s))As=(P,u

isanapproximationtoA.Becauseofpossiblecancellationsinthecomputationof

(s)canbeabadapproximationofu(s),andforthisreasonitcannotbev(s 1),u

expectedthatAsapproximateAwithsmallentrywiserelativeerror.Whatmakesouralgorithmworkisthat,nomatterwhethersuchcancellationoccursornot,therelativeerrorbetweenγs,thesmallesteigenvalueofAs,andλ,thesmallesteigenvalueofA,isalwayssmall.Toshowthis,we rstinvestigatetherelativeerrorbetweenγsandγs+1,whichiscausedbyonestepofiterationofAlgorithm2.

s, s+1vv(s)andu (s+1),λ (s+1)bethecomputedquantitiesLemma4.2.Letu (s),λ

atthes-thand(s+1)-thiterationofAlgorithm2respectively,andletγsandγs+1bethesmallesteigenvaluesof

su s+1u (s),λ (s)+ v(s))andAs+1=(P,u (s+1),λ (s+1)+v (s+1))As=(P,u

respectively.Then

|γs γs+1|

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

ACCURATECOMPUTATIONOFTHESMALLESTEIGENVALUE

Notingthat

u(s+1)=w(s+1)

w (s+1) ,∞

weobtain

(4.4)|u(s+1) u(s+1)|≤((2φ(n)+1) +O( 2))u(s+1).

Therespectivei-thentriesofq(s+1)and q(s+1)are

q(s+1)u (s)u

i= λs+min (s)

w(s+1) min

i

(4.5)(s+1)

w(s+1)ui

i

and

q (s+1)(s)

i=fl λs+minu (s)

w (s+1) minu

i

w (s+1)u (s+1)i

+(1+ 5)(1+ 6)u (s+1)

i(1+ u (s)

3)i

w (s+1)

s)

u (s+1))

=i s+ u(

λi

w (s+1)+η2minu (s

i

)

w (s+1)+η2minu (s

iw(s+1).

i

Pluggingthebounds(4.3)and(4.5)into(4.6),wehave

q (s+1)

i=(1+η3)q(s+1)

i,|η3|≤3(φ(n)+3) +O( 2).

Thus

(4.7)|q(s+1) q(s+1)|≤(3(φ(n)+3) +O( 2))q(s+1).

Associating(4.4)and(4.7)withLemma2.1yields

0<γs+1 γs229

Abstract. If each off-diagonal entry and the sum of each row of a diagonally dom …… 此处隐藏：5099字，全部文档内容请下载后查看。喜欢就下载吧 ……