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]

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]

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 u, v im Intervall [-1, 1]
  2. Berechne q=u^2+v^2. Falls q = 0 oder q \geq 1, gehe zurück zu Schritt 1.
  3. Berechne p = \sqrt {\frac{-2 \cdot \ln q}{q}}.
  4. x_1=u \cdot p und x_2=v \cdot p sind nun zwei voneinander unabhängige, standardnormalverteilte Zufallszahlen.

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

Durch lineare Transformation lassen sich hieraus beliebige normalverteilte Zufallszahlen erzeugen: Die generierten Werte x_i sind \mathcal{N}(0,1)-verteilt, somit liefert a \cdot x + b Werte, die \mathcal{N}(b,a^2)-verteilt sind.

Implementierung[Bearbeiten]

Pseudocode[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]

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);
 
   p = sqrt(-2 * log(q) / q);
   *x1 = u * p;
   *x2 = v * p;
}

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]