π-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.
