Java/Monte-Carlo-Methode

Aus ZUM-Unterrichten

In den achtziger Jahren besuchte ich mit einer Schulklasse eine Landesgartenschau. Am Eingang musste jeder Besucher einen Pingpong-Ball in eine Öffnung werfen, und eine große Digitalanzeige verriet dann eine nächste Näherung für die Kreiszahl p …

So mitten im Trubel konnte ich den verdutzten Schülern keine erschöpfende Erklärung bieten; außerdem ging es an diesem Tage ja auch um Pflanzen. Da es sich jedoch um eine 10.Klasse handelte, bekam ich später einen guten Aufhänger für die Behandlung von Näherungsverfahren für die Kreiszahl.


Monte-Carlo-Methode zur Bestimmung der Kreiszahl p

Mathematischer Hintergrund

Pi statistisch.png

Bei der Monte-Carlo-Methode approximiert man p durch sehr spektakuläre stochastische Überlegungen.

In ein Einheitsquadrat mit Einheitsviertelkreis ergießt sich ein Zufallsregen. Die Gesamtzahl g der Tropfen verhält sich zur Zahl der Tropfen im Viertelkreis v wie der Inhalt der Quadratfläche zum Inhalt der Viertelkreisfläche. Entsprechend ergibt sich folgende Näherungsgleichung:

Monte-carlo-1.png

Monte-carlo-2.png

Ein Tropfen treffe im Quadrat in P auf; ist die Streckenlänge OP kleiner oder gleich 1, befindet sich P sogar im Viertelkreis (, und der Zähler v muss erhöht werden).


Struktogramm

Struktogramm-Monte-Carlo.svg


Java-Quelltext / For-Schleife

Die Schleife könnte man wieder mit "Solange" realisieren, wobei man vorher die Zahl der Tropfen i mit 0 initialisieren müsste; außerdem wäre dafür Sorge zu tragen, dass die Tropfenzahl i bei jedem Schleifendurchgang um eins erhöht wird und die vereinbarte Gesamtzahl g nicht übersteigt. Bequemer ist es, wenn man in einem solchen Falle die sog. For-Schleife verwendet:

// i ++ steht für das Inkrementieren von i um 1 pro Schleifendurchgang
for (int i = 1; i <= g; i++) {
  //Schleifenrumpf
   
}


class Pi  {
  public static void main(String[] args)  {
    // Gesamtzahl der Tropfen
    int g = Integer.parseInt(args[0]); 
    // Tropfen im Viertelkreis
    int v = 0;
    // Koordinaten des Punktes P 
    double x,y;
    System.out.println(" Monte Carlo Methode");
    System.out.println(" Naeherung fuer Pi:");
    for (int i = 1; i <= g; i++)   {	
      x = Math.random();
      y = Math.random();
      if (Math.hypot(x,y) <= 1)	
        v = v + 1;
    }  
    double pi = 4*(double)v / g; 
    System.out.printf(" %d Tropfen, davon %d Tropfen im Viertelkreis, Pi etwa %g%n",g,v,pi);	 
  }
}

Monte-carlo-6.png

Für die Koordinaten und für p benötigt man Gleitkommazahlen; diese werden durch den Datentyp double bereitgestellt.

  • Math.random() liefert Zufallszahlen von 0 bis (ausschließlich) 1.
  • Math.hypot(x,y) berechnet die Streckenlänge OP (Hypotenusenlänge).
  • Das float bei der Berechnung der Näherung für p ist notwendig, da sonst eine Ganzzahldivision durchgeführt würde.
  • Im Formatstring ist %g ein Platzhalter für eine Gleitkommazahl.

Benutzereingaben über den Scanner

Der Benutzer soll zur Laufzeit die gewünschte Tropfenzahl eingeben können; dafür führen wir das sog. Scanner-Objekt - zunächst als "black box"- ein.

Wir interessieren uns für das Konvergenzverhalten der Monte-Carlo-Methode; deshalb lassen wir uns schon im Schleifendurchgang jeweils nach 100 Iterationsschritten den aktuellen Näherungswert ausgeben.

