Abstract
In this paper, we propose a monotone mixed finite difference scheme for solving the two-dimensional Monge–Ampère equation. In order to accomplish this, we convert the Monge–Ampère equation to an equivalent Hamilton–Jacobi–Bellman (HJB) equation. Based on the HJB formulation, we apply the standard 7-point stencil discretization, which is second order accurate, to the grid points wherever monotonicity holds, and apply semi-Lagrangian wide stencil discretization elsewhere to ensure monotonicity on the entire computational domain. By dividing the admissible control set into six regions and optimizing the sub-problem in each region, the computational cost of the optimization problem at each grid point is reduced from \(O(M^2)\) to O(1) when the standard 7-point stencil discretization is applied and to O(M) otherwise, where the discretized control set is \(M\times M\). We prove that our numerical scheme satisfies consistency, stability, monotonicity and strong comparison principle, and hence is convergent to the viscosity solution of the Monge–Ampère equation. In the numerical results, second order convergence rate is achieved when the standard 7-point stencil discretization is applied monotonically on the entire computation domain, and up to order one convergence is achieved otherwise. The proposed mixed scheme yields a smaller discretization error and a faster convergence rate compared to the pure semi-Lagrangian wide stencil scheme.
Similar content being viewed by others
Notes
Although (6) defines the admissible control set to be in the range of \([0,1]\times [-\,\pi ,\pi )\), the optimal control pair \((a^*,\theta ^*)\) that maximizes (7) may not be unique in \([0,1]\times [-\,\pi ,\pi )\). We notice that since \(\mathcal {L}_{a,\theta } \, u = \mathcal {L}_{a,\theta +\pi } \, u\), and \(\mathcal {L}_{a,\theta } \, u = \mathcal {L}_{1-a,\theta +\frac{\pi }{2}} \, u\), the admissible control set \(\varGamma \) can be reduced to \([0,1]\times [-\,\frac{\pi }{4},\frac{\pi }{4})\). Such removal of the redundancy of \(\varGamma \) ensures that the optimal control pair \((a^*,\theta ^*)\) is unique in \(\varGamma \), except when \(a^*=\frac{1}{2}\) or when \(f=0\).
It is unnecessary to consider the line \(a_{i,j}=\frac{1}{2}\), since the objective function is a constant on this line. Also it is unnecessary to consider the line \(\theta _{i,j} = \pm \frac{\pi }{4}\), since \(\mathcal {L}_{a,\theta } \, u = \mathcal {L}_{1-a,\theta +\frac{\pi }{2}} \, u\) indicates that \(\theta _{i,j} = \pm \frac{\pi }{4}\) is indeed an interior part of \(\varGamma _{i,j}^1\) and \(\varGamma _{i,j}^2\).
References
Azimzadeh, P., Forsyth, P.A.: Weakly chained matrices, policy iteration, and impulse control. SIAM J. Numer. Anal. 54(3), 1341–1364 (2016). https://doi.org/10.1137/15M1043431
Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4(3), 271–283 (1991)
Benamou, J.D., Collino, F., Mirebeau, J.M.: Monotone and consistent discretization of the Monge–Ampère operator. Math. Comput. 85(302), 2743–2775 (2016). https://doi.org/10.1090/mcom/3080
Benamou, J.D., Froese, B.D., Oberman, A.M.: Two numerical methods for the elliptic Monge–Ampère equation. M2AN. Math. Model. Numer. Anal. 44(4), 737–758 (2010). https://doi.org/10.1051/m2an/2010017
Böhmer, K.: On finite element methods for fully nonlinear elliptic equations of second order. SIAM J. Numer. Anal. 46(3), 1212–1249 (2008). https://doi.org/10.1137/040621740
Bokanowski, O., Maroso, S., Zidani, H.: Some convergence results for Howard’s algorithm. SIAM J. Numer. Anal. 47(4), 3001–3026 (2009). https://doi.org/10.1137/08073041X
Brenner, S.C., Gudi, T., Neilan, M., Sung, Ly: \(C^0\) penalty methods for the fully nonlinear Monge–Ampère equation. Math. Comput. 80(276), 1979–1995 (2011). https://doi.org/10.1090/S0025-5718-2011-02487-7
Caffarelli, L.A., Milman, M. (eds.): Monge–Ampère equation: applications to geometry and optimization, Contemporary Mathematics, vol. 226. American Mathematical Society, Providence (1999). https://doi.org/10.1090/conm/226
Ciarlet, P.G.: Discrete maximum principle for finite-difference operators. Aequ. Math. 4, 338–352 (1970)
Crandall, M.G., Ishii, H., Lions, P.L.: User’s guide to viscosity solutions of second order partial differential equations. Bull. Am. Math. Soc. (N.S.) 27(1), 1–67 (1992). https://doi.org/10.1090/S0273-0979-1992-00266-5
Crandall, M.G., Lions, P.L.: Viscosity solutions of Hamilton–Jacobi equations. Trans. Am. Math. Soc. 277(1), 1–42 (1983). https://doi.org/10.2307/1999343
Dean, E.J., Glowinski, R.: Numerical methods for fully nonlinear elliptic equations of the Monge–Ampère type. Comput. Methods Appl. Mech. Eng. 195(13–16), 1344–1386 (2006). https://doi.org/10.1016/j.cma.2005.05.023
Debrabant, K., Jakobsen, E.R.: Semi-Lagrangian schemes for linear and fully non-linear diffusion equations. Math. Comput. 82(283), 1433–1462 (2013). https://doi.org/10.1090/S0025-5718-2012-02632-9
Feng, X., Jensen, M.: Convergent semi-Lagrangian methods for the Monge–Ampère equation on unstructured grids. SIAM J. Numer. Anal. 55(2), 691–712 (2017)
Feng, X., Neilan, M.: Vanishing moment method and moment solutions for fully nonlinear second order partial differential equations. J. Sci. Comput. 38(1), 74–98 (2009). https://doi.org/10.1007/s10915-008-9221-9
Forsyth, P.A., Labahn, G.: Numerical methods for controlled Hamilton–Jacobi–Bellman PDEs in finance. J. Comput. Finance 11(2), 1 (2007)
Froese, B.D., Oberman, A.M.: Convergent finite difference solvers for viscosity solutions of the elliptic Monge–Ampère equation in dimensions two and higher. SIAM J. Numer. Anal. 49(4), 1692–1714 (2011). https://doi.org/10.1137/100803092
Froese, B.D., Oberman, A.M.: Fast finite difference solvers for singular solutions of the elliptic Monge–Ampère equation. J. Comput. Phys. 230(3), 818–834 (2011). https://doi.org/10.1016/j.jcp.2010.020
Froese, B.D., Oberman, A.M.: Convergent filtered schemes for the Monge–Ampère partial differential equation. SIAM J. Numer. Anal. 51(1), 423–444 (2013). https://doi.org/10.1137/120875065
Gutiérrez, C.E.: The Monge–Ampère Equation, vol. 42. Springer, Berlin (2012)
Howard, R.A.: Dynamic Programming and Markov Processes. The Technology Press of M.I.T, Cambridge (1960)
Krylov, N.V.: The control of the solution of a stochastic integral equation. Teor. Verojatnost. i Primenen. 17, 111–128 (1972)
Lakkis, O., Pryer, T.: A finite element method for nonlinear elliptic problems. SIAM J. Sci. Comput. 35(4), A2025–A2045 (2013). https://doi.org/10.1137/120887655
Lin, J.: Wide stencil for the Monge–Ampère equation. Technical report, University of Waterloo master essay, supervised by Justin WL Wan, https://uwaterloo.ca/computational-mathematics/sites/ca.computational-mathematics/files/uploads/files/cmmain1.pdf (2014)
Lions, P.L.: Hamilton–Jacobi–Bellman equations and the optimal control of stochastic systems. In: Proceedings of the International Congress of Mathematicians, vol. 1, 2 (Warsaw, 1983), pp. 1403–1417. PWN, Warsaw (1984)
Ma, K., Forsyth, P.: An unconditionally monotone numerical scheme for the two factor uncertain volatility model. Preprint (2014)
Oberman, A.M.: Wide stencil finite difference schemes for the elliptic Monge–Ampère equation and functions of the eigenvalues of the Hessian. Discrete Contin. Dyn. Syst. Ser. B 10(1), 221–238 (2008). https://doi.org/10.3934/dcdsb.2008.10.221
Oliker, V.I., Prussner, L.D.: On the numerical solution of the equation \((\partial ^2z/\partial x^2)(\partial ^2z/\partial y^2)-((\partial ^2z/\partial x\partial y))^2=f\) and its discretizations. I. Numer. Math. 54(3), 271–293 (1988). https://doi.org/10.1007/BF01396762
Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2003). https://doi.org/10.1137/1.9780898718003
Samarskii, A.A.: The Theory of Difference Schemes, Monographs and Textbooks in Pure and Applied Mathematics, vol. 240. Marcel Dekker, Inc., New York (2001). https://doi.org/10.1201/9780203908518
Shivakumar, P.N., Williams, J.J., Ye, Q., Marinov, C.A.: On two-sided bounds related to weakly diagonally dominant \(M\)-matrices with application to digital circuit dynamics. SIAM J. Matrix Anal. Appl. 17(2), 298–312 (1996). https://doi.org/10.1137/S0895479894276370
Smears, I.: Hamilton–Jacobi–Bellman equations analysis and numerical analysis. Technical report, research report available on www.math.dur.ac.uk/Ug/projects/highlights/PR4/Smears_HJB_report.pdf
Wang, J., Forsyth, P.A.: Maximal use of central differencing for Hamilton–Jacobi–Bellman PDEs in finance. SIAM J. Numer. Anal. 46(3), 1580–1601 (2008). https://doi.org/10.1137/060675186
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, Y., Wan, J.W.L. & Lin, J. Monotone Mixed Finite Difference Scheme for Monge–Ampère Equation. J Sci Comput 76, 1839–1867 (2018). https://doi.org/10.1007/s10915-018-0685-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-018-0685-y