Fast weak–KAM integrators for separable Hamiltonian systems
HTML articles powered by AMS MathViewer
- by Anne Bouillard, Erwan Faou and Maxime Zavidovique PDF
- Math. Comp. 85 (2016), 85-117 Request permission
Abstract:
We consider a numerical scheme for Hamilton–Jacobi equations based on a direct discretization of the Lax–Oleinik semi–group. We prove that this method is convergent with respect to the time and space stepsizes provided the solution is Lipschitz, and give an error estimate. Moreover, we prove that the numerical scheme is a geometric integrator satisfying a discrete weak–KAM theorem which allows us to control its long time behavior. Taking advantage of a fast algorithm for computing (min,plus) convolutions based on the decomposition of the function into concave and convex parts, we show that the numerical scheme can be implemented in a very efficient way.References
- R. Abgrall, Numerical discretization of the first-order Hamilton-Jacobi equation on triangular meshes, Comm. Pure Appl. Math. 49 (1996), no. 12, 1339–1373. MR 1414589, DOI 10.1002/(SICI)1097-0312(199612)49:12<1339::AID-CPA5>3.0.CO;2-B
- Marianne Akian, Stéphane Gaubert, and Asma Lakhoua, The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis, SIAM J. Control Optim. 47 (2008), no. 2, 817–848. MR 2385864, DOI 10.1137/060655286
- Patrick Bernard and Boris Buffoni, Weak KAM pairs and Monge-Kantorovich duality, Asymptotic analysis and singularities—elliptic and parabolic PDEs and related problems, Adv. Stud. Pure Math., vol. 47, Math. Soc. Japan, Tokyo, 2007, pp. 397–420. MR 2387248, DOI 10.2969/aspm/04720397
- François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. MR 1204266
- Guy Barles and Espen R. Jakobsen, Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations, SIAM J. Numer. Anal. 43 (2005), no. 2, 540–558. MR 2177879, DOI 10.1137/S003614290343815X
- A. Bouillard, L. Jouhet, and E. Thierry, Computation of a (min,+) multi-dimensional convolution for end-to-end performance analysis. In Proceedings of Valuetools’2008, 2008.
- Patrick Bernard and Jean-Michel Roquejoffre, Convergence to time-periodic solutions in time-periodic Hamilton-Jacobi equations on the circle, Comm. Partial Differential Equations 29 (2004), no. 3-4, 457–469 (English, with English and French summaries). MR 2041603, DOI 10.1081/PDE-120030404
- Yann Brenier, Un algorithme rapide pour le calcul de transformées de Legendre-Fenchel discrètes, C. R. Acad. Sci. Paris Sér. I Math. 308 (1989), no. 20, 587–589 (French, with English summary). MR 1001813
- G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal. 4 (1991), no. 3, 271–283. MR 1115933
- Anne Bouillard and Éric Thierry, An algorithmic toolbox for network calculus, Discrete Event Dyn. Syst. 18 (2008), no. 1, 3–49. MR 2388919, DOI 10.1007/s10626-007-0028-x
- G. Contreras, R. Iturriaga, and H. Sanchez-Morgado, Weak solutions of the Hamilton-Jacobi equation for time periodic Lagrangians, preprint, 2000.
- M. G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp. 43 (1984), no. 167, 1–19. MR 744921, DOI 10.1090/S0025-5718-1984-0744921-8
- M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory, Appl. Math. Optim. 15 (1987), no. 1, 1–13. MR 866164, DOI 10.1007/BF01442644
- Albert Fathi, Théorème KAM faible et théorie de Mather sur les systèmes lagrangiens, C. R. Acad. Sci. Paris Sér. I Math. 324 (1997), no. 9, 1043–1046 (French, with English and French summaries). MR 1451248, DOI 10.1016/S0764-4442(97)87883-4
- Albert Fathi, Sur la convergence du semi-groupe de Lax-Oleinik, C. R. Acad. Sci. Paris Sér. I Math. 327 (1998), no. 3, 267–270 (French, with English and French summaries). MR 1650261, DOI 10.1016/S0764-4442(98)80144-4
- A. Fathi, Weak KAM Theorem in Lagrangian Dynamics, preliminary version, Pisa, 16 février 2005.
- M. Falcone and R. Ferretti, Semi-Lagrangian schemes for Hamilton-Jacobi equations, discrete representation formulae and Godunov methods, J. Comput. Phys. 175 (2002), no. 2, 559–575. MR 1880118, DOI 10.1006/jcph.2001.6954
- Albert Fathi and Ezequiel Maderna, Weak KAM theorem on non compact manifolds, NoDEA Nonlinear Differential Equations Appl. 14 (2007), no. 1-2, 1–27. MR 2346451, DOI 10.1007/s00030-007-2047-6
- Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration, 2nd ed., Springer Series in Computational Mathematics, vol. 31, Springer-Verlag, Berlin, 2006. Structure-preserving algorithms for ordinary differential equations. MR 2221614
- Renato Iturriaga, Minimizing measures for time-dependent Lagrangians, Proc. London Math. Soc. (3) 73 (1996), no. 1, 216–240. MR 1387088, DOI 10.1112/plms/s3-73.1.216
- Espen Robstad Jakobsen, Kenneth Hvistendahl Karlsen, and Nils Henrik Risebro, On the convergence rate of operator splitting for Hamilton-Jacobi equations with source terms, SIAM J. Numer. Anal. 39 (2001), no. 2, 499–518. MR 1860266, DOI 10.1137/S003614290036823X
- Guang-Shan Jiang and Danping Peng, Weighted ENO schemes for Hamilton-Jacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 2126–2143. MR 1762034, DOI 10.1137/S106482759732455X
- Guang-Shan Jiang and Chi-Wang Shu, Efficient implementation of weighted ENO schemes, J. Comput. Phys. 126 (1996), no. 1, 202–228. MR 1391627, DOI 10.1006/jcph.1996.0130
- Shi Jin and Zhouping Xin, Numerical passage from systems of conservation laws to Hamilton-Jacobi equations, relaxation schemes, SIAM J. Numer. Anal. 35 (1998), no. 6, 2385–2404. MR 1655852, DOI 10.1137/S0036142996314366
- Jean-Yves Le Boudec and Patrick Thiran, Network calculus, Lecture Notes in Computer Science, vol. 2050, Springer-Verlag, Berlin, 2001. A theory of deterministic queuing systems for the internet. MR 1932706, DOI 10.1007/3-540-45318-0
- Pierre-Louis Lions, Generalized solutions of Hamilton-Jacobi equations, Research Notes in Mathematics, vol. 69, Pitman (Advanced Publishing Program), Boston, Mass.-London, 1982. MR 667669
- P.-L. Lions, G. Papanicolaou, and S.R.S. Varadhan, Homogenization of Hamilton-Jacobi equation, unpublished preprint, 1987.
- Benedict Leimkuhler and Sebastian Reich, Simulating Hamiltonian dynamics, Cambridge Monographs on Applied and Computational Mathematics, vol. 14, Cambridge University Press, Cambridge, 2004. MR 2132573
- P.-L. Lions and P. E. Souganidis, Convergence of MUSCL and filtered schemes for scalar conservation laws and Hamilton-Jacobi equations, Numer. Math. 69 (1995), no. 4, 441–470. MR 1314597, DOI 10.1007/s002110050102
- Chi-Tien Lin and Eitan Tadmor, $L^1$-stability and error estimates for approximate Hamilton-Jacobi solutions, Numer. Math. 87 (2001), no. 4, 701–735. MR 1815732, DOI 10.1007/PL00005430
- Yves Lucet, Faster than the fast Legendre transform, the linear-time Legendre transform, Numer. Algorithms 16 (1997), no. 2, 171–185 (1998). MR 1619184, DOI 10.1023/A:1019191114493
- John N. Mather, Action minimizing invariant measures for positive definite Lagrangian systems, Math. Z. 207 (1991), no. 2, 169–207. MR 1109661, DOI 10.1007/BF02571383
- Stanley Osher and James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79 (1988), no. 1, 12–49. MR 965860, DOI 10.1016/0021-9991(88)90002-2
- Stanley Osher and Chi-Wang Shu, High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations, SIAM J. Numer. Anal. 28 (1991), no. 4, 907–922. MR 1111446, DOI 10.1137/0728049
- M. Rorro, An approximation scheme for the effective Hamiltonian and applications, Appl. Numer. Math. 56 (2006), no. 9, 1238–1254. MR 2244974, DOI 10.1016/j.apnum.2006.03.006
- Kohei Soga, Stochastic and variational approach to the Lax-Friedrichs scheme, Math. Comp. 84 (2015), no. 292, 629–651. MR 3290958, DOI 10.1090/S0025-5718-2014-02863-9
- Panagiotis E. Souganidis, Approximation schemes for viscosity solutions of Hamilton-Jacobi equations, J. Differential Equations 59 (1985), no. 1, 1–43. MR 803085, DOI 10.1016/0022-0396(85)90136-6
- Maxime Zavidovique, Strict sub-solutions and Mañé potential in discrete weak KAM theory, Comment. Math. Helv. 87 (2012), no. 1, 1–39. MR 2874895, DOI 10.4171/CMH/247
Additional Information
- Anne Bouillard
- Affiliation: Ecole Normale Supérieure, 45 rue d’Ulm, 75230 Paris Cedex 05, France.
- Email: anne.bouillard@ens.fr
- Erwan Faou
- Affiliation: INRIA & Ecole Normale Supérieure de Cachan Bretagne, Avenue Robert Schumann 35170 Bruz, France
- MR Author ID: 656335
- Email: Erwan.Faou@inria.fr
- Maxime Zavidovique
- Affiliation: IMJ-PRG, Université Pierre et Marie Curie, Case 247 4, place Jussieu, 75252 Paris Cedex 05, France
- Email: Maxime.Zavidovique@upmc.fr
- Received by editor(s): October 15, 2012
- Received by editor(s) in revised form: December 5, 2013, and May 13, 2014
- Published electronically: May 26, 2015
- Additional Notes: The second author was supported by the ERC starting grant GEOPARDI
The third author was supported by ANR-12-BLAN-WKBHJ - © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 85-117
- MSC (2010): Primary 35F21, 65M12, 06F05
- DOI: https://doi.org/10.1090/mcom/2976
- MathSciNet review: 3404444