Quelltext der Seite Iteriertes Funktionensystem

Ein '''iteriertes Funktionensystem''' ('''IFS''') ist eine Menge <math> \mathcal F</math> von [[Funktion (Mathematik)|Funktionen]], die denselben Raum <math>M</math> als Definitions- und Wertebereich haben und unter Verknüpfung abgeschlossen sind. Also
:<math> \mathcal F\circ\mathcal F\subset\mathcal F\;</math> d.&nbsp;h. <math>\; \forall f,g\in\mathcal F:\; f\circ g\in\mathcal F.</math>

Iterierte Funktionensysteme dienen meist der Konstruktion von [[Fraktal]]en, die dann auch als ''IFS-Fraktale'' bezeichnet werden. Bekannte Vertreter dieser Klasse von Fraktalen sind das [[Sierpinski-Dreieck]] und die [[Koch-Kurve]] wie auch die Grenzmengen von [[Lindenmayer-System]]en.

<gallery>
Bild:Sierpinski-Trigon-7.svg|[[Sierpinski-Dreieck]]
Bild:Kochkurve.png|[[Koch-Kurve]]
Bild:Menger_5.PNG|[[Sierpinski-Teppich]]
Bild:Drachen_p.png|[[Drachenkurve|Drachen-Fraktal]]
</gallery>

Diese Art der Fraktalkonstruktion wurde 1981 von John Hutchinson erfunden<ref name="hutchinson1981"/> und später von [[Michael F. Barnsley]] mit seinem Buch ''Fractals Everywhere''<ref name="barnsley1988"/> popularisiert.<ref name="peruggia1993"/> Dort gab Barnsley auch den ''Collage-Satz'' an, welcher die Grundlage der [[Fraktale Bildkompression|fraktalen Bildkompression]] bildet. Diese Art, Bilder effizient mittels Datenstrukturen zu kodieren, hat sich jedoch nie richtig durchsetzen können und wird heute im Wesentlichen nur noch als Hybridverfahren in Kombination mit einer [[Wavelet-Transformation]] untersucht.

== Invariante, selbstähnliche Mengen ==

Um für ein IFS Eigenschaften ableiten zu können, muss die Funktionenmenge zusätzliche Voraussetzungen erfüllen. Üblicherweise, wenn von ''IFS'' gesprochen wird, werden diese Voraussetzungen stillschweigend als gegeben angenommen. Diese Voraussetzungen sind 
# dass das IFS endlich erzeugt ist, also endlich viele Funktionen enthält, aus welchen die anderen durch wiederholte (iterierte) Verknüpfung zusammengesetzt werden können, 
# dass der Raum <math>M</math> ein [[Vollständiger Raum|vollständiger]] [[metrischer Raum]] mit Metrik <math>d</math> ist, und
# dass jede Funktion des IFS [[Kontraktion (Mathematik)|kontraktiv]] bezüglich <math>d</math> ist. Mit Voraussetzung 1. reicht es, dies von den Erzeugenden zu verlangen.

Unter diesen Umständen gibt es eine invariante, [[Selbstähnlichkeit|selbstähnliche]] Menge <math>X \subseteq M</math>.
* Die Teilmenge <math>X</math> ist invariant, wenn sie von jeder Funktion des IFS wieder in sich abgebildet wird.
* Die Teilmenge <math>X</math> ist selbstähnlich, wenn jeder Punkt aus <math>X</math> in der Bildmenge <math>F(X)</math> einer Funktion <math>F\in\mathcal{F}</math> liegt. 
Selbstähnliche Mengen haben meist keine ganzzahlige [[Hausdorff-Dimension]] und werden dann auch als Fraktal bezeichnet, deshalb die Bezeichnung ''IFS-Fraktal''. Man könnte auch weitergehend den Begriff der Selbstähnlichkeit durch die Forderung der Existenz eines IFS definieren.

== Existenz und Eindeutigkeit der invarianten Menge ==

[[Mathematik|Mathematisch]] gesehen handelt es sich bei der Theorie der ''iterierten Funktionensysteme'', wie auch die Begrifflichkeit vermuten lässt, um eine direkte Anwendung des
[[Fixpunktsatz von Banach|banachschen Fixpunktsatzes]], wobei mehrere Funktionen statt einer betrachtet werden und, statt eines eindeutigen Fixpunktes, sich eine invariante, meist fraktale, Teilmenge des Raumes <math>M</math> ergibt. Zur Illustration wird meist das zweidimensionale Einheitsquadrat <math>M=[0,1]\times [0,1]</math> mit dem euklidischen Abstand gewählt.

