Article Contents
Article Contents

# Efficient spectral sparse grid approximations for solving multi-dimensional forward backward SDEs

• * Corresponding author

This work was supported by the National Natural Science Foundations of China under grants 91630312,91630203,11571351,11171189 and 11571206. The last author was also supported by NCMIS

• 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, Y. Fu and T. Zhou, SIAM J. Sci. Comput., 36 (2014), pp. A1731-A1751] 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.

Mathematics Subject Classification: 60H35, 65C20, 60H10.

 Citation:

• Figure 1.  Sparse grid for CGL $(x_1, x_2)\in\mathcal{C}_2^6$ (Left) and sparse grid for GH $(x_1, x_2)\in\mathcal{G}_2^6$ (Right)

Figure 2.  Dimensions v.s. the running time for Example 3 with $N=128$

Table 1.  Main techniques used in the SSG and LTG methods for solving FBSDEs. TP: tensor product. SG: sparse grid. GH: Gaussian-Hermite

 Method Meshes Conditional expectations Approximation & interpolation SSG sparse grid SG GH quadrature SG interpolation LTG TP uniform mesh TP GH quadrature Lagrangian

Table 2.  Errors and convergence rates for Example 1 by SSG (Top) and LTG (Bottom)

 step number errors N=8 N=16 N=32 N=64 N=128 CR 1-step $\mathcal{E}_Y$ 3.991E-02 2.050E-02 1.039E-02 5.232E-03 2.625E-03 0.982 $\mathcal{E}_Z$ 5.186E-02 2.649E-02 1.339E-02 6.733E-03 3.377E-03 0.986 RT 2.519 4.638 9.521 19.199 38.679 2-step $\mathcal{E}_Y$ 5.620E-03 1.456E-03 3.670E-04 9.182E-05 2.286E-05 1.987 $\mathcal{E}_Z$ 6.978E-03 1.847E-03 4.813E-04 1.225E-04 3.090E-05 1.955 RT 6.852 15.596 33.401 68.541 143.552 3-step $\mathcal{E}_Y$ 9.748E-04 1.342E-04 1.728E-05 2.264E-06 8.196E-07 2.632 $\mathcal{E}_Z$ 3.091E-03 3.850E-04 4.757E-05 6.009E-06 8.834E-07 2.955 RT 6.899 19.403 43.835 95.902 197.608 step number errors N=8 N=16 N=32 N=64 N=128 CR 1-step $\mathcal{E}_Y$ 7.204E-01 3.989E-01 1.849E-01 7.321E-02 2.871E-02 1.174 $\mathcal{E}_Z$ 2.670E-01 1.534E-01 7.409E-02 3.152E-02 1.332E-02 1.093 RT 1.047 4.609 24.120 141.209 844.974 2-step $\mathcal{E}_Y$ 4.873E-01 1.105E-01 2.220E-02 4.165E-03 7.708E-04 2.333 $\mathcal{E}_Z$ 1.999E-01 4.706E-02 1.174E-02 2.494E-03 4.159E-04 2.205 RT 3.861 12.970 60.661 363.052 2139.540 3-step $\mathcal{E}_Y$ 2.656E-01 2.252E-02 2.295E-03 2.247E-04 2.024E-05 3.401 $\mathcal{E}_Z$ 1.136E-01 9.841E-03 1.306E-03 1.417E-04 1.244E-05 3.243 RT 13.010 43.490 193.784 968.788 4929.977

Table 3.  Errors and convergence rates for Example 2

 step number errors N=8 N=16 N=32 N=64 N=128 CR 1-step $\mathcal{E}_Y$ 6.229E-03 3.173E-03 1.547E-03 7.695E-04 3.849E-04 1.008 $\mathcal{E}_Z$ 8.693E-02 4.335E-02 2.165E-02 1.082E-02 5.411E-03 1.001 RT 4.268 9.036 17.720 35.740 76.049 2-step $\mathcal{E}_Y$ 4.126E-05 1.148E-05 2.251E-06 3.986E-07 1.051E-07 2.208 $\mathcal{E}_Z$ 5.470E-04 1.630E-04 4.222E-05 8.722E-06 2.061E-06 2.032 RT 6.986 15.926 34.530 72.690 153.092 3-step $\mathcal{E}_Y$ 4.078E-05 8.408E-06 1.107E-06 1.370E-07 1.837E-08 2.817 $\mathcal{E}_Z$ 4.438E-04 5.143E-05 7.673E-06 1.049E-06 1.514E-07 2.865 RT 7.980 20.650 48.610 102.595 212.189

