A level set approach for computing discontinuous s

MATHEMATICSOFCOMPUTATIONVolume72,Number241,Pages159{181S0025-5718(02)01438-2ArticleelectronicallypublishedonAugust13,2002ALEVELSETAPPROACHFORCOMPUTINGDISCONTINUOUSSOLUTIONSOFHAMILTON-JACOBIEQUATIONSYEN-HSIRICHARDTSAI,YOSHIKAZUGIGA,ANDSTANLEYOSHERAbstract.WeintroducetwotypesofnitedierencemethodstocomputetheL-solutionandtheproperviscositysolutionrecentlyproposedbythesecondauthorforsemi-discontinuoussolutionstoaclassofHamilton-Jacobiequa-tions.Byregardingthegraphofthesolutionasthezerolevelcurveofacontinuousfunctioninonedimensionhigher,wecantreatthecorrespondinglevelsetequationusingtheviscositytheoryintroducedbyCrandallandLions.However,weneedtopayspecialattentionbothanalyticallyandnumericallytopreventthezerolevelcurvefromoverturningsothatitcanbeinterpretedasthegraphofafunction.WedemonstrateourLax-Friedrichstypenumeri-calmethodsforcomputingtheL-solutionusingitsoriginallevelsetformula-tion.Inaddition,wecoupleournumericalmethodswithasingulardiusivetermwhichisessentialtocomputingsolutionstoamoregeneralclassofHJequationsthatincludesconservationlaws.Withthissingularviscosity,ournumericalmethodsdonotrequirethedivergencestructureofequationsanddoapplytomoregeneralequationsdevelopingshocksotherthanconservationlaws.ThesenumericalmethodsaregeneralizedtohigherorderaccuracyusingweightedENOlocalLax-FriedrichsmethodsasdevelopedrecentlybyJiangandPeng.Weverifythatournumericalsolutionsapproximatethepropervis-cositysolutionsobtainedbythesecondauthorinarecentHokkaidoUniversitypreprint.Finally,sincethesolutionofscalarconservationlawequationscanbeconstructedusingexistingnumericaltechniques,weuseittoverifythatournumericalsolutionapproximatestheentropysolution.1.IntroductionNonlinearHamilton-Jacobiequationsariseinmanydierentelds,includingmechanics,calculusofvariations,geometricoptics,controltheory,anddierentialgames.Becauseofthenonlinearity,theCauchyproblemsusuallyhavenonclassicalsolutionsduetothecrossingofcharacteristiccurves.Forscalarequationsofconservationlawtype,thereisawellknowntheoryre-gardingtheexistenceanduniquenessofaweaksolution,calledanentropysolution,usingthespecialintegralstructureoftheequation[23].Advancednumericalmeth-ods,e.g.,[15],[16],[30],[34],havebeendevelopedandwidelyusedtocomputeapproximationsthatconvergetothecorrectentropysolutions.ReceivedbytheeditorMarch7,2001.2000MathematicsSubjectClassication.Primary65Mxx,35Lxx;Secondary70H20.Keywordsandphrases.Hamilton-Jacobiequations,singulardiusion,levelsets.TherstandthethirdauthorsaresupportedbyONRN00014-97-1-0027,DARPA/NSFVIPgrantNSFDMS9615854andARODAAG55-98-1-0323.c2002AmericanMathematicalSociety159160Y.-H.R.TSAI,Y.GIGA,ANDS.OSHERNevertheless,thisnotionofweaksolutioncannotbeappliedtomanyfullynonlin-earequations,e.g.,theeikonalequationut+jruj=0:In1983,CrandallandLions[7]rstintroducedthenotionofviscositysolutionforthistypeofequations,basedonamaximumprincipleandtheorder-preservingpropertyofparabolicequations.Ingeneral,foranygivenHamilton-Jacobiequationoftheformut+H(x;t;u;Du)=0;whereHisacontinuousfunctionfromR+RRn;nondecreasinginu;andisanopensubsetofRn;thereexistsauniqueuniformlycontinuousviscositysolutioniftheinitialdataisboundedanduniformlycontinuous.1Thecontinuityofthesolutioncanbeunderstoodintuitivelyfromthe1Dfactthat\HJequationsaretheconservationlawsintegratedonce.Theviscositysolutionissometimesunderstoodasthelimitofthesolutionstotheequationwithvanishingviscosity.Correspondingly,CrandallandLionsin[6]provedtheconvergenceoftwoap-proximationstotheviscositysolutionofequationswhoseHamiltoniansonlydependonDu.ThiswasgeneralizedbySouganidistoequationswithvariablecoecientsin[31].Manysophisticatednumericalmethodshavesincebeendeveloped[21],[24],[26],[27].However,thereareproblemsincontroltheoryanddierentialgameswhichde-manddiscontinuoussolutions.Theoriginalviscositytheorydoesnotapplytodis-continuousinitialdata.ThenotionofsemicontinuousviscositysolutionhasbeenintroducedrstbyIshii[18,20]usinganextensionofPerron'smethod.BecauseofthenonuniquenessinIshii'sresult,othernotionsofsemicontinuoussolutionswereproposedbyvariousauthors[2],[4],withdierentkindsofadditionalpropertiesimposedontheHamiltonian.SomeofthesenotionsneedseriousrestrictionsontheHamiltonians,andothersareimplicitinthesensethattheprocessesoftak-ingsupremumandinmumareinvolved.Asaconsequence,onecannotdevelopnumericalmethodstoconstructapproximations.Foranoverviewoftheviscositytheoryandapplications,see[3]and[1].Finally,fortheclassofequationswithHamiltoniansH(x;u;Du)nondecreasinginu,M.-H.Satoandthesecondauthor[14]introducedanewnotionofsemicontin-uoussolution.ThisnotionofsolutionisdenedbytheevolutionofthezerolevelcurveoftheauxiliarylevelsetequationwhichembedstheoriginalHJequation.ItisthuscalledtheL-solution.Inthisarticle,wewilldeviseaLax-FriedrichstypeschemetocomputeapproximationoftheL-solutioninitsoriginalformulation(i.e.,levelset).WewillalsoshowthatwithsuitableCFLcondition,ourschemeskeepthediscreteversionofanimportantpropertyofthisclassofHJequations.WhentheHamiltonianH(t;x;u;Du)isnotnondecreasinginu,thesolutionma