# Variable Step Size Adams Methods for BSDEs

Authors: Qiang Han
Journal: Journal of Mathematics
 (2021)

---

## Abstract

For backward stochastic differential equations (BSDEs), we construct variable step size Adams methods by means of Itô–Taylor expansion, and these schemes are nonlinear multistep schemes. It is deduced that the conditions of local truncation errors with respect toY and Z reach high order. The coefficients in the numerical methods are inferred and bounded under appropriate conditions. A necessary and sufficient condition is given to judge the stability of our numerical schemes. Moreover, the high-order convergence of the schemes is rigorously proved. The numerical illustrations are provided.


---

## Body

## 1. Introduction

In 1973, Bismut [1] introduced the linear BSDEs. Until 1990, the well-posedness result of nonlinear BSDEs was rigorously proved by Pardoux and Peng [2–4]. After boomingly developed for three past decades, BSDEs become a vital tool to formulate many problems such as mathematical finance [5], partial differential equations [4], actuarial and financial [6], risk measures [7], and finance [8]. However, the theory of nonlinear BSDEs indicates that a majority of nonlinear BSDEs do not have analytical solutions [9]. Thus, the main purpose of this paper is to design a new numerical scheme to solve the following BSDE:(1)Yt=ΦWT+∫tTfs,Ys,Zsds−∫tTZsdWs,where T>0 denotes a fixed terminal time and W is a d-dimensional Brownian motion defined on a filtered complete probability space Ω,ℱ,ℱt0≤t≤T,ℙ; ΦWT:ℝd⟶ℝm is a given terminal condition of BSDE, and ft,y,z:0,T×ℝm×ℝm×d⟶ℝm is the generator function. In addition, they satisfy the following.Assumption 1.
ft,Y,Z∈Cbk,k∈ℕ+, and ΦWT∈Cb1 where Cbk are the set of all k-times continuously differential functions with all partial derivatives bounded.
The papers with respect to numerical solutions of BSDEs are unlikely to list exhaustively because there is a vast literature. Therefore, we recommend milestone papers to readers with respect to time-discretization of BSDEs. The paper [10] was the first work of designing efficient algorithms for BSDEs. After that, a modified and implementable numerical scheme was adopted to calculate BSDEs in [11]. In the meantime, the Malliavin calculus and Monte Carlo methods were utilized by [12] to discretize BSDEs. The empirical regression method was constructed by [13] for BSDEs. The papers [14, 15] presented the θ-scheme to discretize BSDEs. The forward Picard iterations method was designed by [16]. The cubature method was used to solve BSDEs in [14, 17]. In [15], authors proposed the BCOS method based on the Fourier cosine series expansions to approximate the solutions of BSDEs. The stochastic grid binding method [18] was introduced to solve BSDEs. The authors in [19] proposed the branching diffusion method for BSDEs, and the branching techniques do not suffer from the curse of dimensionality. A deep learning method was constructed to solve BSDEs in [20, 21]. This method could also overcome the curse of dimensionality and deal with the numerical solutions of BSDEs via the Euler scheme under the condition of minimizing the global loss function. The papers [22, 23] improved the deep learning method via solving the fixed point problem.
If the Euler scheme (explicit, implicit, or generalized) is utilized to discretize BSDEs, the order of discretization error is1/2 (see [11, 13, 18, 24]). The θ-schemes [14, 15] are adopted to discretize BSDEs, and the corresponding rate of convergence is 2. To obtain higher-order schemes, the multistep schemes [16, 25–27] are developed to solve BSDEs.
From the above review, the time-discretization of BSDEs can adopt low-order schemes or high-order schemes. Notice that the Euler schemes, theθ-schemes, and the multistep schemes are constant variable step size. And there are a large number of documents about the constant variable step size schemes. This implies that the theory of implementable numerical methods of BSDEs is booming. The variable step size numerical methods play a vital role in the field of numerical methods of stochastic differential equations (see [28, 29]) while they are not seen in the field of numerical theory of BSDEs. Thus, for this motivation, this paper is to provide novel high-order nonlinear discretization schemes called variable step size Adams scheme (14) by utilizing Itô–Taylor expansion. Note that our high-order nonlinear scheme is always explicit with respect to Z. We provide conditions of local truncation errors with respect to Y and Z reaching high order (see Lemmas 3 and 4). Moreover, a sufficient and necessary condition for the stability of our schemes is derived (see Theorem 1). Finally, we derive the convergence of our schemes (see Theorem 3). To the best of our knowledge, this is the first attempt to come up with a variable step size numerical scheme for BSDEs. Note that the developed schemes can be also applied to solve decoupled forward-backward stochastic differential equations, and the forward stochastic differential equation can be approximated by using an appropriate scheme.
The main contributions are as follows. (i) We derive the variable step size Adams scheme for BSDEs by means of Itô–Taylor expansion. And this scheme is a novel high-order nonlinear time-discretization scheme. (ii) The stability and high-order discretization property of our schemes are rigorously proved. Note that we present a sufficient and necessary condition for the stability of our schemes. (iii) The constant variable one-step size schemes [11, 15, 18, 24] and the constant variable multistep size schemes [16, 26, 27] are the particular cases of our variable step size Adams scheme.
An outline of this paper is as follows. In Section2, we present two lemmas that can be used in the following sections. The variable step size Adams schemes of BSDEs are demonstrated in Section 3. Section 4 shows the stability and convergence of the variable step size Adams scheme. In Section 5, numerical experiments are carried out to illustrate the theoretical consequences. In the end, Section 6 is devoted to the conclusion of this paper.


