; TeX output 2001.12.13:1621UjK`y cmr101,src:4Jacobi.texkAH cmssbx10ConvergenceofscalediteratesbytheJacobimethoN9d,src:5Jacobi.texJ.UUMatejaxs^ O!cmsy7,X-ffD&esrc:8Jacobi.texo cmr9ABSTRA9CT Aaquadraticcon9vergencebAoundforscalediteratesbytheserialJacobimethoAdfornHermitianpAositiv9ede nitematricesisderived.Byscalediterateswemean &Dthe^*matrices[diag2(:5" cmmi9H-=(Aacmr6(*;cmmi6k) O)]-=+q% cmsy6b33Zcmr5133 Љfeg M2 H-=(k)[diag(H-=(k))]-=b33133 Љfeg M2rɺwhere^*H-=(k),p`kN; cmsy9 +0arematricesgenerated^b9ythemethoAd.Theboundisobtainedinthegeneralcaseofm9ultipleeigen9v|ralues.pItTdepAendsontheminimumrelativeseparationoftheeigenv|ralues.&fffD7src:18Jacobi.tex': cmti10Keywor}'ds.qDzJacobiUUmethoGd,scaledmatrices,quadraticconvergence.psrc:21Jacobi.texAMSsubje}'ctclassi cation.qDz65F15,UU65G05.(2f0.INTRODUCTION 3src:34Jacobi.texIn+[11 ]wederivedaquadraticconvergencebGoundforscaledJacobiiter- atesprovidedtheinitialsymmetricpGositivede nitematrix b> cmmi10Hhassimpleeigenvqalues.LetH^ٓRcmr7( 0ercmmi7k+B) ,kt !", cmsy10#0,H^(0)_=H]bGethematricesgeneratedbytheserialB-(i.e.8Othecolumn-ortherow-cyclic)JacobimethoGd.LetnbGethematrix_orderandH^(N,),N=rn(nꝸ1)=2_thematrixobtainedafterone ƍcycle.7LetkеH:(k+B)"S=^(k+B)r 0ncmsy51}aH^(k+B) ^(k+B)r1,qn^(k+B)!=[diag(H^(k+B) )]^1=2 ʲ,k=&0kbGethescaledUUiterates.qTheresult[11 ,Theorem6]readsh/~ N \ɸ<$K0:715Kwfe! (֍õ  z20providedUUthatSص 0C<$K1Kwfe (֍4 'minոf<$133wfe (֍ng;q 8g;src:47Jacobi.texwhere kUO=ik (H:(k+B)"S )kF \͵kV0,SkykFdenotestheF*robGeniusnorm,S E%theminimum]relativegapinthespGectrum(seetherelations(8)and(9)here)and (X)=X#Zdiag(X)foranymatrixX. In[11 ]theauthordiscussedsome,numericalapplicationsofthisresult,4espGeciallythoseconnectedwith Off @ -:L|{Ycmr8FJacultÎykofEconomics,MUniversityofZagreb,MKennedyjevtrg6,10000Zagreb, CRÎOAJTIA:sj cmti9LINEARN_0024-3795/92/$5.00*UR2RthestoppingcriterionofthemethoGd. GTheimportanceoftheresultis RenhancedUUwhentheeigenvqaluesclusteraroundtheorigin.asrc:57Jacobi.texIn=thispapGerwederiveaquadraticconvergencebGoundforscaledJacobiRiterates5inthegeneralcasewhichincludescomplexJacobialgorithmandRmultipleGeigenvqaluesoftheinitialHermitianpGositivede nitematrix.TheRestimate^provedhereisageneralizationtocomplexHermitianmatricesofRtheestimateforrealsymmetricmatricespresentedintheauthor'sPh.D.Rthesis[10 ]whichwaswrittenunderthesupGervisionofProfessorVjeranRHari.asrc:66Jacobi.texSincetheproGofofthemainresultisprettycomplex, thepaperisor-Rganized *asfollows.GInSection1recentresultsonthestructureofscaledRdiagonallyE}dominantpGositivede nitematricesarepresented.*InSection2aRbriefMdescriptionoftheHermitianJacobimethoGdisgiven.InSection3some cRauxiliary]resultsdealingwithnonunitarytransformationsH:(k+B)"Sn`!rеH:(k+B+1)"SRarederived.N8Themainresult(Theorem6)isprovedinSection4.N8SincetheRproGofsofauxiliarylemmasarelongandtediouswegivethemasatechnicalRrepGort.%ZR1.cSCALEDUUDIAGONALL*YDOMINANTMATRICESVRsrc:79Jacobi.texLet."V cmbx10C^nn+denotethesetofcomplexmatricesofordern.WQLetHӸ2C^nnRbGeapositivede nitematrix.SinceHOisHermitianitseigenvqaluesandRdiagonalg4elementsarerealandpGositive."gLettheeigenvqaluesofH72bGeorderedRnonincreasingly*,9Ǎ1C=2=:::8ײ=s1 r>8(1)s1 +1u=:::8ײ=s2 r>:::>sO \cmmi5p1 +11=:::=sp c;Rsrc:88Jacobi.texwherepsp ?=n.8ThenpisthenumbGerpofdistincteigenvqaluesofHgnand Rfor eachi,F91Gip,ni\=si Ysi1̲(s0=0) isthemultiplicity ofsiq2.RW*eassumethattherowsandcolumnsofH]aresopGermutedthatfortheRcorrespGondingUUsetsofindices9ǍmNr =mft2N-:sr71+81tsrmg; 1r5pUU;8(2)Rsrc:97Jacobi.texandUUforthediagonalelementsholdsA(8t2NlȲ)UU(8q"2Nrm)lxhq@Lq :8(3)Rsrc:102Jacobi.texNoteUUthattheassumption(3)isageneralizationoftheusualconditionh11 ?h22:::8׸hnn8(4)sUj3,src:106Jacobi.texAccordingsjtothepartitionn=n1+u n2+::: +npwesjde neforanyX2C^nn ,theUUbloGck-matrixpartition"yM޵XO=Xmu cmex102m6fim4z؉X11,µ:::BgX1pԍ߲...Iv.Iv.Iv.Xp1,µ:::BViXppXX]3X]7fiX]5`E; Xij 2C Npni*nj";UR1i;jYp:c8(5)#⍑,src:116Jacobi.texInUUthesequelweusethefollowingnotation(cf.q[7]):=idiagO(X)j=|^diag?(x11x;:::xnn b); theUUdiagonalofPG#X:;H (X)j=|^X¸8diag9(X); theUUo -diagonalpartoft#X:;I[ٲ(X)j=|^diag?(X11x;:::;Xpp); theUUbloGck-diagonalpartof\X:;J>!Dz(X)j=|^X¸8[ٲ(X); theUUo -bloGck-diagonalpartof,Xs:,src:128Jacobi.texF*orUU1ipwesetrHiTL(X)) ='Xii(;siTL(X)) ='[Xi1g:::PXi;i1$Xi;i+1SC:::!Xips]UU:,src:134Jacobi.texF*orUUapGositivede nitematrixH,thematrix]HS=[diagUY(H)]1=2˵H[diag(H)]1=2c8(6),src:138Jacobi.texisreferredtoassc}'aledFmatrix^yB|ofѵHϲorshorterscaledH.0uT#'0;Da=b=0V:c8(7),src:154Jacobi.texUsing(therelation(1)onecande nether}'elativegapofsi =ZinthespGectrum ,ofUUH,. id=min Uc1jK}pjg6=iȲrg%t(siq2;sj); 1ip;c8(8)Bg,src:160Jacobi.texandUUtheminimumr}'elativegapr UP=)minw1ip7( i:c8(9),Nff [-:yLܼWJeXusede nitionsrestrictedtop9jlwfe O (֍hjgjOj2S+jj ([ٲ(HS))jj2፴F l<$R2Kwfe 8 (֍ 8r2ejj!Dz(HS)jj4፴F 9ǵ: ڍRsrc:187Jacobi.texW*ew\seethatforanpGositivede nite z-s.d.d.matrixwith <w 8=3,theRo -diagonal=elementsofdiagonalbloGckswhicharealiatedwiththesameReigenvqalue5 arequadraticallysmallwithrespGecttojj!Dz(HS)jjF.g ThesameisRtrue(fortherelativedistancejsi IhjgjXj=hjgj,%ݵjo2"NiTL.fAThis(structurehasRimpactUUontherateofconvergenceUUofscalediteratesinJacobimethoGd.#R2.cTHEUUHERMITIANJACOBIMETHOD`Rsrc:197Jacobi.texHerek]ashortdescriptionofJacobimethoGdforcomputingtheeigendecom-RpGositiongofHermitianmatricesisgiven.LetHebeaHermitianmatrixofRordern.JacobimethoGdgeneratessequenceofmatrices(H^(k+B) ;k<j0)byRtheUUruleɵH(k+B+1)⫲=(U(k+B) B)H(k+B) U(k+B); k0;H(0)S=HA;8(10)`Rsrc:204Jacobi.texwhereUUU^(k+B) B;k0areunitaryplanematricesoftheform'#[(U^(k+B) B)iiﰲ=(U^(k+B))jgj p=cosO'^(k+B) [[(U^(k+B) B)ij =Cfe!謟 V(Ur(k+B))jgi$IJ=e^{!k]ӲsinO'^(k+B)Ս[(U^(k+B) B)l `m {=l `m*bwheneverFfl2`;mg8\fi;jg=;UU:8(11)'"Rsrc:211Jacobi.texHereԵ{denotestheimaginaryunit,s~fegz ethecomplexconjugateofz,2Cand cRl `m aisVtheKronecker'sVdelta.vLetH^(k+B)l=(h:(k+B)6l `m +),Whks0.TheVpairofindicesR h:ff [-:zLܼThegoriginalassumption)2cmmi8hq11 1½\thq22:j::hnn $hisgreplacedwiththewÎeakergone(3).)Uj5qƍ,(i;j)=(i(kP);j(k))riscalledpivotp}'airandh:(k+B)Zijthepivotelement.The ,relationUU(10)de nesthekP'thsteporthek'thiter}'ationofthemethoGd. ƍ;src:219Jacobi.texF*orUUh:(k+B)Zij 6=0theangles'^(k+B)and!k@arechosentosatisfy-?ڵh:(k+B+1)Zij=0UU:>b,src:222Jacobi.texW*eUUassumetheusualchoicevWe{!k=󙍒t*h:(k+B)Zij fe|ß jh:(k+B)Zij +j]; i.e."qĵ!k =marg*(h:(k+B)Zij +)UU;^8(12)(J` tanp~2'(k+B)=󙍒2jh:(k+B)Zij +j fe. h:(k+B)Zjgj dr8h:(k+B)Zii0; '(k+B) 2[[=4;q=4]UU:^8(13)".U,src:229Jacobi.texF*orXh:(k+B)Zij 9=̧0,YthekP'thstepisskippGedi.e.!k7='^(k+B) 9=0ispresumed.{IfH,isrealsymmetric,*all!karesetzero,sothatallU^(k+B)̲areorthogonalandall c,H^(k+B)KareP realsymmetric.pInthiscasejh:(k+B)Zij +jintherelation(13)isreplacedˍ,byUUh:(k+B)Zij +.;src:236Jacobi.texUsingSthenotationc^(k+B)=cosK'^(k+B) +,Ss^(k+B)=sinڵ'^(k+B)andSt^(k+B)=tan'^(k+B),,theUUtransformationformulasreadC Zh:(k+B+1)Zij=0YZh:(k+B+1)6il=[ fe h:(k+B+1)6l `i =c^(k+B) +h:(k+B)6il dr8e^{!k +s^(k+B)h:(k+B)6jgl;URlx62fi;jgZh:(k+B+1)6jgl=[ fe h:(k+B+1)6l `j =c^(k+B) +h:(k+B)6jgl dr+8e^{!k,s^(k+B)h:(k+B)6il;URlx62fi;jgYZh:(k+B+1)Zii=h:(k+B)Zii dr8jh:(k+B)Zij +jt^(k+B)Zh:(k+B+1)Zjgj=h:(k+B)Zjgj dr+8jh:(k+B)Zij +jt^(k+B)Zh:(k+B+1)6l `m=h:(k+B)6l `m +;URl2`;m62fi;jgUU:^8(14)F$ ,src:250Jacobi.texF*romUUtherelation(14)weobtainforlx62fi;jg0!,Mjh:(k+B+1)6ilKj2[f=m.(c(k+B) +)2|sjh:(k+B)6ilj2S+8(s(k+B))2jh:(k+B)6jglj2S82s(k+B)c(k+B)<(e{!k +[ fe h:(k+B)6ilh:(k+B)6jgl);^8(15) ,Mjh:(k+B+1)6jglKj2[f=m.(c(k+B) +)2|sjh:(k+B)6jglj2S+8(s(k+B))2jh:(k+B)6ilj2S+82s(k+B)c(k+B)<(e{!k +[ fe h:(k+B)6ilh:(k+B)6jgl):^8(16)>b,src:261Jacobi.texHere`4<(zp)denotestherealpartofz.cIfH02isrealthenintherelations ƍ,(14)-(16),pz!kVandk jh:(k+B)6il +j,jh:(k+B)6jglj,jh:(k+B)Zijjk arereplacedby0andh:(k+B)6il,pzh:(k+B)6jgl,h:(k+B)Zij,respGectively*.;src:267Jacobi.texThewayofselectingpivotpairsiscalledpivotstr}'ategy. nItcanbGe,identi edwithafunctionF/:N0ii!Pnq~,1whereN0=N[f0gandPn ^t=8UR6Rf(l2`;m)9:1lktW*econsideronlycyclic*opivotstrategieswhich RareUUde nedbytheconditionF9(t8+rGN)=F(t),UU0tVN3=<$Kn(n81)Kwfe%1 (֍2-:8(17)%2Rsrc:275Jacobi.texThe|?mostcommoncyclicstrategiesarether}'ow-andthecolumn-cyclicones,RalsoUUcalledserialstrategies,de nedbytheorderingsWb(1;2);(1;3);:::;(1;n);(2;3);:::;(2;n);:::;(n81;n)Rsrc:279Jacobi.texand zE(1;2);(1;3);(2;3);(1;4);:::;(1;n);(2;n);:::;(n81;n);4nRsrc:281Jacobi.texrespGectively*.kfEveryS5NjPsubsequentiterations,startingwith0,N,2N,...RmakeQonecycleorswe}'epofthemethoGd.gjUndertheserialstrategiestheRmethoGd isglob}'ally'$convergent i.e.foreveryinitialH,y5lim\Ɵk+B!1)ȵH^(k+B)Dz=RdiagdUY(1|s;:::nq~)nwhere1;:::n lisanorderingoftheeigenvqaluesofH.RThisisprovedin[4]. ,InthecaseofsimpleeigenvqaluesthemethoGdisRquadr}'atically8convergentI(see[15 ]).mInthecaseofmultipleeigenvqalues,L theRmethoGdconvergesquadraticallyprovidedthediagonalsconvergingtotheRsame eigenvqalueoGccupysuccessivepGositionsonthediagonal.UnderthisRconditionUUithasbGeenprovedUUin[6]that  jj (H((r7+1)N,)"X)jjF l<$K1:8Kwfe  (֍;jj (H(r7N,)S)jj2፴F; r5r08(18)lRsrc:297Jacobi.texholds,ʍprovidedthatjj (H^(r0 N,)CW)jjF Bcb`=3.HereE=minfl,wdm :lu*>RmgUUistheminimumabsolutegapinthespGectrumofH.asrc:301Jacobi.texLetH2C^nnbGepositivede nite.9#ThenallH^(k+B) ,k0arepositiveRde niteUUandscalediteratesarede nedby}H:(k+B)"S¨=[diagUY(H(k+B) )]1=2˵H(k+B)[diag(H(k+B))]1=2˵; k0:8(19)Rsrc:308Jacobi.texW*eUUshallfrequentlyusetheo -diagonalpartofH:(k+B)"S ,L A(k+B) = (H:(k+B)"S )=H:(k+B)"S4p8I; k0;8(20)WbRsrc:312Jacobi.texandUUitso -norm, c k=jj (H:(k+B)"S )jjF; k0:8(21)Rsrc:316Jacobi.texNotethatalldiagonalelementsofA^(k+B)?=(a:(k+B)6l `m +);kD0arezeroandthe Ro -diagonalUUelementsaregivenby%a:(k+B)6l `m =_4bh:(k+B)6l `mKӉfe/bÏandAarereplacedRbyUU r7Nبand 8,respGectively*.K Uj7,3.=THEUUEFFECTSOFNONUNIT*ARYUUTRANSFORMATIONS,src:331Jacobi.texIteiswellknownthattheo -normofH^(k+B) reducesmonotonicallybythe ,rulebjj (H(k+B+1))jj2፴F l=jj (H(k+B) )jj2፴F82jh:(k+B)Zij +j2|s;URk0UU:,src:335Jacobi.texThisUUpropGertyisnotsharedwiththesequenceofscaledmatricessinceSٍQ ʵH:(k+B+1)"S⫲=((k+B+1)K)1 t(U(k+B) B)(k+B) +H:(k+B)"S (k+B)U(k+B)((k+B+1)K)1L,src:339Jacobi.texwhere^(r7) =s diagd(H^(r7) });]r(s 0,VMisnotaunitarytransformation. @In,factHtheo -normofscaledmatricescantempGorarilyincreaseduringthe,proGcess.Our rsttaskwillbeto ndauniformupperboundforthis,growth˘duringone(say*,)(the rst)cycle.ԏInouranalysisweshallneed,theEfollowingauxiliaryresults.TheirproGofscanbefoundinthetechnical,repGort.qǵH%ScanUUbecomplexorreal.p;Lemma2.m:src:348Jacobi.texL}'et[HZk=m(hl `m *c)beapositivede nitematrixofordern. @,Supp}'osex䍑)Ne2Hbis2obtainedfromH0byapplyingasingleJacobistepwhichan-,nihilatestheelementhij .L}'etA=(al `m *c)andx䍑\eA =({eal `ms)bede nedby-QAc =t5HS8I; f]HS=1=2˵H1=2;=diag(H);@x䍑S狫eQAc =x䍑w)Qet5HS&8I;x䍑ye f]HSH|=x䍑*e1=2x䍑 EVe:Hx䍑(qǫe'81=2B5Z;x䍑 e f]=diag(x䍑WeH ):,src:360Jacobi.texThen\5 (i)ヸj{eail /Dj2S+8j{eajgl j2ྲ=<$jailj^2S+8jajgltj^22<(aij ~fe /Dgail:jjAjjF,theny/N!(iii)ヸjaij jZ<$212wfe (֍2 fjjAjj2፴F:Oy,src:372Jacobi.texW*e,seethatonlyquadraticallysmall(inthescaledsense)pivotelement ,cancausethegrowthofjjAjjF.QNowweareableto ndanuppGerbound,forUUthe nitesequence 0|s; 1;:::; N providedUUthat 0Ȳissmallenough.p;Lemma3.m:src:378Jacobi.texL}'etHbeapositivede nitematrixofordernq3andlet,N(b}'e givenbytherelation(17). LetH^(0)Y@=͵HA;H^(1) s;:::;H^(N,) 8^Eo; f]n3;^8(25)+,src:429Jacobi.texwher}'eۖ 0X and iarede nedbytherelations(21)and(9),srespectively.\&Then,fore}'ach0kNthefollowingrelationshold3E(i)R>W(180:0279 8)sr  <h:(k+B)͍tt <(18+0:0281 )sr t2Nrm;>1r5p;ƍ/Q(ii)R>Wr}'gZ(h:(k+B)͍tt +;h(k+B)፴q@Lq)>0:9454 8; f]t2Nlȵ;>q"2Nrm;lx6=r;S~,!](iii)R>Wjtan'(k+B) +j0:529󙍑33ja:(k+B)Zijj33fe (֍# ib; f]i2Nlȵ;>jY2Nrm;lx6=r:ya,src:442Jacobi.texIn(iii)(i;j)=(i(kP);j(k))isthepivotp}'air.+,src:444Jacobi.texF*romUUlemma5(i)itfollowsimmediatelythatforany0k1|s;k2CN, 37>0:9455<<$K180:0279 Kwfe2 (֍18+0:0281 :3<<$Kh:(k1 )͍ttKwfeg h:(k2 )]"q@Lq<<$K18+0:0281 Kwfe2 (֍180:0279 <1:0577;t;q"2Nrm;^8(26)Q'ҳ1r5pUU;+,src:452Jacobi.texholds.qAlso,UUtheassertion(i)(seealsoitsproGof)impliesWw沵h:(k1 )͍tt>h(k2 )፴q@Lqp;URt2Nlȵ;q"2Nrm;lxhq@Lqksrc:485Jacobi.texwhereUUthesetsNrm;1r5pUUarede nedbytherelation(2).΍Rsrc:488Jacobi.texThe rstcondition(A1)showstowhatextentHhastobGealmostdiagonalRin"thescaledsense.`Theconstant1=6canbGeincreasedtoacertainextent.RHere^itischosentoobtainamoGderatequadraticconvergencebGound.TheRsecondUUcondition(A2)canbGeremovedUUinthecaseofsimpleeigenvqalues.asrc:494Jacobi.texIn practicehowever,None generallydoGesnotknowwhethertheeigenvqal-RuesbofH2޲aresimpleornot,^soinordertopreservethequadraticconvergenceRundertheserialstrategies(orsimilarones,see[12 ]),thealgorithmsarede-RsignedXtoorderthediagonalsduringtheproGcess(seetheLAP*ACKXSauxiliaryRroutineSLAEV2ortheconstructionofsomeecientstrategiesfrom[13 ]).RThus,˘theassumption(A2)canbGeachievedinpracticeinearlierstageofRtheUUproGcessasthecondition(4).9R4.2.lTheMainThe}'oremڍRsrc:507Jacobi.texHereAwestatethemainresultandproveitbrie y*.^ThedetailsoftheproGofRareUUgiveninthefollowingSubsection4.3andinthetechnicalrepGort.aTheorem6.~{src:511Jacobi.texL}'etyH7d2C^nnsatisfytheasymptoticassumptions(A1)Rand(A2).L}'etthesequenceH^(0)S=YHA;H^(1) s;:::;H^(N,)begeneratedbytheRc}'olumn-cyclicJacobimethod.Then)+ N ZIdr[Idfefg<$33533wfe (֍2G<$l ^ z2l0lwfe 됟 (֍ QRsrc:516Jacobi.texwher}'e 0|s, N )and "arede nedbytherelations(21)and(9)respectively.asrc:519Jacobi.texPr}'oof. TheproGofofTheorem6islongandcomplicated.:ItusestheRinductionUUoverthesetf1;2;:::;pg.qFirst,weintroGducenotation.qLetX3EtLn=[e1|s;e2;:::;etV];UR1tn Ue11,src:523Jacobi.texwherep Ine=[e1|s;e2;:::;enq~]p istheidentityp matrixofordern.Bytriu(X)is ,denotedUUtheuppGer-triangularpartofX7i.e.m2Y=triu(X) q¸(UX)yl `m {=^dGxl `m *c;+lxmز0;+lx>m22,src:528Jacobi.texwhereUUY=(yl `m *c),X=(xl `m *c). ƍ,Recall|>fromtherelation(20)thatA^(k+B) =(A:(k+B)Zij +)denotesthematrixH:(k+B)"S FI,partitionedinaccordancewiththerelation(5). F*or1tnwede ne,matrices2*sM:(k+B)͍t/=pMETtCA(k+B) +EtV;^8(28)ƍu]N:(k+B)͍t/=pMETtCA(k+B) +;^8(29)|uwBT:c(k+B)͍t/=pMtriu[ETtC(A(k+B) drbp 獍8X ߴl `=1UQA:(k+B)6l `l +)EtV];^8(30) +,src:540Jacobi.texwhere꩸denotesthedirectsum.1ZerosupGerscriptsareomittede.g.A= c,A^(0) u,@MthP=M:(0)͍tlԲetc.=InDthe gurebGelowmatricesMtV,NtandTtare,sketched.;8src:593Jacobi.tex ӊjwfeV(dU[U[feR3U[U[fefefeV(dqijwfeV(dU[U[feR3U[U[fefefeV(djwfeV(dU[U[feR3U[U[fefefeV(d9jwO line10@9jw@"9jw@,9jw@69jw@@9jw@J9jw@T9jw@Y@qxjw@{xjw@xjw@xjw@xjw@xjw@xjw@xjw@+@ejw@ejw@ejw@ejw@ejw@ejw@ejw@ejw@ @) Mt(NtTt ӊjwfefetfefefe⎎$-fe"n"$"$fe"$"$fefefe"nqijwfefetfefefe⎎,+-fe"n"$"$fe"$"$fefefe"njwfefetfefefe⎎-fe"n"$"$fe"$"$fefefe"nFFR3fe@sލsfesބsfefefe@PϟR3fe@sލsfesބsfefefe@ XR3fe@sލsfesބsfefefe@ tPt jPyt tt捒F0xčj0;܍}0)0L$6=0ި卑͕ jAqި卑͕ jAqި"-F卑"-F͕"-F "-Fj"-FA"-Fq"-F"-Fި*o卑*o͕*o *oj*oA*oq*o*oި3?卑3?͕3? 3?j3?A3?q3?3?ި;卑;͕; ;j;A;q;;ިDQ卑DQ͕DQ DQjDQADQqDQDQިL卑L͕L LjLALqLLިt}卑t}͕t} t}jt}At}qt}t}ި}9卑}9͕}9 }9j}9A}9q}9}9ި卒͕ jAqިK卒K͕K KjKAKqKKި!卒!͕! !j!A!q!!ި^J卒^J͕^J ^Jj^JA^Jq^J^Jިs卒s͕s sjsAsqssިp卒p͕p pjpApqppި卒͕ jAqި卒͕ jAqAqAjqjjAqA |q | |卒%͕% %j%A%q%% m#jwEDIHDIH̍\DIHDIH̎̉EqjwV2DIHDIH̍\U[DIH̎̉V2Ԙ5jwEDIHDIH̍\DIHDIH̎̉E2*,src:598Jacobi.texW*eUUshallalsomakeuseofcertainbloGcksofA^(k+B) +;k1:*Í􍍑8F:c(k+B)]"rV9=(a:(k+B)Zij +);1isr71q.havezero ,norm."Note:thatFrm,tV}feȟF FrandGrconformwiththepartition(5).These,bloGcksUUaresketchedinthefollowing gure. UR12jazsrc:642Jacobi.texQfexMwDwDfe?ގwDwDfefefexMQfe궍fe 궄fefefe'ojrfe۟fefefefeێm$fe۟fefefefeێQJfexM'l'lfeJwD'lfefefexMEOfe(6wDwDfe?ގ'lwDfefefe(6궟@궟@'궟@1궟@;궟@E궟@O궟@Y궟@c궟@m궟@w궟@j@FHPsr71 fsr<rsr71;hsrʍT2EFr-%ڵF^cTrҋCuk}feȟF}=zTK}=zrS~}feȟF[RFr䦟fexMwDwDfe?ގwDwDfefefexM䦟fe궍fe 궄fefefe\jrfe۟fefefefeێٟfe۟fefefefeێK S!fdwD wDfeK @K @K @K @K @K @K @K @K @K @ K @O@K }fd궎⠟jrfeFsr71 ߵsrhǵsr71;\msr%QGr-G^Tr]Rsrc:647Jacobi.texInUUtheproGofofTheorem6weshallusetheinequality7omjjT;c(Qsrေ)!srQLjjF lCr<$ljjNsrMjj^2bFlwfe"( (֍.Ƶ &n;UR1r5p8(32)ÍRsrc:652Jacobi.texwhereUUQsr Fisgivenby(24)andCrisde nedby aCr4=0:9-r AY ti=1(18+25<$33jjGiTLjj^2bF33wfel (֍ ] 8r2YҲ)1=2 ʵ;UR1r5pUU:8(33)!.Rsrc:657Jacobi.texUsingUUtheinequalityϾGY 8le(18+xlȲ)(18X (lUQxl)1 t;URxl0;X  lnxl<18(34)!Rsrc:661Jacobi.texandUUtheassumption(A1),weobtainfromtherelation(33)Ũ\C2፴r]<$~X0:9^2WwfeQi 鍲1825Pލ 8r% 8i=1Kg jjGi*jj2?F gˉfeHM n92⠸<$j0:9^2Kwfe*$h X!1825}/ô 2w0336fe !2 n92! ]<$t[0:9^2WwfeE|p (֍1812:5(1=6)r2 Χ<1:241UU:Rsrc:668Jacobi.texThusUUwehaveuniformbGoundsforCrm,]󍍒? 0:9Cr4<=Vp o=Vfe!ª1:241%8; 1r5pUU:8(35)Rsrc:672Jacobi.texThe9proGofoftherelation(32)usesinductionwithrespecttor.hW*edevide Ritintothreeparts.MInthe rstpartthebaseofinductionischecked.MIntheRsecondUUandthirdparttheinductionstepisproved. EUe13,P ARTTI,fe'uG/,If_or =1,aT:c(Qs1)"s12C^n1 n1Ьiszero,hence(32)holdsforr =1.Nextassume ,that~OjjTc(IJ)፴sr,r1jjF lCr71HljjNsr,r1jj^2bFlfe* (֍ ^8(36)$,src:685Jacobi.texholdsforsome1r5p,whereI:=Qsr,r1ز=1vi+2+:::y+(sr71 1)isthe,supGerscriptobtainedafterrotatingtheelementatposition(sr71h{e1;qsr71).N8,P ARTTIQI,fe,#~,T*oFprovetheinductionstepweconsiderQsr r$õQsr,r1stepsinwhichtheele- ,mentsofGrarerotatedinthecolumn-wisefashion.,Notethatthisordering,(of 1annihilations)oftheelementsofGrvӲisequivqalenttotheorderingob-,tainedbyconcatenatingthecolumn-wiseorderingassoGciatedwithFryand,theUUcolumn-wiseorderingassoGciatedwithAr7r[D.qThisfactisprovedUUlater.;src:697Jacobi.texLetwIIsղ:=Qsr,r1++ksr71(srh sr71)=IM+ksr71nrIbGewthesuperscript,obtainedךaftercompletitionoftheannihilationsinthebloGckF:c(IJ)]"r :&.GW*eshall,prove$Qo|vjjTc(IJI)፴sr,r1jjFCr71<$ljjNsrMjj^2bFlwfe"( (֍.Ƶ &n;^8(37)$Q|@BjjFc(IJI)፴rPjjF4:356<$33jjNsrMjj^2bF33wfe"( (֍ 8r2$jjGrmjjF 5:^8(38)#"5,P ARTTIQII,fe0ѵp,LetIII:=Qsr  =1+2+::: ɲ+(sr31)=IIts+nrm(nr1)=2bGethesuperscript ƍ,obtainedz27ȉfe/?]ꍄ]fe .u]fefefe/?گȉfe/?]ꍄ]fe .u]fefefe/?>27QBfe/?]ꍄ]fe .u]fefefe/?گQBfe/?]ꍄ]fe .u]fefefe/?'Ȭ@'@#'@-'@7'@A'@K'@U'@_'@i'@s'@}'@_k@#@#@#@#@#@#@#@#@#@#@#@#@Tk@'QB@'QB@#'QB@-'QB@7'QB@A'"QB@K',QB@U'6QB@_'@QB@i'JQB@s'TQB@}'^QB@_c@#QB@#QB@#QB@#QB@#QB@#"QB@#,QB@#6QB@#@QB@#JQB@#TQB@#^QB@Tc@&woJ!&w07 F!<oJ!׍MI׍5; IGIn]˾IGII|Msr,r1u'PFr/G "F^cTr/gN$3Ar7rSfeՅ?T, cfe^?f˄fe96f?ݠbfe?i|y:feÜ|?|U+feN|U?f.- fe.-?? %feѲq ?1ބ*@fedI?C.ufe"C?CB=.ufeCJt=?G=.ufeGL=?Lz=.ufeL$=?Q,ʟ=.ufeQ_=?Uޢ=.ufeVԟ=?Zz=.ufeZì=?_BR=.ufe_u=?c*=.ufed'\=?h=.ufeh4=?mWڟ=.ufem =?ߔȟsfes?F$ cfeyӟ$?yƄfe+?RĈbfe݄Ĉ?\*:wy:fe\:w?P+feA5P?۟Ҟ( fe Ҟ(?qP%feP?#ل*@feV? eೲ.ufe ೲ?їRsrc:758Jacobi.texT*o nishtheproGof,weusetherelations(40),(39),(37),(38),(33)and(35) RtoUUobtainїijjTc(IJII)፴srgPjj2፴F=ݯjjTc(IJII)፴sr,r1gPjj2፴F+8jjFc(IJII)፴rjj2፴F8(41)8ݯjjTc(IJI)፴sr,r1jj2፴F+81:0212|sjjFc(IJI)፴rPjj2፴F5썍ݯC2፴r71<$IjjNsrMjj^4bFIwfe"( (֍ 8r25b+81:0212S4:3562<$ljjNsrMjj^4bFlwfe"( (֍ 8r4&njjGrmjj2፴FݯC2፴r71T^ܲ18+(<$331:0214:35633wfe4 (֍0:97-)2S<$ljjGrmjj^2bFlwfe Ÿ (֍ Z 8r2"^qԸ<$ljjNsrMjj^4bFlwfe"( (֍ 8r2gݯC2፴r<$f¸jjNsrMjj^4bFfŸwfe"( (֍ 8r2-r:gRsrc:771Jacobi.texThis'completestheinductionstep.bThuswehaveprovedtherelation(32).RTheUUproGofofTheorem6goesoninthesimpleway*.qWeUUhaveӍS/ z2፴Nk=}k2jjTc(N,)፴sp9Bjj2፴F+bp 獍8X ti=1UQjjA:(N,)Zii ճjj2፴F8(42)yUe15 5EWk2jjTc(N,)፴sp9Bjj2፴F+<$2lwfe 8 (֍ 8r258(2jjTc(N,)፴spjj2፴F)2 5 q²2jjTc(N,)፴spjj2፴F(18+<$4lwfe 8 (֍ 8r2UjjTc(N,)፴spjj2፴F)P퍍EWk2C2፴pf¸jjNspyjj^4bFfŸvfe"DE (֍  8r2):(18+4C2፴pf¸jjNspyjj^4bFfŸvfe"DE (֍  8r4) q¸2C2፴p<$fµ ^ z4l0fŸwfe 됟 (֍Y 8r2(18+4C2፴p<$fµ ^ z4l0fŸwfe 됟 (֍Y 8r4)EWk281:241(1+41:241(1=6)4|s)<$l ^ z4l0lwfe 됟 (֍Y 8r2 q²2:5<$l ^ z4l0lwfe 됟 (֍Y 8r2,src:786Jacobi.texwherewҟPލ p% i=1%jjA:(N,)Zii ճjj^2bF haswbGeenboundedbyTheorem1(ii).?Thiscomple- ,tesPtheproGofofTheorem6.p,src:793Jacobi.texHere8wepresenttheproGofoftherelation(32)inalldetails.qHowever,qto,makethepapGershorterwehavemovedtheproGofsofauxiliarylemmasto,theUUtechnicalrepGort.;src:797Jacobi.texW*edstartourconsiderationbyshowingthatthesamematricesareob-,tained1ifthecolumn-wiseorderingofannihilationsinGrӲisreplacedby rst,the%column-wiseorderingofannihilationswithinFr]andafterwardsbythe,column-wiseޖannihilationswithinAr7r[D.J2Thisisindicatedinthe gurebGelow,inTiamoregeneralsetting(indicesqBandwLcanbGespecializedtosr71.qxand,srm,UUrespGectively)k[8src:836Jacobi.tex ӊjwfeV(dU[U[feR3U[U[fefefeV(dqijwfeV(dU[U[feR3U[U[fefefeV(djwfeV(dU[U[feR3U[U[fefefeV(d9jw@9jw@"9jw@,9jw@69jw@@9jw@J9jw@T9jw@Y@qxjw@{xjw@xjw@xjw@xjw@xjw@xjw@xjw@+@ejw@ejw@ejw@ejw@ejw@ejw@ejw@ejw@ @3S1.(S2M$S ӊjwfe@sލsfesބsfefefe@*GhUfe98缍8fe"8缄8fefefe9qijwfe@sލsfesބsfefefe@Ufe98缍8fe"8缄8fefefe9jwfe@sލsfesބsfefefe@rzUfe98缍8fe"8缄8fefefe9ɘDf+ݍdz-Xw qZ (1鍑(Dxq͍_޸w鍒q͍tAw鍒oq͍' wꟾfe?q? afe??"vRfeU?<ϡmfenϡm?R3sfe4R3?4ȟ"$feg?原೿'jfe೿?Td-0feɆd?GK36fezLK?8fe+?0+aUsfe0^U?5'Usfe6YU?;ퟸUsfe;U?A=UsfeAp埸U?FyUsfeG!U?L?UsfeLqU?RPUsfeR7U?X˟UsfeX3U?]Usfe]ßU?cbWUsfecU?Vs"$fe?9?'jfe:k??-0fe1?hşϡm36feϡm?R38feLR3?Q>fe?{೿DIHfeI೿?+ݟdIfe_d?$ܣKOfe%՟K?*iU[fe*?,src:839Jacobi.texHereUUS1|s,S2ȲandSdenotethesequencesofpivotpairs:qRNS1f=xs((1;q+81);(2;q+81);:::;(q[;q+81);xs(1;q+82);(2;q+82);:::;(q[;q+82);[uxs(1;wD);(2;w);:::;(q[;w))pRNS2f=xs((q+81;q+2);ކUR16s(q+81;q+3);(q+2;q+3);[us(q+81;wD);(q+82;wD);:::;(w}ø1;wD))p{4S=s((1;q+81);(2;q+81);:::;(q[;q+81);s(1;q+82);(2;q+82);:::;(q[;q+82);(q+81;q+82);]s(1;wD);(2;w);:::;(w}ø81;w))iRsrc:854Jacobi.texandB+denotestheconcatenationofthesesequences.PStartingwithS1.+nS2 RwerhavetoshowthatusingonlyadmissibletranspGositionsthesequenceSRcan bGereached.VAnadmissibletranspositionisasimpleinterchange oftwoRadjacent8pairs(k됵;k),q(k+B+1 ;k+B+1)8providedthatfk됵;kg\fk+B+1 ;k+B+1g=R;.aLemma7.:src:862Jacobi.texS1S+8S2CS,i.e.these}'quenceS1+8S2Zise}'quivalenttoS.asrc:865Jacobi.texPr}'oof. Starting=withS1ʲ+ WS2weuseadmissibletranspGositiontomove R(q+@1;q+2)#justbGehind(q[;q+2),DthenwemovebGoth(q+@1;q+3)Rand(q+O2;q+3)justbGehind(q[;q+3)etc. YFinally*,`_thesubsequenceR(q+81;w}ø1);:::;(w}ø2;w}ø1)UUismovedUUjustbGehind(q[;w}ø81).qDŽRUsing[6,Lemma1.1]weconcludethatthebGothsequencesofpivotpairs:S ƍRand2S1C+ƝS2yieldthesamematrixH^(IJII)oandthereforeA^(IJII)ٲ=H:(IJII)"S\I.asrc:874Jacobi.texSince^wehavealreadycheckedtherelation(32)forr=L{1(PartI),weRproGceedUUwithadetailedproofoftheinductionstep.pRP*ARTUUIGIRfe&;RHere6ttheelementsofFoc(Qstr,r1O)퍴r#Yarerotatedbycolumns.$W*econsidertheXRsequence9ofmatricesAz(Qstr,r1O+tsr,r1 ن);=Ho(Qstr,r1O+tsr,r1 ن) 荴S;)sCI,0Dtnrm,RwhereUUt=0correspGondstotheinitialmatrixinthispart.qLetv!wm _=Qsr,r1X+8(m1sr71)sr71; sr71+81msr:8(43)K/A㍑Rsrc:887Jacobi.texW*econsiderannihilationsoftheele-Rmentsinthe xed(mth)columnwithinRthe(bloGckFrm.MNotethatthesuperscriptRwm LFcorrespGondstothestagejustbeforeRannihilationڶoftheelementsofcolumnRm.qW*eUUhave<^/src:905Jacobi.tex0ferBqxqxfeDqxqxfefeferB0fe+z*͍*fe*̈́*fefefe+zUfeV(d*͍*feU[*fefefeV(d0@ 0@0@0@(0@20@<0@F0@P0@Z0@d0@gx@*z"*feU(hU*feGn>Msr,r12:ŵFr-GF^cTr捑8Ar7rލGcmK3 NfeKf?N?K3 _ф~feKf?_?K3 U~feKf?U?oUe17;Lemma8.m:src:909Jacobi.texL}'et`H}^satisfytheassumptionsofTheorem6.Letwm Ebe ,de ne}'dbytherelation(43).Then H;(i)`a:(wm+k+B)6k+Bm =0;v1ksr71`F(ii)`ja:(wm+k+B)6l `mj=Vp o=Vfe!ª1:015!(ja:(wm)6l `m,۸j8+<$l1:058lwfe! (֍õ ",k X Gt=1--ja:(wm)6l `ta:(wm+t1)͍tm&5j);M1ksr71;>k1lx6=tsr719⍍GZV(v[ٲ)`ja㍱(wm+sr,r1 ن)K\l `t)+jja:(wm)6l `t,۸j8+<$l0:529lwfe! (֍õ fgja:(wm+l `1)6l `m&a:(wm+l `1)͍tmj;1lxsr71q.1lxsr71;"|z7+(ii)3O֚sr,r1 q͍P햟X Q͕l `=1`vZ(a:(wm+qlұ)6l `mᆲ)2 r<$20:569^2፴m2wfe$fB (֍  8r2-'jj[ٱ(wm)፴mjj2፴F(jjM(wm)፴sr,r1CjjFԍf:+<$l0:387^2፴mlwfe$fB (֍US )jj[ٱ(wm)፴mjj2፴F)2|s;>forany(b lxqlsr71;>1lsr71;,src:957Jacobi.texwher}'e[Om _=<$APp'۟Pfe!E1:015KwfeU 18 l0:754l&feQ̟ jjM:(wm)]"sr,r1CjjF^lO:^8(46)vUR18Rsrc:962Jacobi.texThenextlemmaestimatesthenormsofthematricesMsr,r1VandTsr,r1after RtheUUannihilationsinthemthcolumnofthebloGckFrarecompleted.OaLemma10.Ssrc:967Jacobi.texL}'etϵHsatisfytheassumptionsofTheorem6.GNThenforRsr71+81msrholdڕS(i) jjM(wm+1.)፴sr,r1ΪjjFIjjjM(wm)፴sr,r1CjjF+<$l0:749^2፴mjj:[ٱ(wm)]"mjj^2bFlwfeNh (֍$vf &[18+<$lPp jPfe!E0:569lwfex (֍ n #(jjM(wm)፴sr,r1CjjF+<$l0:387^2፴mlwfe$fB (֍US )jj[ٱ(wm)፴mjj2፴F)];rV$(ii)'θjjTc(wm+1.)፴sr,r1jjFIjjjTc(wm)፴sr,r1jjjF+<$l0:529^2፴mjj:[ٱ(wm)]"mjj^2bFlwfeNh (֍$vf [18+<$lPp jPfe!E0:569lwfex (֍ n #(jjM(wm)፴sr,r1CjjF+<$l0:387^2፴mlwfe$fB (֍US )jj[ٱ(wm)፴mjj2፴F)];4Rsrc:981Jacobi.texwher}'eM:[ٱ(k+B)]"mandm &arede nedbytherelations(44)and(46),lrespectively.AcBRsrc:984Jacobi.tex8src:985Jacobi.texTheMԲ(ii)mڸja(wm)፴q@Lm,۸j=ja(wq-+1 )፴q@Lm j=Vp o=Vfe!ª1:015!(ja(wqV)፴q@LmQj8+<$l1:058qlwfe!8< (֍ P %ׂjj[ٱ(wqV)፴q*jjFjj[ٱ(wqV)፴mjjF):5Rsrc:1023Jacobi.texInfctheprecedingthreelemmaswehaveestimatedcertainmatrixelementsRaftervrotatingsome(orall)elementsofthemthcolumnofFr dviatheRelementsofmatrixatstagebGeforetheserotationstookplace.eOuraimisRto1obtainbGoundsexpressedintermsoftheinitialdatai.e.theelementsRofvthescaledmatrixA.QF*orthatpurpGoseweusetheinductionhypGothesisRstatedUUbytherelation(36).rUe19;Lemma12.sSsrc:1032Jacobi.texL}'etֵHTsatisfytheassumptionsofTheorem6.lcIfthehy- ,p}'othesis(36)holds,thent_E֨jjM(IJ)፴sr,r1jjF l3:134H33jjNsr,r1jj^2bF33fe* (֍ -Q];DI=18+2+:::g+(sr711):Te,src:1037Jacobi.texWithUUlemma12wecanprove?;Lemma13.sSsrc:1040Jacobi.texL}'et̵HnsatisfytheassumptionsofTheorem6.ELetwm 7gand,m b}'eDBde nedbytherelations(43)and(46),T0respectively. Ifthehypothesis,(36)holds,thenforsr71+81msrwehave4p(i)Esrc:1045Jacobi.tex 8m _=1:079Ql,<Ս1`(ii)Esrc:1046Jacobi.tex 8jjM(wm+1.)፴sr,r1ΪjjF l3:134<$33jjNmjj^2bF33wfe!cҟ (֍  <, .P(iii)Esrc:1048Jacobi.tex 8jjTc(wm+1.)፴sr,r1jjF lCr71<$IjjNmjj^2bFIwfe!cҟ (֍  .,src:1052Jacobi.texF*orm=sr\$theassertion(iii)isjusttherelation(37).OLetusconsidernow,the9)q[thcolumninFr˲(sr71+1q"srm)9)aftertheannihilationsinithave,bGeenUUcompleted.;Lemma14.sSsrc:1060Jacobi.texL}'etHhsatisfytheassumptionsofTheorem6.ELetsr71+1 ,qssr.;andletwm,ŵ:[ٱ(k+B)]"mHandm Y4b}'ede nedbytherelations(43),(44)and,(45),r}'espectively.Ifthehypothesis(36)holds,thenҍBZjj;[ٱ(wsr+1l4)!qQjjF l1:012jj[ٱ(wq-+1 )፴qh޸jjF+<$l0:66lwfe (֍µ c!wsr v{X m=q@L+15yja(wq-+1 )፴q@Lm j8jjmjjF 9ǵ;,src:1067Jacobi.texwher}'eforq"=srtheemptysumisassumedtobezero.,src:1069Jacobi.texNowUUweareabletoprovetherelation(38).;Lemma15.sSsrc:1072Jacobi.texL}'etֵHTsatisfytheassumptionsofTheorem6.lcIfthehy-,p}'othesis(36)holds,then jjFc(IJI)፴rPjjF l4:3568<$ljjNsrMjj^2bFlwfe"( (֍ 8r2&njjGrmjjF 9ǵ:➍,src:1076Jacobi.texByFprovingtherelations(37)and(38)P*ARTEIGIofFtheproofiscompleted.p,P*ARTUUIGII,fe)ʎ,OpGerating-onthematrixMsr,r1MlandontheblockFr NaltogetherII2= ,Qsr,r1;G+(sr)sr71)sr71JacobiFrotationshaveFbGeenperformed.lAfterthat)EUR20qƍRtheelementsofthediagonalbloGckAr7r _arerotated.MatricesM:(IJI)]"sr,r1$]andryRT:c(IJI)]"sr,r1willf]notchangeatthisstagewhichimpliestherelation(40)."However, RthisUUisnotthecasewiththebloGckFrm.qF*orsr71+82msrlet%^avm=Qsr,r1X+8(srsr71)sr718(47)+8(msr711)(msr712)=2UU:Rsrc:1091Jacobi.texThe ~indexvm correspGondstothestagejustbeforerotatingoftheelementsRofUUmthcolumnwithinAr7r[D.P΍aLemma16.Ssrc:1095Jacobi.texL}'etõHsatisfytheassumptionsofTheorem6,zwherevm S^isRde ne}'dbytherelation(47).ThenȓjjF;c(vsr+1l4)!rǸjjF l1:0218jjFoc(vstr,r1 ن+2>)퍴r%ajjF 9ǵ:Rsrc:1099Jacobi.texThe.?lastlemmaproves.?therelation(39)andcompletesP*ART.IGIIof.?theRproGof.qTheUUrestoftheproofhasbeengivenintheprecedingsubsection."5R5.cCOMMENTSUUANDNUMERICALTESTS|Rsrc:1106Jacobi.texLetusrecalltheestimatesobtainedfortheHermitianJacobimethoGdap-Rplied[*toapGositivede nitematrixH.GW*ehavetheclassicalresultwithRabsoluteUUgap(seetherelation(18))whichcanbGestatedasfollows:SՍ<$%jj (H^((k+B+1)N,)#qF)jjF%wfeL (֍#y룒1:88^<$ ȇjj (H^(k+BN,)A)jjF ȇwfe<# (֍wHQ^O{ş2U;8(48)%UxprovidedUUthat<$IBjj (H^(k+BN,)A)jjFIBwfe<# (֍wg$<$K1Kwfe (֍3 Ե; Rsrc:1117Jacobi.texand4#thenewresultwithrelativegapandscaledo -norm(seeTheorem6): /)Gbqjj (H:((k+B+1)N,)"S#qF)jjFbqfeL (֍#d 1:68\ )G Vjj (H:(k+BN,)"SA)jjF Vfe<# (֍3 H\!P5ٱ2VP;8(49)*a>providedUUthat maxT$\()G•jj (H:(k+BN,)"SA)jjF•fe<# (֍3 \;URnjj (H:(k+BN,)"SA)jjF\)XO<$K1Kwfe (֍6 Ե:ӍRsrc:1128Jacobi.texLet~usinspGectthesituationwhenthenewresultimproves~theclassicalRresult.qSuppGoseUUthatH%Shasaclusteroftinyeigenvqalues.qIfeEi=a810k +; and)t=b810(k+B+l `) ; 1a;b<10;kP;lx20N7uUe21,src:1135Jacobi.texareUUthesmallestrepresentativesUUfromthatcluster,wehaveMiPx"ϵ8=10k +(a8b10l Qɲ)NM#ErgV (;)x"=<$8wfe (֍8+,=<$Ka8b10^lKwfe0W` (֍a8+b10rl8K=<$K18c10^lKwfe0b (֍18+c10rl5D; c=<$ybKwfeI0 (֍a v: ,src:1142Jacobi.texW*eseethattheabsolutegapᴲstronglydepGendsonkhandisverytiny ,evenpforsmallkP.\Onthecontrary*,therelativegapdoGesnotdependonk,anyMmore.-Since0:1>`,wecanexpGectthatthescaledRiteratesbGehavemoreregularlythantheordinaryiterates.VThetablebGelowRshowsUUthatstraightforwardlyOUe23DJ,src:1242Jacobi.texGffo qƍͤ bffğfdr.ᡄ bffk (H^(r7N,)S)kF r bff]8k (H:(r7N,)"SS)kF r bffffofdͤ ff͟fd0 ffI0:29Em+804  ffb*0:99Em+802  ff ͤ ff͟fd1 ffI0:10Em+803  ffb*0:38Em+801  ffͤ ff͟fd2 ffI0:20Em+801  ffb*0:24Em+801  ffͤ ff͟fd3 ffI0:15Em+800  ffb*0:26Em+801  ffͤ ff͟fd4 ffI0:13Em801  ffb*0:13Em+801  ffͤ ff͟fd5 ffI0:34Em803  ffb*0:69Em+800  ffͤ ff͟fd6 ffI0:69Em806  ffb*0:31Em801  ffͤ ff͟fd7 ffI0:31Em808  ffb*0:53Em803  ffͤ ff͟fd8 ffI0:11Em811  ffb*0:17Em806  ffͤ ff͟fd9 ffI0:13Em818  ffb0:17D813  ffffoqsrc:1258Jacobi.texW*e seethatduetotiny`, qthequantityk (H^(r7N,)S)kF ϲbGehavesqstrangely;8after*quadraticreductionqinthe5thand6thcycleonewouldqexpGectZfurtherquadraticreductions.qHowever,b"at,theendof6thcycle,qָk (H^(r7N,)S)kF l0:69O10^6 is(largerqthan`,.theclassicalquadraticcon-qvergenceÎresultcannotbGeapplied,qandthereisnowarrantyforfurtherqquadraticUUreductions.U-,On|theotherhand,̨since 8islarge,thequantity|k (H:(r7N,)"SS)kF P\bGehavesreg-b,ularly*.ONamely,bythemaintheorem,theconditionk (H:(r7N,)"SS)kF l< 8=200,impliesRthatk (H:(r7N,)"SS)kF N2reducesquadraticallyforr>Qh6.jNotonlythat,k (H:(r7N,)"SS)kF Breducesquadratically*,butitgivesalowerbGoundonthenum- ,bGerofsuredigitsindiagonalelements.&_Evenbetterboundforthatisthe c,quantityPp gܟPfeE2gݸk (H:(r7N,)"SS)k^2bF= (seeTheorem1).[Notethatincaseslikehere,,whenlk (H:(r7N,)"SS)kF l<1,ftherearesimplewaysltocomputetheneededlower,bGoundUUfor ㍲(see[7]).ꨍ,Ac9knowledgement,The authoristhankfultoPr}'ofessorV.Harifortheguidanceandhelpin,thisr}'esearch.%,REFERENCES61@src:1285Jacobi.texBarlow84J.,>DemmelJ.W.(1990)ComputingyA}'ccurateEigensystemsof@Sc}'aledYDiagonallyDominantMatric}'es+,a$SIAM+]J.Num.Anal.27,762-@791.62@src:1288Jacobi.texDemmelSJ.W.,#V*eseliGcK.(1992)Jac}'obi'sLMethodismoreAccurate@thenQR,UUSIAMJ.MatrixAnal.Appl.13,1204-1245.63@src:1290Jacobi.texDrmaGciZ.,nHariV.(1993)On7Quadr}'aticConvergenceBoundsforthe@J-symmetricJac}'obimethod,UUNumer.Math.64,147-180.64@src:1292Jacobi.texF*orsytheG.,OHenriciP.(1960)TheUCyclicJac}'obiMethodforComput-@ingthePrincip}'alV;aluesofaComplexMatrix,T*rans.v[Amer.Math.@SoGc.UU94,1-23.cϠUR24\5fsrc:1295Jacobi.texHansenE.R.(1963)OnICyclicJac}'obiMethods,SIAMJ.Appl.Math. f11,UU449-459.\6fsrc:1297Jacobi.texHariV.(1991)OnSharpQuadr}'aticConvergenceBoundsfortheSerialfJac}'obiMethods,UUNumer.Math.60,375-406.\7fsrc:1299Jacobi.texHariR|V.,SDrmaGcZ.(1997)OnISc}'aledAlmostDiagonalHermitianMa-ftrixJPairs,SIAMJ.MatrixAnalysisandApplications18(4),1000-f1012.\8fsrc:1302Jacobi.texV*anKempGenH.P.M.(1966)OntheQuadr}'aticConvergenceoftheSpe-fcialCyclicJac}'obiMethod,UUNum.Math.9,19-22.\9fsrc:1304Jacobi.texMascarenhasW.F.(1993)On/theConver}'gence/oftheJac}'obiMethodfforArbitr}'aryOrderings,UUUniversityofMinnesota,MinneapGolis.W10fsrc:1306Jacobi.texMatejaxsJ.(1996)Quadr}'aticConvergenceofScaledIteratesbyDi-fagonalizationMetho}'ds,UniversityEofZagreb,Ph.D.Thesis(Croatianflanguage).W11fsrc:1309Jacobi.texMatejaxseJ.(2000)Quadr}'atictheGlob}'alandCubicConvergenceofafQuasi-cyclicJac}'obiMethod,UUNumer.Math.66,97-122.W13fsrc:1313Jacobi.texDeЖRijkP*.P.M.Ж(1989)A.One-side}'dKJacobiAlgorithmforComputingftheKSingularV;alueDe}'compositionKonaVe}'ctorComputer,sSIAM J.;Sci.fStat.UUComp.10,359-371.W14fsrc:1316Jacobi.texRuheA.(1967)OnWtheQuadr}'aticConvergenceoftheJacobiMethodfforNormalMatric}'es,UUBIT7,305-313.W15fsrc:1318Jacobi.texWilkinsonvJ.H.(1962)NotelontheQuadr}'aticConvergenceofthefCyclicJac}'obiProcess,UUNum.Math.4,296-300.u);U; cmsy9:5" cmmi9+q% cmsy6*;cmmi6)2cmmi8(Aacmr6- cmcsc10': cmti10 cmmi10 0ercmmi7O \cmmi5K`y cmr10ٓRcmr7Zcmr5O line10u cmex10}