Semi-implicit spectral deferred correction methods

COMM.MATH.SCI.c°2003InternationalPressVol.1,No.3,pp.471–500SEMI-IMPLICITSPECTRALDEFERREDCORRECTIONMETHODSFORORDINARYDIFFERENTIALEQUATIONS¤MICHAELL.MINIONyAbstract.Asemi-implicitformulationofthemethodofspectraldeferredcorrections(SISDC)forordinarydifferentialequationswithbothstiffandnon-stifftermsispresented.Severalmodi-ficationsandvariationstotheoriginalspectraldeferredcorrectionsmethodbyDutt,Greengard,andRokhlinconcerningthechoiceofintegrationpointsandtheformofthecorrectioniterationarepresented.ThestabilityandaccuracyoftheresultingODEmethodsforbothstiffandnon-stiffproblemsareexploredanalyticallyandnumerically.TheSISDCmethodsareintendedtobecombinedwiththemethodoflinesapproachtoyieldaflexibleframeworkforcreatinghigher-ordersemi-implicitmethodsforpartialdifferentialequations.AdiscussionandnumericalexamplesoftheSISDCmethodappliedtoadvection-diffusiontypeequationsareincluded.Theresultssuggestthathigher-orderSISDCmethodsareacompetitivealternativetoexistingRunge-Kuttaandlinearmultistepmethodsbasedontheaccuracyperfunctionevaluation.Keywords.StiffEquations,FractionalStepMethods,MethodofLines1.IntroductionThequestionofhowtoconstructstableandaccuratenumericalmethodsforthesolutionofinitialvalueproblemsdeterminedbyordinarydifferentialequations(ODEs)hasbeenstudiedextensivelyandwithagreatdealofsuccessinthelastthirtyyears.Inparticularfornon-stiffODEs,explicithigh-ordermethodssuchasRunge-Kutta,linearmulti-step,orpredictorcorrectormethodsarewellunderstood,andarereadilyavailable,e.g.[3,8,18].Forstiffsystems,whereefficientmethodsareimplicit,theissuescanbemorecomplicated,butstillmanygoodmethodshavebeendeveloped,e.g.[3,8,19].Nevertheless,Dutt,Greengard,andRokhlinrecentlypresentedanewvariationoftheclassicalmethodofdeferredcorrections,thespectraldeferredcorrectionmethod(SDC)[13].Implicitversionsofthismethodareshowntohavegoodstabilityandaccuracypropertiesforstiffequationsevenforversionswithveryhigh-orderaccuracy(uptothirtiethorderin[13]).However,whentheequationofinterestcontainsbothstiffandnon-stiffcompo-nents,traditionalexplicitorimplicitmethodsmayleadtoanumericallyinefficientapproach.Forsuchproblemsanimplicittreatmentofthestifftermsisdesirableinordertoavoidanunreasonablysmalltimestep.However,insituationsinwhichthenon-stifftermsaremuchlesscomputationallyexpensivetotreatexplicitlythanimplicitly,aconsiderablesavingsincomputationalcostmaybeachievedbyusingasemi-implicitapproachinwhichstifftermsaretreatedimplicitlyandnon-stifftermsexplicitly.ItiscertainlynotthecasethatallsystemsofODEscaneasilybesplitintostiffandnon-stiffparts,butaprimaryexampleofsuchequationsthatmotivatethecurrentworkresultsfromthetemporaldiscretizationofpartialdifferentialequations(PDEs)whichmodelphysicalsystemswithtwoormoredisparatetimescales.Twowell-knownexamplesareadvection-diffusion-reactionproblemsandsystemscontainingfluid-membraneinteractions.Acommonstrategyforproducinghigher-ordermethodsforPDEsisthesocalledmethodoflinesapproach(hereafterMOL).InMOLa¤Received:October8,2002;accepted(inrevisedversion):June28,2003.CommunicatedbyShiJin.yDepartmentofMathematics,PhillipsHall,CB3250,UniversityofNorthCarolina,ChapelHill,NC27599([e-mail]).471472CORRECTIONMETHODSFORORDINARYDIFFERENTIALEQUATIONSPDEisdiscretizedinspaceonly,whichresultsinasetofcoupledODEs,oneforeachdiscretizationvariable.TheseODEscanthen,inprinciple,besolvedwithanyappropriateintegrationmethod.HoweverforPDEswithmultipletimescales,theODEswhichresultfromaMOLdiscretizationwillgenerallyincludebothstiffandnon-stiffterms.Whennon-stifftermscontainspatialnonlinearities(asinthecaseofadvection),itisgenerallymuchmoreexpensivetoimplementfullyimplicitODEmethodsbecauseoftheresultinglargesystemofcouplednonlinearequations,hencesemi-implicitmethodsareattractive.Manysemi-implicitmethodsforODEshaveindeedappearedinrecentyears,andthereareadvantagesanddisadvantagestoeach(e.g.[2,4,5,9,15,21,22,27,28,32]).Inthispaper,afamilyofsemi-implicitSDCmethodswillbeintroducedwhichisdesignedtoovercomesomeofthedisadvantagesofexistingmethods.ThemainadvantageofSDCmethodisthatonecanuseasimplenumericalmethod(evenafirst-ordermethod)tocomputeasolutionwithhigher-orderaccuracy.Thisisaccomplishedbyusingthenumericalmethodtosolveaseriesofcorrectionequationsduringeachtimestep,eachofwhichincreasestheorderofaccuracyofthesolution.TheflexibilityinthechoiceofthemethodusedinthedeferredcorrectioniterationsmakesSDCmethodsparticularlyattractivetoproblemspossessingdisparatetimescalessincealower-orderaccuratesemi-implicitortime-splitapproachcanbeusedduringeachiterationwithoutlimitingtheoverallsolutiontolower-orderaccuracy.Inthiswork,asimplefirst-order,semi-implicitmethodisusedinthecontextofSDCtoconstructhigher-ordersemi-implicitSDCmethods(hereafterSISDCmethods).Theoutlineofthispaperisasfollows.AfterashortdescriptionoftheSDCmethodinSect.2,asemi-implicitversionforageneralclassofODEsisintroducedinSect.3.1.AcomparativediscussionofexistingapproachesispresentedinSect.3.2.ThestabilityandaccuracyofSISDCmethodsareinvestigatedinSect.4.Tech-niquesforreducingthenumberoffunctionevaluationsnecessaryforag