Monte-Carlo-Simulation

zur Berechnung des Inhaltes unregelmäßiger Flächen und Körper


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 auszurechnen. Für derart große Raumdimensionen ist die Monte-Carlo-Simulation 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...). Nun wird ein Punkt mit zufälligen Koordinaten ermittelt und in den Raum, den die Begrenzungsfläche einschließt, gesetzt. Danach wird über eine Formel ermittelt, ob dieser Punkt im Körper oder nur im Raum innerhalb der Begrenzungsfläche liegt. Diesen Vorgang wiederholt man sehr oft, so dass am Ende viele Punkte vorhanden sind. Hier das Beispiel für einen zweidimensionalen Kreis; die Farben der Punkte variieren:

Monte-Carlo-Simulation am Kreis

Über folgende Formel wird nun die Wahrscheinlichkeit berechnet, mit der die Punkte in den Körper fallen:

- * 100  =  Wahrscheinlichkeit in %
Anzahl der Punkte im Körper
Gesamtzahl der Punkte
-

Die Wahrscheinlichkeit ist gleichzeitig der Wert, wie viel Prozent des Raumes der Körper einnimmt. Dadurch kann dessen Flächeninhalt über folgende Formel bestimmt werden:

- * Wahrscheinlichkeit = Inhalt des Körpers
Inhalt Begrenzungskörper
100
-

 

Das Programm "Monte Carlo"

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 Sigma (Sigma) 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:

Varianz

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:

-  = Varianz
Wahrscheinlichkeit - Wahrscheinlichkeit˛
gesetzte Punkte - 1
-

Ist die Varianz kleiner als Sigma=10-5, so wird der Vorgang abgebrochen und die Wahrscheinlichkeit akzeptiert. Sie ändert sich nur noch geringfügig, wenn die Varianz so klein ist. 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 Sigma 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.

 

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 die Formel für den Kreis beschreiben. Sie lautet:

xPosition˛  +  yPosition˛  + .....

Es entsteht die Summe jeder Koordinate hoch 2. Je mehr Dimensionen, desto größer wird der Wert. Ist die Summe gleich oder kleiner als der Radius ins Quadrat, so liegt der Punkt innerhalb des Kreises, der Kugel... Logischerweise liegt der Punkt nicht im Körper, wenn die Summe größer als der Radius ins Quadrat ist.

xPosition˛  +  yPosition˛  + .....  <=  radius˛    //Punkt liegt im Körper

xPosition˛  +  yPosition˛  + .....    >  radius˛    //Punkt liegt nicht im Körper

 

Das Programm "Monte Carlo 2" (mehr Dimensionen)

In diesem Programm wurde die obige Formel zur Bestimmung des Punktes im Raum einfach erweitert: logischerweise stellt auch hier wieder jeder Summand eine Koordinate im Raum dar, für 3 Dimensionen wären das x, y und z:

xPosition˛  +  yPosition˛  +  zPosition˛ .....  <=  radius˛    //Punkt liegt im Körper

xPosition˛  +  yPosition˛  +  zPosition˛ .....    >  radius˛    //Punkt liegt nicht im Körper

Das lässt sich auf beliebig viele Dimensionen anwenden; der Benutzer kann nun über die Anzahl entscheiden.

 

Die Berechnung von Pi:

Pi lässt sich ebenfalls mit Hilfe der Monte-Carlo-Simulation am Kreis berechnen:

Pi = 4 *  m
n

Da das Programm jedoch unter anderem innerhalb der Begrenzungsfläche nur ganzzahlige Zufalls-Koordinaten 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.

 

Version 2.0: ab Windows 95
-Quellcode herunterladen (C++-Quellcode; WinAPI)
-Programm herunterladen (.zip-Datei, Windows)

 

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.