Table of Contents
Go Back
High Strong Order Implicit Runge-Kutta Methods for
Stochastic Ordinary Differential Equations
by
G. Barid Loghmani
Department of Mathematics, Yazd University, Yazd, [RAN
E-mail: loghmani@yazduni.ac.ir
Abstract
The modelling of many real life phenomena for which either the parameter esti-
mation is difficult, or which are subject to random noisy perturbation, is often car-
ried out by using stochastic ordinary differential equations(SODEs). In this paper,
a class of high strong order implicit Runge-Kutta methods for SODEs is introduced.
Keywords: stochastic differential equations; rooted trees theory; Runge-Kutta
methods for ODEs and SODEs
AMS 2000 subject classification: 60H10, 65L06
1. Introduction
Consider the autonomous ordinary differential equation (ODE)
y(t) = f(y), ylto) =4o, yeR” (1)
The autonomous Jt6 stochastic version of (1) can be written in differential form as
dy = f(y)dt + g(y)dW, y(to)=yo, yeR™ (2)
Here f is an m-vector-valued function, g is an m xp matrix - valued function and W (¢)
is a p-dimensional process having independent scalar Wiener process components
(t > 0) , and the solution y(t) is an m-vector process. The integral formulation of
(2) can be written as
uit) = w+ f fluls)as+ f° aluls)av(s) (3)
where the second integral in (3) is an /¢6 stochastic integral (see[8,9]) with respect
to the Wiener process W(t). If the autonomous version of an Jt6 stochastic ordinary
differential equation (SODE) given by (2) then the related Stratonovich SODE is
given by 7
dy = f(y)dt + g(y)odW, y(to)=yo, yeR™, (4)
where
ly) = Flu) — 59" Wav.
In other words two differential equations (2) and (4) , under different rules of calcu-
lus, have the same solution. There are many different methods to solve these kinds
of differential equations (see, for example [9,10,11,12]).
An outline of this paper is as follows: In section 2 a discussion on Runge-Kutta
methods, especially implicit and semi-implicit Runge-Kutta methods for SODE,
based on rooted trees theory is introduced(see [6,7]). In section 3 a new class of
semi-implicit Runge-Kutta methods for SODE, is constructed. Numerical results
are reported in section 4.
2. Runge-Kutta Methods for SODE,
A sstage Runge-Kutta method for calculating a numerical approximation to the
solution of an autonomous ODE (1) is given by the recursive formula
Yo = mwthDayf(¥%) 1=1,2,...8
j=l
tout = Yn FHI OLY) 65)
j=l
which can be represented in tableau form:
In tableau (6) if we do not require that the numbers aj; for all i,j with j > i, are
zero, then the assaciated methods of this general type will be called implicit Runge-
Kutte methods, however if a;; = 0 for j > 7 the corresponding method known as an
explicit Runge-Kutta method and if aj; = 0 for j > i, the corresponding method is
known as a semi-implicit or semi-explicit Runge-Kutta method(see[7]).
For an autonomous Stratonovich SODE (4) we obtain by a straight forward
generalization of (5) the class of methods
s
Y= Yn +h ay f(¥j) + Ad bi g(¥)) i=1,2,...,8
j=l
j=l
Yast = Ym th aif(¥j) + AY 9%), (7)
j=l j=l
where J; = ie odW is the increment of the Wiener process from t,, to tn41. which
can be represented in the tableau form:
@1 a2... Ms bu big... dis
dz. @22—« as | bor bons. as
Dd: (8)
Gg gn + gy | Dg Dgn_—--- Oss
| a, AQ .-. As | io | ne pce
Theorem 1:A stochastic Runge-Kutta method of the form (7) has maximum strong
order 1.5, for any number of stages s. The methods with optimal principal error
coefficients is of strong order 1.5,if:
a™(e,b) = (1,4),
77 (e,c,b,b?, Bb) = (1, a3 "
Here e? = (1,...,1), c= Ae, b= Be.
Proof: see{4].
To break this order barrier, the class of methods (7) has to be modified in some
way so as to include further multiple stochastic integrals (see[4]) of the stochastic
Taylor formula apart from just J;. This has been done by K. Burrage and P.M.
Burrage (see[2]). They proposed the following class of methods:
Y= mt hDayf+ COPA +029) 4=1,2...048
j=l j=l iG
“aa 1
Yost = Wot hYayf(%) + WOP A +1?) 9%), (9)
j=l j=l a
where J, = fe" odW and Jig = fo J? odW,,ds2. which can be represented in
tableau form:
au 42 «+. ts wD wy oo oD OU Det coe oy
gi gq «ss Aas oh? oY aoe 04? Du 0 Re of?
aa z | 3 : (10)
sr dsp Os | OW WD 0D.
a ag. Oy | AD [PP ag
The rest of this section is concerned with the problem of determining the strong
order of convergence of stochastic Runge-Kutta methods (9). In the case of Runge-
Kutta methods for deterministic problems the order of accuracy is found by com-
paring the Taylor series expansion of the approximate solution to the Taylor series
expansion of the exact solution over one step assuming exact initial values.In 1963
Butcher introduced the theory of rooted trees in order to compare these two Taylor
series expansion in a systematic way (see[7]).K. Burrage and P.M. Burrage have
extended this idea of using rooted trees to the stochastic setting. They used the set
of bi-coloured rooted trees, i.e., the set of rooted trees with e (7 for deterministic)
and o (¢ for stochastic) nodes to derive a Stratonovich Taylor series expansion of
the exact solution and a Stratonovich Taylor series expansion of the approximation
defined by the numerical method (9). By comparing these two expantion, they could
prove the following theorem:
Theorem 2: The stochastic Runge-Kutta method (9) is of stronge order 2,if:
a™ (d,b) = (1,0),
YT (6, b?, BY, d?, Bd) = (1,4, t, -2y@ bd, —y)7(BOb+ BY d)),
7)? (6, b?, BYb, d?, BOd) = (—1, -2yT bd, -—y)? (Bb + BOd), 0,0).
Here e7 = (1,..., 1), c= Ae, b= BMe,d = Be.
Proof: see{4].
3. Implicit and Semi-Implicit Runge-Kutta Methods for
SODE,
In 2000 the author and Prof.M. Mohseni generalized the explicit methods satisfy-
ing (7) were derivation by K.Burrage and P.M. Burrage (see{2]) to semi-implicit
and implicit methods (see[1]). More precisely we used theorem 1 and introduced
the semi-implicit and implicit methods of strong order 1.5 with minimum principal
error.Semi-implicit 2-stage stochastic Runge-Kutta methods are shown in tableaux
(11-a) and (11-b), and were referred to ”SIM” class:
(3+ V3)/6 0 (3+ V3)/6 0
=v3/3 (3+ v3)/6 v3 /3 (3+ v'3)/6 (a) (11)
° (B+v3/6 0 |B—v3)6 0
=v3/3 (3+ v3)/6 v3/3 (3- V3)/6 (b)
Implicit 2-stage stochastic Runge-Kutta methods are shown in tableaux (12-a) and
(12-b), and were referred to ”IM” class:
z (3 — 2v3)/12 7 (3 — 2V3)/12
(3+2V3)/12 i (3 +2V3)/12 t (a) (12)
r (3 — 23) /12 i (3+ 2V3)/12
(3 +2V3)/12 a (3 — 2V3)/12 : (b)
i
In this section a semi-implicit stochastic Runge-Kutta method with strong order
2 will be constructed based on (9) and theorem 2 with s=3. Of course it is now
necessary to construct a family of methods satisfying in theorem 2. Some simple
analysis shows that this is not possible with s=2. In the semi-implicit case with
s=3 and throrem 2 we has 27 free parameters and there are 18 equations to be
solved. This system is solved using MAPLE and hence we conclude the following
semi-implicit stochastic Runge-Kutta method with strong order 2 which are shown
in tableau (13), and are referred to ”SIM3” class:
3 0 1
1 4 5 2
9 3 3 (0 378 (13)
% 9 ifo 4 stg 8 42
18 9. 9 6 6
| ior dg | as os | az Te
3 3 3 16 32 32 16 32 32
Certainly, it is possible to satisfy theorem 2 in the implicit case with s=3 or in the
semi-implicit and implicit case with s=4. But the large number of free parameters
makes solving the similar systems difficult.
4. Numerical Results
In this section,numerical results from the implementation of 5 methods are pre-
sented. These methods are ”PL”, ”R2”, ”SIM”, ”IM” and ”SIM3”. The first 4
methods taken from [1] and hence if g: ~ N(0, 1) and g2 ~ N(0, 1), then for stepsize
h, Jy = Vhg, and Fyo/h = Bg, + &)- The above methods will be implemented
with constant stepsize on two problems taken from [9], for which the exact solution
terms of a Wiener process is known. In order to improve the results of employing
the ”SIM”, IM” and ”SIM3” methods at each step, we use an iteration scheme [1]
with starting values come from the ”PL” or ”R2” methods.
For both problems and all methods, 500 trajectories are computed at each step-
size. The implementation determines the average error for each stepsize at the end
of the interval of integration for each method.
Test problem 1. ([8, equation 4.4.31])
dy = —a?y(1—y?)dt + a(L—y?)dW, y(0) = yo, t € (0,1),
with exact solution
y(t) = tanh(aW (t) + arctanh(yo))-
In Stratonovich form, the above SODE becomes
dy = a(1 — y’)odw-
Table 1: global errors for test problem1, a = 1,¢ = 0-001, N = 500
h PL R2 SIM IM SIM3
1/25 | 0- 034189 | 0 - 021000 | 0 - 001221 | 0 - 000775 | 0 - 000505
1/50 | 0- 017179 | 0 - 009935 | 0 - 000580 | 0 - 000324 | 0 - 000114
1/100 | 0 - 008061 | 0 - 004711 | 0 - 000297 | 0 - 000091 | 0 - 000068
1/200 | 0 - 003850 | 0 - 002343 | 0 - 000188 | 0 - 000038 | 0 - 000014
Table 2: global errors for test problem1, a = 0-5,¢ = 0-001, N = 500
h PL R2 SIM IM SIM3
1/25 | 0 003607 | 0 - 001469 | 0 - 000058 | 0 - 000021 | 0 - 000013
1/50 | 0 - 001808 | 0 - 000712 | 0 - 000032 | 0 - 000015 | 0 - 000010
1/100 | 0 - 000861 | 0 - 000330 | 0 - 000019 | 0 - 000011 | 0 - 000007
1/200 | 0 - 000428 | 0 - 000156 | 0 - 000010 | 0 - 000008 | 0 - 000002
oo} oc] co
Test problem 2. ([8, equation 4.4.46])
dy =—(a+ B’y)(1—y?)dt+B80—y?)dW, y(0)=yo, te (0,1),
with exact solution
y(t) = (1 + yo)exp(—2at + 20W (t)) + yo — L
w= (1+ yo)exp(—2at + 23W(t)) + 1— yo
In Stratonovich form, the above SODE has the form
dy = —a(1—y?)dt + B(1 — y?)odW-
Table 3: global errors for test problem2, a = 1-0,3 = 0-01,¢ = 0-001, N = 500
h PL R2 SIM IM SIM3
1/25 | 0- 007381 | 0- 000111 | 0 - 000007 | 0 - 000003 | 0 - 000000
1/50 | 0 - 003666 | 0 - 000027 | 0 - 000001 | 0 - 000000 | 0 - 000000
1/100 | 0 - 001827 | 0 - 000007 | 0 - 000000 | 0 - 000000 | 0 - 000000
1/200 | 0 - 000912 | 0 - 000001 | 0 - 000000 | 0 - 000000 | 0 - 000000
Table 4: global errors for test problem2, a = 1-0,3 = 2-0,¢ = 0-001, N = 500
h PL R2 SIM IM SIM3
1/50 | 0- 179303 | 0 - 143407 | 0 - 039636 | 0 - 029369 | 0 - 017451
1/100 | 0 - 083476 | 0 - 064094 | 0 - 013703 | 0 - 012442 | 0 - 009212
1/200 | 0 - 051587 | 0 - 039694 | 0 - 009300 | 0 - 007101 | 0 - 005013
1/400 | 0 - 022484 | 0 - 018316 | 0 - 003835 | 0 - 001939 | 0 - 000728
ofololo
5. Conclusions
In this paper, we have constructed an implicit Runge-Kutta method of strong order
2.
Our future work should be based on the construction of implicit Runge-Kutta
methods for SODE, with two or more Wiener processes.
References
[1] Barid Loghmani, G. and Mohseni, M. : On the Implicit and Semi-Implicit
Runge-Kutta Methods for Stochastic Ordinary Differential Equations, Italian
Jour, of Pure and Applied Maths,(to appear).
[2] Burrage, k. and Burrage, P.M. : High strong order explicit Runge-Kutta meth-
ods for stochastic ordinary differential equations, Applied Numer. Mathemat-
ics 22(1996), 81-101.
[3] Burrage, k. and Platen, E. : Runge-Kutta methods for stochastic differential
equations, Annals of Numer. Mathematics, 1(1994), 63-78.
[4] Burrage, P.M. : Runge-Kutta methods for stochastic differential equations,
Ph.D thesis, Dept. Maths., Univ. Queensland, Australia(1999).
[5] Butcher, J.C. : Coefficients for the study of Runge-Kutta integration processes,
J. Austral. Math. soc., 3(1963), 185-201.
[6] Butcher, J.C. : On Runge-Kutta processes of high order, J.Austral. Math. soc.,
4(1964), 179-194.
[7] Butcher, J.C. : The numerical analysis of ordinary differential equation, J.
Wiley, U.K(1987).
[8] Kloeden, P.E. and Platen, E. : Stratonovich and Jt6é Taylor expansions, Math.
Nachr. 151(1991), 33-50.
[9] Kloeden, P.E. and Platen, E. : Numerical solution of stochastic differential
equations, Springer, Berlin(1995).
[10] Kloeden, P.E. Platen, E. and Schurz, H. : Numerical solution of stochastic
differential equations throuth computer experiments, Spring-Verlag(1994).
[11] Mohseni, M., Barid Loghamani, G. : Hybrid Methods for Stochastic Ordinary
Differential Equations,Int. J. Appl. Math,Vol 8,No 4(2001), 395-416.
[12] Mohseni, M., Barid Loghamani, G. : On the Euler-Maruyama and Milstein
methods for approximation of stochastic differential equations, Thirty first
Iranian mathematics conference, Tehran, Univ(2000).
t
Back to the Top
