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

Authors:
Yen-Hsi Richard Tsai, Yoshikazu Giga and Stanley Osher

Journal:
Math. Comp. **72** (2003), 159-181

MSC (2000):
Primary 65Mxx, 35Lxx; Secondary 70H20

Published electronically:
August 13, 2002

MathSciNet review:
1933817

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**1.**Rahul Pandharipande,*Equivariant Chow rings of 𝑂(𝑘),𝑆𝑂(2𝑘+1), and 𝑆𝑂(4)*, J. Reine Angew. Math.**496**(1998), 131–148. MR**1605814**, 10.1515/crll.1998.025**2.**Guy Barles,*Discontinuous viscosity solutions of first-order Hamilton-Jacobi equations: a guided visit*, Nonlinear Anal.**20**(1993), no. 9, 1123–1134. MR**1216503**, 10.1016/0362-546X(93)90098-D**3.**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****4.**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****5.**C. Carathéodory,*Calculus of variations and partial differential equations of the first order. Part I: Partial differential equations of the first order*, Translated by Robert B. Dean and Julius J. Brandstatter, Holden-Day, Inc., San Francisco-London-Amsterdam, 1965. MR**0192372**

C. Carathéodory,*Calculus of variations and partial differential equations of the first order. Part II: Calculus of variations*, Translated from the German by Robert B. Dean, Julius J. Brandstatter, translating editor, Holden-Day, Inc., San Francisco, Calif.-London-Amsterdam, 1967. MR**0232264****6.**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**, 10.1090/S0025-5718-1984-0744921-8**7.**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**, 10.1090/S0002-9947-1983-0690039-8**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**, 10.1137/S0036141094275439**9.**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ōtosho, Tokyo, 2000, pp. 64–79. MR**1793023****10.**Mi-Ho Giga, Yoshikazu Giga, and Ryo Kobayashi,*Very singular diffusion equations*, Advanced Studies in Pure Mathematics 31, 2001, pp. 93-125.**11.**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**, 10.1512/iumj.1991.40.40023**12.**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.**13.**-,*Viscosity solutions with shocks*, Hokkaido Univ. Preprint Series in Math. (2001), no. 519.**14.**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.**15.**Ami Harten,*High resolution schemes for hyperbolic conservation laws*, J. Comput. Phys.**49**(1983), no. 3, 357–393. MR**701178**, 10.1016/0021-9991(83)90136-5**16.**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**, 10.1016/0021-9991(87)90031-3**17.**J. Helmsen, E. Puckett, P. Colella, and M. Dorr,*Two new methods for simulating photolithography development in 3d*, SPIE 2726, 1996, pp. 253-261.**18.**Hitoshi Ishii,*Hamilton-Jacobi equations with discontinuous Hamiltonians on arbitrary open sets*, Bull. Fac. Sci. Engrg. Chuo Univ.**28**(1985), 33–77. MR**845397****19.**Hitoshi Ishii,*Existence and uniqueness of solutions of Hamilton-Jacobi equations*, Funkcial. Ekvac.**29**(1986), no. 2, 167–188. MR**877427****20.**Hitoshi Ishii,*Perron’s method for Hamilton-Jacobi equations*, Duke Math. J.**55**(1987), no. 2, 369–384. MR**894587**, 10.1215/S0012-7094-87-05521-9**21.**Guang-Shan Jiang and Danping Peng,*Weighted ENO schemes for Hamilton-Jacobi equations*, SIAM J. Sci. Comput.**21**(2000), no. 6, 2126–2143 (electronic). MR**1762034**, 10.1137/S106482759732455X**22.**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**, 10.1016/S0378-4371(99)00314-3**23.**Peter D. Lax,*Hyperbolic systems of conservation laws and the mathematical theory of shock waves*, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1973. Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 11. MR**0350216****24.**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 (electronic). MR**1762036**, 10.1137/S1064827598344856**25.**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**, 10.1137/0524066**26.**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**, 10.1016/0021-9991(88)90002-2**27.**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**, 10.1137/0728049**28.**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**, 10.1006/jcph.1999.6345**29.**J.A. Sethian,*Fast marching level set methods for three dimensional photolithography development*, SPIE 2726, 1996, pp. 261-272.**30.**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**, 10.1016/0021-9991(89)90222-2**31.**Panagiotis E. Souganidis,*Approximation schemes for viscosity solutions of Hamilton-Jacobi equations*, J. Differential Equations**59**(1985), no. 1, 1–43. MR**803085**, 10.1016/0022-0396(85)90136-6**32.**Yen-Hsi Richard Tsai,*Rapid and accurate computation of the distance function using grids*, UCLA CAM Report**00**(2000), no. 36.**33.**John N. Tsitsiklis,*Efficient algorithms for globally optimal trajectories*, IEEE Trans. Automat. Control**40**(1995), no. 9, 1528–1538. MR**1347833**, 10.1109/9.412624**34.**S. T. Venkataraman and T. Iberall (eds.),*Dextrous robot hands*, Springer-Verlag, New York, 1990. MR**1036056**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65Mxx,
35Lxx,
70H20

Retrieve articles in all journals with MSC (2000): 65Mxx, 35Lxx, 70H20

Additional Information

**Yen-Hsi Richard Tsai**

Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095

Email:
ytsai@math.ucla.edu

**Yoshikazu Giga**

Affiliation:
Department of Mathematics, Hokkaido University, Sapporo 060-0810, Japan

Email:
giga@math.sci.hokudai.ac.jp

**Stanley Osher**

Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095

Email:
sjo@math.ucla.edu

DOI:
http://dx.doi.org/10.1090/S0025-5718-02-01438-2

Keywords:
Hamilton-Jacobi equations,
singular diffusion,
level sets

Received by editor(s):
March 7, 2001

Published electronically:
August 13, 2002

Additional Notes:
The first and the third authors are supported by ONR N00014-97-1-0027, DARPA/NSF VIP grant NSF DMS 9615854 and ARO DAAG 55-98-1-0323.

Article copyright:
© Copyright 2002
American Mathematical Society