Euler-Maruyama-Verfahren
Das Euler-Maruyama-Verfahren, oft auch Euler-Maruyama-Schema oder stochastisches Euler-Schema genannt, ist das einfachste Verfahren zur numerischen Lösung von stochastischen Differentialgleichungen. Es wurde erstmals in den 1950er-Jahren durch den japanischen Mathematiker Gisiro Maruyama untersucht und basiert auf dem von Leonhard Euler stammenden expliziten Euler-Verfahren zur Lösung gewöhnlicher (deterministischer) Differentialgleichungen.
Während das explizite Euler-Verfahren seit seiner Erfindung ständig verbessert und weiterentwickelt wurde (implizites Euler-Verfahren, Runge-Kutta-Verfahren, Mehrschrittverfahren) und selbst dadurch an praktischer Bedeutung verloren hat, ist Euler-Maruyama mangels entsprechender Alternativen noch immer das in der Praxis dominierende Verfahren.
Formulierung
Gegeben sei ein Wiener-Prozess <math>(W_t)_{t \geq 0}</math> sowie dazu folgendes stochastisches Anfangswertproblem (S-AWP):
- <math> \mathrm dS_t = a(t,S_t)\,\mathrm dt + b(t,S_t)\,\mathrm dW_t, \quad S_0=A</math>.
Zur Berechnung einer numerischen Näherungslösung auf dem Intervall <math>[0,T]</math> mit <math>T > 0</math> werden wie beim gewöhnlichen Euler-Verfahren diskrete Zeitpunkte
- <math>0 = t_0 < t_1 < \dots < t_n = T</math>
mit <math>t_k = k h</math> und Schrittweite <math>h = \tfrac{T}{n}</math>, <math>n \in \N</math> gewählt. Zusätzlich wird das stochastische Differential <math>\mathrm dW_t</math> durch die Zuwächse
- <math>\Delta W_k := W_{t_{k+1}} - W_{t_k}, \quad k = 0,\ldots,n-1</math>
ersetzt. Aus den Eigenschaften des Wiener-Prozesses folgt, dass die <math>\Delta W_k</math> unabhängig und normalverteilt mit Erwartungswert <math>0</math> und Varianz <math>h</math> sind.
Das Euler-Maruyama-Verfahren berechnet damit eine Approximation <math> \hat{S} </math> von <math>S</math> folgendermaßen:
- <math>\begin{align}
\hat{S}_0 &=A\,, \\ \hat{S}_{k+1} &= \hat{S}_k + a(t_k, \hat{S}_k)\cdot h + b(t_k, \hat{S}_k)\cdot \Delta W_k\quad k = 0,\ldots,n-1\,. \end{align}</math> Dann ist <math>\hat{S}_k</math> eine Näherung für <math>S_{t_k}</math>.
Konvergenz des Verfahrens
Das wichtigste theoretische Resultat bezüglich des Maruyama-Schemas beschreibt dessen starke Konvergenz (oder stochastische Konvergenz) gegen die gesuchte Lösung <math>S</math>: Eine Folge von stochastischen Prozessen <math>\left(S_t^{(n)}\right),\;0 \le t \le T, \;n \in \N </math> auf einem gemeinsamen Wahrscheinlichkeitsraum konvergiert definitionsgemäß stark mit Ordnung <math>q</math> gegen einen Prozess <math> (S_t), \;0 \le t \le T </math>, wenn es eine Konstante <math>c</math> gibt, so dass für alle <math>t \in [0,T]</math>:
- <math>E(|S_t^{(n)}-S_t|) \le c n^{-q} \;\;\forall t \in [0,T] </math>.
Im Falle des Maruyama-Schemas kann nun gezeigt werden: Die Diskretisierung <math> (\hat{S}_t) </math> konvergiert für <math>n \to \infty</math> stark mit Ordnung <math> \tfrac{1}{2} </math> gegen die Lösung <math>S</math> des S-AWP, wenn für alle reellen Zahlen <math>x</math> und alle positiven <math>s,t</math> die folgende Schranke gilt:
- <math>|a(s,x)-a(t,x)| + |b(s,x)-b(t,x)| \le K(1+|x|)\sqrt{(|t-s|)} </math>.
Von schwacher oder Verteilungskonvergenz mit Ordnung <math>q</math> spricht man hingegen, wenn für eine Konstante <math>c</math> gilt:
- <math>|E(f(S_t^{(n)}))-E(f(S_t))| \le c n^{-q} \;\;\forall t \in [0,T] </math>
für alle Funktionen <math>f</math>, die mindestens <math>(2q+2)</math>-mal stetig differenzierbar sind und deren sämtliche Ableitungen durch Polynome beschränkt sind.
Für hinreichend glatte Koeffizientenfunktionen <math>a</math> und <math>b</math> hat das Euler-Maruyama-Verfahren typischerweise die schwache Konvergenzordnung <math>q = 1</math>.
Bemerkungen
- Es gibt auch Lösungsverfahren höherer starker Ordnung als das Euler-Maruyama-Verfahren, etwa das Milstein-Verfahren, das meist Ordnung 1 erreicht. Diese Verfahren sind aber numerisch aufwändiger und resultieren nicht immer in einer schnelleren Konvergenz.
- Die oben angeführte Bedingung für die starke Konvergenz mit Ordnung 0,5 ist nur wenig strenger als die Bedingung an a und b, die die Existenz der Lösung S sicherstellt. Sie ist also beinahe immer erfüllt.
- An starker Konvergenz ist man in der Praxis nur sehr selten interessiert, da zumeist nicht eine spezielle Lösung zu einem speziellen Wiener-Prozess gesucht wird, sondern vielmehr eine Stichprobe aus der Wahrscheinlichkeitsverteilung des Prozesses, wie man sie beispielsweise für Monte-Carlo-Verfahren benötigt.
- Ein implizites Maruyama-Schema als Analogon zum impliziten Euler-Verfahren ist nicht möglich; dies liegt an der Definition des (stochastischen) Ito-Integrals, über das stochastische Differentialgleichungen definiert sind und das Funktionen immer am Anfang eines Intervalls auswertet (siehe dort). Implizite Verfahren konvergieren also hier gegen teilweise völlig falsche Ergebnisse.
- Die übliche Simulation einer brownschen Bewegung durch eine Gaußsche Irrfahrt kann als Anwendung des Euler-Maruyama-Schemas auf die triviale Differentialgleichung <math>\mathrm dS_t =1\,\mathrm dW_t, \;\;S_0=0 </math> interpretiert werden.
Beispiel
Der folgende Beispielcode zeigt die Implementierung des Euler-Maruyama-Verfahrens zur Berechnung des Ornstein-Uhlenbeck-Prozesses als Lösung des Anfangswertproblems <math> dY_t=\theta \cdot (\mu-Y_t)dt + \sigma dW_t,\;\;Y_0=IC</math> in Python (3.x):
<syntaxhighlight lang="python"> import numpy as np import matplotlib.pyplot as plt
tBegin=0 tEnd=2 dt=.00001
t = np.arange(tBegin, tEnd, dt) N = t.size IC=0 theta=1 mu=1.2 sigma=0.3
sqrtdt = np.sqrt(dt) y = np.zeros(N) y[0] = IC for i in range(1,N):
y[i] = y[i-1] + dt*(theta*(mu-y[i-1])) + sigma*np.random.normal(loc=0.0,scale=sqrtdt)
fig, ax = plt.subplots() ax.plot(t,y) ax.set(xlabel='t', ylabel='y',
title='Euler-Maruyama-Verfahren zur Berechnung eines \n Ornstein-Uhlenbeck-Prozesses mit $\\theta=1$, $\mu=1.2$, $\sigma=0.3$')
ax.grid() plt.show() </syntaxhighlight>
Literatur
- Paul Glasserman: Monte Carlo Methods in Financial Engineering. Springer 2003, ISBN 0-387-00451-3