Table 4.  Errors and convergence rates for Example 3

 scheme sparse grid N=8 N=16 N=32 N=64 N=128 CR 1-step $q=3$ $\mathcal{C}_3^4$ & $\mathcal{G}_3^4$ $\mathcal{E}_Y$ 5.717E-02 2.999E-02 1.557E-02 8.021E-03 4.104E-03 0.950 $\mathcal{E}_Z$ 3.129E-02 1.575E-02 7.988E-03 4.057E-03 2.057E-03 0.981 RT 0.107 0.226 0.389 0.627 1.268 2-step $q=3$ $\mathcal{C}_3^4$ & $\mathcal{G}_3^4$ $\mathcal{E}_Y$ 2.766E-03 7.861E-04 2.091E-04 5.396E-05 1.371E-05 1.918 $\mathcal{E}_Z$ 4.833E-03 1.197E-03 3.006E-04 7.588E-05 1.916E-05 1.994 RT 0.131 0.235 0.509 1.067 2.187 3-step $q=3$ $\mathcal{C}_3^4$ & $\mathcal{G}_3^4$ $\mathcal{E}_Y$ 1.244E-04 1.183E-05 1.061E-06 9.522E-08 8.587E-09 3.460 $\mathcal{E}_Z$ 3.425E-04 4.375E-05 5.575E-06 7.067E-07 8.922E-08 2.976 RT 0.173 0.370 0.750 1.478 3.072 1-step $q=4$ $\mathcal{C}_4^5$ & $\mathcal{G}_4^5$ $\mathcal{E}_Y$ 1.196E-01 6.208E-02 3.187E-02 1.626E-02 8.259E-03 0.965 $\mathcal{E}_Z$ 3.445E-02 1.735E-02 8.772E-03 4.439E-03 2.244E-03 0.985 RT 1.682 3.153 6.178 12.934 26.182 2-step $q=4$ $\mathcal{C}_4^5$ & $\mathcal{G}_4^5$ $\mathcal{E}_Y$ 9.114E-03 2.817E-03 7.851E-04 2.087E-04 5.426E-05 1.854 $\mathcal{E}_Z$ 6.769E-03 1.628E-03 4.038E-04 1.012E-04 2.547E-05 2.012 RT 2.513 4.442 9.606 20.160 41.504 3-step $q=4$ $\mathcal{C}_4^5$ & $\mathcal{G}_4^5$ $\mathcal{E}_Y$ 4.879E-04 7.611E-05 1.052E-05 1.378E-06 1.763E-07 2.865 $\mathcal{E}_Z$ 1.176E-03 1.420E-04 1.767E-05 2.215E-06 2.786E-07 3.009 RT 1.993 5.722 13.296 28.614 59.671 1-step $q=5$ $\mathcal{C}_5^6$ & $\mathcal{G}_5^6$ $\mathcal{E}_Y$ 2.269E-01 1.177E-01 6.023E-02 3.061E-02 1.549E-02 0.969 $\mathcal{E}_Z$ 4.345E-02 2.196E-02 1.110E-02 5.608E-03 2.829E-03 0.985 RT 23.196 47.566 99.318 203.587 411.991 2-step $q=5$ $\mathcal{C}_5^6$ & $\mathcal{G}_5^6$ $\mathcal{E}_Y$ 2.941E-02 8.713E-03 2.376E-03 6.223E-04 1.600E-04 1.885 $\mathcal{E}_Z$ 9.182E-03 2.216E-03 5.534E-04 1.393E-04 3.510E-05 2.005 RT 33.610 80.876 177.315 372.765 766.094 3-step $q=5$ $\mathcal{C}_5^6$ & $\mathcal{G}_5^6$ $\mathcal{E}_Y$ 2.549E-03 4.157E-04 6.185E-05 8.531E-06 1.127E-06 2.789 $\mathcal{E}_Z$ 2.364E-03 2.687E-04 3.254E-05 4.031E-06 5.037E-07 3.045 RT 36.049 105.507 245.986 530.853 1106.870 1-step $q=6$ $\mathcal{C}_6^7$ & $\mathcal{G}_6^7$ $\mathcal{E}_Y$ 4.068E-01 2.117E-01 1.084E-01 5.500E-02 2.779E-02 0.969 $\mathcal{E}_Z$ 5.899E-02 2.996E-02 1.516E-02 7.652E-03 3.855E-03 0.984 RT 368.274 792.758 1640.774 3346.529 6758.066 2-step $q=6$ $\mathcal{C}_6^7$ & $\mathcal{G}_6^7$ $\mathcal{E}_Y$ 7.236E-02 2.130E-02 5.783E-03 1.510E-03 3.869E-04 1.891 $\mathcal{E}_Z$ 1.307E-02 3.277E-03 8.382E-04 2.134E-04 5.405E-05 1.978 RT 1112.524 2813.641 6114.390 12814.473 26454.702 3-step $q=6$ $\mathcal{C}_6^7$ & $\mathcal{G}_6^7$ $\mathcal{E}_Y$ 1.037E-02 1.742E-03 2.528E-04 3.407E-05 4.433E-06 2.806 $\mathcal{E}_Z$ 3.924E-03 4.391E-04 5.339E-05 6.647E-06 8.328E-07 3.045 RT 594.060 1767.938 4110.876 8853.131 18481.311

