A level set approach for computing discontinuous solutions of Hamilton-Jacobi equations

Tsai, Yen-Hsi; Giga, Yoshikazu; Osher, Stanley

doi:10.1090/S0025-5718-02-01438-2

A level set approach for computing discontinuous solutions of Hamilton-Jacobi equations
HTML articles powered by AMS MathViewer

by Yen-Hsi Richard Tsai, Yoshikazu Giga and Stanley Osher PDF

Math. Comp. 72 (2003), 159-181 Request permission

Abstract:

We introduce two types of finite difference methods to compute the L-solution and the proper viscosity solution recently proposed by the second author for semi-discontinuous solutions to a class of Hamilton-Jacobi equations. By regarding the graph of the solution as the zero level curve of a continuous function in one dimension higher, we can treat the corresponding level set equation using the viscosity theory introduced by Crandall and Lions. However, we need to pay special attention both analytically and numerically to prevent the zero level curve from overturning so that it can be interpreted as the graph of a function. We demonstrate our Lax-Friedrichs type numerical methods for computing the L-solution using its original level set formulation. In addition, we couple our numerical methods with a singular diffusive term which is essential to computing solutions to a more general class of HJ equations that includes conservation laws. With this singular viscosity, our numerical methods do not require the divergence structure of equations and do apply to more general equations developing shocks other than conservation laws. These numerical methods are generalized to higher order accuracy using weighted ENO local Lax-Friedrichs methods as developed recently by Jiang and Peng. We verify that our numerical solutions approximate the proper viscosity solutions obtained by the second author in a recent Hokkaido University preprint. Finally, since the solution of scalar conservation law equations can be constructed using existing numerical techniques, we use it to verify that our numerical solution approximates the entropy solution.

References