Wir beginnen also mit einer endlichen Menge von Funktionen eines [[Kompakter Raum|kompakten]] [[Metrischer Raum|metrischen Raumes]] <math>(M,d)</math> in sich selbst:
:<math>\mathcal F_1:=\{\phi_1,\dots,\phi_r \colon M\to M\},</math>
von denen wir voraussetzen, dass es eine Kontraktionskonstante <math>0<c<1</math> gibt mit
:<math>\forall x,y\in M,\phi\in\mathcal F_1:\;d(\phi(x),\phi(y))\le c\,d(x,y)</math>

Durch [[Iteration]] setzen wir <math>\mathcal F_1</math> zu einem IFS <math>\mathcal F</math> fort, es sei
:<math>\mathcal F_{n+1}:=\mathcal F_1\circ \mathcal F_n := \{ \phi\circ F:\;\phi\in\mathcal F_1,\;F\in\mathcal F_n\}</math>
und erhalten schließlich
:<math>\mathcal F:=\bigcup_{n=1}^\infty \mathcal F_n</math>.

{{Kasten|
''Satz:'' Sind alle Funktionen <math>\phi_1,\dots,\phi_r</math> in <math>\mathcal F_1</math> [[Kontraktion (Mathematik)|kontraktiv]], so gibt es eine invariante Teilmenge <math>X</math>, welche die Fixpunktgleichung
:<math>X=\bigcup_{i=1}^r \phi_i(X)</math>
erfüllt. Für diese gilt:

* Zu jedem <math>F\in\mathcal F</math> gibt es genau einen Fixpunkt. Die invariante Menge <math>X</math> ist der topologische Abschluss der Menge aller Fixpunkte 
::<math>\{x\in M|\;\exists F\in\mathcal F:\,x=F(x)\}</math>.
* Ist <math>y \in M</math> ein beliebiger Punkt, so gilt für den Abstand dieses Punktes 
::<math>d(X,F(y))\le c_F\,d(X,y)</math> für jedes <math>F\in\mathcal F</math>. 
:Es gilt die Abschätzung <math>c_F\le c^m</math>, falls <math>F</math> eine <math>m</math>-fache Verkettung <math>F\in\mathcal F_m</math> der Ausgangsfunktionen ist. 

* Damit kann <math>X</math> durch Iteration einer beschränkten Ausgangsmenge 
::<math>X_0\subset M,\quad X_{n+1}=\bigcup_{i=1}^r \phi_i(X_n)</math> 
:beliebig gut angenähert werden.
}}

Der Beweis des Satzes erfolgt dadurch, dass man aus dem metrischen Raum <math>(M,d)</math> einen neuen Raum konstruiert, dessen „Punkte“ genau die [[Kompakter Raum|kompakten]] Teilmengen von <math>M</math> sind. Hierauf kann man eine Metrik definieren (die [[Hausdorff-Metrik]]), bezüglich der dieser Raum vollständig und die Abbildung <math>X\mapsto \bigcup_{i=1}^r \phi_i(X)</math> eine Kontraktion ist. Dadurch wird der banachsche Fixpunktsatz anwendbar.

== Approximation der Grenzmenge ==

=== Chaosspiel ===

Die Gestalt der fraktalen Menge <math>X</math> kann durch ein so genanntes ''Chaosspiel'' visualisiert werden. Dabei wird zunächst
ein Fixpunkt <math>\vec x</math> von <math>\vec x=\phi_1(\vec x)</math>
aufgesucht und auf diesen in zufälliger Reihenfolge die definierenden Funktionen angewandt. Als [[Algorithmus]] kann dies wie folgt aussehen:

* Weise 100 mal hintereinander <math>\vec x:=\phi_1(\vec x)</math> zu
* Wiederhole beliebig oft
** Wähle zufällig ein <math>i \in \left\{1, \dots,r\right\}</math>
** Weise <math>\vec x:=\phi_i(\vec x)</math> zu
** Zeichne den Punkt <math>x</math>.

