Geometrie und Topologie
Fakultät für Mathematik
Technische Universität München

Wie ein IFS entsteht

Wir erläutern kurz, wie der Algorithmus zum randomisierten Erzeugen der Grenzpunktmenge funktioniert. Randomisiert heißt “vom Zufall gesteuert”, und in der Tat nutzt der Algorithmus als entscheidendes Element Zufallsstrukturen. Angenommen wir haben zwei Drehstreckungen

\[ z\to f_1(z)\text{ und }z\to f_2(z) \]

gegeben. Der Algorithmus funktioniert dann wie folgt: Ausgehend von einem beliebigen Startpunkt $z_0$ wird zufällig (sagen wir mit einer 50:50-Wahrscheinlichkeit) eine der beiden Abbildungen $f_1(z_0)$ oder $f_2(z_0)$ gewählt und der Bildpunkt $z_1$ berechnet. Dieser Punkt wird nun gezeichnet und dient als Startpunkt für die nächste Iteration. Man wählt also wieder eine der beiden Abbildungen zufällig aus, bildet ab (das Ergebnis ist $z_2$) und zeichnet den Punkt. Das Ganze wiederholt man viele, viele Male. Es entsteht eine Punktewolke, die ungefähr so aussehen wird wie die Grenzpunktmenge.

Das Ganze funktioniert dabei nicht nur mit zwei Abbildungen, sondern im Prinzip mit beliebig vielen. Schreibt man das Verfahren als Computerprogramm auf, so sieht dies für Transformationen f_1, f_2,… f_k ungefähr folgendermaßen aus.

z=startpunkt;
n=Anzahl der Iterationen;
wiederhole n-mal: (
   f=Eine zufällige Transformation aus f_1, f_2,... f_k;
   z=f(z);
   zeichne(z);
)

Die einzelnen Befehle müssen natürlich an die Syntax der jeweiligen Programmiersprache angeglichen werden.

Eine Feinheit blieb bisher noch unerwähnt: Da der Startpunkt ja zufällig gewählt war, kann man nicht erwarten, dass sich gleich die ersten paar Punkte in der Nähe der Grenzpunktmenge befinden. Daher ignoriert man üblicherweise die ersten ca. 100 Punkte.

Das folgende Applet demonstriert am Beispiel der im letzen Kapitel betrachteten Abbildungen die Erzeugung des IFS. Die Abbildungen f1, f2 seien dabei bereits vorher festgelegt. Mit dem Schieberegler kann man die Zahl der verwendeten Iterationen einstellen. Man beobachtet, dass für kleine Punktanzahlen zunächst noch keine Struktur erkennbar ist, dass sich aber für große Punktmengen deutlich die Struktur der Grenzpunktmenge abzeichnet.

Selbst aus sehr einfachen Transformationen lassen sich bereits interessante Grenzpunktmengen erzeugen. Betrachten wir z.B. für einen gegebenen Punkt $p$ die Transformation

\[ f_p(z):=(z+p)/2, \]

die den Punkt $z$ die auf die Mitte zwischen $p$ und $z$ abbildet. Mit anderen Worten ist $f_p$ eine Stauchung um den Faktor $2$ mit Stauchungszentrum $p$. Das folgende Beispiel zeigt, was herauskommt, wenn man aus drei solchen Stauchungen $f_a(z), f_b(z), f_c(z)$ ein iteriertes Funktionensystem bildet. Die entstehende Grenzpunktmenge ist ein bekanntes Fraktal, das so genannte Sierpinski-Dreieck.