## 2. Preliminaries

For readers’ convenience, here we present two lemmas which will be utilized in the sequel part.Lemma 1 (see [3, 4]).
Assume that functionsf and Φ are uniformly Lipschitz with respect to y,z and 1/2-Hölder continuous with respect to t. In addition, assume Φ is of class Cb2+κ for some κ∈0,1. Then, the solution Yt,Zt of the BSDE in (4) can be represented as(2)Yt=ut,Xt,Zt=∇xut,Xt,t∈0,T,where u∈Cb1,20,T×ℝd satisfies the parabolic PDE as follows:(3)ℒ0ut,x+ft,x,ut,x,∇xut,xσt,x=0,with the terminal condition uT,x=Φx where ℒ0=∂/∂t+1/2∑i,j=1d∂2/∂xi∂xj.For readers’ convenience, we introduce some symbols before providing the lemma. For a multi-index with finite lengthα, let ℓα be the length of a multi-index of α; Aα is the set of all functions v:0,T×ℝd⟶ℝ for which ℒαv is well defined and continuous; Abα denotes the subset of all functions v∈Aα such that the function ℒαv is bounded; for positive integer n, Abn is the set of functions v such that vα∈Abα for all α∈α|ℓα≤n∖⊘.Lemma 2 (see Proposition 2.2 in [30]).
Letn≥0. Then, for a function v∈Abn+1, Etvt+h,Xt+h=vt+hvt0+h2/2vt0,0+⋯+hn/n!vt0n+Ohn+1, where Et⋅=E⋅|ℱt; v0=ℒ0v,v0,0=ℒ0°ℒ0v,…, v0n=ℒ0°⋯°ℒ0︸nv.


## 3. Variable Step Size Adams Methods

