IterierteFunktionsSysteme

Iterierte Funktionssysteme (IFS) sind in der Mathematik und der Computergrafik verwendete Modelle zur Generierung fraktalartiger Strukturen. Ein IFS besteht aus einer endlichen Menge von Kontraktionsabbildungen f_i: X -> X auf einem vollständigen metrischen Raum X. Der Hutchinson-Operator F wirkt auf die Menge von Teilmengen durch F(S) = ⋃_i f_i(S). Es existiert eindeutig eine nichtleere kompakte Menge A, die A = F(A) erfüllt; der Attraktor des IFS. Diese Eigenschaft folgt aus dem Banach-Fixpunktsatz, da F eine Kontraktion auf dem Raum der endlichen Mengen mit der Hausdorff-Metrik ist.

Bei Ähnlichkeits-IFS, bei denen jeder f_i eine Skalierung um Faktor r_i < 1 ist, ist A eine selbstähnliche Fraktalstruktur. Die Dimensionsbestimmung erfolgt oft über die Similiaritätsdimension s, die durch Σ_i r_i^s = 1 bestimmt wird (unter geeigneten Voraussetzungen, etwa der Offenbedingung).

Beispiele: Der Cantor-Satz lässt sich als IFS mit zwei Abbildungen x → x/3 und x → x/3 + 2/3 beschreiben. Das Sierpinski-Dreieck ergibt sich aus drei Abbildungen mit Faktor 1/2. Weitere Fraktale wie der Koch-Schneeflocke können ebenfalls als IFS formuliert werden.

Berechnung und Anwendungen: Theoretisch liefert der deterministische Algorithmus A_{n+1} = F(A_n) eine Annäherung an den Attraktor. Praktisch wird oft der Zufalls-Iterationsalgorithmus (Chaos Game) verwendet, bei dem zufällig ausgewählte Funktionen auf einen Punkt angewendet werden und so eine Punktwolke der Fraktalstruktur entsteht. Anwendungen finden sich in der Fraktalgrafik, Datenkompression und Modellierung natürlicher Strukturen.