Rahul Pandharipande, Equivariant Chow rings of $\textrm {O}(k),\ \textrm {SO}(2k+1)$, and $\textrm {SO}(4)$, J. Reine Angew. Math. 496 (1998), 131–148. MR 1605814, DOI 10.1515/crll.1998.025
Guy Barles, Discontinuous viscosity solutions of first-order Hamilton-Jacobi equations: a guided visit, Nonlinear Anal. 20 (1993), no. 9, 1123–1134. MR 1216503, DOI 10.1016/0362-546X(93)90098-D
Guy Barles, Solutions de viscosité des équations de Hamilton-Jacobi, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 17, Springer-Verlag, Paris, 1994 (French, with French summary). MR 1613876
Olivier Guès, Ondes oscillantes simples quasilinéaires, Journées “Équations aux Dérivées Partielles” (Saint Jean de Monts, 1989) École Polytech., Palaiseau, 1989, pp. Exp. No. IX, 8 (French). MR 1030824
Charles Hopkins, An extension of a theorem of Remak, Ann. of Math. (2) 40 (1939), 636–638. MR 33, DOI 10.2307/1968948
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
Michael G. Crandall and Pierre-Louis Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc. 277 (1983), no. 1, 1–42. MR 690039, DOI 10.1090/S0002-9947-1983-0690039-8
Lawrence C. Evans, A geometric interpretation of the heat equation with multivalued initial data, SIAM J. Math. Anal. 27 (1996), no. 4, 932–958. MR 1393417, DOI 10.1137/S0036141094275439
Mi-Ho Giga and Yoshikazu Giga, Crystalline and level set flow—convergence of a crystalline algorithm for a general anisotropic curvature flow in the plane, Free boundary problems: theory and applications, I (Chiba, 1999) GAKUTO Internat. Ser. Math. Sci. Appl., vol. 13, Gakk\B{o}tosho, Tokyo, 2000, pp. 64–79. MR 1793023
Mi-Ho Giga, Yoshikazu Giga, and Ryo Kobayashi, Very singular diffusion equations, Advanced Studies in Pure Mathematics 31, 2001, pp. 93–125.
Y. Giga, S. Goto, H. Ishii, and M.-H. Sato, Comparison principle and convexity preserving properties for singular degenerate parabolic equations on unbounded domains, Indiana Univ. Math. J. 40 (1991), no. 2, 443–470. MR 1119185, DOI 10.1512/iumj.1991.40.40023
Yoshikazu Giga, Shocks and very strong vertical diffusion, To appear, Proc. of international conference on partial differential equations in celebration of the seventy fifth birthday of Professor Louis Nirenberg, Taiwan, 2001.
—, Viscosity solutions with shocks, Hokkaido Univ. Preprint Series in Math. (2001), no. 519.
Yoshikazu Giga and Moto-Hiko Sato, A level set approach to semicontinuous viscosity solutions for Cauchy problems, Comm. Partial Differential Equations 26 (2001), no. 5-6, 813–839.
Ami Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), no. 3, 357–393. MR 701178, DOI 10.1016/0021-9991(83)90136-5
Ami Harten, Björn Engquist, Stanley Osher, and Sukumar R. Chakravarthy, Uniformly high-order accurate essentially nonoscillatory schemes. III, J. Comput. Phys. 71 (1987), no. 2, 231–303. MR 897244, DOI 10.1016/0021-9991(87)90031-3
J. Helmsen, E. Puckett, P. Colella, and M. Dorr, Two new methods for simulating photolithography development in 3d, SPIE 2726, 1996, pp. 253–261.
Hitoshi Ishii, Hamilton-Jacobi equations with discontinuous Hamiltonians on arbitrary open sets, Bull. Fac. Sci. Engrg. Chuo Univ. 28 (1985), 33–77. MR 845397
Hitoshi Ishii, Existence and uniqueness of solutions of Hamilton-Jacobi equations, Funkcial. Ekvac. 29 (1986), no. 2, 167–188. MR 877427
Hitoshi Ishii, Perron’s method for Hamilton-Jacobi equations, Duke Math. J. 55 (1987), no. 2, 369–384. MR 894587, DOI 10.1215/S0012-7094-87-05521-9
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
J. Łuczka, Application of statistical mechanics to stochastic transport, Phys. A 274 (1999), no. 1-2, 200–215. Applications of statistical physics (Budapest, 1999). MR 1739838, DOI 10.1016/S0378-4371(99)00314-3
Peter D. Lax, Hyperbolic systems of conservation laws and the mathematical theory of shock waves, Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 11, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1973. MR 0350216
Chi-Tien Lin and Eitan Tadmor, High-resolution nonoscillatory central schemes for Hamilton-Jacobi equations, SIAM J. Sci. Comput. 21 (2000), no. 6, 2163–2186. MR 1762036, DOI 10.1137/S1064827598344856
Stanley Osher, A level set formulation for the solution of the Dirichlet problem for Hamilton-Jacobi equations, SIAM J. Math. Anal. 24 (1993), no. 5, 1145–1152. MR 1234009, DOI 10.1137/0524066
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
Danping Peng, Barry Merriman, Stanley Osher, Hongkai Zhao, and Myungjoo Kang, A PDE-based fast local level set method, J. Comput. Phys. 155 (1999), no. 2, 410–438. MR 1723321, DOI 10.1006/jcph.1999.6345
J.A. Sethian, Fast marching level set methods for three dimensional photolithography development, SPIE 2726, 1996, pp. 261–272.
Chi-Wang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shock-capturing schemes. II, J. Comput. Phys. 83 (1989), no. 1, 32–78. MR 1010162, DOI 10.1016/0021-9991(89)90222-2
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
Yen-Hsi Richard Tsai, Rapid and accurate computation of the distance function using grids, UCLA CAM Report 00 (2000), no. 36.
John N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Automat. Control 40 (1995), no. 9, 1528–1538. MR 1347833, DOI 10.1109/9.412624
S. T. Venkataraman and T. Iberall (eds.), Dextrous robot hands, Springer-Verlag, New York, 1990. MR 1036056, DOI 10.1007/978-1-4613-8974-3