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

NotethatanyM-matrixAisscaleddiagonallydominant;i.e.,thereexistu>0suchthatAu=v≥0.Inmanycases,thevectorumaynotbeexplicitlyknown.However,ifuandvareknown,theM-matrixAcanbede nedbyitso -diagonalentriesandu,vasinthefollowing.

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

220ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

De nition2.1.LetP=(pij)beann×nnonnegativematrixwithzerodiagonalentries,andletu=(ui)beapositiven-vectorandv=(vi)beanonnegativen-vector.Weuse(P,u,v)torepresenttheuniquematrixAoftheformA=D Pthatsatis esAu=v,whereDisadiagonalmatrix.WewriteA=(P,u,v).

IntherepresentationA=(P,u,v),theo -diagonalentriesofAisgivenby Panditsdiagonalentriesby

(2.3)

(2.4)a=vi+ j=ipijujii 1(1+ )n 1A≤A 1≤(1+ )n(1+ )n 1(1+ )nλ≤ λ≤ ≤4n +O( 2),|A 1 A 1|≤(4n +O( 2))A 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

ACCURATECOMPUTATIONOFTHESMALLESTEIGENVALUE221

Proof.Let

B=ADu=DDu PDu =A D u=D D u P D u.andB

arediagonallydominantM-matriceswithBe=vandBe =vObviously,BandB .

Wehave

D u≤(1+ )2PDu(1 )2PDu≤P

and

≤(1+ )Be.(1 )Be≤Be

FromLemma2.2,wehave

1 B 1|≤((4n 1) +O( 2))B 1,|B

fromwhichitfollows

1 A 1|≤(4n +O( 2))A 1.|A

Thisfurtherimplies

1. 1 A 1|≤(4n +O( 2))A|A

Usingtheperturbationresultforspectralradius(Theorem1in[10]),weobtain 1 ≤(4n +O( 2))1 λ

≤4n +O( 2).

Lemma2.5.LetBbeanM-matrixwiththesmallesteigenvalueλ.If

λ1e≤Be≤λ2e

andλ1>0,then

λ1≤λ≤λ2.

Proof.B 1isanonnegativematrixwithPerroneigenvalue1/λ.Obviously

1

λ1

1

u

1

λ1e.Fromthede nitionofPerronrootin[5,Chapter1],=minmaxv≥0B 1vλ2

whichcompletestheproof.≤

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

222ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

3.Solvinglinearsystems

Inthissection,weconsidersolvingalinearsystemAx=bwithb≥0.Lemma

2.1showsthatifA=(P,u,v),thenA 1andhencethesolutionxtoAx=b≥0aredeterminedtothesameaccuracyentrywiseasinthedata(P,u,v).Thus,wecanexpectalgorithmsthatsolveAx=btothemachineprecisionentrywise.ItturnsoutthatthiscanbeachievedbymodifyingthestandardGaussianelimination.

We rstnotethatifAisadiagonallydominantM-matrix,thenallthesub-matricesproducedintheprocessoftheGaussianeliminationarestilldiagonallydominantM-matricesandcanallberepresentedintherepresentation(P,u,v).ItturnsoutthatwecancarryouttheGaussianeliminationintermsoftherepresen-tation(P,u,v)ratherthantheentriesofAandtheadvantageofthisisthatthereisnosubtractioninvolvedthroughouttheprocess.Inthisway,the nalsolutionobtainedwillhavehighrelativeaccuracy.ThisideaisanextensionoftheGTH-algorithm[14]forstochasticmatricesandhasasimilaralgorithm.WethereforecallthisalgorithmaGTH-likealgorithm.SincesuchanextensionhasnotbeenconsideredbeforeforM-matrices,wepresentthedetailedderivationandanalysisinthissection.

3.1.GTH-likealgorithm.WenowderivethealgorithmforAx=bwithA=(P,u,v)throughLUfactorization,forwardsubstitutionandbackwardsubstitution.AllcomputationsareoperatedonP,u,vandb.

We rstconsidertheLUfactorizationofA,carriedoutwithoutpivoting.ThisproducesaseriesofmatricesofdecreasingorderA=A(1),A(2),A(3),···,whereA(k)denotesthematrixtothesoutheastofthek-thpivotentry(andincludingthatpivotentry),justbeforethek-thGaussianeliminationisapplied.Itiseasilyveri edthatA(k)inheritsthepropertyofbeinganM-matrix.Weshall ndout

(k)itsrepresentationA(k)=(P(k),u(k),v(k)).Inthefollowing,weletpijbethe

(i k+1,j k+1)-thentryofP(k),anduiandvibethe(i k+1)-thentriesofu(k)andv(k)respectively.Toseektherelationbetween(P(k),u(k),v(k))and(P(k+1),u(k+1),v(k+1)),wepartitionA(k)as αk wT(k),A= zB(k)

whereB(k)isofordern k.Wehave

A(k+1)(k)(k)=B(k) zwT

(3.2)uk

(k)(k)(k).From(3.1),wecancomputeP(k+1)accordingtotherelation

(k+1)pij=(k)pij+pikpkj

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

ACCURATECOMPUTATIONOFTHESMALLESTEIGENVALUE223

NowweshowthatA(k+1)isstilladiagonallydominantM-matrixby ndingu(k+1)andv(k+1).Letv(k)betherespectivesubvectorsofu(k)andv(k)withthe rstentriesdeleted.From (k) Tαk wuk,(k) zBv(k)

wehave

wT

u(k)=ukz+

u(k)vk(k)(k)u(k)=B(k)v(k)+

u(k)

i.e.,

(k+1)ujandv(k+1)=αkvk(k)

z,=(k)ujand(k+1)vj=(k)vj+

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

224ATTAHIRUSULEALFA,JUNGONGXUE,ANDQIANGYE

Weassumethefollowingmodelforthe oatingpointarithmetic[6,

p.9]:

fl(xopy)=(xopy)(1+δ),|δ|≤ ,

whereop=+, , or/and isthemachineroundo unit.Fortheeaseofnotation,weshalluse swithsubscriptstodenotequantitiesboundedinmagnitudeby .

Inthefollowing,a“hat”isaddedtothevaluecomputedin oating-pointarith-metic.

Theorem3.1.SupposeAlgo …… 此处隐藏：5466字，全部文档内容请下载后查看。喜欢就下载吧 ……