(1999)_ARTICLES_-_Finite_Difference_Methods_and_Sp

FINITEDIFFERENCEMETHODSANDSPATIALAPOSTERIORIERRORESTIMATESFORSOLVINGPARABOLICEQUATIONSINTHREESPACEDIMENSIONSONGRIDSWITHIRREGULARNODESPETERK.MOOREySIAMJ.NUMER.ANAL.c°1999SocietyforIndustrialandAppliedMathematicsVol.36,No.4,pp.1044{1064Abstract.Adaptivemethodsforsolvingsystemsofpartialdierentialequationshavebecomewidespread.Muchoftheeorthasfocusedonniteelementmethods.Inthispapermodiednitedierenceapproximationsareobtainedforgridswithirregularnodes.Themodicationsarerequiredtoensureconsistencyandstability.Asymptoticallyexactaposteriorierrorestimatesofthespatialerrorarepresentedforthenitedierencemethod.Theseestimatesarederivedfrominterpolationestimatesandarecomputedusingcentraldierenceapproximationsofsecondderivativesofthesolutionatgridnodes.Theinterpolationerrorestimatesareshowntoconvergeforirregulargridswhiletheaposteriorierrorestimatesareshowntoconvergeforuniformgrids.Computationalresultsdemonstratetheconvergenceofthenitedierencemethodandaposteriorierrorestimatesforcasesnotcoveredbythetheory.Keywords.nitedierencemethods,aposteriorierrorestimates,irregulargridsAMSsubjectclassications.65M06,65M15,65M50PII.S00361429973220721.Introduction.Adaptivemethodsforsolvingsystemsofpartialdierentialequationshavebecomewidespread.Robustadaptivesoftwareisnowavailableforproblemsinoneand,toalesserextent,twodimensions[8,10,11].Inthreedimensionsmuchoftheworkhasfocusedontheuseofniteelementandnitevolumemethodsonunstructuredtetrahedralmeshes[17].Hexahedralgridshavealsobeenproposed[18,19].Thesemeshestypicallyhaveirregular(hanging)nodes[3,15,18]atwhichcontinuityisenforced.Aposteriorierrorestimatesforniteelementmethodsonhexahedralgridswithoutirregularnodescanbeobtainedbygeneralizingthetwo-dimensionalestimatesof[1,2].Residual-basedestimatesforgridswithirregularnodesforellipticproblemshavealsobeendeveloped[19].Theseestimatesarenotasymptoticallyexact.Inthispapermodiednitedierencemethodsandasymptoticallyexactapos-teriorierrorestimatesarepresentedforsolvingparabolicequationsoftheformut+f(x;t)=
u;x=(x;y;z)2­[x0;x1][y0;y1][z0;z1];t0;u(x;0)=u0(x);x2­;(1)togetherwithDirichletboundaryconditionsongridswithirregularnodes.Thefamil-iarnitedierencestencilsmustbemodiedtoaccountforthegridirregularity.Theresultingsystemofdierential-algebraicequationsisintegratedusingeitherthefor-wardEulermethodorthemultisteppackageDASPK[7].Throughout,thetemporalReceivedbytheeditorsMay30,1997;acceptedforpublication(inrevisedform)July6,1998;publishedelectronicallyMay26,1999.ThisresearchwaspartiallysupportedbyDepartmentofEnergygrantDOE-FG01-93EW53023andbytheNationalScienceFoundationthroughtheInstituteforMathematicsandItsApplicationsattheUniversityofMinnesota.([e-mail]).1044FINITEDIFFERENCEMETHODSONIRREGULARGRIDS1045integrationisdoneinsuchawaythatthespatialerrordominatesthetemporalerror.Extensionsofuniformgridaposteriorierrorestimates[2,21]areneededtoaccountfortheirregularnodes.Denitionsofadmissibleandcomputablegridsforsolving(1)andrulesgoverninggridrenementandcoarseningarepresentedinsection2.Theone-irregularandk-neighborruleswereintroducedby[6]fortwo-dimensionalgrids.Anadditionalrule,thesiblingrule,isproposedsothaterrorestimatesandconsistentnitedierenceapproximationscanbecomputed.Iprovethattheone-irregularrulerestrictsthenumberandpositionofirregularnodesonanelementtoeightcases.Ialsoprovethatthesiblingrulelimitsthetypesofregularnodesthatcanoccur.Thepapercontainstwomajorresults.Therst(section3)providesformulasfortheinterpolationerroronelementswithirregularnodes.Theseformulas,asintheuniformgridcase,dependonsecondderivativesofthesolution,butinamorecompli-catedfashion.Iprovethat\aposterioriestimatesoftheinterpolationerrorcanbeobtainedusingtheseformulasandestimatesofthesecondderivativescomputedfromcentraldierenceapproximationsofthetheinterpolatingpolynomial.Thesecondkeyresult(section4)showsthatinthecaseofuniformgridstheformulasfortheaposterioriinterpolationerrorestimateswiththeinterpolatedvaluesreplacedbythenitedierencesolutionareasymptoticallyexactaposteriorispatialerrorestimatesofthenitedierencesolution.Modiednitedierenceapproximationsforirregulargridsarederivedinsection4andareshowntoconverge.Computationsinsection5suggestthattheseaposteriorierrorestimatescanbeextendedtoirregulargridsusingtheresultsofsection3.Someconclusionsarepresentedinsection6.2.Griddenition.Thegrid,
­,for­willbeobtainedbyrecursivetrisection,beginningwith­.Thus,thegridhasanoctreestructurewiththerootcorrespondingto­.Theleafverticesofthetreearecalledelements(unrenedelementsin[20]).Thelevelofanelementinthegridisthelengthofthepathfromtheroottotheelement.Avertexwitheightsubverticesisreferredtoasaparentvertexandtheeightsubverticesareitsospringorchildren.Eightverticeshavingacommonparentarecalledsiblings.Agridissaidtobeuniformifallitselementsareatthesamelevel.AgridisadmissibleinthesenseofBabuskaandRheinboldt[4,5]ifitisdenedrecursivelybythefollowingt