Iteriertes Funktionensystem

Ein iteriertes Funktionen-System ist in der Mathematik ein endlicher Satz von Funktionen eines kompakten metrischen Raumes (M,d) in sich selbst:

$\phi _{1},\dots ,\phi _{r}:M\to M$

Sind alle Funktionen [Kontraktion (Mathematik)|kontraktiv]], so gibt es eine invariante Teilmenge X, welche die Fixpunktgleichung

$X=\bigcup _{i=1}^{r}\phi _{i}(X)$

erfüllt. Diese wird auch als selbst-ähnliche oder fraktale Menge bezeichnet.

Beispiele mit dem Einheitsquadrat als metrischem Raum sind die affinen Fraktale bzw. Grenzmengen der Lindenmayer-Systeme wie das Sierpinski-Dreieck und die Koch-Kurve. Für diese sind die definierenden Funktionen affine Abbildungen $\phi _{i}({\vec {x}})=A_{i}\,{\vec {x}}+{\vec {b}}_{i}$, die Kontraktionskonstanten sind die Operatornormen der Matrizen A_i.

Approximation der Grenzmenge

Chaosspiel

Die Gestalt der Menge X kann durch ein sog. Chaosspiel visualisiert werden. Dabei wird zunächst ein Fixpunkt ${\vec {x}}$ von ${\vec {x}}=\phi _{1}({\vec {x}})$ aufgesucht und auf diesen in zufälliger Reihenfolge die definierenden Funktionen angewandt. Als Algorithmus kann dies wie folgt aussehen:

• Weise 100 mal hinereinander ${\vec {x}}:=\phi _{1}({\vec {x}})$ zu
• Wiederhole beliebig oft
  • Wähle zufällig ein i in {1,...,r}
  • Weise ${\vec {x}}:=\phi _{i}({\vec {x}})$ zu
  • Zeichne den Punkt x

Rekursion

Eine weitere Möglichkeit der Darstellung, vorzugsweise für die affinen Fraktale, ist die rekursive Approximation der Menge X. Dazu braucht es eine rekursiv aufrufbare Funktion, welche die Zuordnung $F(n)=\bigcup _{i=1}^{r}\phi _{i}(F(n-1))$ bei einer beliebigen Menge $F(0)$ realisiert. Dies ist bei der Turtle-Grafik, die zur Konstruktion der L-Systeme verwendet wird, der Fall. Die Implementierung benötigt einen Stackspeicher, in welchem das jeweils aktuelle Koordinatensystem als affine Koordinatentransformationen festgehalten wird. Damit ergibt sich als Algorithmus

Figur(n):

• Falls n=0
  • zeichne die Basisfigur (z.B. eine Strecke, einen Buchstaben, ein schwarzes Rechteck)
• sonst:
  • Für i:=1 bis r
    • Lege aktuelles Koordinatensystem auf Stack ab
    • Transformiere das aktuelle Koordinatensystem entsprechend $\phi _{i}$
    • Rufe Figur(n-1) auf
    • Stelle Koordinatensystem vom Stack wieder her

Fraktal:

• Rufe Figur(10) auf (10 als Beispiel)

Beispiele für iterierte Funktionensysteme

Das Koch-Fraktal wird z.B. von folgendem System von 2 Funktionen erzeugt

• $\phi _{1}(x,y)=\left({\frac {x+{\frac {1}{\sqrt {3}}}y}{2}},{\frac {{\frac {1}{\sqrt {3}}}x-y}{2}}\right)$
• $\phi _{2}(x,y)=\left({\frac {1+x-{\frac {1}{\sqrt {3}}}y}{2}},{\frac {{\frac {1}{\sqrt {3}}}(1-x)-y}{2}}\right)$

Die klassische Methode zur Erzeugung der Koch-Kurve benutzt 4 Funktionen

• $\phi _{1}(x,y)=\left({\frac {x}{3}},{\frac {y}{3}}\right)$
• $\phi _{2}(x,y)=\left({\frac {2+x-{\sqrt {3}}y}{6}},{\frac {{\sqrt {3}}x+y}{6}}\right)$
• $\phi _{3}(x,y)=\left({\frac {3+x+{\sqrt {3}}y}{6}},{\frac {{\sqrt {3}}-{\sqrt {3}}x+y}{6}}\right)$
• $\phi _{4}(x,y)=\left({\frac {2+x}{3}},{\frac {y}{3}}\right)$

Das rechtwinklige Sierpinski-Dreieck wird erzeugt von

• $\phi _{1}(x,y)=(x/2,y/2)$
• $\phi _{2}(x,y)=((x+1)/2,y/2)$
• $\phi _{3}(x,y)=(x/2,(y+1)/2)$

Links

Eine Sammlung fraktaler Kunst von Paul Bourke

Farbige Erweiterungen des Chaosspiels fraktale Flammen, unter math die Theorie dazu.

Zu Geschichte und Verallgemeinerungen: Cabrelli, Molter: Generalized Self-Similarity ...

• 1957 Selbstähnliche Funktionen von Bajraktarevic und de Rham untersucht
• 1981 Selbstähnliche Mengen und Kurven von Hutchinson untersucht
• 1986 definiert Barnslay fraktale Funktionen