On the global error of discretization methods for

OntheGlobalErrorofDiscretizationMethodsforOrdinaryDifferentialEquationsJitseNiesenTrinityHallUniversityofCambridgeSubmittedMarch2004RevisedJune2004AdissertationpresentedinthefulfilmentoftherequirementsforthedegreeofDoctorofPhilosophyattheUniversityofCambridgeAbstractDiscretizationmethodsforordinarydifferentialequationsareusuallynotexact;theycommitanerrorateverystepofthealgorithm.Alltheseerrorscombinetoformtheglobalerror,whichistheerrorinthefinalresult.Theglobalerroristhesubjectofthisthesis.Inthefirsthalfofthethesis,accurateaprioriestimatesoftheglobalerrorarederived.Threedifferentapproachesarefollowed:tocombinetheeffectsoftheerrorscommittedateverystep,toexpandtheglobalerrorinanasymptoticseriesinthestepsize,andtousethetheoryofmodifiedequations.Thelastapproach,whichisoftenthemostusefulone,yieldsanestimatewhichiscorrectuptoatermoforderh2p,wherehdenotesthestepsizeandptheorderofthenumericalmethod.ThisresultisthenappliedtoestimatetheglobalerrorfortheAiryequa-tion(andrelatedoscillatorsthatobeytheLiouville–Greenapproximation)andtheEmden–Fowlerequation.Thelatterexamplehastheinterestingfeaturethatitisnotsufficienttoconsideronlytheleadingglobalerrorterm,becausesubsequenttermsofhigherorderinthestepsizemaygrowfasterintime.Thesecondhalfofthethesisconcentratesonminimizingtheglobalerrorbyvaryingthestepsize.Itisarguedthatthecorrectobjectivefunctionisthenormoftheglobalerrorovertheentireintegrationinterval.Specifically,theL2normandtheL∞normarestudied.Intheformercase,Pontryagin’sMinimumPrincipleconvertstheproblemtoaboundaryvalueproblem,whichmaybesolvedanalyti-callyornumerically.WhentheL∞normisused,aboundaryvalueproblemwithacomplementarityconditionresults.Alternatively,theExteriorPenaltyMethodmaybeemployedtogetaboundaryvalueproblemwithoutcomplementaritycondition,whichcanbesolvedbystandardnumericalsoftware.ThetheoryisillustratedbycalculatingtheoptimalstepsizeforsolvingtheDahlquisttestequationandtheKeplerproblem.iiiDeclarationThisdissertationistheresultofmyownworkandincludesnothingwhichistheoutcomeofworkdoneincollaborationexceptwherespecificallyindicatedinthetext.JitseNiesenPrefaceItisagreatpleasuretobeabletowritethispreface.Itnotonlysignalsthatthethesishascometocompletion,butitalsogivesmetheopportunitytothankallthepeoplewithoutwhosehelpIwouldnothavecometothispoint.MyPhDsupervisorisAriehIserles.Theresearchdescribedinthisthesisbuiltonhisideas,andhehasbeenasourceofassistanceandinspirationthroughout.PerChristianMoanhasputmeontherighttrackinthefirstfewmonthsofmyPhD,whileAriehwasabroad,andhehasbeenveryhelpfuleversince.AriehandPerChristian,thankyou.Iamalsogratefultothemanycolleagueswhodis-cussedmyworkwithme,includingSergioBlanes,ChrisBudd,StigFaltinsen,TonyHumphries,TobiasJahnke,ErjenLefeber,ChristianLubich,MarcelOliver,BrynjulfOwren,MatthewPiggot,DivakarViswanath,andWillWright.TheNu-mericalAnalysisgroupoftheUniversityofCambridgeisagreatplacetoworkandIthankitspresentandformermembersforprovidingapleasantatmosphere;theyareArieh,PerChristian,Sergio,andStigwhomIhavealreadymentioned,andBradBaxter,AurelianBejancu,NicoletaBˆıl˘a,CoraliaCartis,AnitaFaul,SimonFoucart,Hans-MartinGutmann,RaphaelHauser,MikePowell,MalcolmSabin,andAlexeiShadrin.IamespeciallygratefulforthecompanyofCora,withwhomIsharedanofficeforfouryears.ShewentthroughherPhDatthesametimeandwasagreatsupportforme.IthanktheVSBFundsandNufficintheNetherlands,theEPSRCinBritain,andvariousotherDutchsponsorsfortheirfinancialsupport.IalsothankSimonMalhamforlettingmecontinuemyworkonthethesiswhileatHeriot-Watt.Lastbutnotleast,Iwishtothankmyfriendsandfamily.Theymaynothavecontributeddirectlytothethesis,buttheyalwaysweretheretogivesupport.Iwouldnothavemanagedtoendurethisordealwithouttheirhelp.Thankstoallofyou.Edinburgh,March2004JitseNieseniiiContentsAbstractiPrefaceiii1Introduction1PartIEstimatingtheglobalerror62Thenumericalsolutionofordinarydifferentialequations72.1Basictheory.............................72.2Runge–Kuttamethods.......................102.3ButchertreesandB-series.....................112.4Backwarderroranalysis......................152.5Variablestep-sizemethods.....................193Threemethodstoestimatetheglobalerror223.1LadyWindermere’sfan.......................233.2Asymptoticexpansion.......................313.3Modifiedequationsandtheglobalerror..............334Applicationsofglobalerrorestimates384.1Errorgrowthinperiodicorbits...................384.2TheAiryequationandrelatedoscillators..............394.3TheEmden–Fowlerequation....................48ivCONTENTSvPartIIMinimizingtheglobalerror605Formulationoftheoptimizationproblem615.1Minimizingthefinalerror......................625.2Minimizingtheerroratallintermediatepoints...........645.3Formulationasanoptimalcontrolproblem.............666MinimizingtheerrorintheL2norm696.1Optimalcontrolproblems......................706.2Analytictreatment.........................746.3Numericaltreatment........................777Minimizingthemaximalerror887.1State-constrainedoptimalcontrolproblems............897.2Analytictreatment.........................937.3Numeri