π-Bestimmung mit der Monte-Carlo-Methode

Aus ProgrammingWiki

Autor: DevWurm (2016)

Die Kreiszahl \pi ist eine der bekanntesten Konstanten der Mathematik.
Neben verschiedenen algebraischen und trigonometrischen Verfahren zur Bestimmung von \pi, sind auch statistische Methoden zu diesem Zweck anwendbar.
Die Monte-Carlo-Methode ist ein einfacher und sehr anschaulicher Vertreter dieser Gruppe

Theoretische Grundlagen

  • Betrachtet man eine (rechteckige) Fläche A_{ges}, in welche eine Kreisfläche A_k einbeschrieben ist, lässt sich das Verhältnis \frac{A_k}{A_{ges}} in Abhänigkeit von \pi aus den Maßen dieser Flächen bestimmen.
  • Erzeugt man nun eine Anzahl (praktisch) eindimensionaler Objekte n_{ges} (z.B. Nadeln) an eine völlig zufällige Stelle dieses Aufbaus, lässt sich durch Auszählen die Anzahl n_k der Objekte bestimmen, welche sich im Kreis befinden.
  • Aufgrund der Laplace-Wahrscheinlichkeiten dieses Zufallsversuchs gilt: \frac{A_k}{A_{ges}} = \frac{n_k}{n_{ges}}
  • Aufgrund des Zusammenhanges A_k = \pi \cdot r^2 gilt, für eine rechteckige Gesamtfläche mit den Maßen h und w, sowie einer Kreisfläche mit dem Radius r, ergibt sich eine Gleicung für \pi: \pi = \frac{w \cdot h \cdot n_k}{r^2 \cdot n_{ges}}

    Dabei müssen n_k und n_{ges} aus dem Zufallsexperiment ermittelt werden.


Mithilfe einiger weiterer Elemente und Spezialisierungen, lässt sich das Verfahren für die programmatische Verarbeitung vereinfachen:

  • Als erstes wird ein Koordinatensystem definiert, dessen Ursprung in der Mitte des Aufbaus liegt, um zufällig erzeugte Zahlenwerte in einen geometrischen Zusammenhang zu bringen.
  • Das Erzeugen der Objekte wird nun realisiert, indem Punkte mit zufälliger x- und y-Koordinate erzeugt werden.
  • Der Mittelpunkt des Kreises liegt im Koordinatenursprung und der Kreis hat den Radius r = 1.
  • Bei dem Rechteck handelt es sich um ein Quadrat (w=h) mit der Kantenlänge w = 2 \cdot r und der Mittelpunkt des Quadrates liegt im Koordinatenursprung
  • Zudem sind alle Punkte Elemente eines Kreises, deren Abstand zum Mittelpunkt kleiner ist als der Radius des Kreises. Ein Objekt, welches im Punkt P(x_P | y_P) in dem beschriebenen Aufbau geberiert wird, ist also dann innerhalb des Kreises, wenn gilt: 1 = x_P^2 + y_p^2
  • Es wird nur der 1. Quadrant des Aufbaus betrachtet (somit \frac{1}{4} von A_{ges} und \frac{1}{4} von A_{k}). Die Objekte P(x_P | y_P) könne somit erzeugt werden für x_P \in \mathbb{R}; 0 \leq x_P \leq 1 und y_P \in \mathbb{R}; 0 \leq y_P \leq 1. Trotz dieser Vereinfachung gilt der oben genannte Zusammenhang für \pi.

Implementation in Scheme

Zurück zum Algorithmusbegriff.