Semi-Lagrangian Approximation Schemes for Linear and Hamilton–Jacobi Equations OT133_Falcone-Ferretti_FM.indd 1 10/21/2013 10:53:31 AM Semi-Lagrangian Approximation Schemes for Linear and Hamilton–Jacobi Equations Maurizio Falcone Sapienza – Università di Roma Rome, Italy Roberto Ferretti Università di Roma Tre Rome, Italy Society for Industrial and Applied Mathematics Philadelphia OT133_Falcone-Ferretti_FM.indd 3 10/21/2013 10:53:31 AM Copyright © 2014 by the Society for Industrial and Applied Mathematics 10 9 8 7 6 5 4 3 2 1 All rights reserved. Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 Market Street, 6th Floor, Philadelphia, PA 19104-2688 USA. Trademarked names may be used in this book without the inclusion of a trademark symbol. These names are used in an editorial context only; no infringement of trademark is intended. Mathematica is a registered trademark of Wolfram Research, Inc. Figures 3.2, 6.1, 6.4-6, 8.4-7, 9.9-11 reprinted with kind permission of Springer Science + Business Media. Figures 6.2-3, 8.10-15, and right image of 8.16 reprinted with permission of World Scientific Publishing. Figure 7.7 reprinted with permission from Global Science Press. Figures 7.8, 7.11, 8.2, 8.3, 9.4, 9.8 reprinted with permission from Elsevier. Figure 7.10 reprinted with permission from John Wiley and Sons. Figures 9.6 and 9.7 reprinted with permission from European Mathematical Society. Left image of Figure 8.16 reprinted with permission from Antony Willits Merz. Library of Congress Cataloging-in-Publication Data Falcone, Maurizio, author. Semi-Lagrangian approximation schemes for linear and Hamilton–Jacobi equations / Maurizio Falcone, Sapienza – Università di Roma, Rome, Italy, Roberto Ferretti, Università di Roma Tre, Rome, Italy. pages cm. -- (Applied mathematics) Includes bibliographical references and index. ISBN 978-1-611973-04-4 1. Hamilton–Jacobi equations. 2. Approximation theory. 3. Differential equations, Partial–Numerical solutions. I. Ferretti, Roberto, author. II. Title. QA377.F35 2013 515’.353--dc23 2013033334 is a registered trademark. OT133_Falcone-Ferretti_FM.indd 4 10/21/2013 10:53:31 AM To our daughters Cecilia and Flavia, who will never read this book. 1 OT133_Falcone-Ferretti_FM.indd 5 10/21/2013 10:53:31 AM Contents Preface ix Notation xi 1 Modelsandmotivations 1 1.1 Linearadvectionequation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 NonlinearevolutiveproblemsofHJtype . . . . . . . . . . . . . . . . . . 3 1.3 Nonlinearstationaryproblems. . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Simpleexamplesofapproximationschemes . . . . . . . . . . . . . . . . 10 1.5 Somedifficultiesarisingintheanalysisandintheapproximation . . 12 1.6 Howtousethisbook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Viscositysolutionsoffirst-orderPDEs 15 2.1 Thedefinitionofviscositysolution . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Viscositysolutionforevolutiveequations. . . . . . . . . . . . . . . . . . 24 2.3 Problemsinboundeddomains . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4 Viscositysolutionsandentropysolutions . . . . . . . . . . . . . . . . . . 35 2.5 Discontinuousviscositysolutions . . . . . . . . . . . . . . . . . . . . . . . 37 2.6 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3 Elementarybuildingblocks 41 3.1 AreviewofODEapproximationschemes . . . . . . . . . . . . . . . . . 41 3.2 Reconstructiontechniquesinoneandmultiplespacedimensions . . 45 3.3 Functionminimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.4 NumericalcomputationoftheLegendretransform . . . . . . . . . . . 71 3.5 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4 Convergencetheory 75 4.1 Thegeneralsetting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.2 Convergenceresultsforlinearproblems: TheLax–Richtmeyerthe- orem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.3 Moreonstability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.4 ConvergenceresultsforHJequations . . . . . . . . . . . . . . . . . . . . 88 4.5 Numericaldiffusionanddispersion . . . . . . . . . . . . . . . . . . . . . . 98 4.6 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 First-orderapproximation schemes 101 5.1 Treatingtheadvectionequation . . . . . . . . . . . . . . . . . . . . . . . . 101 5.2 TreatingtheconvexHJequation . . . . . . . . . . . . . . . . . . . . . . . 126 vii viii Contents 5.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.4 Stationaryproblems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 5.5 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 6 High-orderSLapproximation schemes 147 6.1 SLschemesfortheadvectionequation . . . . . . . . . . . . . . . . . . . . 147 6.2 SLschemesfortheconvexHJequation . . . . . . . . . . . . . . . . . . . 172 6.3 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 7 FluidDynamics 189 7.1 TheincompressibleEulerequationin(cid:2)2 . . . . . . . . . . . . . . . . . . 189 7.2 TheShallowWaterEquation . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7.3 Someadditionaltechniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 7.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 7.5 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 8 Controlandgames 207 8.1 Optimalcontrolproblems: Firstexamples . . . . . . . . . . . . . . . . . 208 8.2 DynamicProgrammingforotherclassicalcontrolproblems. . . . . . 213 8.3 ThelinkbetweenBellmanequationandPontryaginMaximumPrin- ciple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 8.4 SLschemesforoptimalcontrolproblems . . . . . . . . . . . . . . . . . . 219 8.5 DynamicProgrammingfordifferentialgames . . . . . . . . . . . . . . . 246 8.6 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 9 Frontpropagation 269 9.1 Frontpropagationviathelevelsetmethod . . . . . . . . . . . . . . . . . 269 9.2 FrontsevolvingbyMeanCurvature . . . . . . . . . . . . . . . . . . . . . 276 9.3 Applicationstoimageprocessing . . . . . . . . . . . . . . . . . . . . . . . 279 9.4 FastMarchingMethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 9.5 Commentedreferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Bibliography 299 Index 317 Preface ThisbookisforpeopleinterestedinthenumericalsolutionofPDEs,withanempha- sisonhigh-orderschemesforhyperbolicproblems. Infact,evolutivelinearandnonlinear first-orderPDEsappearinavarietyofapplicationsrangingfromgeophysicalandatmo- spheric problems to control theory, Fluid Dynamics, and image processing. Although everyapplicationhasitsownfeatures,ausualrequirementforthenumericalsolutionis to keep accuracy and stability without overly restrictive assumptions on the time step, whichusuallyimplyahighcomputationalcomplexity. WewilldescribeandanalyzebasicandrecentdevelopmentsoftheSemi-Lagrangian techniquefortheapproximation offirst-orderPDEswithaspecialfocusonHamilton– Jacobiequations. Themainpurposeistoobtainmethodswhichareunconditionallysta- blewithrespecttothechoiceofthetimestep. Thebasicideadatesbacktothemethod proposedbyCourant,Isaacson,andReesin1952[CIR52]forfirst-ordersystemsoflin- earequationsandhasgonethroughanumberofimprovementsandextensionssince. In particular, the main developments have been proposed within the Numerical Weather Predictioncommunity[SC91],wherethisclassofschemeshasbecomeofcommonuse. Asfortheadvectionequation,thedrivingforceofthismethodisthemethodofchar- acteristicswhichaccountsfortheflowofinformationinthemodelequation. Atthenu- mericallevel, theSemi-Lagrangian approximation mimicsthemethod ofcharacteristics lookingforthefootofthecharacteristiccurvepassingthrougheverynodeandfollowing thiscurveforasingletimestep. In order to derive a numerical method from this general idea, several ingredients should be put together, mainly a technique for ODEs to track characteristics and a re- construction technique to recover pointwise values of the numerical solution. In this framework,theorderofspaceandtimediscretizationsistypicallyreversedwithrespectto moreconventionalschemes—thefirstdiscretizationisdoneintime,thesecondinspace— althoughthefinalresultisclearlyafullydiscretescheme. Thisreversalisthekeytogetting weakerstabilityrequirements. Thisbookhastwomainpurposes. ThefirstistopresentSemi-Lagrangianapproxima- tionschemes,reviewingtheirconstructionandtheoryonmodelequationswhichrange fromthesimpleadvectionequationtoHamilton–Jacobiequations. Inthebasicsituation offirst-orderschemes,wewillalsomakeacomparisonwithmorestandardapproximation techniques, namelyfinitedifferenceschemesofupwindandcentered types. Thereader willfindinformationontheconstructionoftheschemestogetherwithadetailedtheoret- icalanalysis,atleastforthemorepopularchoicesoftheirelementarybuildingblocks. We haveincludedanumberofpracticalalgorithmicrecipes,andwebelievethatafterreading thisbook it should bepossible toprogram and apply themethods described herefrom scratch. The second goal of the book is to present some applications and show the Semi- Lagrangian approximations at work on a variety of nonlinear problems of applicative ix x Preface interest. Wealsoaimatshowingthatthistechniqueiswellsuitedfortheapproximation ofproblemswithnonsmoothsolutions,likeweaksolutionsintheviscositysenseinthe caseofHamilton–Jacobiequations. The book is intended to be accessible to a reader with a basic knowledge of linear PDEsandstandardnumericalmethods. TheanalysisofHamilton–Jacobiequationswill, ofcourse,requirespecificanalyticaltools,whichhavebeenincludedinthesectiondevoted toviscositysolutions. Thepresentationisconceivedtobereasonablyself-contained,but atthesametimeitwillcollectinaunifiedframeworkresultswhicharespreadoverthelit- erature. Clearly,moreinformationonthetheoryofviscositysolutionscanbeobtained looking at thespecific references, and in particular at thebooks [Ba98, BCD97, FS93]. Some standard finite difference schemes for Hamilton–Jacobi equations can be found in [Se99, OF03], whereas other schemes based on control techniques are presented in [KuD01]. AlthoughHamilton–Jacobi equationsandtheirapplicationsaretheobject ofanex- tensiveliterature,wewillmostlylimitourpresentationtotheSemi-Lagrangianapproach and toitsrelationship withDynamic Programming. A detailedoverview of numerical methodsforHamilton–Jacobi equationsgoesbeyond thescopesofthisbook, although wehopetodevelopthistopicingreaterdetailinthefuture. Acknowledgments Wewishtothankallcolleaguesandstudentswhocontributedto the development of the results reviewed in this book or took part in enlightening dis- cussionsonalgorithmicandtheoreticalissues. WearealsoindebtedtoL.Bonaventura, E.Carlini, J.-M.Qiu, M.Restelli, G.Rosatti, C.-W. Shu, andG.Tumolo forproviding someofthenumericaltestspresentedhere. SpecialthanksgotoourAcquisitionsEditor, ElizabethGreenspan,forherendlesspatienceduringthewritingofthemanuscript,and toourfamiliesfortheirconstantsupport. MaurizioFalconeandRobertoFerretti Rome,May20th,2013 Notation a.e. almosteverywhere(withrespecttotheLebesguemeasure) (cid:2)d euclideand-dim(cid:2)ensionalspace x·y scalarproduct d x y oftwovectorsx,y∈(cid:2)d i=1 i i |x| euclideannormofx∈(cid:2)d,|x|=(x·x)1/2 B(x ,r) openballofcenterx andradiusr in(cid:2)d,{x:|x−x |<r} 0 0 0 B(x ,r) closedballofcenterx andradiusr in(cid:2)d,{x:|x−x |≤r} 0 0 0 ∂E boundaryofthesetE intE interiorofthesetE E closureofthesetE coE convexhullofthesetE a∨b min{a,b}fora,b∈(cid:2) a∧b max{a,b}fora,b∈(cid:2) Du(x) gradientofafunctionu:(cid:2)d →(cid:2)atthepointx d(x,C) distancefromthepointxtotheclosedsetC Δt,Δx discretizationsteps,⎧incompactformΔ=(Δx,Δt) ⎪⎨+1 ifx>0, sgn(x) signofx:sgn(x):= 0 ifx=0, ⎪ ⎩ −1 ifx<0. i imaginaryunit (cid:7) 1 ifx∈Ω, 1Ω(x) characteristicfunctionofthe(cid:7)setΩ:1Ω(x):= 0 ifx(cid:7)∈Ω. 1 ifi=j, δ Kronecker’ssymbol:δ := ij ij 0 ifi(cid:7)=j. (cid:8)x(cid:9) lowerintegerpartofx:(cid:8)x(cid:9):=max{m∈(cid:3):m≤x} I [G](x) valueatthepointxoftheinterpolateofdegreekofthefunctiong k basedonthevectorG=(g(x))ofgridvaluesof g i ν(x) exteriornormaltoasurfaceatthepointx y(x,t;s) positionattimes ofthetrajectorystartingatxattimet y (s;α) positionattimes ofthetrajectorystartingatxattimet x,t anddrivenbythecontrolα y (s;α) positionattimes ofthetrajectorystartingatxattimet=0 x anddrivenbythecontrolα (cid:8) TV(w) totalvariationoftheunivariatefunctionw:TV(w)= |w(cid:10)(x)|dx D suppw supportofthefunctionw ω(δ) amodulusofcontinuity BUC(Ω) spaceofboundeduniformlycontinuousfunctionsontheopensetΩ Ck(Ω) spaceoffunctionsu:Ω→(cid:2)withcontinuouskthderivative Ck(Ω) spaceoffunctionswithcompactsuppo(cid:8)rtbelongingtoCk(Ω) 0 Lp(Ω) spaceoffunctionsu:Ω→(cid:2)suchthat |u|p(x)dx<+∞,1≤p<+∞ Ω L∞(Ω) spaceoffunctionsu:Ω→(cid:2)suchthatesssup|u(x)|<+∞ xi xii Notation Lp (Ω) spaceoffunctionsu∈Lp(K)foranycompactsetK⊂Ω,1≤p≤+∞ loc (cid:13)u(cid:13) normofuinLp(Ω),1≤p≤∞ p Wm,p(Ω) Sobolevspaceoffunctionsu:Ω→(cid:2)withthefirstmderivativesinLp(Ω) Wm,p(Ω) SobolevspaceoffunctionsuwiththefirstmderivativesinLp(K) loc foranycompactsetK⊂Ω C([0,T];X) spaceoffunctionsu:[0,T]×(cid:2)→(cid:2)suchthat(cid:13)u(t,·)(cid:13) ∈C([0,T]) X L∞([0,T];X) spaceoffunctionsu:[0,T]×(cid:2)→(cid:2)suchthat(cid:13)u(t,·)(cid:13) ∈L∞([0,T]) X lp spaceof pthpowersummablevectorsorsequences l∞ spaceofboundedvectorsorsequences V,v numericalsolutionasavectorandasavalueatthenodex j j Vn,vn numericalsolutionasavectorandasavalueatthenode(x ,t ) j j n V(k),v(k) numericalsolutionattheiterationkasavectorandasavalue j atthenodex j (cid:13)V(cid:13)p norminl(cid:9)p(cid:10),Δrexno·r·m·Δalxize(cid:2)dif|vref|eαr(cid:11)r1e/αdtoifaαn<um∞er,icalsolution: (cid:13)V(cid:13) := 1 d j j α max |v | ifα=∞. j j Bt transposeofamatrixB tr(B) traceofamatrixB ρ(B) spectralradiusofasquarematrixB∈(cid:2)m×m (cid:13)B(cid:13) fora(possiblyinfinite)matrixB,naturaloperatornorminlp: p (cid:13)BV(cid:13) (cid:13)B(cid:13) :=sup p p V(cid:7)=0 (cid:13)V(cid:13)p (cid:2) (cid:13)B(cid:13)∞ ∞-normofamatrixB:(cid:13)B(cid:13)∞=ma(cid:2)xi j|bij| (cid:13)B(cid:13)1 1-normofamatrixB:(cid:13)B(cid:13)1=m(cid:12)axj i|bij| (cid:13)B(cid:13) 2-normofamatrixB:(cid:13)B(cid:13) = ρ(BtB) 2 2 w,w l(cid:7)oweranduppersemicontinuousenvelopes: w(x):=liminf w(y), y→x w(x):=limsup w(y). y→x