Finite difference methods and spatial a posteriori

FINITEDIFFERENCEMETHODSANDSPATIALAPOSTERIORIERRORESTIMATESFORSOLVINGPARABOLICEQUATIONSINTHREESPACEDIMENSIONSONGRIDSWITHIRREGULARNODESPETERK.MOOREAbstract.Adaptivemethodsforsolvingsystemsofpartialdierentialequationshavebecomewidespread.Muchoftheeorthasfocusedonniteelementmethods.Inthispapermodiednitedierenceapproximationsareobtainedforgridswithirregularnodes.Themodicationsarerequiredtoensureconsistencyandstability.Asymptoticallyexactaposteriorierrorestimatesofthespatialerrorarepresentedforthenitedierencemethod.Theseestimatesarederivedfrominterpolationestimatesandarecomputedusingcentraldierenceapproximationsofsecondderivativesofthesolutionatgridnodes.Theinterpolationerrorestimatesareshowntoconvergeforirregulargridswhiletheaposteriorierrorestimatesareshowntoconvergeforuniformgrids.Computationalresultsdemonstratetheconvergenceofthenitedierencemethodandaposteriorierrorestimatesforcasesnotcoveredbythetheory.Keywords.nitedierencemethods,aposteriorierrorestimates,irregulargridsAMSSubjectclassications.65M06,65M15,65M50AbbreviatedTitleFiniteDierenceMethodsonIrregularGrids1.Introduction.Adaptivemethodsforsolvingsystemsofpartialdierentialequationshavebecomewidespread.Robustadaptivesoftwareisnowavailableforproblemsinone,andtoalesserextent,twodimensions[8,10,11].Inthreedimensionsmuchoftheworkhasfocusedontheuseofniteelementandnitevolumemethodsonunstructuredtetrahedralmeshes[17].Hexahedralgridshavealsobeenproposed[18,19].Thesemeshestypicallyhaveirregular(hanging)nodes[3,12,18]atwhichcontinuityisenforced.Aposteriorierrorestimatesforniteelementmethodsonhexahedralgridswithoutirregularnodescanbeobtainedbygeneralizingthetwo-dimensionalestimatesof[1,2].Residual-basedestimatesforgridswithirregularnodesforellipticproblemshavealsobeendeveloped[19].Theseestimatesarenotasymptoticallyexact.Inthispapermodiednitedierencemethodsandasymptoticallyexactaposteriorierrorestimatesarepresentedforsolvingparabolicequationsoftheformut+f(x;t)=u;DepartmentofMathematics,TulaneUniversity,NewOrleans,LA70118,[e-mail],504-865-5757(Phone),504-865-5063(Fax).ThisresearchwaspartiallysupportedbytheDepartmentofEnergygrant,DOE-FG01-93EW53023andbytheNationalScienceFoundationthroughtheInstituteforMathematicsanditApplicationsattheUniversityofMinnesota.1x=(x;y;z)2[x0;x1][y0;y1][z0;z1];t0;u(x;0)=u0(x);x2;(1)togetherwithDirichletboundaryconditionsongridswithirregularnodes.Thefamiliarnitedierencestencilsmustbemodiedtoaccountforthegridirregularity.Theresultingsystemofdierential-algebraicequationsisintegratedusingeithertheforwardEulermethodorthemultisteppackageDASPK[7].Through-outthetemporalintegrationisdoneinsuchawaythatthespatialerrordominatesthetemporalerror.Extensionsofuniformgridaposteriorierrorestimates[2,21]areneededtoaccountfortheirregularnodes.Denitionsofadmissibleandcomputablegridsforsolving(1)andrulesgoverninggridrenement/coarseningarepresentedinx2.Theone-irregularandk-neighborruleswereintroducedby[6]fortwo-dimensionalgrids.Anadditionalrule,thesiblingruleisproposedsothaterrorestimatesandconsistentnitedierenceap-proximationscanbecomputed.Iprovetheone-irregularrulerestrictsthenumberandpositionofirregularnodesonanelementtoeightcases.Ialsoprovethatthesiblingrulelimitsthetypesofregularnodesthatcanoccur.Thepapercontainstwomajorresults.Therst(x3)providesformulasfortheinterpolationerroronelementswithirregularnodes.Theseformulas,asintheuniformgridcase,dependonsecondderivativesofthesolution,butinamorecomplicatedfashion.Iprovethat\aposterioriestimatesoftheinterpolationerrorcanbeobtainedusingtheseformulasandestimatesofthesecondderivativescomputedfromcentraldierenceapproximationsofthetheinterpolatingpolynomial.Thesecondkeyresult(x4)showsthatinthecaseofuniformgridstheformulasfortheaposterioriinterpolationerrorestimateswiththeinterpolatedvaluesreplacedbythenitedierencesolutionareasymptoticallyexactaposteriorispatialerrorestimatesofthenitedierencesolution.Modiednitedierenceapproximationsforirregulargridsarederivedinx4andareshowntoconverge.Computationsinx5suggestthattheseaposteriorierrorestimatescanbeextendedtoirregulargridsusingtheresultsofx3.Someconclusionsarepresentedinx6.2.Griddenition.Thegrid,,forwillbeobtainedbyrecursivetrisection,beginningwith.Thus,thegridhasanoctreestructurewiththerootcorrespondingto.Theleafverticesofthetreearecalledelements(unrenedelementsin[20]).Thelevelofanelementinthegridisthelengthofthepathfromtheroottotheelement.Avertexwitheightsubverticesisreferredtoasaparentvertexandtheeight2subverticesareitsospringorchildren.Eightverticeshavingacommonparentarecalledsiblings.Agridissaidtobeuniformifallitselementsareatthesamelevel.AgridisadmissibleinthesenseofBabuskaandRheinboldt[4,5]ifitisdenedrecursivelybythefollowingtworules:1.isanadmissiblegrid;2.Ifisanadmissiblegridand~isanelementofthenthegridobtainedfromandtheeightelementscreatedbytrisecting~isadmissible.Suchgridscontaintwogeneraltypesofnodesregularandirregular.Anodeofisregularifforeveryelement~2suchthat2~,isacornernode