Runge-Kutta methods for sdes

* A Brief Introduction to Stochastic Differential Equations *

Runge-Kutta methods for sdes

This Taylor expansion of strong solutions of sdes can be employed to develop Runge-Kutta algorithms and other integration schemes.

For simplicity consider the case of autonomous equations. Define $f_j({\bf X}_t)$ for j = 1,..., n via

$\begin{eqnarray} f_j({\bf X}_t)&=&\frac{\partial X^j_t}{\partial t}\Delta t+\sum... ...number \\ &+&\sum_{k=1}^mb^j_k({\bf X}_t) \Delta W^k_t.\nonumber \end{eqnarray}$

The displaced solution $\bf X_{{t_{i+1}}}^{}$ = $\bf X$ (t_i + $\Delta$ t, W¹_{t_i} + $\Delta$ W_{t_i}¹,..., W^m_{t_i} + $\Delta$ W_t^m) can be expanded in a Taylor series about the initial solution $\bf X_{{t_i}}^{}$ = $\bf X$ (t_i, W¹_{t_i},..., W^m_{t_i}) using the formula

$\begin{eqnarray} {\bf X}_{t_{i+1}}&=&\exp\{\Delta t\frac{\partial}{\partial t}+\... ...ta W^k_t \frac{\partial}{\partial W^k_t}\}{\bf X}_{t_i}.\nonumber \end{eqnarray}$

It is convenient to rewrite the Taylor expansion in terms of $f_j({\bf X}_t)$ using

$\begin{eqnarray} \frac{\partial}{\partial t}&=&\sum_{l=1}^n\frac{\partial{ X}_{t... ... b^l_k({\bf X}_t)\frac{\partial}{\partial{ X}_{t_i}^l }.\nonumber \end{eqnarray}$

It then follows that

$\begin{eqnarray} \exp\{\Delta t\frac{\partial}{\partial t}+\sum_{k=1}^m \Delta W... ...{\sum_{l=1}^n f_l\frac{\partial}{\partial{ X}_{t_i}^l}\}\nonumber \end{eqnarray}$

and so the Taylor expansion can be equivalently expressed as

$\begin{eqnarray} {\bf X}_{t_{i+1}}&=&\sum_{k=0}^{\infty}\frac{1}{k!}\left[\sum_{... ...\partial}{\partial{ X}_{t_i}^l} \right]^k {\bf X}_{t_i}.\nonumber \end{eqnarray}$

By expressing the Taylor expansion in this form we can treat ordinary and stochastic differential equations in a unified way. All classical Runge-Kutta methods reproduce this Taylor expansion up to a certain number of terms. The terms following these serve as an estimate of the error. If the order of the error for some Runge-Kutta method is $\delta$ t to the exponent l for odes then the same method will be order l /2 for sdes.

Now Runge-Kutta methods can be developed in a straightforward way. Consider the following four stage method

$\begin{eqnarray} K_j^1&=&f_j({\bf X}_{t_i})\nonumber \\ K_j^2&=&f_j({\bf X}_{t_... ..._i}+c_1{\bf K}^1+c_2{\bf K}^2+c_3{\bf K}^3+c_4{\bf K}^4 \nonumber \end{eqnarray}$

where $\alpha$ , $\beta$ , $\gamma$ and c_i are to be determined. Taylor expansion of $\bf X_{{t_{i+1}}}^{}$ about $\bf X_{{t_i}}^{}$ to order $\Delta$ t² then gives the result

$\begin{eqnarray} {\bf X}_{t_{i+1}}^j&=&{\bf X}_{t_i}^j+(c_1+c_2+c_3+c_4)f_j +(\a... ...}_{t_i}^l}\frac{\partial f_l}{\partial { X}_{t_i}^m}f_m.\nonumber \end{eqnarray}$

Here it is understood that f_j and their derivatives are evaluated at $\bf X_{{t_i}}^{}$ . The requirement that this expansion reproduce the exact Taylor expansion then yields the conditions

$\begin{eqnarray} c_1+c_2+c_3+c_4&=& 1\nonumber \\ \alpha c_2+\beta c_3 +\gamma ... ...^2 c_4 &=&1/8\nonumber \\ \alpha\beta\gamma c_4&=&1/24.\nonumber \end{eqnarray}$

It can be readily verified that c₁ = 1/6 = c₄, c₂ = 1/3 = c₃, $\alpha$ = 1/2 = $\beta$ , $\gamma$ = 1 is a solution.

This procedure generalized to the non-autonomous case gives the classic fourth order Runge-Kutta scheme with four stages

$\begin{eqnarray} K_j^1&=&f_j({\bf X}_{t_i},t_i)\nonumber \\ K_j^2&=&f_j({\bf X}... ...}+\frac{1}{6}({\bf K}^1+2{\bf K}^2+2{\bf K}^3+{\bf K}^4)\nonumber \end{eqnarray}$

where

$\begin{eqnarray} f_j({\bf X}_t,t)&=&\frac{\partial X^j_t}{\partial t}\Delta t+\s... ...mber \\ &+&\sum_{k=1}^mb^j_k({\bf X}_t,t) \Delta W^k_t.\nonumber \end{eqnarray}$

Here t_i is the initial time and t_i+1 = t_i + $\Delta$ t.

Thus, it is possible to develop Runge-Kutta type schemes which reproduce the Taylor expansion of the solution to some given order. Fixed step-size Runge-Kutta methods are neither accurate nor efficient for general systems of equations. We need some means of controlling the local error. Hence ANISE, which is based on this sort of Taylor expansion, is implemented with variable step sizes such that local error can be internally minimized.

Top Next

* Innovative Stochastic Algorithms *