Monte-Carlo-Simulation
Auf dieser Seite wird kurz die Methode der Monte-Carlo-Simulation an einem Kreis verdeutlicht. Dazu gibt es ein Windows-Programm, welches das Verfahren demonstriert:
mc2.zip (102 KB: Programm für Windows 9x, Quellcode: C++/WinAPI)
Allgemein
Man benutzt die Monte-Carlo-Methode, um den Inhalt von Körpern und Flächen mit unregelmäßiger Begrenzung oder in großen Raumdimensionen zu berechnen. Hier ist sie das schnellstmögliche Verfahren. Dazu wird eine Begrenzungsfläche um den Körper gelegt, von der man leicht den Flächeninhalt ausrechnen kann (z.B. Quadrat, Würfel, Hyperwürfel…). Nun wird ein Punkt mit zufälligen Koordinaten ermittelt und in den Raum, den die Begrenzungsfläche einschließt, gesetzt. Danach wird anhand einer Formel ermittelt, ob dieser Punkt im Körper oder nur im Raum innerhalb der Begrenzungsfläche liegt. Diesen Vorgang wiederholt man sehr oft, sodass am Ende viele Punkte vorhanden sind. Hier das Beispiel für einen Kreis; die Farben der Punkte variieren:
Liegt der Punkt innerhalb des Körpers?
Wie oben bereits erwähnt, existieren Formeln, um zu bestimmen, ob der zufällig ermittelte Punkt innerhalb des Körpers liegt. Da ich nur den Kreis in mehreren Dimensionen betrachtet habe, kann ich hier nur das Verfahren für den Kreis beschreiben. Der euklidische Abstand, gemessen vom Mittelpunkt des Kreises, darf nicht größer sein als der Radius des Kreises. Den Abstand selbst gibt uns der Satz des Pythagoras:
x2 + y2 + … ≤ r2 (Punkt liegt im Körper)
x2 + y2 + … > r2 (Punkt liegt nicht im Körper)
Diese Vorgehensweise funktioniert sowohl für Kreise (Koordinaten x und y) als auch für beliebige Kugeln im n-dimensionalen Raum (x, y, z, …).
Berechnung des Inhalts
Über folgende Formel wird nun die Wahrscheinlichkeit berechnet, mit der die Punkte in den Körper fallen:
P = Anzahl Punkte im Körper / Gesamtzahl der Punkte
Die Wahrscheinlichkeit gibt gleichzeitig an, wie viel Prozent des Raumes der Körper einnimmt. Dadurch kann dessen Inhalt AK über den bekannten Inhalt des Begrenzungsraumes AB berechnet werden:
AK = P⋅AB
Das Programm »Monte Carlo« berechnet den Flächeninhalt eines zweidimensionalen Kreises. Die Anzahl der zu setzenden Punkte kann entweder durch den Benutzer bestimmt werden, oder sie wird über eine Varianz ermittelt.
Zur Varianzberechnung
Die Varianz σ gibt an, wie groß der Unterschied zwischen der berechneten Wahrscheinlichkeit und den gesetzten Punkten ist.
Stellt man die Wahrscheinlichkeit in Abhängigkeit der gesetzten Punkte in einem Diagramm dar, so ergibt sich beispielsweise folgende Kurve:
Am Anfang steigt und fällt die Wahrscheinlichkeit im Verhältnis zu den Gesamtpunkten rapide. Die Varianz ist also sehr hoch. Mit der Zeit pegelt sie sich jedoch in einen bestimmten, sehr kleinen Wert ein; die Kurve im Diagramm wird gleichmäßiger.
Über folgende Formel wird die Varianz berechnet:
σ = (P - P2) / (n - 1)
Wobei n die Gesamtzahl der Punkte darstellt. Ist die Varianz σ<10-5, so wird der Vorgang abgebrochen und die Wahrscheinlichkeit akzeptiert. Sie ändert sich dann nur noch geringfügig. Tatsächlich bricht das Programm jedoch erst frühestens nach dem zwanzigsten Punkt ab, weil vorher die Möglichkeit besteht, dass die Varianz zwar kleiner als der Schwellenwert ist, jedoch noch nicht genügend Punkte zur Verfügung stehen. Dies ist zum Beispiel der Fall, wenn die ersten drei Punkte alle im Kreis liegen: Die Wahrscheinlichkeit würde immer 100% betragen und nicht variieren.
Die Berechnung von Pi
π lässt sich ebenfalls mit Hilfe der Monte-Carlo-Simulation am Kreis berechnen. Wir gehen zunächst von der Formel für den Flächeninhalt eines Kreises aus:
AK = π⋅r2
Die Kreisfläche lässt sich allerdings auch mit Hilfe der Trefferwahrscheinlichkeit P und der Fläche des Begrenzungsquadrats AB berechnen, wie oben gezeigt wurde.
AK = P⋅AB mit AB = a2 = (2⋅r)2
Eine Seite des Quadrats ist doppelt so lang wie der Radius des Kreises: a=2r. Setzen wir beide Formeln für die Kreisfläche gleich, erhalten wir:
π = 4⋅P = 4⋅m / n
m gibt hier die Anzahl der Treffer an, während n die Anzahl der geschossenen Punkte repräsentiert.
Da das Programm jedoch unter anderem innerhalb der Begrenzungsfläche nur ganzzahlige Zufallskoordinaten ermittelt, kann Pi nie genau errechnet werden. Des weiteren wurde einfach die Standard-C++-Funktion zur Erzeugung von Zufallszahlen benutzt, welche sicher auch nicht perfekt ist.
Zusätzlich zu diesen »schön geometrischen« Formen und Körpern habe ich den Näherungswert für den Flächeninhalt einer Mandelbrotmenge bestimmt. Dazu mehr auf der Seite über die Mandelbrotmenge.
