Beiträge durchsuchen

Approximation an PI mit Hilfe der Monte-Carlo-Methode

Die Zahl PI weist unendlich viele Nachkommastellen auf und ist nicht periodisch. Deshalb können nur Näherungswerte diese Zahl angeben. Mit Hilfe von Computern und verschiedenen Methoden haben Mathematiker und Informatiker versucht, stets einen genaueren Näherungswert zu errechnen. Eine Methode wird hier vorgestellt – diese Methode ist jedoch nur für Lernzwecke gedacht. Für normale Kreisberechnungen ist die Konstante PI aus der Math-Unit vorzuziehen!
Wenn der Sinn von PI an dieser Stelle nicht klar sein sollte, wäre diese Seite empfehlenswert.

Ausgangspunkt und Idee

Die Fläche eines Kreises ist:

A = PI * r^2
Da PI berechnet werden soll und 3 Unbekannte vorhanden sind, wird r (= 1) ein Wert zugewiesen, um weitere Rechenschritte zu ermöglichen. Die zweite Unbekannte A wird später ausgemessen und dann lässt sich die Unbekannte PI einfach berechnen. Die Formel sieht nun so aus:

A = PI * 12
A = PI
Um einfacher rechnen zu können, denkt man sich jetzt einen Viertelkreis, der von einem Quadrat begrenzt wird. Dieses Quadrat hat die Seitenlänge 1. Folglich passt der Viertelkreis genau in das Quadrat, füllt es jedoch nicht ganz aus.
Die Fläche des Viertelkreises ist nun:

A/4 = PI/4
Und die Fläche des Quadrates ist:

A_q = h * w = 1 * 1 = 1
Anschließend werden zufällig Punkte in dem Quadrat verteilt. Jeder Punkt, der in dem Viertelkreis landet, wird gezählt. Da bekannt ist, wieviele Punkte insgesammt verteilt wurden, kann die Wahrscheinlichkeit, dass ein Tropfen in dem Viertelkreis landet, ausgerechnet werden:

(A/4)/A_q * 100%
Diese Wahrscheinlichkeit ist auch gleichzeitig die Fläche von A/4. Nun kann die Fläche auf A hochgerechnet werden und da

A = PI
ist, wird damit auch gleichzeitig PI ausgerechnet.

Quelle: Wikipedia (http://de.wikipedia.org/w/index.php?title=Datei:Pi_statistisch.png&filetimestamp=20090530150137)
Quelle: Wikipedia (http://de.wikipedia.org/w/index.php?title=Datei:Pi_statistisch.png&filetimestamp=20090530150137)

 

Diese Methode gehört zu den randomisierten bzw. stochastischen Algorithemen, da Zufallswerte erzeugt werden, um sich einem Ergebniss anzunähern bzw. es genau zu errechnen. Genau gesagt fällt dieser Algorithmus in die Familie der Monte Carlo Algorithmen, welche nach einem Casino in Monte Carlo (Monaco) benannt wurden. Diese Algorithmen haben die Eigenschaft, dass sie auch falsche Ergebnisse liefern können, sich die Wahrscheinlichkeit für ein solches „falsches“ Ergebnis jedoch problemlos verringern lässt. So kann hier einfach die Anzahl der Zufallsexperimente, d.h. die Anzahl der zufälligen Punkte erhöht werden, um ein präziseres Ergebnis zu erzielen. Nach dem Gesetz der großen Zahlen wird die Wahrscheinlichkeit, dass ein „falsches“, d.h. ungenaues Ergebnis berechnet wird, so immer geringer. Um ein möglichst genaues Ergebnis zu bekommen, sollten so viele Zufallsversuche wie möglich durchgeführt werden.
Da der ganze Algorithmus auf einem Zufallsversuch basiert, muss erstmal der Zufallsgenerator initialisiert werden. Dafür bietet sich vor allem das OnCreate-Event an:

procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize();
end;

Nun kommt die eigentliche Funktion. Mit dem Parameter ACount wird der Funktion die Anzahl der Schleifendurchläufe übergeben.

function CalculatePi(ACount: Cardinal): Extended;
var
  x, y: Real;
  i, hits: Cardinal;
begin
  hits := 0;
  for i := 0 to ACount-1 do
  begin
    x := Random();
    y := Random();

    if ((x * x) + (y * y) <= 1) then
      Inc(hits);
  end;
  Result := 4 * (hits / ACount);
end;