Fast weak–KAM integrators for separable Hamiltonian systems

Bouillard, Anne; Faou, Erwan; Zavidovique, Maxime

doi:10.1090/mcom/2976

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