Polar-Methode

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Polar-Methode von George Marsaglia und Thomas A. Bray ist ein Verfahren zur Erzeugung normalverteilter Zufallszahlen (Zufallszahlengenerator).

Geschichte[Bearbeiten | Quelltext bearbeiten]

Diese Methode geht zurück auf den Box-Muller Algorithmus zur Erzeugung normalverteilter Zufallsgrößen. Bei diesem werden die euklidischen Koordinaten verwertet. Bei der Polar-Methode werden diese euklidischen Koordinaten in Polarkoordinaten umgewandelt. Dadurch spart man sich die Auswertung von trigonometrischen Funktionen.

Beschreibung[Bearbeiten | Quelltext bearbeiten]

Man geht von zufälligen Punkten in der Ebene aus, die im Einheitskreis gleichverteilt sind. Aus deren Koordinaten werden jeweils zwei standardnormalverteilte Zufallszahlen erzeugt:

  1. Erzeuge zwei voneinander unabhängige, gleichverteilte Zufallszahlen , im Intervall
  2. Berechne . Falls oder , gehe zurück zu Schritt 1.
  3. Berechne .
  4. und sind nun zwei voneinander unabhängige, standardnormalverteilte Zufallszahlen.

Der Punkt muss im Einheitskreis liegen (), und es muss gelten, da in den reellen Zahlen der Logarithmus von Null und die Division durch Null nicht definiert sind. Anderenfalls müssen zwei neue Zahlen und erzeugt werden.

Durch lineare Transformation lassen sich hieraus beliebige normalverteilte Zufallszahlen erzeugen: Die generierten Werte sind -verteilt, somit liefert Werte, die -verteilt sind.

Implementierung[Bearbeiten | Quelltext bearbeiten]

Pseudocode[Bearbeiten | Quelltext bearbeiten]

Prozedur ErzeugeNormalverteilteZufallszahlen (Referenzparameter x1, x2)
  Wiederhole
    u = 2 * Zufallszahl - 1  // "Zufallszahl" liefert in [0,1)
    v = 2 * Zufallszahl - 1  //   gleichverteilte Werte
    q = u * u + v * v
  Solange bis (0 < q) und (q < 1)
  p = Wurzel (-2 * ln(q) / q)
  x1 = u * p
  x2 = v * p  // Rückgabe durch die Referenzparameter x1, x2
Ende

C[Bearbeiten | Quelltext bearbeiten]

double random(); // liefert im Intervall [0,1) gleichverteilte Zufallszahlen

void polar(double *x1, double *x2)
{
   double u, v, q, p;

   do {
      u = 2.0 * random() - 1;
      v = 2.0 * random() - 1;
      q  = u * u + v * v;
   } while (q <= 0.0 || q >= 1.0);

   p = sqrt(-2 * log(q) / q);
   *x1 = u * p;
   *x2 = v * p;
}

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]