Monte-Carlo-Integration

Die direkte Monte-Carlo-Integration kann auch als randomisierte Quadratur bezeichnet werden, die englische Bezeichnung ist crude Monte-Carlo. Dabei werden im Definitionsbereich einer Gleichverteilung folgend zufällige Werte erzeugt; die zu integrierende Funktion f wird an diesen Stellen ausgewertet. Anschließend wird der Mittelwert dieser Funktionswerte gebildet und mit der Breite des Definitionsbereiches multipliziert. Dieser Wert wird dann zur Schätzung des Integrals verwendet. Im Vergleich zur numerischen Integration werden also die deterministischen Stützstellen durch zufällige ersetzt. Angesichts der Approximationsgüte numerischer Quadraturverfahren mag es verwundern, dass es Verfahren wie die Monte-Carlo-Integration überhaupt gibt. In der Tat lässt sich beim Testen des Verfahrens auch schnell sehen, dass gegenüber der numerischen Quadratur normalerweise viel mehr Stützstellen gebraucht werden, um ein vergleichbar gutes Resultat zu erzielen.

Im Gegensatz zu numerischen Quadratur-Verfahren kann die Idee der Monte-Carlo-Integration sehr einfach auf die Berechnung hochdimensionaler Integrale übertragen werden. Dort hat die Monte-Carlo-Integration gegenüber numerischen Integrationsverfahren Vorteile und wird daher auch heute noch eingesetzt.

Einen weiteren Unterschied zur numerischen Integration stellt die Form der Konvergenz dar. Bei der numerischen Quadratur gibt es Fehlerabschätzungen, d.h. obere Schranken für die Abweichung zwischen dem tatsächlichen Wert des Integrals und der berechneten Approximation. Diese Schranken streben für feiner werdende Zerlegungen des Definitionsbereiches gegen 0. Bei der Monte-Carlo-Integration wird das zu berechnende Integral durch einen zufälligen Wert geschätzt. Es lässt sich zeigen, dass der Erwartungswert dieses Schätzers der exakte Wert des Integrals ist, und dass die Varianz dieses Schätzers gegen 0 strebt, d.h. mit steigender Anzahl von Stützstellen wird die Schwankung um den exakten Wert geringer.

Die Fehlerschranken der numerischen Integrationsregeln enthalten einen Ableitungsterm, d.h. damit die Approximation gegen den richtigen Wert strebt, muss verlangt werden, dass die zu integrierende Funktion f hinreichend glatt  ist (etwa muss f für die Simpsonsche Regel viermal differenzierbar sein). Derartige Forderungen werden bei der Monte-Carlo-Integration nicht gestellt.

Die hit-or-miss Monte-Carlo-Integration macht direkt von der Interpretation des Integrals als Flächeninhalt Gebrauch. Die untersuchte Fläche wird durch ein Rechteck eingegrenzt, und auf diesem werden einer Gleichverteilung folgend zufällige Punkte erzeugt. Die Wahrscheinlichkeit, dass ein solcher Punkt in der untersuchten Fläche liegt, entspricht dem Verhältnis des gesuchten Flächeninhaltes und dem Flächeninhalt des Rechteckes. Nach dem starken Gesetz der großen Zahlen konvergiert die relative Häufigkeit der Punkte, die innerhalb der untersuchten Fläche liegen, gerade gegen diese Wahrscheinlichkeit. Der gesuchte Flächeninhalt kann also durch den Anteil der Punkte innerhalb der untersuchten Fläche multipliziert mit dem Flächeninhalt des Rechteckes approximiert werden.

Anstelle eines Rechteckes können natürlich auch andere geometrische Abgrenzungen verwendet werden, wichtig ist, dass der Flächeninhalt relativ einfach ausgerechnet werden kann, und dass auf möglichst einfache Art und Weise gleichverteilte Punkte auf dieser Fläche erzeugt werden können.Wie für die direkte Monte-Carlo-Integration gilt auch hier, dass numerische Quadraturverfahren bei den hier veranschaulichten Funktionen deutlich bessere Ergebnisse liefern; auch die hit-or-miss-Variante der Monte-Carlo-Integration wird heutzutage nur noch zur Berechnung hochdimensionaler Integrale verwendet.

Im Vergleich zur direkten Monte-Carlo-Integration ist bei der hit-or-miss-Variante die Varianz des Schätzers noch größer, d.h. die Ergebnisse sind bei gleicher Anzahl an Punkten noch ungenauer. Im Gegensatz zu allen anderen Verfahren muss aber nur entschieden werden, ob eine y-Koordinate unter dem Graphen der Funktion liegt oder nicht, dies kann mit deutlich weniger Rechenaufwand verbunden sein als die Berechnung des Funktionswertes selbst.

Ein klassisches Beispiel stellt der Halbkreis dar, der durch den Graphen der Funktion mit Funktionsterm f(x)=sqrt(1-x²) und die x-Achse begrenzt ist. Die Gleichung y<f(x) kann hier äquivalent zu y²+x²<1 umgeformt werden, d.h. für diese Entscheidung ist es nicht notwendig, die Wurzel zu ziehen. Da auch für Computer das Addieren und Multiplizieren wesentlich einfacher als das Wurzelziehen ist, kann auf diese Weise deutlich Rechenzeit gespart werden. Es gibt Beispiele, in denen durch derartige Termumformungen der Vorteil der hit-or-miss-Variante der Monte-Carlo-Integration noch größer als in dem einfachen Beispiel ist; es kann sogar vorkommen, dass es möglich ist, zu entscheiden, ob y<f(x) gilt oder nicht, obwohl es keine Möglichkeit gibt, f(x) explizit auszurechnen. In solchen Situationen ist die hit-or-miss-Methode häufig die einzige Möglichkeit, ein Integral (approximativ) auszurechnen.

Funktionsweise dieser interaktiven Seite

In diesem Fenster können zwei vorgegebene Funktionen per Monte-Carlo-Integration integriert werden. Die zu integrierende Funktion kann über das Auswahlfeld unten links gewählt werden. Mit dem Schieberegler ganz unten kann eingestellt werden, wie viele Punkte zur Monte-Carlo-Integration verwendet werden sollen.

In diesem Fenster können zwei vorgegebene Funktionen per Monte-Carlo-Integration integriert werden. Die zu integrierende Funktion kann über das Auswahlfeld unten links gewählt werden. Mit dem Schieberegler ganz unten kann eingestellt werden, wie viele Punkte zur Monte-Carlo-Integration verwendet werden sollen.