An High Accurate Numerical Method For Solving Backward Stochastic Differential Equations

In this thesis, we consider the numerical solution of the following backward stochas-tic differential equation (BSDE): where T is a fixed positive number, Wt is the standard d-dimensional Brownian motion defined on some complete, filtered probability space (Ω,F, P,{Ft}0≤t≤T), f{t,yt,zt) is an adapted stochastic process with respect to {Ft} (0≤t≤T) for each real pair {y,z), andζis an {FT} measurable random variable. The linear form of BSDEs was first introduced in [36]. The existence and uniqueness of the solution of the backward stochastic differential equation (1) are originally proved by Pardoux and Peng in [25] in 1990. Since then BSDEs and their solutions have been extensively studied by many re-searchers. In [27], Peng obtained a direct relation between forward-backward stochastic differential equations(FBSDEs) and partial differential equations, and then in [26], he also found the maximum principle for the stochastic control problems. Many important properties of BSDEs and their applications in finance were studied by Karoui, Peng and Quenez in [15]. An important concept of g-expectation was introduced in [28] for the solutions of BSDEs, and subsequently it was found in [13] that a dynamic coherent risk measure can be valued by a properly defined g-expectation.While analytic solutions of BSDEs are often very difficult to obtain, approximate numerical solutions of BSDEs are relatively easier to compute and so become highly desired in practical applications. There are mainly two families of numerical methods for solving BSDEs. One is proposed based on the relation between the target BSDE and the corresponding parabolic PDE. A typical four step method for studying FBSDEs was first developed in [18] using this relation. Based on similar ideas, some algorithms were proposed to numerically solve FBSDEs, see [11; 19; 20; 21; 23; 24; 33] for details. When the corresponding parabolic PDE is quasi-linear, Delarue and Menozzi proposed in [9] a special time-space forward-backward discretization scheme based on the theory of fully coupled FBSDEs, and later in [10] they improved the proposed scheme through an interpolation procedure.The other approach is developed directly based on the target BSDE [3; 4; 5; 7; 8; 9; 14; 22; 29; 32; 34; 35]. In [7], Chevance suggested an effective time-space discretization scheme when the function f does not depend on the variable zt. Bally proposed in [3] a numerical discretization when f depends on the variables yt and zt, where in partic-ular the time discretization is performed on a random net to overcome the difficulties of discretizing the stochastic integral. In [4] Bender and Denk introduced a forward scheme for solving BSDEs. In [29], Peng proposed an iterative linear approximation algorithm which converges under reasonable assumptions. Some random walk methods for solving BSDEs were suggested by Memin, Peng and Xu in [22] and convergences of those methods were also proven there. Cvitanic and Zhang proposed some Monte-Carlo methods for solving FBSDEs in [8], and then under certain weaker regularity assump-tions, Zhang developed a modified numerical scheme and studied its convergence rate in [32]. In [14], Gobet et. al. generalized Zhang's result, and obtained error estimates of the scheme measured in the strong Lp-sense (p≥1). Bouchard and Touzi also pre-sented an implicit scheme in [5] based on Zhang's work. Zhao et. al. proposed an numerical method calledθ-scheme with high accuracy for solving BSDEs in [34] and studied its error estimates in [35].Note that most of the numerical methods reviewed above for solving BSDEs are not of high accuracy due to the low accuracy of the approximation of the standard Brownian motion. Although the Monte-Carlo method could lead to a good accuracy based on sufficient scale of sampling points, the computational cost is not acceptable because the desired accuracy 1/(?) depends on the number of sampling points N. Theθ-scheme in [34], which is the most accurate scheme so far, is just a one-step method.In this thesis, we study the numerical methods for solving BSDEs in the following aspects.●Proposing a stable multi-step method for solving BSDEs. This method is constructed on time-space grids. The integrands, which are conditional mathe-matical expectations derived from the original equation, are approximated by using the Lagrange interpolating polynomials with values of the integrands at multi-time levels. In particular, they are then numerically evaluated using the Gauss-Hermite quadrature rules and polynomial interpolations on the spatial grid. Theoretically, in the sense of multi-step method, a scheme of arbitrary order can be obtained once the conditions are provided.●Proving the convergence of the semi-discrete scheme. When the generator f is independent of zt, we theoretically prove that the convergence of the semi-discrete scheme can be of high order depending on the number of time levels used.●Proposing an efficient scheme based on the multi-step scheme. Although the multi-step scheme is of high accuracy, it leads to expensive computation when using large number of time steps. The reason is that we apply Gauss-Hermite quadrature rule to approximate the conditional mathematical expectations with-out considering the properties of the standard Brownian motion. In other words, we don't consider how to construct a discrete stochastic process in our scheme to approximate the behavior of the standard Brownian motion. Therefore, we pro-pose an efficient scheme by constructing a new random walk, called Gauss-Hermite process, based on Gauss-Hermite quadrature rule. By the efficient scheme, the computation expense will be reduced significantly, at the same time, the accuracy of the numerical solution is not affected at all.●Proving the efficient scheme reaches the same accuracy as the multi-step scheme. By tracking the propagation of the errors in the efficient scheme, we can prove that if the time-space domain is reduced by a suitable proportion, the efficient scheme has the identical accuracy to the multi-step scheme while the computational expense is reduced significantly.●Parallelization of both schemes. In order to improve the efficiency of the computation, we combine the parallel techniques with our multi-step method in the implementation. Here we divide the whole job on each time level into several sub-jobs according to the number of available processors and then assign each sub-job to a processor and let them do the computations separately. After that, all the results of the sub-jobs are assembled by a control processor. Since our schemes can be easily localized, the computational job for each spatial point at the same time level is independent of other points once the data of the later time levels are ready to use. Thus, our schemes can be parallelized with high efficiency.The rest of the thesis is organized as follows.●Chapter 1:Background of backward stochastic differential equations; ●Chapter 2:A brief review of present methods for solving BSDEs:●Chapter 3:Proposing the multi-step method and obtaining the error estimation of the semi-discrete scheme;●Chapter 4:Proposing An efficient scheme for solving BSDEs and obtain the error estimation;●Chapter 5:Numerical Experiments and the investigation into parallelization of both schemes.