Value iteration convergence of $\epsilon$-monotone schemes for stationary Hamilton-Jacobi equations

Olivier Bokanowski; Maurizio Falcone; Roberto Ferretti; Lars Grüne; Dante Kalise; Hasnaa Zidani

doi:10.3934/dcds.2015.35.4041

Article Contents

2015, Volume 35, Issue 9: 4041-4070. Doi: 10.3934/dcds.2015.35.4041

This issue Previous Article Computation of Lyapunov functions for systems with multiple local attractors Next Article (Un)conditional consensus emergence under perturbed and decentralized feedback controls

Value iteration convergence of $\epsilon$-monotone schemes for stationary Hamilton-Jacobi equations

1.
Laboratoire Jacques-Louis Lions, UMR 7598, Université Paris-Diderot (Paris 7), UFR de Mathématiques - 5 rue Thomas Mann, 75205 Paris CEDEX 13
2.
Dipartimento di Matematica, Istituto "Guido Castelnuovo", Sapienza Università di Roma, Piazzale Aldo Moro, 2 I-00185 Roma
3.
Dipartimento di Matematica e Fisica, Università di Roma Tre, L.go S. Leonardo Murialdo, 1, 00146 Roma
4.
Mathematisches Institut, Fakultät für Mathematik, Physik und Informatik, Universität Bayreuth, 95440 Bayreuth
5.
Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenbergerstraße 69, 4040 Linz
6.
Unité des mathématiques appliquées (UMA), ENSTA ParisTech, 828 Bd Maréchaux, 91120 Palaiseau

Received: April 2014

Published: May 2017

Abstract Related Papers Cited by

Abstract

We present an abstract convergence result for the fixed point approximation of stationary Hamilton--Jacobi equations. The basic assumptions on the discrete operator are invariance with respect to the addition of constants, $\epsilon$-monotonicity and consistency. The result can be applied to various high-order approximation schemes which are illustrated in the paper. Several applications to Hamilton--Jacobi equations and numerical tests are presented.

Keywords:

Mathematics Subject Classification: Primary: 65M12, 49L25; Secondary: 65M06, 65M08.

Citation:

Related Papers

Cited by

References