import java.util.Scanner;
class Pi_1  {
  public static void main(String[] args)  {
    // Das System liest von der Standardeingabe
    Scanner s = new Scanner(System.in);
    System.out.println(" Wie viele Tropfen soll es regnen?");
    int g = s.nextInt();
    // Tropfen im Viertelkreis
    int v = 0;
    // Koordinaten des Punktes P 
    double x,y;
    for (int i = 1; i <= g; i++)   {	
	x = Math.random();
	y = Math.random();
	if (Math.hypot(x,y) <= 1)	
	  v++;
	double pi = 4*(float)v / i;
	if (i%100 == 0)  
	  System.out.printf(" Nach %6d Tropfen ist die Naeherung fuer Pi  %g%n",i,pi);	 
    }  
  }
}

Monte-carlo-3.png

Wir erkennen an dieser Stelle: Unsere Methode ist zwar sehr spektakulär, aber sie konvergiert sehr langsam …

Konvergiert das Verfahren überhaupt?

Wir müssen uns verabschieden von der Schleife vorgegebener Länge; das Verfahren soll so lange laufen, bis eine "vernünftige" Näherung erreicht ist. Aber wie realisiert man eine "Wiederhole-Schleife" in Java?

Wiederhole-Schleife

// Jetzt soll die Iteration abgebrochen werden, wenn sich die Näherungswerte
// nur noch im Rahmen eines vorgegebenen Epsilon-Bereiches ändern
class Pi_2  {
  public static void main(String[] args)  {
    int i = 0;
    int v = 0;
    // Startwert von Pi für den ersten Vergleich
    double pi = 3;
    double x,y,pi_alt;
    // Falls sich zwei Näherungswerte um höchstens diese Differenz epsi
    // unterscheiden, soll die Iteration abgebrochen werden
    double epsi = 1.E-5;
    do   {
      i++;   // Tropfenzahl
      pi_alt = pi;
      x = Math.random();
      y = Math.random();
      if (Math.hypot(x,y) <= 1)
        v++;  // Tropfen im Viertelkreis
      pi = 4*(float)v / i;
    }
    while (Math.abs(pi_alt - pi) > epsi);  
    System.out.printf(" Nach %6d Tropfen ist die Naeherung fuer Pi  %g%n",i,pi);
    //System.out.printf(" Der Konvergenzbereich ist %g breit", 2*epsi);   
  }
}

Monte-carlo-4.png

Die drei Aufrufe des Programmes verdeutlichen, wie sich im Sinne des Gesetzes der großen Zahl der Wert von p herauskristallisiert; allerdings ist eine sehr große Tropfenzahl für eine vergleichsweise "bescheidene" Näherung erforderlich; das Konvergenzverhalten des Verfahrens ist also "ungünstig".

Operatoren

Außerdem kann man mit dem o.g. Quelltext auch Überraschungen erleben: Ggf. steigt das Programm z.B. mit der Meldung aus, dass es nach 2 Tropfen eine Näherung 4 für p gäbe. Wie man leicht sieht, folgt dies, wenn die ersten Tropfen alle im Viertelkreis landen.

Um auch dies zu berücksichtigen, passen wir unsere Schleifenbedingung an:

 while ((Math.abs(pi_alt - pi) > epsi) || (i < 10));

Die Schleife soll also in jedem Fall für die ersten 9 Tropfen weiterlaufen; als logischen Operator haben wir || (für ODER) gewählt.

Weitere logische Operatoren sind && ( für UND) und  ! (für NICHT).

An arithmetischen Operatoren haben wir bereits kennengelernt: + - * /  %

Relationale Operatoren < > <= >= ==  !=

Runden

Wie viele Tropfen unseres Zufallsregens sind nun notwendig, um p wenigstens auf 4 Dezimalen zu bestimmen?

Ausgehend von pi = 4*(float)v / i;

kann man z.B. pi mit 10000 multiplizieren, auf Einer runden und durch 10000 dividieren.

Aus dem unteren Teil des Schleifenrumpfes würde dann

    ......
  pi = 4*(float)v / i;
  pi = Math.round(10000 * pi)/10000.0;
  }
 while (pi != 3.1415);

Hier verdeutlichen die 5 Aufrufe, dass sogar das verhaltene Tempo der Konvergenz sehr statistisch ist.

Monte-carlo-5.png

Siehe auch