Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

Beitrag_17_titel_zufall

Van der Corput-, Halton- und Hammersleyfolgen

Max und Rike machen einen Osterspaziergang, doch leider fängt es an zu regnen. Max fragt Rike, ob sie so etwas auch simulieren könnte, der Regen sieht so gleichmäßig aus, bildet aber kein Muster. Rike erklärt ihm die Van-der-Corput-, Halton- und Hammersleyfolgen, die man für gleichmäßiges Licht in der Computergrafik oder für numerische Integration benutzt.

Max Hey, so ein Regen! Sag mal Rike, kannst Du sowas simulieren?

Rike Ja, so ein Regen! Ich find‘s schön! Ich wäre glücklich, wenn ich das so gut simulieren könnte. Doch es gibt ein paar mathematische Ideen dazu.

Max Ja?

Rike Diese Gleichmäßigkeit ohne Musterbildung ist eine echte Herausforderung. Die erste Idee dazu kam von van der Corput. Dazu muss man ein Zahlensystem wählen.

Max Also, ich liebe das Dezimalsystem!

Darstellung von n im b-System

Rike Okay. Also, Du wählst eine Basis b und kannst jede Zahl n in Potenzen von b^i entwickelt, die Koeffizienten dazu sind die d_i(n):

n\;=\;\sum_{i=0}\;d_i(n) b^i,

und die Koeffizienten d_i liegen natürlich zwischen 0 und b:

0\;\le\; d_i(n)\;<\;b.

Max Hmmm.

Rike Ach, im Dezimalsystem bedeutet das, dass Du Ziffern d_i von 0 bis 9 hast und jede Zahl n schreiben kannst mittels Entwicklung in Zehnerpotenzen:

n\;=\;\sum _{i=0}\;d_i(n) 10^i,

zum Beispiel ist

13\;=\;1\;\cdot\;10^1\;+\;3\;\cdot\;10^0

und

100\;=\;1\;\cdot\;10^2\;+\;0\;\cdot\;10^1\;+\;0\;\cdot\;10^0

Max Stimmt!

Inverse Radical Function

Rike Und aus dieser Darstellung findet man die inverse radical function, das ist eine Abbildung, die jeder Zahl n die inverse Darstellung zuordnet:

\Phi_b(n)\;=\;\sum_{i=0}\;d_i(n) b^{-i-1},

das erklär ich Dir mal: Du nimmst also die Ziffern d_i(n) und schreibst sie in umgekehrter Reihenfolge:

\Phi_b(n)\;=\; \sum _{i=0}\;\frac{d_i(n)}{ b^{i+1}},

die kleinste Potenz b^0 wird zur größten inversen Potenz

b^{-1}\;=\;\frac{1}{b},

der Koeffizient d_0 zu b^0 bleibt.

Max Was wird dann aus 13?

Rike Die Reihenfolge der Ziffern ändert sich zu 31, der Wert wird:

13\;\longrightarrow\;\Phi_{10}(13)

\;=\;\frac{3}{10}\;+\;\frac{1}{10^2}

\;=\;0.31

Max Okay, verstehe, aus 100 wird dann

100\;\longrightarrow\;\Phi_{10} (100)

\;=\;\frac{0}{10}\;+\;\frac{0}{10^2}\;+\;\frac{1}{10^3}

\;=\;0.001

Rike Richtig! Das gibt folgendes Bild für die ersten 100 Zahlen zur Basis 10:

Van-Corput-Folge \Phi_{10} (n) zur Basis 10.

Max Okay, verstehe, sieht aber noch lange nicht wie unser Osterregen aus.

Rike Haha, stimmt, er ist viel zu regelmäßig. Halton hat dann die Basen gewechselt. Viel besser ist das Binärsystem, das kennst Du doch?

Beispiel im Binärsystem

Max Okay,

13\;=\;1\;\cdot\;2^3\;+\;1 \;\cdot\; 2^2\;+\;0 \;\cdot\; 2^1 +1 \;\cdot\; 2^0 \;=\;[1101]_2

und

100\;=\; 1\;\cdot\; 2^6\;+\;1 \;\cdot\; 2^5\;+\;0 \;\cdot\; 2^4\;+\; 0\;\cdot\; 2^3\;+\;1 \;\cdot\; 2^2\;+\;0 \;\cdot\; 2^1\;+\; 0 \;\cdot\; 2^0

 \;=\;[1100100]_2

Rike Max, das machst Du toll! Die radikal inverse Darstellung ist dann

13\;=\;[1101]_2\;\longrightarrow\;\Phi_2(13)

\;=\;\frac{1}{2}\;+\;\frac{0}{4}\;+\;\frac{1}{8}\;+\;\frac{1}{16}

= \frac{11}{16}

= 0.6875

Und

100\;=\;[1100100]_2\;\longrightarrow\;\Phi_2(100)

\;=\;\frac{0}{2}\;+\;\frac{0}{4}\;+\;\frac{1}{8} + \frac{0}{16}\;+\;\frac{0}{32}\;+\;\frac{1}{64}\;+\;\frac{1}{128}

= \frac{19}{128}

= 0.1484375

Max Verstehe!

Rike Und das Bild sieht schon sehr gut aus:

17-halton_02-00-06
Halton-Folge \Phi_2 (n) zur Basis 2.

Max Hey, das gefällt mir!

Hammersley-Punkte