In this part, we introduce the variable step size Adams schemes of BSDEs in detail.Now, we deduce the variable step size Adams schemes of BSDEs with respect toY. A discretization π=t0,t1,…,tN of the time interval 0,T is defined with step size hi=ti+1−tiandh=max0≤i≤N−1hi; then, we can restate the BSDE (1) as follows:(4)Yti=Yti+1+∫titi+1fs,Ys,Zsds−∫titi+1ZsdWs.Taking conditional expectations on both sides of (4), we get the result as follows:(5)Yti=EiYti+1+∫titi+1Eifs,Ys,Zsds,where Ei⋅=E⋅|ℱti. It is straightforward that the integrand Eifs,Ys,Zs in the above equation is a deterministic function of time s. Naturally, we can replace the function Eifs,Ys,Zs in (5) by using multistep methods through the support points tn,Eifn|n=i,i+1,…,i+k where k is a given positive integer and satisfies 0≤k<N, namely,(6)∫titi+1Eifs,Ys,Zsds=hi∑j=0kΓj,iEifti+j,Yi+j,Zi+j+Riy,where coefficients Γj,i depend on hi for i=N−1,…,0 and will be given soon; Riy=∫titi+1Eifs,Ys,Zs−∑j=0kΓj,iEifti+j,Yi+j,Zi+jds. Inserting (6) into (5), we obtain(7)Yti=EiYti+1+hi∑j=0kΓj,iEifti+j,Yi+j,Zi+j+Riy.Hence, the time-discretization ofY is, for i=N−k,N−k−1,…,0,(8)Yiπ=EiYi+1π+hi∑j=0kΓj,iEifti+j,Yi+jπ,Zi+jπ.In what follows, we demonstrate the expression with respect toZ. Multiplying (4) by ΔWi,n:=Wti+n−Wti,n∈ℕ+ and then taking conditional expectation on the derived equation, we obtain(9)0=EiYti+1ΔWi,1⊤+∫titi+1Eifs,Ys,ZsΔWi,s⊤ds−∫titi+1EiZsds,where ΔWi,s=Ws−Wti. Analogously, we approximate the two integral terms on right-hand side of (9) by the manner as calculating Yti, namely,(10)∫titi+1Eifs,Ys,ZsΔWi,s⊤ds=hi∑j=1kΓj,i∗Eifti+j,Yi+j,Zi+jΔWi,j⊤+R1,iz,(11)∫titi+1EiZsds=hi∑j=0kΓj,i∗∗EiZti+j+R2,iz,where R1,iz=∫titi+1Eifs,Ys,ZsΔWi,s⊤ds−hi∑j=1kΓj,i∗Eifti+j,Yi+j,Zi+jΔWi,j⊤ and R2,iz=∫titi+1EiZsds−hi∑j=0kΓj,i∗∗EiZti+j. Plugging (10) and (11) into (9), we deduce(12)0=EiYti+1ΔWi,1⊤+hi∑j=1kΓj,i∗Eifti+j,Yi+j,Zi+jΔWi,j⊤−hi∑j=0kΓj,i∗∗EiZti+j+Riz,where Riz=R1,iz−R2,iz. Hence, the time-discretization of Z is, for i=N−k,N−k−1,…,0,(13)Γ0,i∗∗EiZiπ=EiYi+1πΔWi,1⊤hi+∑j=1kΓj,i∗Eifti+j,Yi+jπ,Zi+jπΔWi,j⊤−∑j=1kΓj,i∗∗EiZi+jπ,Thus, from the two equations (8) and (13), we propose the explicit Adams schemes to solve BSDE (1) as follows.Giving the initial valuesYN−lπ,YN−lπl=0k−1, we solve random variables Yiπ,Ziπ for i=N−k,N−k−1,…,0 from(14)Yiπ=EiYi+1π+hi∑j=0kΓj,iEifi+jπ,0=EiYi+1πΔWi,1⊤hi+∑j=1kΓj,i∗Eifi+jπΔWi,j⊤−∑j=0kΓj,i∗∗EiZi+jπ,where fiπ=fti,Yiπ,Ziπ for i=N−1,N−2,…,0; coefficients Γj,i, Γj,i∗, and Γj,i∗∗ depend on hi for i=N−1,…,0.Remark 1.
IfΓ0,i=0, the scheme with respect to Y is explicit and Γj,i=Γj,i∗ for j=1,2,…,k. If Γ0,i≠0, the scheme with respect to Y is implicit and Γj,i=Γj,i∗∗ for j=1,2,…,k.


## 4. Theoretical Analysis