Table 5.  Errors and convergence rates for Example 4

 scheme sparse gird N=8 N=16 N=32 N=64 N=128 CR 1-step $q=2$ $\mathcal{C}_2^3$ & $\mathcal{G}_2^3$ $\mathcal{E}_Y$ 4.246E-03 1.925E-03 9.181E-04 4.508E-04 2.243E-04 1.058 $\mathcal{E}_Z$ 1.149E-02 4.898E-03 2.098E-03 9.057E-04 3.948E-04 1.216 RT 0.030 0.045 0.083 0.160 0.267 2-step $q=2$ $\mathcal{C}_2^3$ & $\mathcal{G}_2^3$ $\mathcal{E}_Y$ 4.093E-04 8.289E-05 1.646E-05 3.207E-06 6.101E-07 2.347 $\mathcal{E}_Z$ 5.429E-03 1.395E-03 3.568E-04 9.099E-05 2.315E-05 1.968 RT 0.032 0.059 0.090 0.171 0.327 3-step $q=2$ $\mathcal{C}_2^3$ & $\mathcal{G}_2^3$ $\mathcal{E}_Y$ 2.459E-05 2.651E-06 2.695E-07 2.658E-08 2.538E-09 3.312 $\mathcal{E}_Z$ 5.266E-05 5.713E-06 6.099E-07 6.276E-08 6.215E-09 3.261 RT 0.033 0.075 0.132 0.276 0.430 1-step $q=3$ $\mathcal{C}_3^4$ & $\mathcal{G}_3^4$ $\mathcal{E}_Y$ 2.463E-03 1.068E-03 4.812E-04 2.229E-04 1.072E-04 1.130 $\mathcal{E}_Z$ 3.243E-03 1.363E-03 5.990E-04 2.630E-04 1.154E-04 1.200 RT 0.295 0.422 0.762 1.420 2.690 2-step $q=3$ $\mathcal{C}_3^4$ & $\mathcal{G}_3^4$ $\mathcal{E}_Y$ 2.044E-04 7.910E-05 1.676E-05 3.397E-06 6.738E-07 2.103 $\mathcal{E}_Z$ 1.073E-03 2.444E-04 6.285E-05 1.632E-05 4.227E-06 1.988 RT 0.352 0.717 1.385 2.610 4.946 3-step $q=3$ $\mathcal{C}_3^4$ & $\mathcal{G}_3^4$ $\mathcal{E}_Y$ 8.103E-06 1.743E-06 1.890E-07 1.942E-08 1.933E-09 3.055 $\mathcal{E}_Z$ 7.540E-06 1.577E-06 1.795E-07 1.933E-08 1.995E-09 3.012 RT 0.364 1.223 1.936 3.743 7.150 1-step $q=4$ $\mathcal{C}_4^5$ & $\mathcal{G}_4^5$ $\mathcal{E}_Y$ 1.663E-03 7.351E-04 3.068E-04 1.370E-04 6.294E-05 1.187 $\mathcal{E}_Z$ 1.360E-03 5.763E-04 2.374E-04 1.068E-04 4.838E-05 1.206 RT 3.916 8.050 15.738 29.987 55.418 2-step $q=4$ $\mathcal{C}_4^5$ & $\mathcal{G}_4^5$ $\mathcal{E}_Y$ 6.776E-05 4.165E-05 1.569E-05 3.408E-06 6.925E-07 1.684 $\mathcal{E}_Z$ 3.665E-04 8.033E-05 1.727E-05 4.479E-06 1.191E-06 2.070 RT 5.064 13.279 28.974 56.345 105.155 3-step $q=4$ $\mathcal{C}_4^5$ & $\mathcal{G}_4^5$ $\mathcal{E}_Y$ 4.932E-06 1.065E-06 1.111E-07 1.115E-08 1.087E-09 3.087 $\mathcal{E}_Z$ 2.474E-06 5.495E-07 6.062E-08 6.348E-09 6.390E-10 3.027 RT 34.015 117.047 250.853 483.481 926.454 1-step $q=5$ $\mathcal{C}_5^6$ & $\mathcal{G}_5^6$ $\mathcal{E}_Y$ 1.167E-03 5.489E-04 2.341E-04 9.343E-05 4.184E-05 1.216 $\mathcal{E}_Z$ 6.751E-04 3.055E-04 1.268E-04 5.183E-05 2.408E-05 1.218 RT 58.937 134.345 289.234 570.587 1049.247 2-step $q=5$ $\mathcal{C}_5^6$ & $\mathcal{G}_5^6$ $\mathcal{E}_Y$ 6.572E-05 4.173E-05 1.246E-05 2.548E-06 5.087E-07 1.806 $\mathcal{E}_Z$ 1.464E-04 2.885E-05 6.466E-06 1.763E-06 4.792E-07 2.054 RT 736.405 2004.185 4124.286 7776.645 14561.700 3-step $q=5$ $\mathcal{C}_5^6$ & $\mathcal{G}_5^6$ $\mathcal{E}_Y$ 1.649E-06 6.334E-07 9.009E-08 9.209E-09 9.147E-10 2.774 $\mathcal{E}_Z$ 5.318E-07 2.072E-07 3.079E-08 3.274E-09 3.372E-10 2.723 RT 709.587 2599.783 5916.660 11366.633 21380.402
