Approximation of solutions of Hamilton-Jacobi equations on the Heisenberg group

Achdou, Yves; Capuzzo-Dolcetta, Italo

ESAIM: Modélisation mathématique et analyse numérique, Tome 42 (2008) no. 4, pp. 565-591.

We propose and analyze numerical schemes for viscosity solutions of time-dependent Hamilton-Jacobi equations on the Heisenberg group. The main idea is to construct a grid compatible with the noncommutative group geometry. Under suitable assumptions on the data, the hamiltonian and the parameters for the discrete first order scheme, we prove that the error between the viscosity solution computed at the grid nodes and the solution of the discrete problem behaves like $\sqrt{h}$ where $h$ is the mesh step. Such an estimate is similar to those available in the euclidean geometrical setting. The theoretical results are tested numerically on some examples for which semi-analytical formulas for the computation of geodesics are known. Other simulations are presented, for both steady and unsteady problems.

[1] Y. Achdou and N. Tchou, A finite difference scheme on a non commutative group. Numer. Math. 89 (2001) 401-424. | MR | Zbl

[2] M. Bardi, A boundary value problem for the minimum-time function. SIAM J. Control Optim. 27 (1989) 776-785. | MR | Zbl

[3] M. Bardi and I. Capuzzo-Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Systems & Control: Foundations & Applications. Birkhäuser Boston Inc., Boston, MA (1997). With appendices by M. Falcone and P. Soravia. | MR | Zbl

[4] G. Barles and E.R. Jakobsen, Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations. SIAM J. Numer. Anal. 43 (2005) 540-558 (electronic). | MR | Zbl

[5] R. Beals, B. Gaveau and P.C. Greiner, Hamilton-Jacobi theory and the heat kernel on Heisenberg groups. J. Math. Pures Appl. 79 (2000) 633-689. | MR | Zbl

[6] A. Bellaïche and J.-J. Risler, Eds., Sub-Riemannian Geometry, Progress in Mathematics 144. Birkhäuser Verlag, Basel (1996). | MR

[7] I. Birindelli and J. Wigniolle, Homogenization of Hamilton-Jacobi equations in the Heisenberg group. Commun. Pure Appl. Anal. 2 (2003) 461-479. | MR | Zbl

[8] R.W. Brockett, Control theory and singular Riemannian geometry, in New directions in applied mathematics (Cleveland, Ohio, 1980), Springer, New York (1982) 11-27. | MR | Zbl

[9] I. Capuzzo Dolcetta, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming. Appl. Math. Optim. 10 (1983) 367-377. | MR | Zbl

[10] I. Capuzzo Dolcetta, The Hopf-Lax solution for state dependent Hamilton-Jacobi equations (Viscosity solutions of differential equations and related topics) (Japanese). Sūrikaisekikenkyūsho Kōkyūroku 1287 (2002) 143-154. | MR

[11] I. Capuzzo Dolcetta, The Hopf solution of Hamilton-Jacobi equations, in Elliptic and parabolic problems (Rolduc/Gaeta, 2001), World Sci. Publishing, River Edge, NJ (2002) 343-351. | MR | Zbl

[12] I. Capuzzo Dolcetta, A generalized Hopf-Lax formula: analytical and approximations aspects, in Geometric Control and Nonsmooth Analysis, F. Ancona, A. Bressan, P. Cannarsa, F. Clarkeă and P.R. Wolenski Eds., Series on Advances in Mathematics for Applied Sciences 76, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ (2008). | MR

[13] I. Capuzzo Dolcetta and H. Ishii, Approximate solutions of the Bellman equation of deterministic control theory. Appl. Math. Optim. 11 (1984) 161-181. | MR | Zbl

[14] M.G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations. Math. Comp. 43 (1984) 1-19. | MR | Zbl

[15] A. Cutrí and F. Da Lio, Comparison and existence results for evolutive non-coercive first-order Hamilton-Jacobi equations. ESAIM: COCV 13 (2007) 484-502. | Numdam | MR | Zbl

[16] B. Engquist and S. Osher, One-sided difference approximations for nonlinear conservation laws. Math. Comp. 36 (1981) 321-351. | MR | Zbl

[17] M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory. Appl. Math. Optim. 15 (1987) 1-13. | MR | Zbl

[18] M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations. Numer. Math. 67 (1994) 315-344. | MR | Zbl

[19] S. Gottlieb, C.-W. Shu and E. Tadmor, Strong stability-preserving high-order time discretization methods. SIAM Rev. 43 (2001) 89-112 (electronic). | MR | Zbl

[20] A. Harten, B. Engquist, S. Osher and S.R. Chakravarthy, Uniformly high-order accurate essentially nonoscillatory schemes. III. J. Comput. Phys. 71 (1987) 231-303. | MR | Zbl

[21] A. Korányi and H.M. Reimann, Quasiconformal mappings on the Heisenberg group. Invent. Math. 80 (1985) 309-338. | MR | Zbl

[22] N.V. Krylov, On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients. Probab. Theory Relat. Fields 117 (2000) 1-16. | MR | Zbl

[23] N.V. Krylov, The rate of convergence of finite-difference approximations for Bellman equations with Lipschitz coefficients. Appl. Math. Optim. 52 (2005) 365-399. | MR | Zbl

[24] J.J. Manfredi and B. Stroffolini, A version of the Hopf-Lax formula in the Heisenberg group. Comm. Partial Diff. Eq. 27 (2002) 1139-1159. | MR | Zbl

[25] S. Osher and J.A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79 (1988) 12-49. | MR | Zbl

[26] S. Osher and C.-W. Shu, High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J. Numer. Anal. 28 (1991) 907-922. | MR | Zbl

[27] J.A. Sethian, Level set methods and fast marching methods, Evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science, Cambridge Monographs on Applied and Computational Mathematics 3. Cambridge University Press, Cambridge, 2nd edition (1999). | MR | Zbl