Anmerkung:
#Es ist in den ersten, blinden, [[Iteration]]en unwesentlich, welche Funktion gewählt wird, da in jedem Schritt der Abstand zur fraktalen Menge <math>X</math> reduziert wird. Ist z.&nbsp;B. die Kontraktionskonstante <math>c=0{,}5</math> und die Grundmenge <math>M</math> das [[Einheitsquadrat]], welches mit 1024×1024 [[Pixel]]n dargestellt wird, so ist bereits nach 12 blinden Iterationen der Fehler unter die Pixelgröße gesunken.
#Es werden im Allgemeinen bessere Darstellungen erzielt, wenn die Wahrscheinlichkeit des Aufrufs jeder der Funktionen <math>\phi_i</math> in etwa proportional zum Volumen von <math>\phi_i(M)</math> ist.

=== Rekursion ===

Eine weitere Möglichkeit der Darstellung, vorzugsweise für die affinen Fraktale, ist die ''rekursive'' Approximation der Menge <math>X</math>. Dies wird meist anschaulich mittels eines Fotokopierers
erklärt: Man macht verschiedene Verkleinerungen eines Ausgangsbildes, fixiert diese nach Vorschrift
auf einem neuen Blatt und benutzt dieses dann als Ausgangsbild des nächsten Schrittes.

Auch die ''Turtle-Grafik'', die zur Konstruktion der [[Fraktal|L-Systeme]]
verwendet wird, folgt einer ähnlichen Idee. 

Als Algorithmus braucht man dazu eine rekursiv aufrufbare Funktion, welche die Zuordnung 
<math>F(n)=\bigcup_{i=1}^r \phi_i(F(n-1))</math> bei einer beliebigen Menge <math>F(0)</math>
realisiert. Die Implementierung benötigt einen Stackspeicher, in welchem das jeweils aktuelle Koordinatensystem als affine
Koordinatentransformationen festgehalten wird. Damit ergibt sich als Algorithmus

[[Datei:Koch-rekursiv.png|mini|Das Koch-Fraktal in den Rekursionstiefen 0 bis 5]]
<math>Figur(n)</math>:
* Falls <math>n=0</math> 
** zeichne die Basisfigur (z.&nbsp;B. eine Strecke, einen Buchstaben, ein schwarzes Rechteck)
* sonst:
** Für <math>i:=1</math> bis <math>r</math> 
*** Lege aktuelles Koordinatensystem auf Stack ab
*** Transformiere das aktuelle Koordinatensystem entsprechend <math>\phi_i</math>
*** Rufe <math>Figur(n-1)</math> auf
*** Stelle Koordinatensystem vom Stack wieder her

Fraktal:
* Rufe <math>Figur(10)</math> auf (10 als Beispiel)

== Beispiele für iterierte Funktionensysteme ==

=== Affine Abbildungen ===

Die erzeugenden Funktionen des IFS seien [[affine Abbildung]]en des zweidimensionalen
Einheitsquadrates in sich selbst. Jede Funktion <math>\phi_k</math> ist gegeben durch eine 2×2-[[Matrix (Mathematik)|Matrix]] <math>A_k</math> und einen Verschiebungs[[vektor]] <math>b_k</math>.

Das [[Koch-Kurve|Koch-Fraktal]] wird z.&nbsp;B. von folgendem System von 2 Funktionen erzeugt:
* <math>\phi_1\binom{x}{y}= \frac1{\sqrt3}\begin{pmatrix}\cos30^\circ&\sin30^\circ\\ \sin30^\circ&-\cos30^\circ\end{pmatrix}\, \binom{x}{y}</math>, 
* <math>\phi_2\binom{x}{y}= -\frac1{\sqrt3}\begin{pmatrix}-\cos30^\circ&\sin30^\circ\\ \sin30^\circ&\cos30^\circ\end{pmatrix} \binom{x}{y}+\frac1{\sqrt3}\binom{\cos30^\circ}{\sin30^\circ}</math>

Die klassische Methode zur Erzeugung der Koch-Kurve benutzt 4 Funktionen
* <math>\phi_1(x,y)=\left(\frac{x}3,\frac{y}3 \right)</math>
* <math>\phi_2(x,y)=\left(\frac{2+x-\sqrt3 y}6,\frac{\sqrt3 x+y}6\right)</math>
* <math>\phi_3(x,y)=\left(\frac{3+x+\sqrt3 y}6,\frac{\sqrt3-\sqrt3 x+y}6\right)</math>
* <math>\phi_4(x,y)=\left(\frac{2+x}3 ,\frac{y}3\right)</math>

Das rechtwinklige Sierpinski-Dreieck wird erzeugt von
* <math>\phi_1(x,y)=\left(\frac{x}2,\frac{y}2\right)</math>
* <math>\phi_2(x,y)=\left(\frac{x+1}2,\frac{y}2\right)</math>
* <math>\phi_3(x,y)=\left(\frac{x}{2},\frac{y+1}{2}\right)</math>