Before showing the stability and convergence analysis of the variable step size Adams scheme (14), we first provide a few lemmas.Lemma 3.
Under Assumption1, assume that the parameters Γj,i0≤j≤k satisfy the relation as follows:(15)1=∑p=0kΓp,i,q=1,1q=∑p=1k∑ℓ=0p−1hi+ℓq−1hiq−1Γp,i,q≥2.
Then,(16)Riy=Ohk,Γ0,i=0,Ohk+1,Γ0,i≠0.Proof.
By Assumption1, the integrand Etfs,Ys,Zs,s>t, is a continuous function with respect to s (see Theorem 2.2.1 of [31]). Then, by taking derivative with respect to s on(17)EtYs=EtΦWT+∫sTEtfs¯,Ys¯,Zs¯ds¯,∀s∈t,T,we obtain the following reference ordinary differential equation:(18)dEtYsds=−Etfs,Ys,Zs,s∈t,T.
Thus, from the definition ofRiy, we have(19)Riy=∫titi+1Eifs,Ys,Zs−∑j=0kΓj,iEifti+j,Yi+j,Zi+jds=Yti−EiYti+1−hi∑j=0kΓj,iEifti+j,Yi+j,Zi+j.
Substituting (18) into (19) and utilizing Itô–Taylor expansion at ti,Wti, we have(20)Riy=Eiuti−uti+1−hi∑j=0kΓj,ifti+j,Yi+j,Zi+j=Eiuti−uti+1+hi∑j=1kΓj,iuti+j0=Eihiuti0−1+Γ1,i+Γ2,i+⋯+Γk,i+hi2uti0,0−12+Γ1,i+hi+hi+1hiΓ2,i+⋯+∑ℓ=0k−1hi+ℓhiΓk,i+hi3uti0,0,0−16+12Γ1,i+hi+hi+12hi2Γ2,i+⋯+∑ℓ=0k−1hi+ℓ2hi2Γk,i+⋯+hiquti0q−1q!+1q−1!Γ1,i+hi+hi+1q−1hiq−1Γ2,i+⋯+∑ℓ=0k−1hi+ℓq−1hiq−1Γk,i+⋯=Eihiuti0−1+∑p=0kΓp,i+∑q≥2hqq!uti0q−1+q∑p=1k∑ℓ=0p−1hi+ℓq−1hiq−1Γp,i,where uti=uti,Wti. The conclusion is obvious with the help of equation (20). The proof is completed.Lemma 4.
Under Assumption1, assume that the parameters Γj,i0≤j≤k satisfy(21)1=∑j=0kΓj,i∗∗,0≠Γ0,i∗∗,1=∑j=1k∑ℓ=0j−1hi+ℓqhiqqΓj,i∗+Γj,i∗∗,q≥1.
Then,Riz=Ohk+1.Proof.
By Assumption1, the two integrands Etfs,Ys,ZsΔWt,s⊤ and EtZs, s>t, are continuous function of s (see Theorem 2.2.1 of [31]). Taking derivative with respect to s, we have the ordinary differential equation as follows:(22)dEtYsΔWt,s⊤ds=−Etfs,Xs,Ys,ZsΔWt,s⊤+EtZs,s∈t,T.
Thus,(23)RizΓ0,i∗∗hi=Zti−EiYti+1ΔWi,1⊤Γ0,i∗∗hi−∑j=1kΓj,i∗Γ0,i∗∗Eifti+j,Yi+j,Zi+jΔWi,j⊤+∑j=1kΓj,i∗∗Γ0,i∗∗EiZti+j=Zti−EiYti+1ΔWi,1⊤Γ0,i∗∗hi+∑j=1kΓj,i∗Γ0,i∗∗EiYti+jΔWi,j⊤0+∑j=1kΓj,i∗∗−Γj,i∗Γ0,i∗∗EiZti+j=Zti−1Γ0,i∗∗EiZti+1+∑j=1kΓj,i∗Γ0,i∗∗Eiti+j−tiZti+j0+Γj,i∗∗Γj,i∗Zti+j,where the last equality can be verified via relation (2) and integration by parts. Substituting (22) into (23) and utilizing Itô–Taylor expansion at ti,Wti, we have(24)RizΓ0,i∗∗hi=EiZti1−1Γ0,i∗∗+∑j=1kΓj,i∗∗Γ0,i∗∗+hiZti0−1Γ0,i∗∗+∑j=1k∑ℓ=0j−1hi+ℓΓ0,i∗∗hiΓj,i∗+Γj,i∗∗+hi22Zti0,0−1Γ0,i∗∗+∑j=1k∑ℓ=0j−1hi+ℓ2Γ0,i∗∗hi22Γj,i∗+Γj,i∗∗+hi36Zti0,0,0−1Γ0,i∗∗+∑j=1k∑ℓ=0j−1hi+ℓ3Γ0,i∗∗hi33Γj,i∗+Γj,i∗∗+⋯+hiqq!Zti0q−1Γ0,i∗∗+∑j=1k∑ℓ=0j−1hi+ℓqΓ0,i∗∗hiqqΓj,i∗+Γj,i∗∗+⋯=EiZti1−1Γ0,i∗∗+∑j=1kΓj,iΓ0,i∗∗+∑q≥1hiqq!Zti0q−1Γ0,i∗∗+∑j=1k∑ℓ=0j−1hi+ℓqΓ0,i∗∗hiqqΓj,i∗+Γj,i∗∗.
The conclusion is obvious with the help of equation (24). The proof is completed.
In what follows, we list the numerical expressions with respect toY and Z by utilizing Lemmas 3 and 4.(1)
IfΓ0,i=0, the numerical schemes of Y for k=1,2,3 with respect to time are(25)k=1,Yiπ=EiYi+1π+hiEifi+1π,k=2,Yiπ=EiYi+1π+hiEifi+1π+hi2hi+1fi+1π−fi+2π,k=3,Yiπ=EiYi+1π+hiEifi+1π+hi2hi+1fi+1π−fi+2π+2hi+3hi+16hi+hi+1hihi+hi+1hi+1+hi+2hi+1fi+1π−hihi+hi+1hi+1hi+2fi+2π+hihi+hi+1hi+1+hi+2hi+2fi+3π.(2)
IfΓ0,i≠0, the numerical schemes of Y for k=0,1,2 with respect to time are(26)k=0,Yiπ=EiYi+1π+hifiπ,k=1,Yiπ=EiYi+1π+hi2Eifiπ+fi+1π,k=2,Yiπ=EiYi+1π+hiEi2hi+3hi+16hi+hi+1fiπ+hi+3hi+16hi+1fi+1π−hi26hi+hi+1hi+1fi+2π.(3)
The numerical expressions with respect toZ are provided for k=0,1,2, namely,(27)k=0,Ziπ=EiYi+1πΔWi,1⊤hi,k=1,12Ziπ=EiYi+1πΔWi,1⊤hi+Eifi+1πΔWi,1⊤−12EiZi+1π,k=2,2hi+3hi+16hi+hi+1Ziπ=EiYi+1πΔWi,1⊤hi+Eifi+1πΔWi,1⊤+hi2hi+1fi+1πΔWi,1⊤−fi+2πΔWi,2⊤−Ei4hi+3hi+16hi+hi+1Zi+1π+hi26hi+1hi+hi+1Zi+1π−Zi+2π.Lemma 5.
If constraints (15) and (21) and hi/hi+j≤M,M∈0,+∞ are satisfied, then the coefficients Γj,i, Γj,i∗, and Γj,i∗∗ in scheme (14) are bounded.Proof.
From Lemma3, we know that the coefficients Γj,i are composed of products and sums of hi/hi+j for j=1,2,…,k. Under the condition hi/hi+j≤M, it is clear that the coefficients Γj,i are bounded. Analogously, we derive that coefficients Γj,i∗ and Γj,i∗∗ are bounded.
In what follows, two definitions are introduced to serve the stability of scheme (14).Definition 1.
The characteristic polynomials of (14) are given by(28)Pyζ=ζ−1,(29)Pzζ=ζk−1−∑j=0kΓj,iζk−j.
and Equation (14) is said to fulfil Dahlquist’s root condition if(i)
The roots ofPyζ and Pzζ lie on or within the unit circle(ii)
The roots on the unit circle are simpleDefinition 2.
LetYiπ,Ziπ,i=0,1,…,N−k, be the time-discretization approximate solution given by (14) and Y¯iπ,Z¯iπ be the solution of its perturbed form (see (31)). Then, scheme (14) is said to be L2-stable if(30)max0≤i≤N−kEYiπ−Y¯iπ2+Ziπ−Z¯iπ2≤CmaxN−k+1≤ℓ≤NEYiπ−Y¯iπ2+Ziπ−Z¯iπ2+∑ℓ=0N−kE|εℓY|2+|εℓZ|2,where C denotes a constant which changes from line to line; Y¯iπ,Z¯iπ satisfies a perturbed form of (14) for i=N−k,N−k−1,…,0:(31)Y¯iπ=EiY¯i+1π+hi∑j=0kΓj,iEif¯i+jπ+εiY,0=1hiEiY¯i+1πΔWi,1⊤+∑j=1kΓj,i∗Eif¯i+jπΔWi,j⊤−∑j=0kΓj,i∗∗EiZ¯i+jπ+εiZ,where f¯iπ=fti,Y¯iπ,Z¯iπ; sequences εiY and εiZ which belong to L2ℱi are random variables.
The following theorem is devoted to analyze the stability of scheme (14).Theorem 1.
Suppose Assumption1 and the condition of Lemma 5 hold. Then, the variable step size explicit Adams methods (that is, the coefficient Γ0,i=0) is numerically stable if and only if its characteristic polynomial (29) satisfies Dahlquist’s root condition.Proof (sufficiency).
LetΔYi=Yiπ−Y¯iπ,ΔZi=Ziπ−Z¯iπ,andΔfi=fti,Yiπ,Ziπ−fti,Y¯iπ,Z¯iπ for i=N−k,N−k−1,…,0. We complete the proof of the theorem in three steps.Step 1. From (14) and (31) with respect to Y, one obtains(32)ΔYi=EiΔYi+1+hi∑j=1kΓj,iΔfi+j−εiY.Furthermore,(33)ΔYi≤EiΔYi+1+hi∑j=1kΓj,iEiΔfi+j+εiYπ,≤EiΔYi+1+hiLf∑j=1kΓj,iEiΔYi+j+ΔZi+j+εiY,whereLf denotes the Lipschitz constant. Squaring equation (33), then from the inequalities ∑i=1nai2≤n∑i=1nai2 and a+b2≤δ1+δa2+1+1/δb2, δ>0, one deduces(34)ΔYi2≤EiΔYi+12+3+52hiLf∑j=1kΓj,iEiΔYi+j+ΔZi+j+εiY2≤EiΔYi+12+3+522k+1Lf2hi2max1≤j≤kΓj,i2∑j=1kEiΔYi+j2+ΔZi+j2+3+522k+1εiY2.Summing over the above inequality fromi to N−k, we have(35)ΔYi2≤EiΔYN−k+12+3+522k+1Lf2h2max1≤j≤kΓj,i2∑ℓ=iN−k∑j=1kEiΔYℓ+j2+ΔZℓ+j2+3+522k+1∑ℓ=iN−kεℓY2.Step 2. Subtracting (31) from (14) with respect to Z, we obtain(36)ΔZi=1Γ0,i∗∗hiEiΔYi+1ΔWi,1⊤+∑j=1kΓj,i∗Γ0,i∗∗EiΔfi+jΔWi,j⊤−∑j=1kΓj,i∗∗Γ0,i∗∗EiΔZi+j−εiZΓ0,i∗∗.By (2) and (3), one can verify that(37)EiYti+1ΔWi,1⊤hi=1hi2πhi∫−∞+∞uti+1,x+vve−v2/2hidv=12πhi∫−∞+∞∂u∂xti+1,x+ve−v2/2hidv=EiZti+1.Plugging (37) into (36), we have(38)ΔZi=1−Γ1,i∗∗Γ0,i∗∗EiΔZi+1−∑j=2kΓj,i∗∗Γ0,i∗∗EiΔZi+j+∑j=1kΓj,i∗Γ0,i∗∗EiΔfi+jΔWi,j⊤−εiZΓ0,i∗∗.We rearrange thek-step recursion to a one-step recursion as follows:(39)EiZi=EiAZi+1+Fi+Ri,where(40)Zi=ΔZiΔZi+1⋮ΔZi+k−1,A=1−Γ1,i∗∗Γ0,i∗∗−Γ2,i∗∗Γ0,i∗∗⋯−Γk,i∗∗Γ0,i∗∗10⋱⋱10,Fi=∑j=1kΓj,i∗Γ0,i∗∗EiΔfi+jΔWi,j⊤0⋮0,Ri=−εiZΓ0,i∗∗0⋮0.To ensure the stability of thek-step scheme, the norm of the matrix A in equation (39) is not more than 1 (see Chapter III.4, Lemma 4.4 in [32]). This can be satisfied if the eigenvalues eigA of the matrix A make eigA≤1 and the eigenvalues are simple if eigA=1. In addition, the eigenvalues of A satisfy the root condition by Definition 1. By Dahlquist’s root condition, it is possible that there exists a nonsingular matrix D such that D−1AD2≤1 where ⋅2 denotes the spectral matrix norm induced by Euclidian vector norm in ℝk×m×d. Hence, we can choose a scalar product for A¯,A˜∈ℝk×m×d as A¯,A˜∗:=D−1A¯,D−1A˜=A¯⊤D−1⊤D−1A˜. And we have A¯∗2:=A¯,A¯∗ with the induced vector norm on ℝk×m×d. Let A∗=D−1AD2 be the induced matrix norm. Owing to the norm equivalence, we know that there exist positive constants c1andc2 such that(41)c1A¯22≤A¯∗2≤c2A¯22,∀A¯∈ℝk×m×d,whereA¯22=∑j=1,2,…,maj2 for A¯=a1⊤,…,am⊤⊤. Applying ⋅∗ to equation (39), we have(42)EiZi∗=EiAZi+1+Fi+Ri∗=A∗EiZi+1∗+EiFi∗+EiRi∗≤EiZi+1∗+EiFi|∗+EiRi∗.Squaring equation (42), then from the inequalities ∑i=1nai2≤n∑i=1nai2 and a+b2≤δ1+δa2+1+1/δb2, δ>0, one deduces(43)EiZi∗2≤EiZi+1∗2+3+52EiFi∗+EiRi∗2≤EiZi+1∗2+k+1c23+52∑j=1kEiΓj,i∗Γ0,i∗∗Δfi+jΔWi,j⊤2+k+1c23+5/2Γ0,i∗∗2EiεiZ2.By the Lipschitz condition off with respect to y,z, (43) can be restated as(44)EiZi∗2≤EiZi+1∗2+k+1c23+52Lf2∑j=1kΓj,i∗Γ0,i∗∗2EiΔYi+j+ΔZi+jΔWi,j⊤2+k+1c23+5/2Γ0,i∗∗2EiεiZ2.By the Cauchy–Schwarz inequality, we have the following estimates:(45)EiZi∗2≤EiZi+1∗2+3+52kk+1c2Lf2hmax1≤j≤kΓj,i∗2Γ0,i∗∗2∑j=1kEiΔYi+j2+ΔZi+j2+k+1c23+5/2Γ0,i∗∗2EiεiZ2.Summing over the above inequality fromi to N−k, we have(46)EiZi∗2≤EiZN−k+1∗2+3+52kk+1c2Lf2hmax1≤j≤kΓj,i∗2Γ0,i∗∗2∑ℓ=iN−k∑j=1kEiΔYℓ+j2+ΔZℓ+j2+k+1c23+5/2Γ0,i∗∗2∑ℓ=iN−kEiεℓZ2≤EiZN−k+1∗2+3+52kk+1c2c1Lf2hmax1≤j≤kΓj,i∗2Γ0,i∗∗2∑ℓ=iN−k∑j=1kc1EiΔYℓ+j2+∑ℓ=i+1N−k+1EiZℓ∗2+k+1c23+5/2Γ0,i∗∗2∑ℓ=iN−kEiεℓZ2.Step 3. Adding (35) to (46), we obtain(47)ΔYi2+EiZi∗2≤Ch+h2∑ℓ=i+1N−k+1EiΔYℓ2+Zℓ∗2+C∑ℓ=N−k+1NEiΔYℓ2+Zℓ2+3+522k+1∑ℓ=iN−kεiY2+k+1c23+5/2Γ0,i∗∗2∑ℓ=iN−kEiεℓZ2.
From the discrete Gronwall inequality, we have(48)ΔYi2+EiZi∗2≤Cmaxi+1≤ℓ≤N−k+1khEiΔYℓ2+Zℓ∗2+∑ℓ=N−k+1NEiΔYℓ2+Zℓ2+∑ℓ=iN−kEiεℓY2+εℓZ2.
Moreover,(49)max0≤i≤N−kEΔYi2+ΔZi2≤CmaxN−k+1≤ℓ≤NEΔYℓ2+ΔZℓ2+∑ℓ=0N−kEεℓY2+εℓZ2.
Necessity. The proof is analogous to ordinary differential equations (see Theorem 6.3.3 in [33]). So, we omit it.Theorem 2.
Suppose Assumption1 and the condition of Lemma 5 hold. Then, the variable step size implicit Adams methods (that is, the coefficient Γ0,i≠0) is numerically stable if and only if its characteristic polynomial (29) satisfies Dahlquist’s root condition.Proof.
The proof of this theorem is analogous to that of Theorem1. Thus, we omit it here.
Next, the convergence property of scheme (14) is given in the theorem as below.Theorem 3.
Suppose Assumption1 and the condition of Lemma 5 hold. Let Yti,Zti and Yiπ,Ziπ be solutions of the BSDE in (1) and solutions of the variable step size Adams methods (14), respectively. The terminal values satisfy EsupN−k<i≤NYiπ−Yti2+Ziπ−Zti21/2≤Chk. Then, as h is small enough,(50)Esup0≤i≤N−kYiπ−Yti2+Ziπ−Zti212≤Chk,where C is a constant changing from line to line.Proof.
The proof is obvious with the help of Theorem1 and Lemmas 3 and 4.