[1]	R. Abgrall, Numerical discretization of the first-order Hamilton-Jacobi equation on triangular meshes, Comm. Pure Appl. Math., 49 (1996), 1339-1373.doi: 10.1002/(SICI)1097-0312(199612)49:12<1339::AID-CPA5>3.0.CO;2-B.
[2]	R. Abgrall, Numerical discretization of boundary conditions for first order Hamilton-Jacobi equations, SIAM J. Numer. Anal., 41 (2003), 2233-2261.doi: 10.1137/S0036142998345980.
[3]	S. Augoula and R. Abgrall, High order numerical discretization for Hamilton-Jacobi equations on triangular meshes, J. Sci. Comput., 15 (2000), 197-229.doi: 10.1023/A:1007633810484.
[4]	D. S. Balsara, T. Rumpf, M. Dumbser and C.-D. Munz, Efficient, high accuracy ader-weno schemes for hydrodynamics and divergence-free magnetohydrodynamics, J. Comput. Phys., 228 (2009), 2480-2516.doi: 10.1016/j.jcp.2008.12.003.
[5]	M. Bardi and I. Capuzzo Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, 1997.doi: 10.1007/978-0-8176-4755-1.
[6]	G. Barles, Solutions de Viscositè des Equations d'Hamilton-Jacobi, Springer-Verlag, 1998.
[7]	G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal., 4 (1991), 271-283.
[8]	F. Bauer, L. Grüne and W. Semmler, Adaptive spline interpolation for Hamilton-Jacobi-Bellman equations, Appl. Numer. Math., 56 (2006), 1196-1210.doi: 10.1016/j.apnum.2006.03.011.
[9]	O. Bokanowski, E. Cristiani and H. Zidani, An efficient data structure and accurate scheme to solve front propagation problems, J. Sci. Comput., 42 (2010), 251-273.doi: 10.1007/s10915-009-9329-6.
[10]	O. Bokanowski, J. Garcke, M. Griebel and I. Klompmaker, An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations, J. Sci. Comput., 55 (2013), 575-605.doi: 10.1007/s10915-012-9648-x.
[11]	O. Bokanowski, N. Megdich and H. Zidani, Convergence of a non-monotone scheme for Hamilton-Jacobi-Bellman equations with discontinuous initial data, Numer. Math., 115 (2010), 1-44.doi: 10.1007/s00211-009-0271-1.
[12]	O. Bokanowski and H. Zidani, Anti-dissipative schemes for advection and application to Hamilton-Jacobi-Bellmann equations, J. Sci. Comput., 30 (2007), 1-33.doi: 10.1007/s10915-005-9017-0.
[13]	S. Bryson, A. Kurganov, D. Levy and G. Petrova, Semi-discrete central-upwind schemes with reduced dissipation for Hamilton-Jacobi equations, IMA J. Numer. Anal., 25 (2005), 113-138.doi: 10.1093/imanum/drh015.
[14]	S. Bryson and D. Levy, High-order central WENO schemes for multidimensional Hamilton-Jacobi equations, SIAM J. Numer. Anal., 41 (2003), 1339-1369 (electronic).doi: 10.1137/S0036142902408404.
[15]	S. Bryson and D. Levy, Mapped WENO and weighted power ENO reconstructions in semi-discrete central schemes for Hamilton-Jacobi equations, Appl. Numer. Math., 56 (2006), 1211-1224.doi: 10.1016/j.apnum.2006.03.005.
[16]	F. Camilli, L. Grüne and F. Wirth, A generalization of Zubov's method to perturbed system, SIAM J. Control Optim., 40 (2001), 496-515.doi: 10.1137/S036301299936316X.
[17]	I. Capuzzo Dolcetta and H. Ishii, Approximate solutions of the Bellman equation of deterministic control theory, Appl. Math. Optim., 11 (1984), 161-181.doi: 10.1007/BF01442176.
[18]	E. Carlini, M. Falcone, and R. Ferretti., An efficient algorithm for Hamilton-Jacobi equations in high dimension, Comput. Vis. Sci., 7 (2004), 15-29.doi: 10.1007/s00791-004-0124-5.
[19]	E. Carlini, R. Ferretti and G. Russo, A weighted essentially nonoscillatory, large time-step scheme for Hamilton-Jacobi equations, SIAM J. Sci. Comput., 27 (2005), 1071-1091.doi: 10.1137/040608787.
[20]	F. Coquel and P. LeFloch, Convergence of finite difference schemes for conservation laws in several space dimensions: the corrected antidiffusive flux approach, Math. Comp., 57 (1991), 169-210.doi: 10.1090/S0025-5718-1991-1079010-2.
[21]	F. Coquel and P. LeFloch, Convergence of finite difference schemes for conservation laws in several space dimensions: A general theory, SIAM J. Numer. Anal., 30 (1993), 675-700.doi: 10.1137/0730033.
[22]	L. Corrias, M. Falcone and R. Natalini, Numerical schemes for conservation laws via Hamilton-Jacobi equations, Math. Comp., 64 (1995), 555-580, S13-S18.doi: 10.1090/S0025-5718-1995-1265013-5.
[23]	M. G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp., 43 (1984), 1-19.doi: 10.1090/S0025-5718-1984-0744921-8.
[24]	M. G. Crandall and L. Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc., 78 (1980), 385-390.doi: 10.1090/S0002-9939-1980-0553381-X.
[25]	M. Falcone, Numerical methods for differential games via PDEs, Int. Game Theor. Rev., 8 (2006), 231-272.doi: 10.1142/S0219198906000886.
[26]	M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numer. Math., 67 (1994), 315-344.doi: 10.1007/s002110050031.
[27]	M. Falcone and R. Ferretti, Semi-Lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and Godunov methods, J. Comp. Phys., 175 (2002), 559-575.doi: 10.1006/jcph.2001.6954.
[28]	M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, SIAM, Philadelphia, 2014.doi: 10.1137/1.9781611973051.
[29]	R. Ferretti, Convergence of semi-Lagrangian approximations to convex Hamilton-Jacobi equations under (very) large Courant numbers, SIAM J. Numer. Anal., 40 (2002), 2240-2253.doi: 10.1137/S0036142901388378.
[30]	B. D. Froese and A. M. Oberman, Convergent filtered schemes for the Monge-Ampère partial differential equation, SIAM J. Numer. Anal., 51 (2013), 423-444.doi: 10.1137/120875065.
[31]	E. Godlewski and P.-A. Raviart, Numerical Approximation of Hyperbolic Systems of Conservation Laws, volume 118 of Applied Mathematical Sciences, Springer-Verlag, New York, 1996.doi: 10.1007/978-1-4612-0713-9.
[32]	L. Grüne, An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation, Numer. Math., 75 (1997), 319-337.doi: 10.1007/s002110050241.
[33]	L. Grüne, M. Kato and W. Semmler, Solving ecological management problems using dynamic programming, J. Econ. Behav. Organ., 57 (2005), 448-473.doi: 10.1016/j.jebo.2005.04.002.
[34]	A. Harten, B. Engquist, S. Osher and S. R. Chakravarthy, Uniformly high order accurate essentially non-oscillatory schemes III, J. Comput. Phys., 71 (1987), 231-303.doi: 10.1016/0021-9991(87)90031-3.
[35]	A. Harten and S. Osher, Uniformly high-order accurate nonoscillatory schemes. I, SIAM J. Numer. Anal., 24 (1987), 279-309.doi: 10.1137/0724022.
[36]	A. Harten, S. Osher, B. Engquist and S. R. Chakravarthy, Some results on uniformly high-order accurate essentially nonoscillatory schemes, Appl. Numer. Math., 2 (1986), 347-377.doi: 10.1016/0168-9274(86)90039-5.
[37]	P. Hoch and O. Pironneau, A vector Hamilton-Jacobi formulation for the numerical simulation of Euler flows, C. R. Math. Acad. Sci. Paris, 342 (2006), 151-156.doi: 10.1016/j.crma.2005.11.007.
[38]	C. Hu and C.-W. Shu, A discontinuous Galerkin finite element method for Hamilton-Jacobi equations, SIAM J. Sci. Comput., 21 (1999), 666-690.doi: 10.1137/S1064827598337282.
[39]	G.-S. Jiang and C.-W. Shu, Efficient implementation of weighted ENO schemes, J. Comput. Phys., 126 (1996), 202-228.doi: 10.1006/jcph.1996.0130.
[40]	F. Li and C.-W. Shu, Reinterpretation and simplified implementation of a discontinuous Galerkin method for Hamilton-Jacobi equations, Appl. Math. Lett., 18 (2005), 1204-1209.doi: 10.1016/j.aml.2004.10.009.
[41]	P. Lions and P. Souganidis, Convergence of MUSCL and filtered schemes for scalar conservation laws and Hamilton-Jacobi equations, Num. Math., 69 (1995), 441-470.doi: 10.1007/s002110050102.
[42]	X.-D. Liu, S. Osher and T. Chan, Weighted essentially non-oscillatory schemes, J. Comput. Phys., 115 (1994), 200-212.doi: 10.1006/jcph.1994.1187.
[43]	S. Osher, Convergence of generalized MUSCL schemes, SIAM J. Numer. Anal., 22 (1985), 947-961.doi: 10.1137/0722057.
[44]	B. van Leer, Towards the ultimate conservative difference scheme. V. A second-order sequel to Godunov's method, J. Comput. Phys., 135 (1997), 227-248.doi: 10.1006/jcph.1997.5757.
[45]	Y.-T. Zhang and C.-W. Shu, High-order WENO schemes for Hamilton-Jacobi equations on triangular meshes, SIAM J. Sci. Comput., 24 (2002), 1005-1030.doi: 10.1137/S1064827501396798.