Matthias Scharwies: Artikel von Claus Schmitt, importiert aus ZUM-Classic

2019-08-25T05:09:37Z

Artikel von Claus Schmitt, importiert aus ZUM-Classic

Neue Seite

In den achtziger Jahren besuchte [[Benutzer:CSchmitt|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'''.

{{Fortsetzung|
vorher=Ulam-Folge|vorherlink=Java/Ulam-Folge|
weiter=Mustererkennung|weiterlink=Java/Mustererkennung|
übersicht=Einstieg in Java<br>(Übersicht)|übersichtlink=Java#Übersicht|}}

== Monte-Carlo-Methode zur Bestimmung der Kreiszahl p ==
=== Mathematischer Hintergrund ===
[[Datei:Pi_statistisch.png|right|300px]]
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 <code> g </code> der Tropfen verhält sich zur Zahl der Tropfen im Viertelkreis <code> v </code> wie der Inhalt der Quadratfläche zum Inhalt der Viertelkreisfläche. Entsprechend ergibt sich folgende Näherungsgleichung:

[[Datei:Monte-carlo-1.png]]
{{clear}}
[[Datei:Monte-carlo-2.png|right|250px]]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).
{{clear}}
=== Struktogramm ===
[[Datei:Struktogramm-Monte-Carlo.svg|400px]]

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

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

<source lang="java">
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);
}
}</source>

[[Datei:Monte-carlo-6.png]]

Für die Koordinaten und für <code>p</code> benötigt man Gleitkommazahlen; diese werden durch den Datentyp <code>double</code> bereitgestellt.
* <code>Math.random()</code> liefert Zufallszahlen von 0 bis (ausschließlich) 1.
* <code>Math.hypot(x,y)</code> berechnet die Streckenlänge OP (Hypotenusenlänge).
* Das <code>float</code> bei der Berechnung der Näherung für <code> p </code> ist notwendig, da sonst eine Ganzzahldivision durchgeführt würde.
* Im Formatstring ist <code> %g </code> 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.

<source lang="java">
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);
}
}
}
</source>

[[Datei: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 "[[Java/Schleife#while-Schleife|Wiederhole-Schleife]]" in Java?

=== Wiederhole-Schleife ===

<source lang="java">
// 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);
}
}</source>

[[Datei: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 <code> p </code> 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:

<source lang="java">
while ((Math.abs(pi_alt - pi) > epsi) || (i < 10));
</source>
Die Schleife soll also in jedem Fall für die ersten 9 Tropfen weiterlaufen; als logischen Operator haben wir <code> || </code>(für ODER) gewählt.

Weitere [[Java/Algorithmik#Operatoren|logische Operatoren]] sind <code> && </code> ( für UND) und <code> ! </code> (für NICHT).

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

Relationale Operatoren <code>< > <= >= == != </code>

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

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

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

Aus dem unteren Teil des Schleifenrumpfes würde dann

<source lang="java"> ......
pi = 4*(float)v / i;
pi = Math.round(10000 * pi)/10000.0;
}
while (pi != 3.1415);
</source>

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

[[Datei:Monte-carlo-5.png|Monte-carlo-5.png]]

{{Fortsetzung|
vorher=Ulam-Folge|vorherlink=Java/Ulam-Folge|
weiter=Mustererkennung|weiterlink=Java/Mustererkennung|
übersicht=Einstieg in Java<br>(Übersicht)|übersichtlink=Java#Übersicht|}}

== Siehe auch ==
* {{wpde|Monte-Carlo-Methode}}

[[Kategorie:Java]]

Java/Monte-Carlo-Methode - Versionsgeschichte

Matthias Scharwies: Artikel von Claus Schmitt, importiert aus ZUM-Classic