Monte-Carlo Integration

Häufig trifft der Naturwissenschaftler bei seiner täglichen Arbeit auf Integrale. Einige sind leicht zu lösen, für andere, insbesondere mehrdimensionale, ist jedoch ein erheblicher Aufwand nötig. Einige sind so komplex, dass sie letztendlich überhaupt nicht mehr lösbar sind. Schon früh entstanden erste Methoden mit denen es möglich war die Lösung an ein Integral zumindest anzunähern. Mit dem Einzug der Mathematik in das Computerzeitalter wurde vieles einfacher. Zwar blieben Integrale immer noch schwer zu lösen, Näherungen konnten dank der Rechenleistung des Computers jedoch beliebig genau werden. Alles was es dazu brauchte war Rechenleistung und Zeit. Eine, in letzer Zeit immer beliebter gewordene, Methode zur Lösung von mehrdimensionalen Integralen ist die Monte-Carlo Integration.

Die Monte-Carlo Integration beruht auf zufällig verteilten Stichproben. Je mehr, desto besser. Daher auch der Name, der auf die Spielbank in Monte-Carlo beruht, bei welcher auch der Zufall entscheidet.
Betrachten wir zunächst ein Einfaches Integral I der Funktion g(x).
Dieses Integral kann auch faktorisiert in der Form
geschrieben werden, wobei π(x) eine Dichtefunktion darstellt, deren Integral immer 1 ergibt. Denkbar wäre hier im einfachsten Falle eine Gleichverteilung in den Grenzen des zu lösenden Integrals.
Mit f(x) ist es nun möglich das eigentliche Integral I zu approximieren. Das ganze geschieht indem sehr viele zufällige Samples gemäß der Verteilung π(x) gezogen werden und daraus der Mittelwert der Funktionswerte gebildet wird.
Das ganze lässt sich gedanklich etwas schwer nachvollziehen. Am besten kann man es mit einem einfachen Beispiel verdeutlichen. Nehmen wir an wir möchten den Flächeninhalt der Funktion g(x) = 5 in den Grenzen von 0 bis 2 berechnen dann benötigen wir zuerst eine Wahrscheinlichkeitsverteilung für π(x), welche π(x) = 0.5 wäre, da das Integral von 0 bis 2 wieder 1 ergibt. f(x) wäre in diesem also Fall 10.
mit
In diesem einfachen Beispiel reicht ein einziger Sample aus um auf das Ergebnis zu kommen. Es ist dabei auch völlig Egal wo dieser liegt, da sein Wert immer 10 ist. Mit drei Samples haben wir beispielsweise
was haargenau dem Integral von g(x) entspricht.
Zugegeben, das ganze war etwas einfach, hat jedoch das Vorgehen bei der Monte-Carlo Integration gut verdeutlicht. Als nächstes nehmen wir ein etwas schwierigeres Integral, x² in den Grenzen von 0 bis 1, dessen Wert 0.3333... entspricht und schauen wie gut wir diesen annähern können.
π(x) nehmen wir der Einfachheit halber wieder als gleichverteilt in den Grenzen von 0 bis 1 an und erhalten für f(x)
Wir müssen also nur den Mittelwert von zufällig gewählten Quadratsummen im Intervall 0 bis 1 berechnen.
Ich hab das in folgender Tabelle einmal für unterschiedliche N in Matlab gemacht:

N = 100 I = 0,3479
N = 1000 I = 0,3430
N = 10000 I = 0,3322
N = 100000 I = 0,3337
N = 1000000 I = 0,3336

Gut zu erkennen ist, dass sich der geschätzte Wert immer weiter dem richtigen Wert annähert, jedoch ein erheblicher Rechenaufwand dafür nötig ist. Niemand möchte 1.000.000 Quadratsummen per Hand berechnen. Die Monte-Carlo Integration ist also durchaus hilfreich, liefert jedoch nur Schätzwerte. Die Fehler approximieren proportional zu
was bedeutet, dass der Aufwand quadratisch ansteigt.
Bookmark and Share

0 Kommentare:

Kommentar veröffentlichen