## 5. Numerical Experiments

In this section, we demonstrate the theory results of scheme (14) via numerical examples. First, we choose a method to approximate the conditional mathematical expectations numerically. Among the popular methods, we focus on the least squares Monte Carlo (LSMC) method (see [13, 27]). Next, we review how to approximate mathematical expectations by the LSMC method.Fori∈0,1,…,N, let Ci:=Wi,m˜:m˜=1,2,…,M˜∈ℕ+ be independently generated copies of Wti. The empirical probability measure of the Ci-simulations is denoted by νi,M˜=1/M˜∑m˜=1M˜δWi+1i,m˜,…,Wi+ki,m˜ where δx is the Dirac measure on x. Denote by KY,i and KZ,i vector spaces of functions, i.e., KY,i:=spanpY,i1,pY,i2,…,pY,iKY,i where KY,i is a nonnegative integer; pY,ik:ℝd⟶ℝm such that EpY,ikWi2<+∞; KZ,i:=pZ,i1⋅,pZ,i2⋅,…,pZ,iKZ,i⋅ where KZ,i is a positive integer; pZ,ik:ℝd⟶ℝm×d such that EpZ,ikXi2<+∞. From ordinary least squares, numerical solutions Yiπ,M˜ and Ziπ,M˜ are obtained by the following manner:(51)Yiπ,M˜=arginfϕ∈KY,i1M˜∑m˜=1M˜ϕWim˜−SY,i2,(52)Ziπ,M˜=arginfϕ∈KZ,i1M˜∑m=1M˜ϕWim˜−SZ,i2,where SZ,i=Yi+1π,M˜ΔWi,i+1⊤/Γ0,i∗∗hi+∑j=1kΓj,i∗/Γ0,i∗∗fti+j,Yi+jπ,M˜,Zi+jπ,M˜ΔWi,i+j⊤−∑j=1kΓj,i∗∗/Γ0,i∗∗Zi+jπ,M˜ and SY,i=Yi+1π,M˜+hi∑j=0kΓj,ifti+j,Yi+jπ,M˜,Zi+jπ,M˜.To obtain the numerical solutions of BSDE (1.1), we have to determine the parameters in the numerical scheme (14). The coefficientsΓj,i, Γj,i∗, and Γj,i∗∗ are obtained by means of Lemmas 3 and 4 as the value of k is given. In what follows, we discuss the numerical schemes according to the following two cases with the nonuniform time grid ti=T1−1−i/N2:(53)Yiπ=EiYi+1π+hiEifi+1π,Ziπ=EiYi+1πΔWi,1⊤hi,(54)Yiπ=EiYi+1π+hiEifi+1π+hi2hi+1fi+1π−fi+2π,12Ziπ=EiYi+1πΔWi,1⊤hi+Eifi+1πΔWi,1⊤−12EiZi+1π.To compare the performance of scheme (53) and scheme (54), we also provide the corresponding constant variable step numerical schemes, namely,(55)Yiπ=EiYi+1π+hEifi+1π,Ziπ=EiYi+1πΔWi,1⊤h,(56)Yiπ=EiYi+1π+hEi32fi+1π−12fi+2π,12Ziπ=EiYi+1πΔWi,1⊤h+Eifi+1πΔWi,1⊤−12EiZi+1π,where the constant step size h=T/N. Before we apply our scheme (14) to the following BSDEs, we first introduce the notations. Let N be the number of time points; M˜ represents the number of simulation paths. The basis functions which are spanned by polynomials whose degree is less than or equal to the order of discretization error are applied to compute the value of Yiπ,M˜. The error of both the numerical solution and the exact solution of the BSDE (1) at the time t=0 is denoted by Y0−Y0π,M˜.andExample 1.
Consider the BSDE as follows:(57)Yt=1+η+sinτ1d⊤WT+∫tTmin1,Ys−η−1−sinτ1d⊤Wsexpτ2dT−t/22ds−∫tTZsdWs,which appears in [26] and is used to illustrate the variance reduction problem with closed-form solutions. Here, η>0; τ>0; 1d is a d-dimensional vector with components all 1. Now, the solution to the above BSDE is(58)Yt=1+η+sinτ1d⊤Wtexpτ2dT−t/2.
TakeT=1,η=0.6,τ=1/d,d=9,andM˜=100000.
Figure1 presents the relationship of the absolute error between the numerical solution and the exact solution of BSDE (57) with respect to Y at time 0 and the number of time points via the variable step size scheme (53), the variable step size scheme (54), the constant variable step size scheme (55), and the constant variable step size scheme (56). To be specific, Figure 1 implies that (i) on the whole, the error of Y becomes smaller as N gets bigger in scheme (53), scheme (54), scheme (55), and scheme (56); (ii) if the the absolute error Y0−Y0π,M˜π is fixed, the number of steps of the constant variable step size schemes is bigger than that of the variable step size schemes; and (iii) the absolute error with respect to Y obtained by schemes (54) and (56) is smaller than the absolute error of Y obtained by schemes (53) and (55).Figure 1
Log2Y0−Y0π,M˜ versus log2N.Example 2.
We consider the BSDE as follows:(59)Yt=expT+∑k=1dWk1+expT+∑k=1dWk+∫tT∑k=1dZk,sYs−2+ddds−∫tTZsdWs.
Therefore, the exact solutions of BSDE (59) can be represented in the following form:(60)Yti=expti+∑k=1dWk1+expti+∑k=1dWk.
TakeT=1,d=5,andM˜=100000.
Figure2 presents the relationship of the absolute error between the numerical solution and the exact solution of BSDE (59) with respect to Y at time 0 and the number of time points via the variable step size scheme (53), the variable step size scheme (54), the constant variable step size scheme (55), and the constant variable step size scheme (56). Figure 2 implies that the variable step size schemes possess almost the same convergence rates as the constant variable step size scheme, but the number of steps of the variable step size schemes is smaller than that of the constant variable step size schemes.Figure 2
Log2Y0−Y0π,M˜ versus log2N.


## 6. Conclusions

We design in this article the variable step size Adams schemes to calculate the solution of BSDEs. To enrich the numerical schemes with high-order convergence, we infer the conditions with respect to the coefficients in the numerical method by means of Itô–Taylor expansion. We then provide a sufficient and necessary condition for the stability of our variable step size Adams schemes via Dahlquist’s root condition. The convergence of the proposed scheme is analyzed too. We illustrate the theory results of our numerical algorithms with two examples. Finally, note that the constant variable one-step size schemes [11, 15, 18, 24] and the constant variable multistep size schemes [16, 26, 27] are the particular cases of our variable step size Adams schemes.



---

*Source: 9799627-2021-12-09.xml*