Rike Aber es noch nicht zufällig genug. Hammersley hat dann vorgeschlagen, solche Punkte im s-dimensionalen Raum zu konstruieren, wo jede Komponente einer anderen Halton-Folge angehört, also

P\;=\;(x_1,\;x_2,\;\dots,\;x_s)\;=\;(\Phi_{b_1}(n),\; \Phi_{b_2}(n),\dots,\;\Phi_{b_s}(n))

Max Kannst Du denn nicht mal ein paar solche Bilder ausrechnen?

Rike Ja, klar, hier:

17-halton_2-3-11
Hammersley-Punkte (\Phi_2 (n),\;\Phi_3 (n))

 

17-halton_2-4-11
Hammersley-Punkte (\Phi_2 (n),\;\Phi_4 (n))

Max Okay, jetzt versteh‘ ich langsam, das Muster mit den Basen 2 und 3 sieht schon wie Regen aus, das mit 2 und 4 gar nicht, das sieht wie Hagel aus.

Rike Stimmt! Solche Folgen wurden ausgiebig untersucht, und am besten nimmt man für gleichmäßige Verteilungen Basen, die teilerfremd sind. Dann gibt es ein paar Kriterien, um ihre Güte zu vergleichen.

Max Ja?

Numerische Integration mit zufälligen Folgen

Rike Ja, als erstes fragt man, ob man bei der 1-dimensionalen Folge, wenn man die Punkte als Näherung fürs Intergral benutzt, auch wirklich eine Näherung des Intergrals herausbekommt:

17-int_11
Fläche I_{2,\;100} unter \Phi_2 (n)

I_{b,\;N}\;=\;\sum _{n=1}^N \frac{\Phi_2 (n)}{N} \approx \int_0^1\;0.5 dx\;=\;0.5,

dabei ist N ist die Anzahl der Punkte n.

Max Okay, und wie gut ist das beim Binärsystem und beim Dezimalsystem?

Rike Beim Dezimalsystem ist die Näherung des Integrals

I_{10,\;100}\;=\;0.49501

und fürs Binärsystem ist das

I_{2,\;100}= 0.49242

Max Also, das Dezimalsystem nähert besser?

Diskrepanz

Rike Ja, diese Näherung ist besser. Aber es gibt noch ein weiteres Kriterium für die Hammersley-Punkte. Wenn wir also 2 solche Folgen \Phi_{b_1} (n) und \Phi_{b_2} (n) kombinieren, und b_1 und b_2 teilerfremd sind, dann fragt man, ob in jedes Kästchen des Gitters gleich viele Punkte fallen.

Max Verstehe, bei 2 und 4 gibt es Kästchen, in die nichts fällt.

Rike Stimmt. Man zählt also die Punkte, die in Kästen fallen. Die Zahl in jedem Kästchen nennt man üblicherweise A(B,\;P) und P ist die gesamte Punktmenge. Um Punkte, die auf den Rand fallen, nicht zweimal zu zählen, einigt man sich, den linken und unteren Rand zu jedem Kästchen B dazu zu nehmen.

Max Okay.

Rike Diese Zahl A teilt man durch die Gesamtzahl der Punkte und berechnet davon die Differenz zum Flächeninhalt \lambda(B) von B. Das ergibt eine Zahl, die nenne ich mal D(B):

D(B)\;:=\;  | \frac{A(B,\;P)}{N}\;-\;\lambda(B)  |

Max Okay.

17-halton_disk_2-4-07
Im Fall b_1\;=\;2 und b_2\;=\;4 ist A(B,\;P)\;=\;0

Für die gelbe Fläche B bekommen wir

D(B)\;=\;|0\;-\;0.2 \;\cdot\; 0.4|\;=\;0.08

Und beim Fall b_1\;=\;2 und b_2\;=\;3 und demselben Viereck B:

A(B,P)\;=\;10

17-halton_disk_2-3-08
Für b_1\;=\;2, \;b_2\;=\;3 ist  A(B,\;P)\;=\;10

Dann ist

D(B)\;=\;|\frac{10}{100}\;-\;0.2 \;\cdot\; 0.4|\;=\;| 0.1\;-\;0.08|\;=\;0.02

Max Okay.

Rike Jetzt musst Du nur noch alle möglichen Kästchen untersuchen und das Maximum, genauer ist es eigentlich das Supremum, der Differenz bilden, das ist dann die sogenannte Diskrepanz.

D_N(P)\;:=\;\sup_B\;| \frac{A(B,\;P)}{N}\;-\;\lambda(B)  |

Max Verstehe, so eine Art größter Fehler.

Rike Ja, alle Kästchen sollen Punkte haben. Und diese Hammersley-Punkte eignen sich sehr gut zur Simulation von Regen, für sehr große N wird nämlich diese Diskrepanz immer kleiner, er geht nach Null für teilerfremde b_1 und b_2\;:

D_N(P)\;\longrightarrow\;0,\;\mathrm {wenn} \;N\;\longrightarrow\;\infty

Max Boah, das ist wirklich genial.

***

Übungsaufgaben

  1. Bestimme die 1- dimensionale Halton-Folge (\Phi_{100} (n)) für N\;=\;b\;=\;100.
  2. Bestimme die Hammersley-Folge (\Phi_{17} (n),\;\Phi_{19} (n)) für b_1\;=\;17 und b_2\;=\;19,\;N\;=\;100.

Lösungen

17-halton_100-02
17-hammersley_17-19-02