Efficient spectral sparse grid approximations for solving multi-dimensional forward backward sdes. (English) Zbl 1368.60071
Summary: This is the second part of a series papers on multi-step schemes for solving coupled forward backward stochastic differential equations (FBSDEs). We extend the basic idea in our former paper [W. Zhao et al., SIAM J. Sci. Comput. 36, No. 4, A1731–A1751 (2014; Zbl 1316.65014)] to solve high-dimensional FBSDEs, by using the spectral sparse grid approximations. The main issue for solving high-dimensional FBSDEs is to build an efficient spatial discretization, and deal with the related high-dimensional conditional expectations and interpolations. In this work, we propose the sparse grid spatial discretization. The sparse grid Gaussian-Hermite quadrature rule is used to approximate the conditional expectations. And for the associated high-dimensional interpolations, we adopt a spectral expansion of functions in polynomial spaces with respect to the spatial variables, and use the sparse grid approximations to recover the expansion coefficients. The FFT algorithm is used to speed up the recovery procedure, and the entire algorithm admits efficient and highly accurate approximations in high dimensions. Several numerical examples are presented to demonstrate the efficiency of the proposed methods.
MSC:
| 60H35 | Computational methods for stochastic equations (aspects of stochastic analysis) |
| 65C20 | Probabilistic models, generic numerical methods in probability and statistics |
| 60H10 | Stochastic ordinary differential equations (aspects of stochastic analysis) |
Keywords:
spectral method; sparse grid approximations; forward-backward stochastic differential equations; conditional expectations; fast Fourier transformCitations:
Zbl 1316.65014References:
| [1] | V. Barthelmann, High dimensional polynomial interpolation on sparse grids,, Adv. Comput. Math., 12, 273 (2000) · Zbl 0944.41001 · doi:10.1023/A:1018977404843 |
| [2] | C. Bender, Time discretization and Markovian iteration for coupled FBSDEs,, Ann. Appl. Probab., 18, 143 (2008) · Zbl 1142.65005 · doi:10.1214/07-AAP448 |
| [3] | J. M. Bismut, Conjugate convex functions in optimal stochastic control,, J. Math. Anal. Appl., 44, 384 (1973) · Zbl 0276.93060 · doi:10.1016/0022-247X(73)90066-8 |
| [4] | B. Bouchard, Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations,, Stoch. Proc. Appl., 111, 175 (2004) · Zbl 1071.60059 · doi:10.1016/j.spa.2004.01.001 |
| [5] | J. F. Chassagneux, Runge-Kutta schemes for backward stochastic differential equations,, Ann. Appl. Probab., 24, 679 (2014) · Zbl 1303.60045 · doi:10.1214/13-AAP933 |
| [6] | P. Cheridito, Second-order backward stochastic differential equations and fully nonlinear parabolic PDEs,, Commun. Pur. Appl. Math., 60, 1081 (2007) · Zbl 1121.60062 · doi:10.1002/cpa.20168 |
| [7] | D. Crisan, Solving backward stochastic differential equations using the cubature method: application to nonlinear pricing,, SIAM J. Financial Math., 3, 534 (2012) · Zbl 1259.65005 · doi:10.1137/090765766 |
| [8] | J. Douglas, Numerical methods for forward-backward stochastic differential equations,, Ann. Appl. Probab., 6, 940 (1996) · Zbl 0861.65131 · doi:10.1214/aoap/1034968235 |
| [9] | A. Fahim, A probabilistic numerical method for fully nonlinear parabolic PDEs,, Ann. Appl. Probab., 21, 1322 (2011) · Zbl 1230.65009 · doi:10.1214/10-AAP723 |
| [10] | Y. Fu, Multistep schemes for forward backward stochastic differential equations with jumps,, J. Sci. Comput., 69, 651 (2016) · Zbl 1368.60072 · doi:10.1007/s10915-016-0212-y |
| [11] | W. Guo, A monotone scheme for high-dimensional fully nonlinear PDEs,, Ann. Appl. Probab., 25, 1540 (2015) · Zbl 1321.65158 · doi:10.1214/14-AAP1030 |
| [12] | N. El Karoui, Reflected solutions of backward SDE’s and related obstacle problems for PDE’s,, Ann. Probab., 25, 702 (1997) · Zbl 0899.60047 · doi:10.1214/aop/1024404416 |
| [13] | N. El Karoui, Backward stochastic differential equations in finance,, Math. Financ., 7, 1 (1997) · Zbl 0884.90035 · doi:10.1111/1467-9965.00022 |
| [14] | T. Kong, High order probabilistic numerical schemes for fully nonlinear parabolic PDEs,, Commun. Comput. Phys., 18, 1482 (2015) · Zbl 1388.65016 · doi:10.4208/cicp.240515.280815a |
| [15] | T. Kong, High order numerical schemes for second order FBSDEs with applications to stochastic optimal control,, Commun. Comput. Phys., 21, 808 (2017) · Zbl 1499.65027 · doi:10.4208/cicp.OA-2016-0056 |
| [16] | J. P. Lemor, A regression-based Monte Carlo method to solve backward stochastic differential equations,, Ann. Appl. Probab., 15, 2172 (2005) · Zbl 1083.60047 · doi:10.1214/105051605000000412 |
| [17] | Y. Li, Convergence error estimates of the Crank-Nicolson scheme for solving decoupled FBSDEs,, Sci. China Math., 60, 923 (2017) · Zbl 1372.65018 · doi:10.1007/s11425-016-0178-8 |
| [18] | J. Ma, Solving forward-backward stochastic differential equations explicitly - a four step scheme,, Probab. Theory Related Fields, 98, 339 (1994) · Zbl 0794.60056 · doi:10.1007/BF01192258 |
| [19] | J. Ma, On numerical approximations of forward-backward stochastic differential equations,, SIAM J. Numer. Anal., 46, 2636 (2008) · Zbl 1177.60064 · doi:10.1137/06067393X |
| [20] | G. N. Milstein, Numerical algorithms for forward-backward stochastic differential equations,, SIAM J. Sci. Comput., 28, 561 (2006) · Zbl 1114.60054 · doi:10.1137/040614426 |
| [21] | F. Nobile, A sparse grid stochastic collocation method for partial differential equations with random input data,, SIAM J. Numer. Anal., 46, 2309 (2008) · Zbl 1176.65137 · doi:10.1137/060663660 |
| [22] | A. Narayan, Stochastic collocation on unstructured multivariate meshes,, Commun. Comput. Phys., 18, 1 (2015) · Zbl 1388.65127 · doi:10.4208/cicp.020215.070515a |
| [23] | E. Pardoux, Adapted solution of a backward stochastic differential equation,, Syst. Control Lett., 14, 55 (1990) · Zbl 0692.93064 · doi:10.1016/0167-6911(90)90082-6 |
| [24] | E. Pardoux, Forward-backward stochastic differential equations and quasilinear parabolic PDEs,, Probab. Theory Related Fields, 114, 123 (1999) · Zbl 0943.60057 · doi:10.1007/s004409970001 |
| [25] | S. Peng, Probabilistic interpretation for systems of quasilinear parabolic partial differential equations,, Stoch. Stoch. Repts., 37, 61 (1991) · Zbl 0739.60060 · doi:10.1080/17442509108833727 |
| [26] | M. J. Ruijter, Fourier-cosine method for an efficient computation of solutions to BSDEs,, SIAM J. Sci. Comput., 37 (2015) · Zbl 1314.65011 · doi:10.1137/130913183 |
| [27] | J. Shen, Efficient spectral sparse grid methods and applications to high dimensional elliptic problems,, SIAM J. Sci. Comput., 32, 3228 (2010) · Zbl 1233.65094 · doi:10.1137/100787842 |
| [28] | J. Shen, Efficient spectral sparse grid methods and applications to high dimensional elliptic problems II unbounded domains,, SIAM J. Sci. Comput., 34 (2012) · Zbl 1269.65130 · doi:10.1137/110834950 |
| [29] | S. A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions,, Dokl. Akad. Nauk SSSR, 4, 240 (1963) · Zbl 0202.39901 |
| [30] | H. M. Soner, Wellposedness of second order backward SDEs,, Probab. Theory Related Fields, 153, 149 (2012) · Zbl 1252.60056 · doi:10.1007/s00440-011-0342-y |
| [31] | T. Tang, Deferred correction methods for forward backward stochastic differential equations,, Numer. Math. Theory Methods Appl., 10, 222 (2017) · Zbl 1389.60083 · doi:10.4208/nmtma.2017.s02 |
| [32] | D. Xiu, High-order collocation methods for differential equations with random inputs,, SIAM J. Sci. Comput., 27, 1118 (2005) · Zbl 1091.65006 · doi:10.1137/040615201 |
| [33] | G. Zhang, A sparse-grid method for multi-dimensional backward stochastic differential equations,, J. Comput. Math., 31, 221 (2013) · Zbl 1289.65011 · doi:10.4208/jcm.1212-m4014 |
| [34] | J. Zhang, A numerical scheme for BSDEs,, Ann. Appl. Probab., 14, 459 (2004) · Zbl 1056.60067 · doi:10.1214/aoap/1075828058 |
| [35] | W. Zhao, A new kind of accurate numerical method for backward stochastic differential equations,, SIAM J. Sci. Comput., 28, 1563 (2006) · Zbl 1121.60072 · doi:10.1137/05063341X |
| [36] | W. Zhao, New kinds of high-order multistep schemes for coupled forward backward stochastic differential equations,, SIAM J. Sci. Comput., 36 (2014) · Zbl 1316.65014 · doi:10.1137/130941274 |
| [37] | W. Zhao, A generalized \(\theta \)-scheme for solving backward stochastic differential equations,, Discrete Contin. Dyn. Syst. Ser. B, 17, 1585 (2012) · Zbl 1250.60033 · doi:10.3934/dcdsb.2012.17.1585 |
| [38] | W. Zhao, Error estimates of the \(\theta \)-scheme for backward stochastic differential equations,, Discrete Contin. Dyn. Syst. Ser. B, 12, 905 (2009) · Zbl 1185.60077 · doi:10.3934/dcdsb.2009.12.905 |
| [39] | W. Zhao, A stable multistep scheme for solving backward stochastic differential equations,, SIAM J. Numer. Anal., 48, 1369 (2010) · Zbl 1234.60068 · doi:10.1137/09076979X |
| [40] | W. Zhao, A numerical method and its error estimates for the decoupled forward-backward stochastic differential equations,, Commun. Comput. Phys., 15, 618 (2014) · Zbl 06799394 · doi:10.4208/cicp.280113.190813a |
| [41] | W. Zhao, A multistep scheme for decoupled forward-backward stochastic differential equations,, Numer. Math. Theory Methods Appl., 9, 262 (2016) · Zbl 1374.65008 · doi:10.4208/nmtma.2016.m1421 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
