On the numerical integration of ordinary different

ONTHENUMERICALINTEGRATIONOFORDINARYDIFFERENTIALEQUATIONSBYPROCESSEDMETHODSS.BLANES†,F.CASAS†,ANDA.MURUA‡Abstract.Weprovideatheoreticalanalysisoftheprocessingtechniqueforthenumericalintegrationofordinarydifferentialequations.Wegettheeffectiveorderconditionsforprocessedmethodsinageneralsettingsothattheresultsobtainedcanbeappliedtodifferenttypesofnumericalintegrators.Wealsoproposeaproceduretoapproximatethepost-processorsuchthatitsevaluationisvirtuallycostfree.Theanalysisisillustratedforaparticularclassofcompositionmethods.Keywords.Effectiveorder,processingtechnique,cheappost-processor,initialvalueproblemsAMSsubjectclassifications.65L05;65L70;22E601.Introduction.Giventheordinarydifferentialequationx0=f(x),x0=x(t0)∈RD,(1.1)withf:RD→RDandassociatedvectorfield(orLieoperatorassociatedwithf)F=DXi=1fi(x)∂∂xi,(1.2)aone-stepnumericalintegratorforatimesteph,ψh:RD→RD,canbeseenasasmoothfamilyofmapswithparameterhsuchthatψ0istheidentitymap.Theintegratorψhissaidtohaveorderofconsistency≥q(orequivalently,tobeoforder≥q)ifψh=ϕh+O(hq+1),(1.3)whereϕhistheh-flowoftheODE(1.1).Then,anapproximationtotheexactsolutionx(h)isgivenbyxh=ψh(x0)=ϕh(x0)+δh,q(x0),whereδh,q(x0)=O(hq+1)denotesthelocaltruncationerror.Theefficiencyoftheintegrator(whencomparedwithmethodsofthesameorderandfamily)dependsbothonitscomputationalcostandthemagnitudeoftheerrorterm.Inthisworkwediscusstheclassofmethodsobtainedbyenhancinganintegratorψhwithprocessing.TheideaofprocessingcanbetracedbacktotheworkofButcher[7]in1969,whereitisconsideredinthecontextofRunge–Kuttamethods,andissummarizedin[12,19].Essentially,itconsistsinobtaininganew(hopefullybetter)integratoroftheformˆψh=πh◦ψh◦π−1h.(1.4)†DepartamentdeMatem`atiques,UniversitatJaumeI,12071-Castell´on,Spain([e-mail],[e-mail]).TheworkoftheseauthorshasbeenpartiallysupportedbyFundaci´oCaixaCastell´o–Bancaixa.SBhasalsobeensupportedbyMinisteriodeCienciayTecnolog´ıa(Spain)throughacontractinthePogrammeRam´onyCajal2001andbytheTMRprogrammethroughgrantEC-12334303730.‡KonputazioZientziaketaA.A.saila,InformatikaFakultatea,EHU/UPV,Donostia/SanSe-basti´an,Spain([e-mail]).12S.BLANES,F.CASAS,ANDA.MURUAThemethodψhisreferredtoasthekernelandtheparametricmapπh:RD→RDasthepost-processororcorrector.Applicationofnstepsoftheintegratorˆψhleadstoˆψnh=πh◦ψnh◦π−1h,whichcanbeconsideredasachangeofcoordinatesinphasespace.Thus,itisnotrequiredthatthekernelψhusedtopropagatethenumericalsolutionbeagoodinte-grator.Itissufficient,usingdynamicalsystemterminology,thatψhbeconjugatetoagoodintegrator.Usuallyoneisinterestedinthecasewhereπ0=id,theidentitymap,i.e.,πhisalsoanear-identitymap,althoughitisnotintendedtoapproximatetheh-flowϕh.Thepre-processorπ−1hisappliedonlyonce,sothatitscomputationalcostmaybeignored,thenthekernelψhactsonceperstepandfinallytheactionofthepost-processorπhisevaluatedonlywhenoutputisrequired.Processingisadvantageousifˆψhisamoreaccuratemethodthanψhandthecostofπhisnegligible:itprovidestheaccuracyofˆψhatthecostofthelessaccuratemethodψh.AlthoughinitiallyintendedforRunge–Kuttamethods,theprocessingtechniquedidnotbecomesignificantinpractice,probablyduetothedifficultiesofcouplingprocessingwithclassicalstrategiesofvariablestep-sizes.Ithasbeenonlyrecentlythatthisideahasproveditsusefulnessinthecontextofgeometricintegration,whereconstantstep-sizesarewidelyemployed.Theaimofgeometricintegrationistoconstructnumericalschemesfordiscretizingthedifferentialequation(1.1)whilstpreservingcertaingeometricpropertiesofthevectorfieldF.Itisgenerallyrecognizedthatthisclassofnumericalalgorithms(theso-calledgeometricintegrators)provideabetterdescriptionofthesystem(1.1)thanstandardmethods,bothwithrespecttothepreservationofinvariantsandalsointheaccumulationofnumericalerrorsalongtheevolution[12,22].Atypicalprocedureingeometricintegrationistoconsideroneormorelow-ordermethodsandcomposethemwithappropriatelychosenweightstoachievehigherorderschemes.Theresultingcompositionmethodinheritstherelevantpropertiesthebasicintegratorshareswiththeexactsolution,providedthesepropertiesarepreservedbycomposition[16].Ithasbeenpreciselyinthiscontextwheretheapplicationofprocessinghasprovedtobeaverypowerfultool,allowingtobuildnumericalschemeswithboththekernelandthepost-processortakenascompositionsofbasicintegrators.Inparticular,highlyefficientprocessedcompositionmethodshavebeenproposedinthelastfewyears,bothintheseparablecase[3](includingfamiliesofRunge–Kutta–Nystr¨omclassofmethods[5,14,15])andalsoforslightlyperturbedsystems[4,17,24].Themethodψhisofeffectiveorderqifapost-processorπhexistsforwhichˆψhisof(conventional)orderq[7],thatis,πh◦ψh◦π−1h=ϕh+O(hq+1).(1.5)Whenanalyzingtheorderconditionsˆψhhastoverifytobeamethodoforderq,ithasbeenshownthatmanyofthemcanbesatisfiedbyusingπh[1,3,8],sothatψhmustfulfillamuchreducedsetofconstraints.Furthermore,theerrortermδh,q(x0)dependsonbothψhandπh,andadditionalconditionscanbeimposedonthepost-processorinordertoreduceitsmagnitude.Thisallows,ontheonehand,toconsiderkernelsinvolvinglessevaluationsand,ontheotherhand,toanalyzeandobtainnewandefficientcompositionme