; TeX output 2000.04.01:1640l'&])FDtGGcmr17Quadratic7tconqvergenceofscaledmatrices_in7tJacobimethosdРXQ cmr12J.Matejaa?s2K cmsy8 .April1,2000*GC!J5t : cmbx9Abstract re4o cmr9A= cmmi10h 0ercmmi7ij jtol8ku cmex10p 8kfeޟvhii(hjgj%Կ; 1iDG^(k+B)=G[diag(H^(k+B))]^1=2 ʲ,9k޸0>andH^(k+B)βarematrices?generatedUUbythemethoGd.NF*orWcyclicmethoGdsitiswell-knownWthattheo -normsequenceassociated?withdH^(k+B)convergesquadraticallypGercycle(see[14 ,9e,8])._Let (X)denotes?theXo -diagonalpartofX.+F*ortheserialmethoGdswehave(see[8,Theorem2.8])YD]pjj (H(N,))jjF M<$O1:8Owfe  (֍:Ijj (H(0) s)jj2፴F4wheneverIjj (H(0))jjF l<$Kwfe (֍3?(1.1)? ffv @ -:q% cmsy6L|{Ycmr8FJacultÎyofEconomics,ΎUniversityofZagreb,ΎKennedyjevtrg6,10000Zagreb,CRÎOAJTIA?AprilUU1,20001*l'?andthediagonalelementsassoGciatedwithmultipleeigenvqaluesoGccupysucces- ?sivepGositionsonthediagonal. #OHereNy=bn(nC1)=2,IH^(N,)isthematrix?obtainedEafteronecycle,"w(istheminimumabsoluteseparationinthespGectrum?ofUUH^(0)S=H%Sandjj8jjF 5standsUUfortheF*robGeniusmatrixnorm.NHence5itseemsnaturalthatasimilarresultholdsforthesequenceofscaled c?iteratesǻH:(k+B)"S ,TkX0.RecentresultsonscaleddiagonallydominantHermitian?matrices1[6],8ZwhichprovidesharpbGoundsfortherelativedistancesbGetweenthe?eigenvqaluesmVandthecorrespGondingdiagonalelements,sVaregivenintermsofthe?o -normswofscaledmatricesandrelativegapsinthespGectrum.k-Thisindicates?thatapropGerquadraticconvergenceresultfortheJacobimethodshouldbe?expressedUUintermsofscalediteratesH:(k+B)"SPandsomeminimumrelativegap 8.NOurUUresultforthesamemethoGd(seeTheorem6)readsF~.~ N \ɸ<$K0:715Kwfe! (֍µ  z20AwheneverG 0C<$K1Kwfe (֍4 'minոf<$133wfe (֍ng; 8gUU;?(1.2)Ђ?whereip k*=蚸jj (H:(k+B)"S )jjF,nwk910and istherelativegapde nedby(2.11)and?(2.12).gThisnnewresultnotonlysupplementstheestimate(1.1)butinmany?situationsprovidesamuchbGetterortheonlyboundconcerningthequadratic?convergenceUUofthemethoGd.NSuppGosetheJacobimethodisappliedtothematrixgeneratedbythefol-?lowingUUMA*TLABprogram썍% UTMatrixUUH; input:qmatrixordern% UTandUUlogspaceparametersd1andd2.h=eye(n); forUUi=1:n-1;forj=i+1:n;h(i,j)=2e-3/(i+j-1)2;h(j,i)=h(i,j);>(1.3)end;end;w=logspace(d1,d2,n);ww=diag(w);h=wwhwwNW*eʧhavetestedquadraticconvergenceforsuchmatricesofdi erentorders ?bGetween40and120andwithdi erentlogspaceparameters.F*oralmostall?matricesdtheclassicalresult(1.1)cannotbGeusedbecausetheabsolutegapźis?toGo"smallwithrespecttotheo -norm(seeSection4forcomputationaldetails).?Our>result(1.2)however,9guarantees>andestimatesthequadraticconvergence?oftheo -normofthescaledmatrix.\HencethenewestimatecansometimesbGe?usedtopredictthenumbGerofcyclesuntilconvergencewhentheclassicalresult?completelyUUfails.qThisisoftenthecasewithgradedmatrices.NThennewresulthasaniceaplicationinconnectionwiththestoppingcriterion?forb$theacceleratedone-sidedJacobiSVDaalgorithmintroGducedbyZ.DrmaGc?(seem[4]).ThemethoGdusestwomQR preconditioningstepstoacceleratethe?Jacobialgorithm.1DThemethoGdorthogonalizesthecolumnsofthecurrentmatrix?AprilUU1,20002 ll'?untilthecosinesoftheanglesbGetweenthembGecomesucientlysmall.Hence, ?thepstoppingcriterion(seetherelation(3)in[4])requiresNdotproGductsafter?eachcycle.USincecosinesareexactlytheelementsofthescaledcross-proGduct?matrix,pour6estimatecanbGeecientlyusedtopredictthenumbGerofcyclesuntil?convergence,UUthussavingunnecesarycomputation.NInLthispapGerweconsiderthequadraticconvergenceofscalediterateswhen?symmetricԬpGositivede nitematrixhassimpleeigenvqalues.Thesameresult?holds,5withmmoGdi edconstants,forgeneralpGositivede niteandgeneralnonsin-?gularHermitianmatrix.JSinceinthosegeneralsituationsthetheorybGecomes?muchmorecomplex(see[11 ]),2wepresenthereonlythesimpliestcase.These?generalizations,includingYtheKogbGetliantztwo-sidedmethoGds,willbepublished?elsewhere.NThepapGerisorganizedasfollows.OInSection2weprovideashortdescrip-?tionofsymmetricJacobimethoGdandprovesomeauxilliaryresultsconcerning c?nonorthogonal6transformationsH:(k+B)"Si!mH:(k+B+1)"S.kThemainresult(Theorem6)?isUUprovedinSection3.qInSection4wepresentsomenumericalapplications.!č?2WLTheffe ectsofnonorthogonaltransformations?W*eQshortlydescribGeJacobimethodforsymmetricmatrices.F*oragivensym-?metricUUmatrixH29"V cmbx10R^n O!cmsy7nRthemethoGdgeneratesasequenceofmatricesrCH(0)S=HA;URH(k+B+1)⫲=(U(k+B) B)TLH(k+B) U(k+B); k=0;1;2;:::?where+U^(k+B)زisJacobirotationintheplane(i;j)wherei.'=i(kP),j=j(kP),with ?angleUU'^(k+B) +,de nedbyo􍍍Ctan`2'(k+B) =󙍑 2h:(k+B)ZijKfe. h:(k+B)Zjgj dr8h:(k+B)Zii3Cn; '(k+B)2[[=4;q=4]:?(2.1)"?Here㶵H^(k+B)=c(h:(k+B)]"pq +),Nk0.Thesubscriptsi,NjvAarecalledpivotindic}'es!,(i;j), ?i(aj6gisthe?minimumUUabsolutegapinthespGectrumofH.NWithH,whosediagonalhasnozeroelement,isassoGciatedsc}'aledDH,thatis?theUUmatrixbzHS=jdiagUY(H)j1=2˵Hzjdiag(H)j1=2˵:?(2.5)?HereDjXj=(jxpqj)providedthatXw=(xpq).MatrixHBis z-sc}'aleddiagonally?dominantꁲ( z-s.d.d.X)withrespGecttoanormkkifk (HS)kդ #forsome?0' 1<1.An> z-s.d.d.hasseveralimpGortantpropGerties.Oneofthemisthat?relativedistancebGetweendiagonalelementsandthecorrespGondingeigenvqalues?canbGeestimated(see[6])byconst_k (HS)k^2bF= 8,dwhere ~̲istheminimum?r}'elativegapinUUthespGectrumofH%S(seetherelation(2.12)). ƍNInTtheproGofweshallusematricesH:(0)"SS=HS,H:(1)"S s,...,H:(N,)"SIandTA^(0) u,A^(1),?...,A^(N,)+wherecfj'H(k+B)¨=DG(k+B) rH:(k+B)"S DG(k+B); DG(k+B)9Dz=[diagUY(H(k+B) )]1=2 ʵ;0kN?(2.6)?AprilUU1,20004*l'?and (A(k+B) =H:(k+B)"S4p8I; 0kN:?(2.7)Ke?AsUUiswellknown,theo -normreductionatonestepofJacobimethoGdreads6"ݸk (H(k+B+1))k2፴F l=k (H(k+B) )k2፴F82(h:(k+B)Zij +)2|s;URk0jȍ?whereaݵh:(k+B)Zijoisthepivotelement.aThispropGertyisnotsharedwiththesequence?ofUUscaledmatricessincemAgH:(k+B+1)"S⫲=(DG(k+B+1))1 t(U(k+B) B)TLDG(k+B) rH:(k+B)"S DG(k+B)U(k+B)(DG(k+B+1))15?isnotanorthogonaltransformation.^_Infact,&k (H:(k+B)"S )kF canincreaseforsome?kP.UOur- rsttaskwillbGeto ndauniformupperboundforthesequence 0|s,h 1,?...,UU N,where c k=k (H:(k+B)"S )kF; 0kN:?(2.8)Ke?The'bGoundwillbegiveninLemma3.bThefollowingtwolemmasareauxilliary*.1?LemmaT1r L}'etٵHbeasymmetricpositivede nitematrixofordern.nSupposex䍑AWe?HKfisFobtaine}'dfromHbyasingleJacobistepwhichannihilatestheelementhij .?L}'ett7A=~εHS8I;vHS=DG1 HDG1;D5=[diagUY(H)]/ 33133#&feg 2M;؍x䍑v$et7A=x䍒e~εHSҵ8I;x䍑 )evHS=x䍑eDG1x䍑ie>׵hjgjL&hr7rY:7?Denoting:bycands,cosineandsineoftherotationangle,therelations(2.2) ?andUU(2.1)implyq\qe)hir.=chir zθ8shjgr$N;\q }e hii]N=hiiax<$lslwfe (֍.c OFhij\qeGChjgr.=chjgr ].+8shirA;\q }e hjgj"=hjgj &8+<$lslwfe (֍.c OFhij?and (hjgj &88hii()sc=hij(c2Ss2|s):^?UsingUUtheserelationsoneobtainsSڵh2፴irAhiiax\q "e8h2፴ir\qe=ŵhiib4+8h2፴jgr$Nhjgj &8\q "eh2፴jgr\qge %hjgj =2hirhjgr$Nhij :?Hences-esӲa2፴ir+[e8a2፴jgr,="ԍ}a^2;Zir zβ+8a^2;Zjgr}^fe&1z (֍R918a:2;Zij <$$2airAajgr$NaijlwfeF (֍ar7r[D(aii(ajgj &88a:2;Zij ),="ԍ}a^2;Zir zβ+8a^2;Zjgr ].2airAajgr$Naij}^fe] (֍  18a:2;Zij,"ԍ}a^2;Zir zβ+8a^2;Zjgr ].+jaij j(a^2;Zir+a^2;Zjgr$N)}^ferER (֍*\%18a:2;Zij-?="ԍKa^2;Zir zβ+8a^2;ZjgrK^fe&1z (֍18jaij j+^:a?NoteCAthattheinequalitybGecomesanequalityifandonlyifjairAjS=jajgr$NjCAand ?sgnO*aij =sgn*(airAajgr$N)UUsimultaneouslyhold.N8?(ii)>5NotethattheconsideredJacobistepchangesonlythepivotrowsand?columns.qHenceUUbyusingtheassertion(i)weobtain⃍?_Bkx䍑\ueAk2፴F8kAk2፴F=2["ԍ Ϣa^2;Zij33^fe (֍18a:2;Zij'~n #5XX#$zO \cmmi5l=1p!l `6=i;j3>e(a2፴il+8a2፴jglt)<$ 2aijlwfe (֍1a:2;Zij*.^n %n8X#'.Zl=1p#l `6=i;j7!ailajgl Ta2፴ij ]*\{=2\""ԍOa^2;Zij2^fe (֍18a:2;Zij'sl(kaiTLk2S+8kaj6k2|s)<$ 2aijlwfe (֍1a:2;Zij",MaTiLajoa2፴ij \# ?AprilUU1,20006P[l'?WithD/Lemma1wecan ndconditionswhichmustbGemetifkAkF increases ?duringEoneJacobistep.VInthesequelkkEandkk2~denoteEtheEuclidianvector?andUUthespGectralmatrixnorm.ۍ?LemmaT2r L}'etpA,x䍑vǫeRAandaiTL,Raj6beasinLemma1.2IfkAk2Z<1andkx䍑\ueAkF /ǵ>?kAkF,then㍍?(i)dJsgntaij =sgna^T;ZiLaj6,?(ii)a"kx䍑\ueAk2፴F8kAk2፴F l2jaij j(<$33kaiTLk^2S+kaj6k^233wfe;O (֍ 1jaijj?fjaijj)jaijj8<$lkAk^2bF2jaijjlwfe;A$ (֍ 1jaijjD,!7?(iii)dSݸjaij jjjaiTLk^2S+8kaj6k^2+a^2;Zij  K1K&fes2 )kAk^2bF.~?ProQof(i)UUSincekaiTLk^2S+8kaj6k^2+2a^2;Zij kAk^2l2C<1UUwehaveު"ԍc8a^2;ZijZ^fe (֍18a:2;Zijy\(kaiTLk2S+8kaj6k2|s)a2፴ij="ԍa^2;ZijR^fe (֍18a:2;Zij(kaiTLk2S+8kaj6k2+a2፴ij Cظ1)"ԍa^2;ZijR^fe (֍18a:2;Zij(kAk22S81)0<0:h鍑?Now,fromAtheassertion(ii)oflemma1weconcludethatthattheassumption @?kx䍑\ueAkF l>kAkF 5impliesUUthe(i).N8?(ii)UsingUUtheSchwarz-CauchyUUinequalityoneobtainsguxkx䍑\ueAk2፴F8kAk2፴F[":2["ԍ33a^2;Zij Cز+8jaij j33^fe*oh (֍q018a:2;Zij,β(kaiTLk2S+8kaj6k2|s)a2፴ij ]Í[=":2jaij j(<$33kaiTLk^2S+8kaj6k^233wfe;O (֍ 18jaijj?f8jaijj)>(2.9)T?whichUUisthe rstinequalityin(ii).qF*urtherestimationyieldsNkƷkx䍑\ueAk2፴F8kAk2፴FK[<$b2jaij jEwfe#A (֍18jaij j [<$33kAk^2bF33wfe% (֍ 2)8a2፴ij Cظjaij j(1jaijj)]UK[=<$jaij jEwfe#A (֍18jaij j (kAk2፴F82jaij j):>(2.10)T?(iii)Thisassertionfollowsfromtherelations(2.9)and(2.10).hTheexpresions?inUUparenthesesmustbGepositive.Ţp?W*eXseethatonlyquadraticalysmallpivotelementcancauseanincreaseofscaled?o -norm.tTheuamountoftheo -normincreaseisalsoquadraticalysmall.The?nextKlemmaestimatestheaccumulatedincreasecommingfromNfsuccessive?steps.?AprilUU1,20007gl'?LemmaT3r L}'et&kHibeasymmetricpositivede nitematrixofordernЅ3and ?letPgNgb}'easintherelation(2.3).LetH^(0)=H,H^(1) s,...,H^(N,)b}'ePgobtained?by̑applyingNJac}'obistepstoHunderanyordering.CLet k!bede nedbythe?r}'elation(2.8).IfM? 0C<$1Kwfe (֍4n.;ƍ?then_4 z2፴kck됵 z20; f]ck=(18+0:007857013=n2|s)k<1:004; f]0kN:?ProQof ,0Firstpweproveck<1:004,81kN.6&Usingptheinequality(1+x)^m _< ?1=(18mx)UUwhichholdsforx;m>0;qxm<1,UUweobtainՑgckz<$cN \ɲ=(18+<$l0:007857013lwfe4' (֍% nr29fm)N<$2g1Kwfeax LǍ1 l0:007857013l&fe*<~n21&hln(n1)lʉfe_r 12hz<<$Z1WwfeK (֍180:0039285065䩵<1:003944000532:%?Theinequality ^ z2vkck됵 ^ z2l0;G1kN.isprovedbyinductionwithrespGecttokP. ?F*or.ki=0theinequalityholdstrivially.RSuppGoseitholdsforsome0ki k됲.?ByUUlemma2(ii)wehave@ z2፴k+B+1Ds8 z2፴kja:(k+B)Zij +j󙍑l ^ z2vk$p2ja:(k+B)Zijjlfe2 1ja:(k+B)Zijj" ?Thehfunctionf(a)a=a33 r2wk_2a33ڳfe$1aK;a2[0;۴ r2wk۟ڳfe DZ2 ]hattainsmaximumataE=r{ r2wk_=2ڳfe.Y&o1+vpUWvfe̟@1 2wk_=2?andUUf(a)=o r4wkKڳfe<|o2(1+vpUWvfe̟@1 2wk_=2$9#)2A9.qSo,wehaveCÍZ z2፴k+B+1ҫ z2፴k$p+8f(a)< z2፴k됲(1+0:125218345626 z2፴k);?andUUusingtheinductionhypGothesis,weobtainGXU z2፴k+B+1ҫ z20ck됲(18+<$l0:0785701293lwfe9( (֍ nr2>fn)ck+B+1 z20?whichUUcompletestheinductionstepandtheproGofofthelemma.91pNInUUthesequelshallusether}'elativegapfunction(UUcf.q[6])de nedbyʍ(a;b)=<$hja8bjKwfe , (֍jaj8+jbj&; (a;b)2R gp2hn8f(0;0)g:?AprilUU1,20008 wl'?Withmthisfunctionwede ninether}'elative`gapZofrdfromtherestofthespGec- ?trumj r4=pmin Uc1sn;s6=ros(rm;sF:);UR1r5n:?(2.11)덑?TheUUminimumrelativegapisthen)C[ UP=minw1r7nU rm:?(2.12)i?LemmaT4r L}'etH^(0)S=H,...,H^(N,)9b}'easinLemma3.Ifinaddition6焵 В<$K1Kwfe (֍4 'min-}^<$'`1&౟wfe (֍n.~; 8^Al;?(2.13)6?thenther}'eisanordering1|s,...o,n eoftheeigenvaluesofH,suchthat)r=(180:06275 8)r4<h(k+B)፴r7r <(18+0:06410 )rm;>1r5n?(2.14)?holdsfor0kN.퍑?ProQof F*romLemma3weknowthat kPp oPfe!E1:004!㐵=4< 8=( +3),{0kN. ?ThereforeUUwecanapply[6,Corollary3.2(i)]toobtainzˍ~18<$l ^ z2vklwfe Q3 (֍ r<$K:(k+B)]"rKwfe 0h:(k+B)]"r7r1+<$l ^ z2vklwfe Q3 (֍ ry;UR1r5n;0kN;?(2.15)s?where:(k+B)l1 +,...,:(k+B)]"n &isanappropriateorderingoftheeigenvqaluesofHlwhichmay?depGendUUonkP.qF*rom(2.15)weobtainfor1r5n;0kNqb&18<$V ^ z2vklwfe!% (֍ r+ : z2vk(u<$1Kwfe1F !1+=/l 2wklvfe z r%%ܸ<${h:(k+B)]"r7rKwfe :(k+B)]"r<$1Kwfe1F !1=/l 2wklvfe z r1+<$V ^ z2vklwfe!% (֍ r : z2vk%]:?(2.16) ?SinceV2 k<$KPp OPfe!E1:004Kwfex (֍ ;4%min6Lf 8;<$۲1۟wfe (֍3 g;?weUUhave"<$r ^ z2vkgwfe!% (֍ r8 : z2vk"R<$dc ^ z2vk됵= wfe6Q (֍ rm= 8 : z2vk됵= ?Ӎ 1:004&feQ̟,s16/_ K _feG՟ 18 l*p ܟ*W Q̟捱1:004l&fe㕟 s4 *p%Gן*W Q̟捱1:004&fe㕟uW12Ok<0:06410 8;΍<$r ^ z2vkgwfe!% (֍ r+8 : z2vk"R<$ ^ z2vkwfe Q3 (֍ rh!<$K1:004Kwfe! (֍c16<$'ҵ 8^2'ҟwfe 8 (֍N r+Z,<0:06275 8;8?andUUconsequently*,)l(180:06275 8)(k+B)፴r <h(k+B)፴r7r<(18+0:06410 8)(k+B)፴r +;1r5n?(2.17)?AprilUU1,20009 Vl'qƍ?holdsUUfor0r5N.qLetUUr4:(0)]"r u,1r5n.qThenitremainstoprovethatH{6(k+B)፴r =rm;1r5n?(2.18)?holdsUUfor0kN. NW*eeprove(2.18)byinductionwithrespGecttokP.F*orkRȲ=10,Atheassertion?(2.18)holdstrivially*.SuppGosethat(2.18)holdsforsomekP,0dkjyweprovethe rstinequality*,Fotherwisethesecond.kThe?bGothEinequalitiesareprovedEinasimilarfashion,soweconsideronlythecase?id>j6.NUsingrtheinductionhypGothesis,therotationanglebounds,thede nition?(2.12)UUof ㍲andtherelations(2.2)and(2.17),weobtaind Qji,8h:(k+B+1)ZjgjKj Ҷji,8j6jjih:(k+B)Zjgj +jjtank됵h:(k+B)Zijj| Ҷ(i,+8j6) 0:0641 8joja:(k+B)Zij +jPSq PSfe! h:(k+B)Ziih:(k+B)Zjgj ҶiTL +80:9359j6 <$n% klwfe UX EPpUWPfeE2(1+0:0641 8)kp kfe5viTLj5:A?SinceUUid>j6,Lemma3andtheassumption(2.13)imply󙍑_>ji,8h:(k+B+1)ZjgjKj_>fe5G (֍jҵiq8# +80:9359<$33j33wfe  (֍q0i ri <$lPp jPfe!E1:004lwfex E㐟Pp8PfeE2<$$ $wfe (֍]Ͳ4+(1+0:0641 8)dr dfe ri6<$33j33wfe  (֍q0iP,q8# +80<$l1+0:06411lwfe98ߟ (֍o4=% 8dr 9dfe ri6<$33j33wfe  (֍q0iՍq8# 80:1885 UP>0:8115 8:?HenceUUh:(k+B+1)Zjgj62Diand(2.18)isproved.%ׄv?Thus,O=theMorderingofthediagonalentriesofH^(k+B)IFremainsinvqariantduringthe?wholeUUcycle.qTherG'thdiagonalelementcanmoveonlyinsidetheintervqalDrm.?AprilUU1,200010 l'?LemmaT5r L}'etĚtheassumptionsofLemma4hold.+If(i;j)R=(i(kP);j(k))Ěisthe ?pivotp}'airatstepkP,then?(i)Z?(h:(k+B)Zii +;h:(k+B)Zjgj)>0:8795226minUVf iTL; j6g0:8795226 8; f]0kN~̍?(ii)^jtan'(k+B) +j0:5685󙍑ϸja:(k+B)Zijj33fe15 (֍minf iTL; j6g6/0:5685󙍑33ja:(k+B)Zijj33fe (֍# ib; f]0kNb.Z?ProQof>O(i)CUsingthetriangleinequality*,?theassertionofLemma4andthe?de nitionUU(2.11)oftherelativegapsinthespGectrum,weobtain [(h:(k+B)Zii +;h:(k+B)Zjgj)=󙍒jh:(k+B)Zii dr8h:(k+B)Zjgj +jfe3* h:(k+B)Zii dr+8h:(k+B)Zjgjy`=󙍑Kji,8jo+h:(k+B)Zii dri+joh:(k+B)Zjgj +jKfe i,+8jo+h:(k+B)Zii dri+h:(k+B)Zjgj drj#Z󙍒ji,8j6jjh:(k+B)Zii driTLjjjoh:(k+B)Zjgj +jfeb i,+8jo+jh:(k+B)Zii driTLj+jh:(k+B)Zjgjj6j <$ji,8j6j0:0641 8(i+j6)wfey (֍i,+8jo+0:0641 8(i+j6)U<$minf iTL; j6g(i,+8j)0:0641 8(i,+j)wfe) (֍di,+8jo+0:0641 8(i+j6)<$minf iTL; j6g80:0641 wfe^џ (֍18+0:0641 >minqƸf iTL; j6g<$33180:064133wfe- (֍18+0:0641MЍ>0:8795226minUVf iTL; j6g0:8795226 8:"}?(ii)UUUsingtherelation(2.1)andtheassertion(i),weobtain Oi jtan'(k+B) +j%󙍒)jh:(k+B)Zij +jvfe3* jh:(k+B)Zjgj dr8h:(k+B)Zii +jja:(k+B)Zij +jMq Mfe! 2h:(k+B)Ziih:(k+B)ZjgjKfegl4Rh33jhV(k).jK}j ͷhV(k).iij33Kfe'ϣn8hV(k).jK}j ͱ+hV(k).ii,8(h:(k+B)Zjgj dr+h:(k+B)Zii +),fՍ%<<$ja:(k+B)Zii +jvwfe3A (h:(k+B)Zjgj +;h:(k+B)Zii) <$l1lwfe (֍2 f_<󙍑'θja:(k+B)Zij +jKfe]t (֍0:8795226minUVf iTL; j6gd`<$l1lwfe (֍2#Z%C0:5685󙍑ϸja:(k+B)Zij +j33fe15 (֍minf iTL; j6g6/0:5685󙍑33ja:(k+B)Zij +j33fe (֍# "ia#Kꍍ?3WLQuadraticffConvergenceofScaledIterates?ThequadraticconvergencebGoundforthescaledmatricesinJacobimethodwill ?bGederivedforthecolumn-cyclicstrategy*.Itwillthenautomaticallyholdfor?thewholeclassofequivqalentcyclicstrategies(see[7]),8e.g.NNitwillholdforthe?row-cyclicUUstrategy*.NLetUUus rstformulatetheAsymptoticAssumptions:?AprilUU1,200011 l'?(A1)[cHpzis|areal,Fsymmetric,pGositive|de nitematrixofordern3,Fwith XsimpleUUeigenvqalues,satisfyingм? 0C<$K1Kwfe (֍4 'minոf<$133wfe (֍ng; 8gRXwhere] 0вand arede nedbytherelations(2.8)and(2.12),&respGectively*. ?(A2)[cTheUUdiagonalelementsofH%Sareorderednonincreasingly:xTh11 ?h22:::8׸hnn b:[$?Thecondition(A2)isactuallynotnecessaryforthequadraticconvergencein?theocaseofsimpleeigenvqalues.W*euseitjusttosimplifytheproGofandensure?aNsomewhatbGetterbound.InasubsequentpaperitwillberemovedNtogether?withotherrestrictionssuchas:qsimpleeigenvqalues,realH,pGositivede nitness?ofUUH.NInApractisehowever,EoneAgeneralydoGesnotknowwhethertheeigenvqaluesof?Hqaressimpleornot,;soinordertopreservethequadraticconvergenceunder?serialTandsimilarstrategies(see[8]),Tthealgorithmsaredesignedtoorder?thesdiagonalsduringtheproGcess(seetheLAP*ACKTauxilliaryroutine=2>:::8>nq~:?(3.1)?NowUUwestatethemainresult?TheoremT6zDL}'etzoHJmsatisfytheasymptoticassumptions(A1)and(A2).Letthe ?se}'quenceP#H^(0)S=HA;H^(1) s;:::;H^(N,)b}'egeneratedbythecolumn-cyclicstrategy.?Then絍) N #00:715<$۵ ^ z2l0۟wfe 됟 (֍ ;{b?wher}'eM k,-'03khʸNhand iar}'ede nedbytherelations(2.8)and(2.12),?r}'espectively.NTheorem6isprovedbyinductionwithrespGectton. enThesameresult,?with+.moGdi edconstant,3holdsforgeneralpositivede nitematricesandalsofor?inde nite+matrices.cInthatcasestheresultisproved+byinductionwithrespGect?toZthenumbGerZofdistincteigenvqaluesofamatrix.Theproofisthenmuch?longerandcomplexanditwillbGepublishedintheseparatedpaper.W*ehave?alsoUUobtainedthesameresultfortheKogbGetliantzmethod.NW*eUUneednowseveraltechnicalresults.?AprilUU1,200012 il'?N cmbx123.1]AuxilliaryLemmasuT?Ifxwetracethemovementofthepivotelementunderthecolumn-cyclicstrategy ?weUUwillnoticethatafterC܍;NtLn=<$Kt(t81)Kwfe 8 (֍ p2Ѝ?steps,6allo -diagonalelementsinthe rsttcolumnshaveoncebGeenannihilated. c?The'latesthasbGeenatposition(ta1;t),0Vso'thath:(NtQ})lt1;t8=0.b]Inthenextlemma?weRshallestimatethematrixelementswhileannihilationsinthet'thcolumn?takeUUplace.?LemmaT7r Supp}'ose>theassumptionsofTheorem6areful lled.If;=ENt1 ,?thenM@#(i)fsa:(wi+k+B)6k+Bt=0;vk=1;:::t81;`K@(ii)fsja:(wi+k+B)6l `tj1:0212(ja:(wi)6l `t 9˸j8+<$l1:137lwfe! (֍µ "+k X C!r7=1--ja:(wi)6l `ra:(wi+r71)͍r7tqj);MmAk=1;:::lk@81;>2lxt1;N;J](iii)fsja:(wi+k+B)6l `tj<$K1:1612Kwfe" (֍ õ +k &X "Hr7=l `+19bE(ja:(wi)6l `r 9˵a:(wi+r71)͍r7tqj8+<$l0:28425lwfe # (֍ õ N;hS8ja:(wi+l `1)6l `t+a:(wi+l `1)͍r7ta:(wi+r71)͍r7tqj);Dk=lk@+1;:::t2;>1lxt2;9⍍J7@(iv)fsja:(wi+k+B)6l `mjja:(wi)6l `m 9˸j8+<$l0:5685lwfe" (֍ õ "`( ja:(wi+l `1)6l `t+a:(wi+l `1)͍mtj+ja:(wi+m1)6l `t"ja:(wi+m1)͍mtj`㔵;MЍj)Zk=maxcfl2`;mg;:::;t81;>1lx6=mt82:?ProQof 10WithinptheproGofweshallshifteachsupGerscriptbyFfandfurtermore,?weUUshallomitthezerosupGerscripts. c?(i)UUThisassertionisobvioussincea:(k+B1)6k+Bt[isthepivotelement.?(ii)UUBytherelation(2.2)wehave(seealsothe gurebGelow)]Xh:(1)6l `tu =c(0) uh:(0)6l `t U+8s(0)h:(0)6l `1vXh:(2)6l `tu =c(1) uh:(1)6l `t U+8s(1)h:(0)6l `2s-\X>ӵh:(k+B)6l `tu =c(k+B1)hh:(k+B1)6l `t+8s(k+B1)h:(0)6l `k u;$.fePʟPPfePPfefefePʎpaPfe\aPfe`aPfe8aPfe4aPfe'40rx䍒\lMptp!p!p!4!$!32fdP$!32fdP$!32fdP$!32fdP$!32fdPMwt'w0rx䍒wlx䍒vvkp?whence\t?h:(k+B)6l `t =c(0) glc(k+B1)hhl `t+k ΟX  r7=1?s(r71)c(r7) XLc(k+B1)hl `rj;>1kl .β1;Ps2lxt1:?AprilUU1,200013Sl'?Here,theemptyproGductofcosines(whenrE=8(kP)isconsideredone.=LTherefore, ?forUUk=1;:::;lk@81,wehavefGja:(k+B)6l `t +j=_sjh:(k+B)6l `tjKӉfe+Ï<1:0427271?(3.4)l?TheUUsamebGoundisusedtoestimatethe rsttermbˍ<$u%jhl `tjj2wfe&U Nq NfeU hl `lh:(k+B)͍tt=<$ Jjhl `tjKwfe ũ:PpUW:Pfe*Űhl `lhtt%6us/7ufeT}<$htt33wfe h:(k+B)͍ttES=Vp o=Vfe*%ª1:04272715㔸jal `tj1:0212jal `tj:?(3.5) H?CombiningFzthelatestrelations(3.3),(3.4)and(3.5),weobtaintheassertion ?(ii).N8?(iii)UUBytherelation(2.2)wehave(seealsothe gurebGelow)a8-T h:(l `+1)6l `ty㓲=vc(l `) 80+s(l `) Qʵh:(l `)6l `;l+1vT h:(l `+2)6l `ty㓲=vc(l `+1)q͵h:(l `+1)6l `t+8s(l `+1)h:(l `)6l `;l+2wϸ]Fh:(k+B)6l `ty㓲=vc(k+B1)hh:(k+B1)6l `t+8s(k+B1)h:(l `)6l `k Qʵ;&ßfePʟPPfePPfefefePʎrPfeTPfeXPfe:Pfe6Pfex䍒7 l'TrMsUts$(s$(s$(U$('$(32fdP'$(32fdP'$(32fdP'$(32fdP'$(32fdPMzUtx䍒z l'yrx䍒ya}k?AprilUU1,200014l'?whencehl `r 8J8s(l `1)h:(l `1)͍tr;URr5=lk@+81;:::kP;/?andUUh:(l `1)͍trUV=h:(l `1)͍r7t>,weobtainud jh:(k+B)6l `t +jA= j ^k BX r7=l `+1Ms(r71)c(r7) XLc(k+B1)h(c(l `1)>hl `r 8J8s(l `1)h:(l `1)͍r7t)j$8鍍A4k 1X  r7=l `+1vjs(r71)j(jhl `rjj8+js(l `1)>h:(l `1)͍r7tj):?(3.6)!.5?NoteGJthathl `l ZYh:(k+B)6l `l +,1lkt-1.GThisGJfollowsfromtheassumption ?(A2),ILemmap4andthefactthatlarger(smaller)diagonalelementbGecomes?afterJthetransformationevenlarger(smaller).RdTherefore,@similarlyasinthe?relationUU(3.3),weobtain׍<${mjs^(r71)hl `rjj{mwfe+곟ÏПh:(l `1)͍r7tj\KwfePşÏmYj<$ {4jh:(l `1)͍r7tj33wfe1oq Nq Nfe'op hr7r[Dh:(l `1)͍tt 3׫v3u3u3t>d fe)֟p<$33hr7r[Dh:(l `1)͍tt33wfe'op /h:(k+B)6l `l +h:(k+B)͍tt$4C<$є0:5685^2єwfe C (֍ õ 8r2H\ja:(r71)͍r7tj8ja:(l `1)6l `t>jja:(l `1)͍r7tj1:0212>(3.8)-ʍ?Here }wehaveusedLemma5(i),;therelation(3.4)(withrTreplacedbyl2`)and ƍ?alsotheassumption(A2)andLemma4toconcludethathr7r "\<h:(k+B)6l `l +.=KCombining?(3.6)UU{(3.8)weobtain(iii).?(iv[ٲ)%8IfkminqƸfl2`;mg,.thenh:(k+B)6l `mPʲhaschangedtwice(seethe gurebGelow).aSince?allH^(k+B)Оaresymmetric,itsucestoconsideronlythecaselV<m.Usingthe?sameUUtechniqueasin(iii)wehaveK؉Xŵh:(l `)6l `mr==c(l `1)>hl `m cC8s(l `1)h:(l `1)͍tmvUh:(m)6l `mr==c(m1)h:(l `)6l `m cC8s(m1)h:(m1)6l `t;".fe@ڟ@@fe@@fefefe@ڎ_.̈́@fe?.ń@feBa@fe.a@fe+.@fehl `m 肸c(m1)s(l `1)h:(l `1)͍tmL]s(m1)h:(m1)6l `t;œkml2`:/?Replacing h:(l `1)͍tm$Jbyh:(l `1)͍mt>,:usingtheinequalitiesh:(k+B)6l `l /ݝh:(m1)6l `lh:(l `1)6l `lk۸v?hl `l,yh:(k+B)]"mm۸䥵h:(m1)]"mmh:(l `1)]"mmrhmm6,h:(l `1)͍ttrh:(k+B)6l `l +,h:(m1)͍tth:(k+B)]"mm۲andusing ?LemmaUU5(i),weobtain>_Qjh:(k+B)6l `m +jDӉfe/bÏj<$ tjh:(l `1)͍mtj33wfe/bÏja:(l `1)͍mtj vuut ; fe5Пp<$33h:(l `1)]"mmh:(l `1)͍tt33wfe2j ڵh:(k+B)6l `l +h:(k+B)]"mmA+8js(m1)ja:(m1)6l `tj-vuut ;-fe>v Ӎ_33h:(m1)6l `lh:(m1)͍tt33Ӊfe; &h:(k+B)6l `l +h:(k+B)]"mmWoljal `m *cj8+js(l `1)>ja:(l `1)͍mtj8+js(m1)ja:(m1)6l `tj9⍍Woljal `m *cj8+<$l0:5685lwfe" (֍ õ "`( ja:(l `1)6l `t>jja:(l `1)͍mtj+ja:(m1)6l `tjja:(m1)͍mtj`^:L?ThisUUcompletestheproGofofthelemma.?d NInUUthesequelweshallfrequentlyusetheinequality(cf.q[8])b*](a8+b)2C(1+x)a2S+(1+x1 t)b2|s;URx>0:?F*or%pGositiveaandnonnegativeb,Xtheequalityisattainedforx!O=b=a.Such?xwillbGereferredtoas\optimal"x.PInthefollowinglemmasweshallusethe?followingUUnotationb':7A:(k+B)͍t +:XA:(k+B)͍tβ=VtheassumptionsofTheorem6areful lled.If;=ENt1 ,?then?(i)Pt1 P#X Ql `=1^S(a:(wi+plұ)6l `tc)2C2፴t|ska:(wi)͍t 9˸k2S,捑Xpr}'ovidedthat0pllk@81holdsfor1lxt1;?(ii)SOt1 SUPX T5Ol `=1a(a:(wi+plұ)6l `tc)2C^<$ Ai0:8211 Aiwfe" (֍ õ &;tVka:(wi)͍t 9˸k^ kA:(wi)lt1 ʲ)kF+<$l0:402lwfe! (֍µ fg2፴t|ska:(wi)͍t)k2^ 2^۱2u,Xpr}'ovidedthatlxplt81holdsfor1lt81.?AprilUU1,200016l'?Her}'e5ǵtLn=<$֦1:0212KwfeQٟ 18 l0:8211l&feN?X -kA:(wi)lt1 ʸkF?(3.9)lۍ?ProQofAsintheproGofofLemma7, VweshallshifteachsupGerscriptby ?andUUomitthezerosupGerscripts. cN(i) Let ^2፴t:=QPލt1%l `=1DV(a:(l `1)6l `t>)^2|s,7@ tyQ0.Usinglemma7(ii)andtheCauchy-?SchwarzUUinequality*,wehaveforanyx>0덍J@ 2፴t_9ϸq1:02122t1 'X l `=1C\"(18+x)a2፴l `tO+(1+x1 t)<$331:137^233wfeC (֍µ 8r2(ƴl `1 X 2r7=1qa2፴l `rj)|nl `1 X ܺr7=1(a:(r71)͍r7t)2|s)\##c_9ϸq1:02122'\" r(18+x)Bt1 X l `=1a2፴l `tO+(1+x1 t)<$331:137^233wfeC (֍µ 8r2ڸ 2፴t /QkAt1 ʸkFk_#katVk=tkatk: ?Now,Qlet\q~P͵ ^2፴tt:=Pލ USt1% USl `=1(a:(plұ)6l `t &)^2@withP0pllb//ϲ1forall2lxt/ϸ1.pESimilarly*, ?asUUabGove,foranyx>0wehaveHR\qM~L 2፴ta+r1:02122t1 'X l `=1C\"(18+x)a2፴l `tO+(1+x1 t)<$331:137^233wfeC (֍µ 8r2(Ҵpl 獍X 2r7=1qa2፴l `rj)`zpl 獍X ܺr7=1(a:(r71)͍r7t)2|s\## a+r1:02122'\" r(18+x)Bt1 X l `=1a2፴l `tO+(1+x1 t)<$331:137^233wfeC (֍µ 8r2ڸ 2፴t /QkAt1kFmC\!o8=<$v1:0212wfed 18 l1:02120:804l&fe+ /> /QkAt1 ʸkFikatVktkatkl?whereUUtګisgivenabGove.?(ii)zLet^[ٱ2፴t+=SVPލ ᑴt1% ᑴl `=1[(a:(plұ)6l `t &)^2|s,lSVpletp1,1SVltp1.n8UsingzLemma7(iii) ?weUUobtainforandforanyx>0ͩE[ٱ2፴tYN<$l1:1612^2lwfe C (֍ õ 8r2ct1 X l `=1瀟\"Cpl 獍qX ״r7=l `+1*|jal `rja:(r71)͍r7tj8+<$l0:28425lwfe # (֍ õ .}pl 獍+9X 'r7=l `+1?~ja:(l `1)6l `t>a:(l `1)͍r7ta:(r71)͍r7tj\#ٱ2&\YN<$l1:1612^2lwfe C (֍ õ 8r2ct1 X l `=1Z瀫2 4,(18+x)\ spl 獍 X  Tr7=l `+1"jal `rja:(r71)͍r7tj\!Uٱ2?(3.10)(o+(18+x1 t)<$330:28425^233wfe%C (֍ õ 8r2)죴t1 )TX *4l `=19q\ I:-pl 獍E[X A[r7=l `+1Yfja:(l `1)6l `t>a:(l `1)͍r7ta:(r71)͍r7tj\!$pٱ2Z3 5a/ֵ:õ?UsingUUtheCauchy-SchwarzUUinequalityweobtainͩkt1 jX kںl `=1{,\ Dpl 獍*rX شr7=l `+1o}jal `rja:(r71)͍r7tj\!dEٱ2֧и_t1 X l `=1㉟\ "pl 獍ϟX 5r7=l `+13;ڵa2፴l `rj\!Iȟ\ Xpl 獍U-X Qtr7=l `+1gq(a:(r71)͍r7t)2|s\!#P~\  Iôt1  ğX ִr7=1#(a:(r71)͍r7t)2|s\!Krat1 JbX Kal `=1b?pl 獍_mX ZӴr7=l `+1sdxa2፴l `r Ƃ2፴t|skatVk2S<$l1lwfe (֍2 GkAt1 ʸk2፴F:>(3.11)X?InUUasimilarway*,UUusingadditionallytheassertion(i)withpl=lk@81,weobtain[⍍Ct1 CX Cဴl `=1S\ b pl 獍_18X [r7=l `+1svCja:(l `1)6l `t>a:(l `1)͍r7ta:(r71)͍r7tj\!Mٱ2ظlt1 mX ll `=16(a:(l `1)6l `t>)2 紴t1  OX 'r7=l `+1(a:(l `1)͍r7t)2 紴t1  OX 'r7=l `+1(a:(r71)͍r7t)2#P8_t1 X *r7=18(a:(r71)͍r7t)2t1 'X l `=1(a:(l `1)6l `t>)2 max'1l `t1,ct1 ,JdX (!ʴr7=l `+1>Dz(a:(l `1)͍r7t)2$U\84፴t|skatVk4'\"cl0 v rX .r7=1a2፴r7t ز+ٴt1 OڟX 8r7=l0 +1؝(a:(l0 1)͍r7tj)2\#AԸ6፴tkatVk6;?(3.12)Jɍ?wherel0isthesubscriptlforwhichthemaximumisattained.Combiningthe ?relationUU(3.10)with(3.11)and(3.12)oneobtainsforx>0K[r[ٱ2፴td<$K1:1612^2Kwfe C (֍ õ 8r2'^,bٲ(18+x)2፴t|skatVk2S<$l1lwfe (֍2 GkAt1 ʸk2፴F+(1+x1 t)<$330:28425^233wfe%C (֍ õ 8r2'6፴tkatVk6^)$_:?AprilUU1,200018*l'?ChoGosingUUtheoptimalxyields⍒5stLn<$K0:8211Kwfe" (֍ õ tVkatk^ kAt1 ʸkF+<$l0:402lwfe! (֍µ fg2፴t|skatk2^~OG:?Notet.thattheemptysums(whenpl K=l2`)areconsideredzerosinceinthatcase ƍ?tLn=0(thisisbGecausea:(l `)6l `t =0for1lxt91).VTheproGofisnowcomplete. NLemmaw<8providesbGoundsforthesumofsquaresoftheelementsofcol- x䍑?umnttakenfromdi erentmatrices.VThebGoundsdependonkA㍱(Nt1 #L)Ít18ӸkF and?ka㍱(Nt1 #L)$t8Ӹk.qjDuringthe rstNt1lUJacobirotationska:(k+B)͍t +kchangesandthenext?lemmaUUestimateshowmuchitcanincrease.C?LemmaT9r Supp}'ose$theassumptionsofTheorem6areful lled.J2ThenfortS=?2;:::;nholds[ka㍱(Nt1 #L)$t8Ӹk2CCtVkatk2Cr?withoCtLn=(18=Vp 7=Vfe!ª0:502!UX 0|s)(2t5)!X<1:477:C?ProQof Since,thepivotstrategyiccolumn-cyclic,4FonecanconsideronlyNt1 r?JacobistepsappliedtoAtV.#Notethata㍱(Nt1 #L)$tɎisalsoobtainedprovidedthe?column-cyclicstrategywithinAt1 ʲ,isreplacedbytherow-cyclicstrategy*.(cf.?[7,UU8UV]).qTheUUchangeofpivotstrategywillmakeestimateseasiertoprove.NT*oUUsimplifynotationweset:C:Xj=Nt1 ʲ,>돵x^kvl됲:Xx^kvl=(a:(k+B)6l `t +)^2|s;UR1lxt81;0k;MECb:Xb=maxcfja:(k+B)i(k+B)jg(k)bj;0kg,pC:X=1=(18b),ע@ȵqrm:Xqr4=(t82)+(t3)+g+(tr1);UR1r5t2.?DuringrEq1sƲ=StL+2annihilationsinthe rstrow,yweobtainaccordingtolemma?1(i)x11S+8x12R.(x01S+8x02|s)x21S+8x23R.(x11S+8x03|s).:::'fx䍴t21+8x䍴t2t1R.(x䍴t31+8x0፴t1 ʲ):?Multiplyingthe rstinequalityby^1 t,'thesecondoneby^1 t,'etc.IIandsuming ?themUUalltogether,wehave:v(t2)A͵x䍴t21+Ĵt2 EşX 8k+B=1ok +xkk+B+1ҫx01S+8x02+Ĵt3 EşX k+B=1ok +x0፴k+B+2;:?AprilUU1,200019@l'qƍ?Sincefduringtheseq1Xrotationseacha:(q1 )6l `tQk,kI2]ltD1fhaschangedjustonce, ?andUUsince1,UUwehaveML_%lL1tp:=Tq1Qjx1ɍq1xݍ1 JI+Ĵt1 EşX 8k+B=2o(k+B1)x1ɍq1vk ؁x01S+8x02+Ĵt2 EşX k+B=2o(k+B1)x0፴k+B+1# uӧTx01S+8x02+Ĵt2 EşX k+B=2ox0፴k+B+1ҫ=katVk2>(3.13)Q?AfterUUthenextt83UUannihilationsinthesecondrow,wehaveMLi(t3)A͵x1ɍq1 +t3xݍ2+Ĵt3 EşX 8k+B=1ok +x1ɍq1 +kvk+B+2gx1ɍq1xݍ2 JI+8x1ɍq1xݍ3+Ĵt4 EşX k+B=1ok +x1ɍq1vk+B+3;;?orUUequivqalently*,W]L2C:=(q2 q1)"bֵx1ɍq2xݍ2 JI+Ĵt1 EşX 8k+B=3o(k+B2)x1ɍq2vk ؁x1ɍq1xݍ2+8x1ɍq1xݍ3+Ĵt2 EşX k+B=3o(k+B2)x1ɍq1vk+B+1 :?AfterUUthenextt83UUannihilationsinthethirdrow,wehaveW]L3C:=(q3 q2)"bֵx1ɍq3xݍ3 JI+Ĵt1 EşX 8k+B=4o(k+B3)x1ɍq3vk ؁x1ɍq2xݍ3+8x1ɍq2xݍ4+Ĵt2 EşX k+B=4o(k+B3)x1ɍq2vk+B+1 :?RepGeatingVQthesamearguments,Vaftert9i1VQannihilationsinthei'throw,Vwe ?have[v_Lid:=(qi*qi1 DZ))Ux1ɍqiˍi !+Yt1 X 8k+B=i+1f(k+Bi)x1ɍqivk Y?(3.14)#P_x㍴qi1i_+8x㍴qi1i+1+Yt2 X k+B=i+1f(k+Bi)x㍴qi1K\k+B+1';1it2:?LetUUuscheckUUtheformula(3.14)fori=t82.qW*eUUhaveXYLt2:=1 tx㍴qt2Ít2u+81x㍴qt2Ít1x㍴qt3Ít2u+8x㍴qt3Ít1M;?whichUUistrue,sincetheinequalitycanbGewrittenintheformOjxt2+8xt1(x䍴wi1t2o+x䍴wi1t16=)?(3.15)?asUUitshouldbGe.qF*romtherelation(3.14)weobtainfor2it82NU(ti2)#Vx㍴qi1i1_+8LiōXUjs2'\" r(ti)x㍴qi1i1_+82 tx㍴qi1i+2 tx㍴qi1i+1E+Yt2 X k+B=i+1f(k+Bi+2)$x㍴qi1K\k+B+1'\##PXUjs2'\" r(qi1 Ƿqi2)2$x㍴qi1i1_+gt2 X 8k+B=i1h(k+Bi+2)$x㍴qi1K\k+B+1'\#i=m2|sLi1 :?AprilUU1,200020O٠l'?InUUparticular,wehave(t4)A͵x1ɍq1xݍ1 JI+8L2~(7 2'L1 (t5)A͵x1ɍq2xݍ2 JI+8L3~(7 2'L2d;ص0|sx㍴qt3Ít3u+8Lt2~(7 2'Lt3#ՍD21|sx㍴qt2Ít2u+81x㍴qt2Ít1~(=7 2'Lt2 ʵ:?Multiplying=thesecondinequalityby^2 t,thethirdoneby^4 t,etc.,thelast ?oneUUby^2(t3)>@,weobtain }t2 ~X {k+B=1Ե(t+k+B5)$x1ɍqkvk+52t+7͵x㍴qt2Ít12|sL1:䍑?Note`ڵ1andx^vk ~=x1ɍqkvkh,1kՋt82.XHence,combining`thiswiththe?relationUU(3.13),wehaveۍsӴt1 sԟX s k+B=1B*xk=kt2 X k+B=1Sx1ɍqkvk+5x㍴qt2Ít12t782|sL1C2t5=katVk2:!`?Finally*,1Esince(A=1=(1޷b)<1=(1޷s0p ޸s0fe #Ѝ1:004=2.P 0|s),the(Aassumption(A1)yieldsBu@S2t5U<$,v1KwfeV X ObW18Pp 7Pfe!E0:502!UX 0|sbDbfh2t5^<$(L1KwfeM ObW18Pp 7Pfe!E0:502 "t2"&fe Aʟ)4n0bI(5fh2U><$ղ1Kwfe<*`18 l*p ܟ*W Q̟捱0:502l&fe㕟 s4۟`8tݱ2D嫸1:4769:% \?TheUUproGofisnowcomplete.ڢ6?3.2]ThePro`ofoftheTheoremuT?W*eUUshallproveUUthat"򍍑i0ukA:(NtQ})͍tgkF 40Kt6<$lkAtVk^2bFlwfe9 (֍ ε J;URKtLn=0:715vuut ;feRa<$331533wfe  (֍16t Y l `=2.(18+2<$33kalȸkr233wfem (֍O 8r2=Ӳ)?(3.16)!,Q?holdscffor2ދtn,fwhenevercfH3dsatis estheassumptions(A1)and(A2).The ƍ?proGofusesmathematicalinductionwithrespecttot.BF*ort>=2,DA:(NtQ})͍t{ײisthe?nullCmatrixofordertwo,Gwhencetheassertion(3.16)istrue.lLetusassumethat?(3.16)UUholdsfort81,UU3tn.qAsearlier,wesetj=Nt1 ʲ.NW*eUUhave2 kA:(NtQ})͍tgk2፴F l=kA:(NtQ})lt1k2፴F+82ka:(NtQ})͍tk2|s:?(3.17)?AprilUU1,200021a\l'?ByUULemma7(iv)wehaveforanyx>0o<$@@1@@wfe (֍2GtkA:(NtQ})lt1gk2፴Fy[=xt2 \yX (3.18)?whereUUtګisde nedby(3.18).qChoGosingtheoptimalxweobtainKvkA:(NtQ})lt1gkF lkA:(wi)lt1 ʸkF+8=Vp 7=Vfeª2<$k0:5685kwfe" (֍ õ -tV:?(3.19)??UsingUULemma8,wehaveforanyy">0JR62፴tgyȲ(18+y[ٲ)Bt2 X l `=1q(a:(wi+l `1)6l `t+)2 }1t1  1X 'm=l `+1 (a:(wi+l `1)͍mt)2#PyȲ+(18+y[ٟ1 M)Bt2 X l `=1/t1 /X m=l `+1+(a:(wi+m1)6l `t"j)2|s(a:(wi+m1)͍mt)2gyȲ(18+y[ٲ)\"YDzmax1l `t2/Ĵt1 /8ğX )zm=l `+1Ch(a:(wi+l `1)͍mt+)2|s\#z2፴t|ska:(wi)͍t 9˸k2yȲ+(18+y[ٟ1 M)t1 X m=2m1 X ߐl `=1%(a:(wi+m1)͍mt"j)2|s(a:(wi+m1)6l `t)2# gyȲ(18+y[ٲ)4፴t|ska:(wi)͍t 9˸k4S+(1+y1 M)t1 X m=2F(a:(wi+m1)͍mt"j)2'm1 X xl `=1|*(a:(wi+m1)6l `t)2x卍gyȲ(18+y[ٲ)4፴t|ska:(wi)͍t 9˸k4S+(1+y1 M)2፴t|ska:(wi)͍t 9˸k2 yȸ^<$$0:8211$wfe" (֍ õ %NtVka:(wi)͍t 9˸k^ kA:(wi)lt1 ʲ)kF+<$l0:402lwfe! (֍µ fg2፴t|ska:(wi)͍tk2^<^۱2^w?ChoGosingUUtheoptimaly[ٲ,weobtainP5tLn2፴t|ska:(wi)͍t 9˸k2'(18+0:8211tV)?(3.20)쨍?where$tLn=KkA:(wi)lt1 ʸkFKfe%筟 (֍ -N +80:4022፴t<$ka:(wi)͍t 9˸k^2wfep (֍ c 8r2%I:?(3.21)M?NextUUwecalculatethebGoundsforKtV,t,tګandt.qUsingtheinequality}+j 獍yY yl `=2(18+xlȲ)\ IJ18nj 獍X ߴl `=2UQxl\!<51I!;xl>0; ]j 獍X l `=2nxl<1;?AprilUU1,200022p;l'?andUUtheassumption(A1),weobtainfor2jYn#]0:715Idr Idfe fh<$331533wfe  (֍16-KjVIg0:715Idr Idfe fh<$331533wfe  (֍16\ 18nj 獍X ߴl `=2UQ2<$33kalȸk^233wfem (֍O 8r2=ӟ\!gy5P 33133#&feg 2>(3.22)#raVI=g0:715avuut ;afe<ݟx<$U1533wfe:Ew 16816KgkAjak2?Fgˉfe/ n92J00:715r feGK񍍟<$ Ϣ1533wfe8 (֍1681*f`=0:715:${:?Using1:thede nition(3.9)oftV,8stheinductionhypGothesis,thebGound(3.22)and ?theUUassumption(A1)wehaveb'tLn<$&1:0212Kwfe`ӱ b18 l0:8211l&feN?X 텵Kt1kAt1 #Lk2!fe?ğ  hG<$$bβ1:0212Kwfe\( 180:82110:715 jL1l&fe16d1:0601:?(3.23) d?InUUasimilarway*,UUusingadditionally(3.23)andLemma9,wehavegGTtZWlKt1<$kAt1 ʸk^2bFwfe%筟 (֍ ϵ 8r28H+80:4022፴t'Ct<$katVk^2wfeJ (֍v 8r2ϸKt1<$kAt1 ʸk^2bFwfe%筟 (֍ ϵ 8r2+0:66727<$33katVk^233wfeJ (֍v 8r2ZWlKt1<$kAtVk^2bFwfe9 (֍ 8r2.<<$KKt1Kwfe@ (֍ 164<0:0446875:>(3.24)MЍ?Usingu-theinductionhypGothesis,}#therelations(3.20){(3.24)andLemma9,we ?have5V`kA:(NtQ})lt1gkFgG.ekA:(wi)lt1 ʸkF+8=Vp 7=Vfeª2<$k0:5685kwfe" (֍ õ -t?(3.25)gG.eKt1<$kAt1 ʸk^2bFwfe%筟 (֍ 8H+8=Vp 7=Vfeª2<$k0:5685kwfe" (֍ õ -2፴t'CtVkatk2( 18+0:8211tV)gG.eKt1<$kAt1 ʸk^2bFwfe%筟 (֍ 8H+81:38347004<$33katVk^233wfeJ (֍ǯ xyKt1<$kAtVk^2bFwfe9 (֍ ε +i:MЍ?ByUULemma8(ii),Lemma9andtherelation(3.24),wehavegiЭ2ka:(NtQ})͍tgk2C280:82112|sCtV2፴tkatk2C1:992K2፴t1<$kAtk^4bFwfe9 (֍ 8r4-~katk2:?(3.26)?CombiningUUtherelations(3.17),(3.25)and(3.26)weobtainokA:(NtQ})͍tgk2፴F l=K2፴t1lr^18+1:992<$33katVk^233wfeJ (֍v 8r2a^<$bkAtVk^4bFbwfe9 (֍ 8r2ZK2፴t<$f¸kAtVk^4bFfŸwfe9 (֍ 8r2qύ?which0?(4.27)A?forUUsome,0<<1.qLetr\qNeƷ۲=min-V0i;jꪍ+i6=jㆸjhiiax8hjgjXjUU:?(4.28)$`?UsingtheWielandt-Ho manpGerturbationtheoremfortheeigenvqaluesofHer-?mitianUUmatriceswehave;n 0X tӴi=1Ljhiiax8iTLj2Cjj (H)jj2ȵ:?(4.29)捑?UsingQ}therelations(4.28)and(4.29)wecanbGoundtheabsolutegapsinthe?spGectrumUUofH,rDi p=mminjg6=iqøji,8j6jʿݲminjg6=i(4.30)W⍑?SuppGosewewanttoapplytheclassicalquadraticconvergenceresult(1.2)toH.?Obviously*,UUwehavetorequirethat܍zjj (H)jj<$K1Kwfe (֍3 -(\q0re 8=Vp 7=Vfeª28jj (H)jj)UU;YB?orUUequivqalentlyjj (H)jj<$\qeKwfe7 E38+Pp 7PfeE2' ;?(4.31)I?holds.qIf\qǫeUU }TisUUtiny*,thecondition(4.31)isnotlikelytohold.NUsingUU[3,PropGosition2.10]wehavez?818jj (HS)jj2C<$[AiKwfe 돟 (֍hii%1+jj (HS)jj2|s;1in;?AprilUU1,200024el'?or,UUsincejj (HS)jj2Cjj (HS)jj= 0|s,:<$uθji,8hii(juΟwfe&J (֍ x]hiiLc 0|s;1inUU:?(4.32)w?F*orUUtherelativegapsinthespGectrumofH,weobtainKH1 id=min+jg6=i<$Oji,8j6jOwfe$ (֍i,+8j?Fmin+jg6=i<$Ojhiiax8hjgjXjji,hii(jjjohjgjjOwfe4f (֍hiiax+8hjgj &8+ji,hii(j+jjohjgjXj:;1inUU:!?DividingK-thenumeratorandthedenominatorbydij =maxcfhii(;hjgjXgandusing ?theUUrelations(4.27)and(4.32)wehave3zE' ò=minLpi7 i pmmin 񄍍: Xi;jƍi6=j텍)jhiihjK}j·j)ŭfe!+ M[dij?o&hlji*hiijlʉfem nOdij$Eи텍ljjahjK}j·jlŭfe! HmdijBfe}`> 텍khii+hjK}jkŭfeOP"dij#\β+&hlji*hiijlʉfem nOdij$Eв+텍ljjahjK}j·jlŭfe! Hmdij ø<$18 0S 0wfeEuM (֍18++ 0S+ 0=<$O182 0Owfe3ZZ (֍18++2 0?2:?(4.33)x?T*oUUchecktheasymptoticassumption(A1)weobviouslyhavetorequirethatvV! 0C<$K1Kwfe (֍4 'min-}^<$'`1&౟wfe (֍n.~;<$30182 030wfe3ZZ (֍18++2 0:^xV:?(4.34)w?TheUUinequality'j4L 0C<$K1Kwfe (֍4 f_<$l182 0lwfe3ZZ (֍18++2 0ӕ?orUUeqiuvqalently ˕8 z20Ͳ+8(6+4) 0S(1)0;?holdsUUfor0 0C 䍐 z+0 _where㍒ 䍐 z+0 t"=5s 5feWПˍ^<$38+2wfe?f (֍ 8&@^-^۱24+<$l18lwfe?e (֍ 8j<$h38+2hwfe?f (֍ 8*ޫ:R?SinceUUfora;b>0,UUwehaveyA-pA-feI+ Sar2S+8b"8a P=<$bwfe4 UNpUWfeI+UUar2S+8b$b+8avѲ=<$bOwfeI0 (֍a<$v1lwfe7 Faq Fafe՟ 18+ ȹb&fe=a2(+81)wɍ P><$̅bwfeI0 (֍aԻ<$u&1lwfe1' 18+ b&fe :2a2)+1;=<$ NbOwfe I1 (֍2a<$ض1lwfeH 18+ b&fe :4a2';:?ifUUweseta=(38+2)=8UUandb=(18)=8,UUweobtainH<$Fb wfeŤ (֍4ar2o=ӍFd1Fd);fe5a8K _fe)g 64bs23+2s2);fe7~b8b 421<Ӎ }1}&fes8K _fe B؟ (48b j3j&fes8 1bg߱2(7n=<$K2Kwfe (֍9?AprilUU1,200025l'?andRӬ 䍐 z+0 t">Ӎ 91 9);fe5a8K _fe!{ ,28l3+2l);fe7~b8(ٸ<$ 1lwfe 18+ 2&fes9=<$zK9Kwfe  (֍22f`<$18lwfe?f (֍38+2$4:?ThusUUtherelation(4.34)andconsequently(A1)willholdif 0Cminn^<$ 1Ϣwfe (֍4n*p;<$0930wfe  (֍22E<$18lwfe?f (֍38+2 ެ^p:?(4.35)?Inpracticalapplicationswecaneasilychecktherelation(4.35)sinceiseasy ?toUUcompute(wecantake=maxcfhi+1;i+1Ȟ=hii(g;1in81UU).NApplyingUUTheorem6andusingtherelation(4.33),weobtaing N \ɸ0:715<$33 ^ z2l033wfe 됟 (֍ 0:715 z20͸<$l18++2 0lwfe3ZZ (֍182 0;N:MЍ?SinceUUtherelation(4.35)yieldsA2 0C<$zK9Kwfe  (֍11f`<$18lwfe?f (֍38+2#<<$zK9Kwfe  (֍11<$l18lwfe?e (֍ 3=<$zK3Kwfe  (֍11-(18)UU;?weUU nallyobtain~ N5lS0:715 z20͸Ӎl18++ jL3&fe11  jL3&fe11 ,l _feJv? 18 jL3&fe11 + jL3&fe11 ,"v5=lS0:715 z20͸<$l148+8lwfe!?g (֍888+<m0:715 z20<$oT22lwfe$ (֍8(18)!5=lS1:96625 z20͸<$ Ų1lwfe?e (֍184:?NowUUwestateTheorem6intheformsuitableforpracticalapplications.?PropQositionT10L}'etGHEbereal,*symmetric,p}'ositivede nitematrixoforder?n63,withmsimpleeigenvalues,whichsatis esther}'elations(4.27)and(4.35).?L}'et_thesequenceH^(0)&==HA;H^(1) s;:::;H^(N,){be_generatedbythecolumn-cyclic?str}'ategy.Then'j6ܵ N #<$2cwfe?e (֍18! z20Ե;MЍ?wher}'e k,0kNisde nedbytherelation(2.8).?Let$usapllytheabGove$considerationstothematrixHf"givenbytheMA*TLAB?programx(1.3)withn^=100,@d1=4xandd2^=4.0ThextablebGellowindicates?howEtheclassicalresult(1.1)andPropGosition10canbeusedtopredictthe?quadraticUUreductionofjj (H^(k+BN,)A)jjand k+BN A,respGectively*.?AprilUU1,200026 l'm?ff:-ӟ sͤ vff͟fdkd vffVjj (H^(k+BN,)A)jj͟ vffa k+BNa vff\qeV vffr.(4.31)͟ vff_r.(4.35)͟ vff_Prop.10̟ vffff:-өfdͤ ffwfd0 ffD.6.50e+04  ffY 8.66e-04͟ ffK4.52e-09͟ ffxnfails % ffholds # ff4.83e-06͟ ffff:-Ӧͤ ffwfd1 ffD.3.81e+00  ffY 4.65e-08͟ ffK4.51e-09͟ ffxnfails % ffholds # ff1.40e-14͟ ffff:-Ӧͤ ffwfd2 ff }3.06e-09ĉ ffY 3.69e-17͟ ffK4.51e-09͟ ffxnfails % ffholds # ff8.76e-33͟ ffff:-Ӧͤ ffwfd3 ff }2.56e-28ĉ ffY 3.09e-36͟ ffK4.51e-09͟ ffholds # ffholds # ff6.15e-71͟ ffff:-Ӧͤ ffwfd4 ff/10  ffhJ+0 ffK4.51e-09͟ ffholds # ffholds # ff0 ffff:-ӎ4/?EachrowinthetablecorrespGondstoonecycleoftheJacobimethodapplied ?to֯H^(0)ɲ=IVH.ThelastcolumngivesthebGoundfromProposition10.W*e?canseethattheinitialmatrixaswellasthematricesobtainedafterthe rst?andthesecondcycledonotsatisfythecondition(4.31).0Thisfactmakesthe?classicalequadraticconvergenceeresultsuseless.&Onthecontrary*,therelation?(4.35)]alwaysholds(<0:7ineachcycle).GuWiththenewestimate,PropGosition?10,wea{canwellpredictthereductionof k+BNbforallkP.9W*eobtainedsimilar?resultsUUforalmostallmatricesgeneratedbytheprogram(1.3).!č?References?[1]N;Barlow&J.,DemmelJ.W.(1990)Computing-A}'ccurateEigensystemsofScaledN;DiagonallyDominantMatric}'esUU,SIAMJ.Num.Anal.27,762-791.?[2]N;De;RijkP*.P.M.;(1989)AԑOne-side}'dJacobiAlgorithmforComputingtheN;SingularV;alueDe}'compositiononaVe}'ctorComputer,SIAMw:J.wSci.Stat.N;Comp.UU10,359-371.?[3]N;DemmelJ.W.,wV*eseliGcK.(1992)Jac}'obiMethodismoreAccuratethenQR,N;SIAMUUJ.MatrixAnal.Appl.13,1204-1245.?[4]N;DrmaGcZ.(1998)AMPosterioriӟComputationoftheSingularV;e}'ctorsinaN;Pr}'econditionedJacobiSVDAlgorithm,UUT*oappGearinIMAJ.Num.Anal.?[5]N;DrmaGc/Z.,+&HariV.(1993)OnQuadr}'aticConvergenceBoundsfortheJ-N;symmetricJac}'obimethod,UUNumer.Math.64,147-180.?[6]N;HariV., DrmaGcZ.:COn?ySc}'aledAlmostDiagonalHermitianMatrixPairs, T*oN;appGearUUinSIAMJ.MatrixAnalysisandApplications.?[7]N;E.R.Hansen:OnCyclicJacobiMethoGds.SIAMJ.Appl.Math.11(1963)N;449{459.?[8]N;HarijV.(1991)OnSharpQuadr}'aticConvergenceBoundsfortheSerialJa-N;c}'obiMethods,UUNumer.Math.60(1991)375-406.?[9]N;H.P*.M.VanKempGen:>$OntheQuadraticConvergenceoftheSpecialCyclicN;JacobiUUMethoGd.NumerischeMathematik9(1966)19{22.?AprilUU1,2000276l'?[10]S cmmi10 0ercmmi7O \cmmi5K`y cmr10ٓRcmr7Zcmr5u cmex10