Jacksons-Theorem-and-the-Circulant-Preconditioned-

Jackson’sTheoremandCirculantPreconditionedToeplitzSystemsRaymondH.ChanandMan-ChungYeungDepartmentofMathematicsUniversityofHongKongPokfulamRoadHongKongDecember1990RevisedSeptember1991AbstractPreconditionedconjugategradientmethodisusedtosolven-by-nHermitianToeplitzsystemsAnx=b.ThepreconditionerSnistheStrang’scirculantpreconditionerwhichisdenedtobethecirculantmatrixthatcopiesthecentraldiagonalsofAn.TheconvergencerateofthemethoddependsonthespectrumofS1nAn.UsingJackson’stheoreminapproximationtheory,weprovethatifAnhasapositivegeneratingfunctionfwhose‘thderivativef(‘),‘0,isLipschitzoforder01,thenthemethodconvergessuperlinearly.Weshowmoreoverthattheerrorafter2qconjugategradientstepsdecreaseslikeQqk=2(log2k=k2(‘+)).AbbreviatedTitle.Jackson’sTheoremandToeplitzSystems.KeyWords.Jackson’stheorem,Toeplitzmatrix,circulantmatrix,precon-ditionedconjugategradientmethod,generatingfunction.AMS(MOS)SubjectClassications.42A10,65F10.11Introduction.Ann-by-nmatrixAn=[ai;j]issaidtobeToeplitzifai;j=aij,i.e.Anisconstantalongitsdiagonals.ToeplitzsystemsoftheformAnx=boccurinavarietyofapplications,especiallyinsignalprocessingandcontroltheory.ExistingdirectmethodsfordealingwiththemincludetheLevison-Trench-ZoharO(n2)algorithms[19],andavarietyofO(nlog2n)algorithmssuchastheonebyAmmarandGragg[1].ThestabilitypropertiesofthesedirectmethodsforsymmetricpositivedenitematricesarediscussedinBunch[2].Inthispaper,weconsideraniterativemethod,thepreconditionedconjugategradientmethod,forsolvingToeplitzsystems.Ann-by-nToeplitzmatrixBnissaidtobecirculantifitsdiagonalsbjsatisfybnj=bjfor0jn1.Weremarkthatcirculantmatricescanalwaysbediagonalizedbyunitarymatrices.Infact,wehaveBn=FnnFn,wherenisdiagonalandFnistheFouriermatrixwithentriesgivenby[Fn]jk=1pne2ijkn,seeDavis[11].Strang[17]rstsuggestedtheuseofpreconditionedconjugategradientmethodwithcirculantmatrixBnaspreconditionerforsolvingpositivedeniteToeplitzsystem.InsteadofsolvingAnx=b,wesolvethepreconditionedsystemB1nAnx=B1nbbytheconjugategradientmethodwithBnbeingacirculantmatrix.Thenumberofoperationsperiterationinthepreconditionedconjugategradientmethoddependsmainlyontheworkofcomputingthematrix-vectormultiplicationB1nAny,seeforinstanceGolubandvanLoan[13].Foranyvectory,sinceB1ny=Fn1nFny,theproductB1nycanbefounde-cientlybytheFastFourierTransforminO(nlogn)operations.Likewise,theproductAnycanalsobecomputedbytheFastFourierTransformbyrstembeddingAnintoa2n-by-2ncirculantmatrix.ThemultiplicationthusrequiresO(2nlog(2n))operations.ItfollowsthatthetotaloperationsperiterationisoforderO(nlogn).Inordertocompetewithdirectmethods,thecirculantmatrixBnshouldbechosensuchthattheconjugategradientmethodconvergessucientlyfastwhenappliedtothepreconditionedsystemB1nAnx=B1nb.Itiswell-knownthatthemethodconvergesfastifB1nAnhasaclusteredspectrum,i.e.B1nAnisoftheformIn+Un+WnwhereInistheidentitymatrix,UnisamatrixoflowrankandWnisamatrixofsmall‘2norm.Strangin[17]proposedapossiblechoiceofcirculantpreconditionerSn.ItisobtainedbycopyingthecentraldiagonalsofAnandreectingthem2aroundtocompletethecirculant.ChanandStrang[3]thenprovedthatifthediagonalsajoftheToeplitzmatrixAnareFouriercoecientsofapositivefunctionintheWienerclass,i.e.Pjjajj1,thentheeigenvaluesofthepreconditionedsystemS1nAnwillbeclusteredaroundoneforlargen.Itfol-lowsthatthepreconditionedconjugategradientmethod,whenappliedtothepreconditionedsystem,convergessuperlinearlyforlargen.Moreprecisely,forall0,thereexistsaconstantc()0suchthattheerrorvectoreqofthepreconditionedconjugategradientmethodattheqthiterationsatisesjjeqjjc()qjje0jj(1)whennissucientlylarge.Herejjxjj2=xS1=2nAnS1=2nx.HencethenumberofiterationsrequiredforconvergenceisindependentofthesizeofthematrixAnwhennislarge.Inparticular,thesystemAnx=bcanbesolvedinO(nlogn)operations.Overthepastfewyears,severalotherpreconditionershavealsobeenproposed,seeforinstance,T.Chan[9],Chan[5],Tyrtyshinkov[20],KuandKuo[16]andHuckle[15].InChan[4,5]andChan,JinandYeung[6],wehaveshownrespectivelythatthepreconditionersproposedin[9],[5]and[20]alsoworkfortheWienerclassfunctions,i.e.(1)holdsifPjjajj1.Huckle,ontheotherhand,hasprovedin[15]thathispreconditionerworksfortheclassoffunctionswithPjjjajj21.WeremarkthatitistheBesovspaceB1=22.ForT.Chan’spreconditioner,ChanandYeung[7]recentlyhaveextendedthesuperlinearconvergenceresultstotheclassof2-periodiccontinuousfunctions.OneoftheaimsofthispaperistoobtainsimilarresultsforStrang’spreconditioner.WewillprovethatStrang’spreconditionerworksforaslightlysmallerclassoffunctions(see(30))thanT.Chan’spreconditionerdoes.Intheconjugategradientmethod,anestimateofthenumberofiterationsrequiredforconvergencecanbeobtainedbystudyingthepreciserateatwhichjjeqjjgoestozeroin(1).Trefethen[18]rstprovedthatiffisapositiverationalfunctionoftype(;),thenthepreconditionedsystemS1nAnhasatmost1+2maxf;gdistincteigenvalues.Hencetheconjugategradientmethod,whenappliedtothepreconditionedsystem,convergesinatmost1+2maxf;gsteps.Healsoprovedthatiffispositiveandanalyticinaneighbourhoodofjzj=1andifSnis