Abstract
We are interested in front propagation problems in the presence of obstacles. We extend a previous work (Bokanowski et al. SIAM J Sci Comput 33(2):923–938, 2011), to propose a simple and direct discontinuous Galerkin (DG) method adapted to such front propagation problems. We follow the formulation of Bokanowski et al. (SIAM J Control Optim 48(7):4292–4316, (2010)), leading to a level set formulation driven by \(\min (u_t + H(x,\nabla u), u-g(x))=0\), where \(g(x)\) is an obstacle function. The DG scheme is motivated by the variational formulation when the Hamiltonian \(H\) is a linear function of \(\nabla u\), corresponding to linear convection problems in the presence of obstacles. The scheme is then generalized to nonlinear equations, written in an explicit form. Stability analysis is performed for the linear case with Euler forward, a Heun scheme and a Runge-Kutta third order time discretization using the technique proposed in Zhang and Shu (SIAM J Numer Anal 48:1038–1063, 2010). Several numerical examples are provided to demonstrate the robustness of the method. Finally, a narrow band approach is considered in order to reduce the computational cost.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
More precisely, it is proved that the bound holds if the CFL condition \(\lambda \max (\mu ,\mu ^2) \frac{\tau }{h}\le 1\) is satisfied, where \(\lambda \ge 0\) is such that \(\lambda +\lambda ^3=\frac{1}{4}\). Since \(\lambda \simeq 0.2367 \le \frac{1}{4}\), it sufficient to have \(\frac{1}{4}\max (\mu ,\mu ^2) \frac{\tau }{h}\le 1\).
\(u(t,\mathbf x ):=u_0(R(-2 \pi a(\mathbf x )\ t )\ \mathbf{x })\) where \(R(\theta ):=\left( \begin{array}{rr} \cos (\theta ) &{} \!\! -\sin (\theta ) \\ \sin (\theta ) &{} \!\!\cos (\theta )\end{array}\right) \) and \(a(\mathbf x ):=\max (1-\Vert \mathbf x \Vert _2,0)\).
References
Achdou, Y., Pironneau, O.: Computational methods for option pricing. In: Frontiers in Applied Mathematics, SIAM, Philadelphia (2005)
Bardi, M., Capuzzo-Dolcetta, I.: Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations. In: Systems and Control: Foundations and Applications. Birkhäuser, Boston (1997)
Barron, E.N.: Viscosity solutions and analysis in \({L}^\infty \), pp. 1–60. Proceedings of the NATO advanced Study Institute, Cambridge 1999
Bensoussan, A., Lions, J.L.: Inéquations variationnelles non linéaires du premier et du second ordre. C. R. Acad. Sci. Paris 276(Série A), 1411–1415 (1973)
Bensoussan, A., Lions, J.L.: On the support of the solution of some variational inequalities of evolution. J. Math. Soc. Jpn. 28(1), 1–17 (1976)
Bokanowski, O., Cheng, Y., Shu, C.-W.: A discontinuous Galerkin solver for front propagation. SIAM J. Sci. Comput. 33(2), 923–938 (2011)
Bokanowski, O., Forcadel, N., Zidani, H.: Reachability and minimal times for state constrained nonlinear problems without any controllability assumption. SIAM J. Control Optim. 48(7), 4292–4316 (2010)
Bokanowski, O., Forcadel, N., Zidani, H.: Deterministic state constrained optimal control problems without controllability assumptions. COCV 17, 995–1015 (2011)
Bokanowski, O., Martin, S., Munos, R., Zidani, H.: An anti-diffusive scheme for viability problems. Appl. Numer. Math., 56(Issue 9, in Numerical Methods for Viscosity Solutions and Applications):1135–1254, (2006)
Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P.: Optimal times for constrained nonlinear control problems without local controllability. Appl. Math. Optim. 36, 21–42 (1997)
Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P.: Numerical schemes for discontinuous value function of optimal control. Set-Value Anal. 8, 111–126 (2000)
Cheng, Y., Shu, C.-W.: A discontinuous Galerkin finite element method for directly solving the Hamilton-Jacobi equations. J. Comput. Phys. 223, 398–415 (2007)
Cockburn, B., Shu, C.-W.: Runge-Kutta discontinuous Galerkin methods for convection-dominated problems. J. Sci. Comput. 16, 173–261 (2001)
Frankowska, H., Plaskacz, S.: Semicontinuous solutions of Hamilton-Jacobi-Bellman equations with degenerate state constraints. J. Math. Anal. Appl. 251(2), 818–838 (2000)
Hu, C., Shu, C.-W.: A discontinuous Galerkin finite element method for Hamilton-Jacobi equations. SIAM J. Sci. Comput. 21, 666–690 (1999)
Kurzhanski, A., Varayiya, P.: Ellipsoidal techniques for reachability under state constraints. SIAM J. Control Optim. 45, 1369–1394 (2006)
Li, F., Shu, C.-W.: Reinterpretation and simplified implementation of a discontinuous Galerkin method for Hamilton-Jacobi equations. Appl. Math. Lett. 18, 1204–1209 (2005)
Li, F., Yakovlev, S.: A central discontinuous Galerkin method for Hamilton-Jacobi equations. J. Sci. Comput. 45, 404–428 (2010)
Saint-Pierre, P.: Approximation of the viability kernel. Appl. Math. Optim. 29, 187–2009 (1994)
Soner, H.M.: Optimal control with state-space constraint II. SIAM J. Control Optim. 24(6), 1110–1122 (1986)
Yan, J., Osher, S.: A local discontinuous Galerkin method for directly solving Hamilton-Jacobi equations. J. Comput. Phys. 230, 232–244 (2011)
Zhang, Q., Shu, C.-W.: Stability analysis and a priori error estimates to the third order explicit runge-kutta discontinuous galerkin method for scalar conservation laws. SIAM J. Numer. Anal. 48, 1038–1063 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by the EU under the 7th Framework Programme Marie Curie Initial Training Network “FP7-PEOPLE-2010-ITN”, SADCO project, GA number 264735-SADCO.
Research supported by NSF grant DMS-1217563.
Research supported by ARO grants W911NF-08-1-0520 and W911NF-11-1-0091, and NSF grants DMS-0809086 and DMS-1112700.
Rights and permissions
About this article
Cite this article
Bokanowski, O., Cheng, Y. & Shu, CW. A discontinuous Galerkin scheme for front propagation with obstacles. Numer. Math. 126, 1–31 (2014). https://doi.org/10.1007/s00211-013-0555-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-013-0555-3