Error bounds for monotone approximation schemes for parabolic Hamilton-Jacobi-Bellman equations

Barles, Guy; Jakobsen, Espen

doi:10.1090/S0025-5718-07-02000-5

Error bounds for monotone approximation schemes for parabolic Hamilton-Jacobi-Bellman equations
HTML articles powered by AMS MathViewer

by Guy Barles and Espen R. Jakobsen PDF

Math. Comp. 76 (2007), 1861-1893 Request permission

Abstract:

We obtain nonsymmetric upper and lower bounds on the rate of convergence of general monotone approximation/numerical schemes for parabolic Hamilton-Jacobi-Bellman equations by introducing a new notion of consistency. Our results are robust and general – they improve and extend earlier results by Krylov, Barles, and Jakobsen. We apply our general results to various schemes including Crank–Nicholson type finite difference schemes, splitting methods, and the classical approximation by piecewise constant controls. In the first two cases our results are new, and in the last two cases the results are obtained by a new method which we develop here.

References

Guy Barles and Espen Robstad Jakobsen, On the convergence rate of approximation schemes for Hamilton-Jacobi-Bellman equations, M2AN Math. Model. Numer. Anal. 36 (2002), no. 1, 33–54. MR 1916291, DOI 10.1051/m2an:2002002
Guy Barles and Espen R. Jakobsen, Error bounds for monotone approximation schemes for Hamilton-Jacobi-Bellman equations, SIAM J. Numer. Anal. 43 (2005), no. 2, 540–558. MR 2177879, DOI 10.1137/S003614290343815X
G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal. 4 (1991), no. 3, 271–283. MR 1115933
J. Frédéric Bonnans, Élisabeth Ottenwaelter, and Housnaa Zidani, A fast algorithm for the two dimensional HJB equation of stochastic control, M2AN Math. Model. Numer. Anal. 38 (2004), no. 4, 723–735. MR 2087732, DOI 10.1051/m2an:2004034
J. Frédéric Bonnans and Housnaa Zidani, Consistency of generalized finite difference schemes for the stochastic HJB equation, SIAM J. Numer. Anal. 41 (2003), no. 3, 1008–1021. MR 2005192, DOI 10.1137/S0036142901387336
Fabio Camilli and Maurizio Falcone, An approximation scheme for the optimal control of diffusion processes, RAIRO Modél. Math. Anal. Numér. 29 (1995), no. 1, 97–122 (English, with English and French summaries). MR 1326802, DOI 10.1051/m2an/1995290100971
I. Capuzzo-Dolcetta and L. C. Evans, Optimal switching for ordinary differential equations, SIAM J. Control Optim. 22 (1984), no. 1, 143–161. MR 728678, DOI 10.1137/0322011
Michael G. Crandall, Hitoshi Ishii, and Pierre-Louis Lions, User’s guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 1, 1–67. MR 1118699, DOI 10.1090/S0273-0979-1992-00266-5
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
Hongjie Dong and N. V. Krylov, On the rate of convergence of finite-difference approximations for Bellman equations with constant coefficients, Algebra i Analiz 17 (2005), no. 2, 108–132; English transl., St. Petersburg Math. J. 17 (2006), no. 2, 295–313. MR 2159586, DOI 10.1090/S1061-0022-06-00905-8
Hongjie Dong and Nicolai V. Krylov, Rate of convergence of finite-difference approximations for degenerate linear parabolic equations with $C^1$ and $C^2$ coefficients, Electron. J. Differential Equations (2005), No. 102, 25. MR 2162263
Harold J. Kushner and Paul Dupuis, Numerical methods for stochastic control problems in continuous time, 2nd ed., Applications of Mathematics (New York), vol. 24, Springer-Verlag, New York, 2001. Stochastic Modelling and Applied Probability. MR 1800098, DOI 10.1007/978-1-4613-0007-6
Lawrence C. Evans and Avner Friedman, Optimal stochastic switching and the Dirichlet problem for the Bellman equation, Trans. Amer. Math. Soc. 253 (1979), 365–389. MR 536953, DOI 10.1090/S0002-9947-1979-0536953-4
Hitoshi Ishii, On uniqueness and existence of viscosity solutions of fully nonlinear second-order elliptic PDEs, Comm. Pure Appl. Math. 42 (1989), no. 1, 15–45. MR 973743, DOI 10.1002/cpa.3160420103
Hitoshi Ishii and Shigeaki Koike, Viscosity solutions for monotone systems of second-order elliptic PDEs, Comm. Partial Differential Equations 16 (1991), no. 6-7, 1095–1128. MR 1116855, DOI 10.1080/03605309108820791
Hitoshi Ishii and Shigeaki Koike, Viscosity solutions of a system of nonlinear second-order elliptic PDEs arising in switching games, Funkcial. Ekvac. 34 (1991), no. 1, 143–155. MR 1116886
Espen Robstad Jakobsen, On the rate of convergence of approximation schemes for Bellman equations associated with optimal stopping time problems, Math. Models Methods Appl. Sci. 13 (2003), no. 5, 613–644. MR 1978929, DOI 10.1142/S0218202503002660
Espen R. Jakobsen and Kenneth H. Karlsen, Continuous dependence estimates for viscosity solutions of fully nonlinear degenerate parabolic equations, J. Differential Equations 183 (2002), no. 2, 497–525. MR 1919788, DOI 10.1006/jdeq.2001.4136
N. V. Krylov, On the rate of convergence of finite-difference approximations for Bellman’s equations, Algebra i Analiz 9 (1997), no. 3, 245–256; English transl., St. Petersburg Math. J. 9 (1998), no. 3, 639–650. MR 1466804
N. V. Krylov, On the rate of convergence of finite-difference approximations for Bellman’s equations with variable coefficients, Probab. Theory Related Fields 117 (2000), no. 1, 1–16. MR 1759507, DOI 10.1007/s004400050264
N. V. Krylov, Approximating value functions for controlled degenerate diffusion processes by using piece-wise constant policies, Electron. J. Probab. 4 (1999), no. 2, 19. MR 1668597, DOI 10.1214/EJP.v4-39
Nicolai V. Krylov, The rate of convergence of finite-difference approximations for Bellman equations with Lipschitz coefficients, Appl. Math. Optim. 52 (2005), no. 3, 365–399. MR 2174020, DOI 10.1007/s00245-005-0832-3
P.-L. Lions. Personal communication.
P.-L. Lions and B. Mercier, Approximation numérique des équations de Hamilton-Jacobi-Bellman, RAIRO Anal. Numér. 14 (1980), no. 4, 369–393 (French, with English summary). MR 596541
Chi-Wang Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1073–1084. MR 963855, DOI 10.1137/0909073
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
Agnès Tourin, Splitting methods for Hamilton-Jacobi equations, Numer. Methods Partial Differential Equations 22 (2006), no. 2, 381–396. MR 2201439, DOI 10.1002/num.20100
Naoki Yamada, Viscosity solutions for a system of elliptic inequalities with bilateral obstacles, Funkcial. Ekvac. 30 (1987), no. 2-3, 417–425. MR 927191