•  V. Barthelmann , E. Novak  and  K. Ritter , High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math., 12 (2000) , 273-288.  doi: 10.1023/A:1018977404843. C. Bender  and  J. Zhang , Time discretization and Markovian iteration for coupled FBSDEs, Ann. Appl. Probab., 18 (2008) , 143-177.  doi: 10.1214/07-AAP448. J. M. Bismut , Conjugate convex functions in optimal stochastic control, J. Math. Anal. Appl., 44 (1973) , 384-404.  doi: 10.1016/0022-247X(73)90066-8. B. Bouchard  and  N. Touzi , Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations, Stoch. Proc. Appl., 111 (2004) , 175-206.  doi: 10.1016/j.spa.2004.01.001. J. F. Chassagneux  and  D. Crisan , Runge-Kutta schemes for backward stochastic differential equations, Ann. Appl. Probab., 24 (2014) , 679-720.  doi: 10.1214/13-AAP933. P. Cheridito , H. M. Soner , N. Touzi  and  N. Victoir , Second-order backward stochastic differential equations and fully nonlinear parabolic PDEs, Commun. Pur. Appl. Math., 60 (2007) , 1081-1110.  doi: 10.1002/cpa.20168. D. Crisan  and  K. Manolarakis , Solving backward stochastic differential equations using the cubature method: application to nonlinear pricing, SIAM J. Financial Math., 3 (2012) , 534-571.  doi: 10.1137/090765766. J. Douglas , J. Ma  and  P. Protter , Numerical methods for forward-backward stochastic differential equations, Ann. Appl. Probab., 6 (1996) , 940-968.  doi: 10.1214/aoap/1034968235. A. Fahim , N. Touzi  and  X. Warin , A probabilistic numerical method for fully nonlinear parabolic PDEs, Ann. Appl. Probab., 21 (2011) , 1322-1364.  doi: 10.1214/10-AAP723. Y. Fu , W. Zhao  and  T. Zhou , Multistep schemes for forward backward stochastic differential equations with jumps, J. Sci. Comput., 69 (2016) , 651-672.  doi: 10.1007/s10915-016-0212-y. W. Guo , J. Zhang  and  J. Zhuo , A monotone scheme for high-dimensional fully nonlinear PDEs, Ann. Appl. Probab., 25 (2015) , 1540-1580.  doi: 10.1214/14-AAP1030. N. El Karoui , C. Kapoudjian , E. Pardoux , S. Peng  and  M. C. Quenez , Reflected solutions of backward SDE's and related obstacle problems for PDE's, Ann. Probab., 25 (1997) , 702-737.  doi: 10.1214/aop/1024404416. N. El Karoui , S. Peng  and  M. C. Quenez , Backward stochastic differential equations in finance, Math. Financ., 7 (1997) , 1-71.  doi: 10.1111/1467-9965.00022. T. Kong , W. Zhao  and  T. Zhou , High order probabilistic numerical schemes for fully nonlinear parabolic PDEs, Commun. Comput. Phys., 18 (2015) , 1482-1503.  doi: 10.4208/cicp.240515.280815a. T. Kong , W. Zhao  and  T. Zhou , High order numerical schemes for second order FBSDEs with applications to stochastic optimal control, Commun. Comput. Phys., 21 (2017) , 808-834.  doi: 10.4208/cicp.OA-2016-0056. J. P. Lemor , E. Gobet  and  X. Warin , A regression-based Monte Carlo method to solve backward stochastic differential equations, Ann. Appl. Probab., 15 (2005) , 2172-2202.  doi: 10.1214/105051605000000412. Y. Li , J. Yang  and  W. Zhao , Convergence error estimates of the {C}rank-{N}icolson scheme for solving decoupled {FBSDE}s, Sci. China Math., 60 (2017) , 923-948.  doi: 10.1007/s11425-016-0178-8. J. Ma , P. Protter  and  J. Yong , Solving forward-backward stochastic differential equations explicitly -a four step scheme, Probab. Theory Related Fields, 98 (1994) , 339-359.  doi: 10.1007/BF01192258. J. Ma , J. Shen  and  Y. Zhao , On numerical approximations of forward-backward stochastic differential equations, SIAM J. Numer. Anal., 46 (2008) , 2636-2661.  doi: 10.1137/06067393X. G. N. Milstein  and  M. V. Tretyakov , Numerical algorithms for forward-backward stochastic differential equations, SIAM J. Sci. Comput., 28 (2006) , 561-582.  doi: 10.1137/040614426. F. Nobile , R. Tempone  and  C. Webster , A sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal., 46 (2008) , 2309-2345.  doi: 10.1137/060663660. A. Narayan  and  T. Zhou , Stochastic collocation on unstructured multivariate meshes, Commun. Comput. Phys., 18 (2015) , 1-36.  doi: 10.4208/cicp.020215.070515a. E. Pardoux  and  S. Peng , Adapted solution of a backward stochastic differential equation, Syst. Control Lett., 14 (1990) , 55-61.  doi: 10.1016/0167-6911(90)90082-6. E. Pardoux  and  S. Tang , Forward-backward stochastic differential equations and quasilinear parabolic PDEs, Probab. Theory Related Fields, 114 (1999) , 123-150.  doi: 10.1007/s004409970001. S. Peng , Probabilistic interpretation for systems of quasilinear parabolic partial differential equations, Stoch. Stoch. Repts., 37 (1991) , 61-74.  doi: 10.1080/17442509108833727. M. J. Ruijter  and  C. W. Oosterlee , Fourier-cosine method for an efficient computation of solutions to BSDEs, SIAM J. Sci. Comput., 37 (2015) , A859-A889.  doi: 10.1137/130913183. J. Shen  and  H. Yu , Efficient spectral sparse grid methods and applications to high dimensional elliptic problems, SIAM J. Sci. Comput., 32 (2010) , 3228-3250.  doi: 10.1137/100787842. J. Shen  and  H. Yu , Efficient spectral sparse grid methods and applications to high dimensional elliptic problems Ⅱ unbounded domains, SIAM J. Sci. Comput., 34 (2012) , A1141-A1164.  doi: 10.1137/110834950. S. A. Smolyak , Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl. Akad. Nauk SSSR, 4 (1963) , 240-243. H. M. Soner , N. Touzi  and  J. Zhang , Wellposedness of second order backward SDEs, Probab. Theory Related Fields,, 153 (2012) , 149-190.  doi: 10.1007/s00440-011-0342-y. T. Tang , W. Zhao  and  T. Zhou , Deferred correction methods for forward backward stochastic differential equations, Numer. Math. Theory Methods Appl., 10 (2017) , 222-242.  doi: 10.4208/nmtma.2017.s02. D. Xiu  and  J. S. Hesthaven , High-order collocation methods for differential equations with random inputs, SIAM J. Sci. Comput., 27 (2005) , 1118-1139.  doi: 10.1137/040615201. G. Zhang , M. Gunzburger  and  W. Zhao , A sparse-grid method for multi-dimensional backward stochastic differential equations, J. Comput. Math., 31 (2013) , 221-248.  doi: 10.4208/jcm.1212-m4014. J. Zhang , A numerical scheme for BSDEs, Ann. Appl. Probab., 14 (2004) , 459-488.  doi: 10.1214/aoap/1075828058. W. Zhao , L. Chen  and  S. Peng , A new kind of accurate numerical method for backward stochastic differential equations, SIAM J. Sci. Comput., 28 (2006) , 1563-1581.  doi: 10.1137/05063341X. W. Zhao , Y. Fu  and  T. Zhou , New kinds of high-order multistep schemes for coupled forward backward stochastic differential equations, SIAM J. Sci. Comput., 36 (2014) , A1731-A1751.  doi: 10.1137/130941274. W. Zhao , Y. Li  and  G. Zhang , A generalized θ-scheme for solving backward stochastic differential equations, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012) , 1585-1603.  doi: 10.3934/dcdsb.2012.17.1585. W. Zhao , J. Wang  and  S. Peng , Error estimates of the θ-scheme for backward stochastic differential equations, Discrete Contin. Dyn. Syst. Ser. B, 12 (2009) , 905-924.  doi: 10.3934/dcdsb.2009.12.905. W. Zhao , G. Zhang  and  L. Ju , A stable multistep scheme for solving backward stochastic differential equations, SIAM J. Numer. Anal., 48 (2010) , 1369-1394.  doi: 10.1137/09076979X. W. Zhao , W. Zhang  and  L. Ju , A numerical method and its error estimates for the decoupled forward-backward stochastic differential equations, Commun. Comput. Phys., 15 (2014) , 618-646.  doi: 10.4208/cicp.280113.190813a. W. Zhao , W. Zhang  and  L. Ju , A multistep scheme for decoupled forward-backward stochastic differential equations, Numer. Math. Theory Methods Appl., 9 (2016) , 262-288.  doi: 10.4208/nmtma.2016.m1421.

Figures(2)

Tables(5)