Monte-Carlo Methode

Monte-Carlo Methode mit Canvas-Pixelgrafik


Monte-Carlo-Methode


Eine wichtige Voraussetzung der Methode ist die möglichst gleiche Wahrscheinlichkeit aller Zufalls-versuche. Sie ist im ↑ Live-Beispiel dieser Seite durch die Standard Zufalls-Funktion der Programmiersprache Javascript bestimmt.
Details und Beispiele zur → Berechnung von Zufallszahlen

Die Monte-Carlo-Methode (Stochastische Simulation) ist auch zur unabhängigen Kontrolle anderer Verfahren geeignet.
Die → Berechnung der Kreiszahl Pi mit guten mathematischen Kenntnissen funktioniert zwar wesentlich rascher. Die Berechnung mit der Monte-Carlo-Methode ist jedoch von den dabei verwendeten Formeln und Algorithmen vollkommen unabhängig.

Wer das Prinzip der Methode verstanden hat, kann sie sinngemäß auch zur Lösung komplizierter Aufgaben verwenden, für die es keine andere Möglichkeit gibt: Für die meisten technischen und kommerziellen Aufgaben genügt eine Genauigkeit von 3-5 Dezimal-Stellen.

Wikipedia: Monte-Carlo-Simulation



Auswertung der Experimente:
  • Die Seitenlänge des Quadrats wird mit 2r bezeichnet.
    Die Fläche des Quadrats beträgt daher
    A[quadrat] = r2·4
    Die Kreis-Fläche beträgt
    A[kreis] = r2·Pi
  • Wenn sehr viele Objekte an zufällige Stellen des Spielfelds fallen, dann sollte die Anzahl der Treffer proportional zur jeweiligen Fläche sein:
    A[quadrat] / A[kreis] ≃ Treffer[quadrat] / Treffer[kreis]
    oder ausgedrückt durch die gezählten Experimente
    r2·4 / r2·Pi ≃ Anzahl[gesamt] / Anzahl[kreis]
  • Diese Gleichung kann man so umformen, dass die Kreiszahl Pi allein auf der linken Seite steht:
    Pi ≃ 4 * Anzahl[kreis] / Anzahl[gesamt]
    Den Faktor r2 kann man kürzen, die Formel ist daher von der Größe des Spielfelds unabhängig.
  • Die Kreiszahl Pi lässt sich aus dem Verhältnis der beiden Zähler berechnen.



Auch die Monte-Carlo Methode kommt nicht ganz ohne Mathematik aus. Der Ausdruck wird hier jedoch auf solche Methoden angewendet, die kompliziertere Algorithmen (meist Reihen-Entwicklungen) verwenden.

Vorteil: Moderne Programmiersprachen liefern schon nach einigen Millisekunden die ersten 100 Stellen (links).

Nachteil gegenüber der Monte-Carlo Methode:
Alle derartigen Algorithmen sind von mehr oder weniger komplizierten mathematischen Vorstellungen abhängig. Diese sind zwar bei François Viète sicher korrekt, es lassen sich jedoch nicht alle Aufgaben mathematisch beschreiben.

Programmierung des Live-Beispiels


Die Mini-Webseite enthält alle verwendeteen Resourcen. Sie braucht keine anderen Dateien (z.B. → CSS-StyleSheet oder Javascript-Bibliothek) und ist daher uneingeschränkt portabel.

Öffnen sie den Quelltext und schalten sie die Zeilen-Nummern mit Mausklick ab. Speichern sie den Text in einer Text-Datei *.html am eigenen Arbeits-PC:
Das Beispiel lässt sich voll funktionsfähig mit jedem modernen Browser öffnen oder - so wie hier - in eigene Webseiten einbetten.



Für jeden einzelnen Versuch werden die XY-Koordinaten mit einem Zufalls-Generator berechnet, danach der Abstand vom Mittelpunkt (=Nullpunkt des Koordinaten-Systems):
d = sqrt(x^2 + y^2)
Jeder Versuch wird in der Variablen count_total (Gesamt-Zähler Anzahl[gesamt] ) gezählt.
Wenn der berechnete Abstand d kleiner als die halbe Seitenlänge des Quadrats ist, dann wird der Versuch zusätzlich in der Variablen count_circle (Kreis-Treffer Anzahl[kreis] ) gezählt.
Der aktuelle Näherungs-Wert von Pi wird aus dem Verhältnis der beiden Zähler-Variablen berechnet.

Digitale Ausgabe: Nach jedem Versuch werden die aktuellen Werte der beiden Zähler und der Näherung für Pi in der Ergebnis-Tabelle angezeigt. Dazu werden Javascript-DOM-Methoden verwendet.

Grafik: Jeder Versuch wird in der Grafik durch eine grüne oder rote Kreis-Scheibe angezeigt.

Weitere Details werden hier nicht vorgestellt. Der ↗ Quelltext ist für dieses Beispiel besonders ausführlich kommentiert.


Richtwerte für einige Versuchs-Zahlen n
nstdevdig
1000.1800.74
10000.0461.34
100000.0121.93
1000000.0032.52

Solche Überlegungen kann man anstellen, um die Genauigkeit der Ergebnisse für ein umfangreiches Experiment mit einigen Vor-Versuchen abzuschätzen. In der Praxis fügt man noch eine weitere Spalte für den jeweiligen Zeit-Aufwand hinzu, der jedoch einfach proportional zur Anzahl der Versuche n wächst.

Aus den Daten geht hervor, dass man sehr viele Versuche verwenden müsste, um Pi mit halbwegs brauchbarer Genauigkeit zu berechnen.



Seit Version HTML-5 ist es möglich, → Canvas-Pixelgrafik in jeder Webseite zu verwenden.

Wenn man Pixel-Grafik übermalt, dann sind die Daten des ursprünglich 'darunter' liegende Bildes verloren. Das wird zwar meist als Nachteil der Pixel-Grafik angeführt, ist hier jedoch sehr vorteilhaft:

Die Anzahl der Bildpunkte (Pixel) bleibt unabhängig von der Anzahl der Versuche konstant. Man kann die bereits vorhandenen Objekte beliebig oft übermalen, ohne dass der Aufwand zunimmt.

Das Beispiel wurde daher auf Pixel-Grafik übertragen. Es arbeitet unabhängig von der Anzahl der Versuche immer gleich schnell und ist daher ab ca. n>1000 Versuchen der Objekt-Grafik klar überlegen.