== Collagen ==

Grundlage für die Begeisterung für solche IFS-Fraktale war das Collage-[[Theorem]] von Barnsley. Es besagt, dass jede kompakte Menge – jede Gestalt – durch ein IFS-Fraktal beliebig genau angenähert werden kann. Die Grundlage dafür sind folgende Beobachtungen:

{{Kasten|
1. Jede endliche Menge ist ein IFS–Fraktal. Die zugehörigen Funktionen sind diejenigen konstanten Funktionen, welche den gesamten Raum auf jeweils einen der endlich vielen Punkte abbilden.

2. Jede kompakte Menge <math>K</math> hat für jedes <math>\varepsilon>0</math> ein <math>\varepsilon</math>-Netz, wird also durch endlich viele Kugeln vom Radius <math>\varepsilon</math> überdeckt.

:⇒ Das IFS-Fraktal der Kugelmittelpunkte enthält die Ausgangsmenge in einer <math>\varepsilon</math>-Umgebung
}}

Anschaulicher: Haben wir in einem 100×100-Pixelbild eine Figur von 500 schwarzen Pixelpunkten, so können wir das Bild um den Faktor 100 auf die Größe eines Pixels verkleinern und mit diesem einen schwarzen Punkt dann wieder die Figur malen, indem wir ihn auf jeden der zugehörigen 500 Pixel abbilden. Diese Vorgehensweise ist bei weitem nicht optimal, hier wäre das einfache Speichern der Positionen der 500 Pixel einfacher. Aber wenn wir für den gleichen Zweck mit nur fünf Abbildungen auskämen, wäre eine Datenreduktion erzielt. 

Wir sind auch nicht auf einfache Schwarzweißbilder eingeschränkt. Bei einem [[Graustufenbild]] kann der Grad der Schwärzung als dritte Koordinate des Punktes aufgefasst werden, es ergibt sich eine kompakte Fläche im dreidimensionalen Raum, auf welche wieder das Collage-Theorem angewendet werden kann. Mit systematischen Verfahren zur Konstruktion eines IFS-Fraktals mit möglichst wenigen Funktionen befasst sich die [[Fraktale Bildkompression]] sowie die [[Fraktale Tonkompression]].

== Weblinks ==
{{Commonscat|Iterated function systems|Iterierte Funktionensysteme}}
* [http://fraktale.quadsoft.org Informative Seite über Fraktale und IFS für Einsteiger mit zahlreichen Illustrationen]
* Eine Sammlung fraktaler Kunst von [http://paulbourke.net/fractals/ Paul Bourke]
* Farbige Erweiterungen des Chaosspiels [http://flam3.com/ fraktale Flammen], unter ''math'' die Theorie dazu.
* Zu Geschichte und Verallgemeinerungen: Cabrelli, Molter: [http://citeseer.ist.psu.edu/165405.html Generalized Self-Similarity ...]
** 1957 Selbstähnliche Funktionen von Bajraktarevic und de Rham untersucht
** 1981 Selbstähnliche Mengen und Kurven von Hutchinson untersucht
** 1986 definiert Barnsley fraktale Funktionen

== Einzelnachweise ==
<references>

<ref name="barnsley1988">{{Literatur |Autor=Michael Barnsley |Titel=Fractals Everywhere |Datum=1988 |Verlag=Academic Press |ISBN=978-0-12-079062-3}}</ref>

<ref name="hutchinson1981">{{Literatur |Autor=John E. Hutchinson |Titel=Fractals and self similarity |Sammelwerk=Indiana University Mathematics Journal |Datum=1981 |Band=30 |Nummer=5 |Online=https://pdfs.semanticscholar.org/b093/7152a00ab8706387cf7fd08e424ab29de6e7.pdf |Format=PDF |KBytes=483}}</ref>

<ref name="peruggia1993">{{Literatur |Autor=Mario Peruggia |Titel=Discrete Iterated Function Systems |Verlag=Taylor & Francis, CRC Press |Datum=1993 |ISBN=978-0-42906-536-1 |DOI=10.1201/9781439864708 |Seiten=ix,xi}}</ref>

</references>

{{Normdaten|TYP=s|GND=4343626-2}}

[[Kategorie:Fraktale Geometrie]]
[[Kategorie:Computerkunst]]