Iteriertes Funktionssystem

In der Mathematik sind iterierte Funktionensysteme ( IFS ) eine Methode zur Konstruktion von Fraktalen ; die resultierenden Fraktale sind oft selbstähnlich . IFS-Fraktale sind enger mit der Mengenlehre als mit der fraktalen Geometrie verwandt. ^{[ 1 ]} Sie wurden 1981 eingeführt.

IFS- Fraktale, wie sie üblicherweise genannt werden, können beliebig viele Dimensionen haben, werden aber üblicherweise zweidimensional berechnet und dargestellt. Das Fraktal besteht aus der Vereinigung mehrerer Kopien von sich selbst, wobei jede Kopie durch eine Funktion transformiert wird (daher „Funktionensystem“). Das bekannteste Beispiel ist das Sierpiński-Dreieck . Die Funktionen sind in der Regel kontrahierend , d. h., sie bringen Punkte näher zusammen und verkleinern Formen. Die Form eines IFS-Fraktals besteht somit aus mehreren sich möglicherweise überlappenden kleineren Kopien von sich selbst, von denen jede wiederum aus Kopien von sich selbst besteht, ad infinitum . Dies ist die Ursache für seine selbstähnliche fraktale Natur.

Formal ist ein iteriertes Funktionensystem eine endliche Menge von Kontraktionsabbildungen auf einem vollständigen metrischen Raum . ^{[ 2 ]} Symbolisch:

${\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} }$

ist ein iteriertes Funktionensystem, wenn jedes f _i eine Kontraktion auf dem vollständigen metrischen Raum X ist .

Hutchinson zeigte, dass für den metrischen Raum ℝ^ⁿ , oder allgemeiner für einen vollständigen metrischen Raum , ein solches Funktionensystem eine eindeutige, nichtleere, kompakte (abgeschlossene und beschränkte) Fixmenge S besitzt . ^{[ 3 ]} Eine Möglichkeit, eine Fixmenge zu konstruieren, besteht darin, mit einer anfänglichen nichtleeren, abgeschlossenen und beschränkten Menge S _₀ zu beginnen und die Operationen der Funktionen f _{_i} zu iterieren , wobei S _{_{n +1}} die Vereinigung der Bilder von S _{_n} unter den Funktionen f _{_i} ist ; anschließend wird S als der Abschluss des Limes gewählt.${\displaystyle X}$limn →∞Symbolisch hat die _eindeutige feste (nichtleere kompakte) Menge S ⊆ X die Eigenschaft

${\displaystyle S={\overline {\bigcup _{i=1}^{N}f_{i}(S)}}.}$

Die Menge S ist somit die Fixmenge des Hutchinson-Operators F  : 2 ^X → 2 ^X, der für A ⊆ X definiert ist durch

${\displaystyle F(A)={\overline {\bigcup _{i=1}^{N}f_{i}(A)}}.}$

Die Existenz und Eindeutigkeit von S ist eine Folge des Fixpunktsatzes , ebenso wie die Tatsache, dass

${\displaystyle \lim _{n\to \infty }F^{n}(A)=S}$

Für jede nichtleere kompakte Menge A in X gilt: (Bei kontraktiven IFS tritt diese Konvergenz sogar für jede nichtleere, abgeschlossene und beschränkte Menge A ein .) Zufällige Elemente beliebig nahe an S können durch das unten beschriebene „Chaosspiel“ gewonnen werden.

Kürzlich wurde gezeigt, dass IFSs nicht-kontraktiver Art (d. h. aus Abbildungen zusammengesetzt, die keine Kontraktionen bezüglich einer topologisch äquivalenten Metrik in X sind ) Attraktoren erzeugen können. Diese treten auf natürliche Weise in projektiven Räumen auf, wobei sich auch die klassische irrationale Rotation auf dem Kreis anpassen lässt. ^{[ 4 ]}

Die Menge der Funktionen f _{_i} erzeugt unter Komposition ein Monoid . Existieren nur zwei solcher Funktionen, lässt sich das Monoid als Binärbaum visualisieren , wobei an jedem Knoten des Baums entweder die eine oder die andere Funktion verwendet werden kann ( d. h. der linke oder der rechte Zweig gewählt wird). Allgemein lässt sich das Monoid bei k Funktionen als vollständiger k -ärer Baum , auch Cayley-Baum genannt, darstellen .

Manchmal wird gefordert, dass jede Funktion f_{_i} eine lineare oder allgemeiner eine affine Transformation ist und daher durch eine Matrix dargestellt wird . IFSs können jedoch auch aus nichtlinearen Funktionen, einschließlich projektiver und Möbius-Transformationen , aufgebaut sein . Die fraktale Flamme ist ein Beispiel für ein IFS mit nichtlinearen Funktionen.

Der gebräuchlichste Algorithmus zur Berechnung von IFS-Fraktalen wird als „ Chaos-Spiel “ bezeichnet. Dabei wird ein zufälliger Punkt in der Ebene gewählt und anschließend iterativ eine zufällig aus dem Funktionensystem ausgewählte Funktion angewendet, um den Punkt zu transformieren und einen nächsten Punkt zu erhalten. Ein alternativer Algorithmus besteht darin, jede mögliche Funktionsfolge bis zu einer vorgegebenen maximalen Länge zu generieren und anschließend die Ergebnisse der Anwendung jeder dieser Funktionsfolgen auf einen Startpunkt oder eine Startform grafisch darzustellen.

Jeder dieser Algorithmen erzeugt eine globale Konstruktion, die Punkte über das gesamte Fraktal verteilt. Wird nur ein kleiner Bereich des Fraktals dargestellt, liegen viele dieser Punkte außerhalb des sichtbaren Bereichs. Daher ist das Hineinzoomen in eine so erstellte IFS-Konstruktion unpraktisch.

Obwohl die Theorie von IFS voraussetzt, dass jede Funktion kontrahierend ist, erfordert Software, die IFS implementiert, in der Praxis lediglich, dass das Gesamtsystem im Durchschnitt kontrahierend ist. ^{[ 5 ]}

PIFS (partitionierte iterierte Funktionensysteme), auch lokale iterierte Funktionensysteme genannt, ^{[ 6 ]} erzielen eine überraschend gute Bildkomprimierung, selbst bei Fotografien, die scheinbar nicht die Art von selbstähnlicher Struktur aufweisen, die einfache IFS-Fraktale zeigen. ^{[ 7 ]}

Es existieren sehr schnelle Algorithmen zur Generierung eines Bildes aus einer Reihe von IFS- oder PIFS-Parametern. Es ist schneller und benötigt deutlich weniger Speicherplatz, eine Beschreibung der Bildgenerierung zu speichern, diese Beschreibung an ein Zielgerät zu übertragen und das Bild dort neu zu generieren, als die Farbe jedes einzelnen Pixels im Bild zu speichern und zu übertragen. ^{[ 6 ]}

Das inverse Problem ist schwieriger: Gegeben ein beliebiges digitales Originalbild, beispielsweise ein digitales Foto, ist ein Satz von IFS-Parametern zu finden, der durch iterative Auswertung ein Bild erzeugt, das dem Original visuell ähnlich ist. 1989 präsentierte Arnaud Jacquin eine Lösung für eine eingeschränkte Form des inversen Problems, die ausschließlich PIFS verwendet; die allgemeine Form des inversen Problems ist weiterhin ungelöst. ^{[ 8 ] [ 9 ] [ 6 ]}

Bis 1995 basierte die gesamte Software zur fraktalen Kompression auf Jacquins Ansatz. ^{[ 9 ]}

Das Diagramm zeigt die Konstruktion eines IFS aus zwei affinen Funktionen. Die Funktionen werden durch ihre Wirkung auf das Bi-Einheitsquadrat dargestellt (die Funktion transformiert das umrandete Quadrat in das schattierte Quadrat). Die Kombination der beiden Funktionen bildet den Hutchinson-Operator . Drei Iterationen des Operators werden gezeigt, und das letzte Bild zeigt den Fixpunkt, das finale Fraktal.

Zu den frühen Beispielen für Fraktale, die durch ein IFS erzeugt werden können, gehören die Cantor-Menge , die erstmals 1884 beschrieben wurde, und die de Rham-Kurven , eine Art selbstähnlicher Kurve, die 1957 von Georges de Rham beschrieben wurde.

IFSs wurden in ihrer heutigen Form von John E. Hutchinson im Jahr 1981 konzipiert ^{[ 3 ]} und durch Michael Barnsleys Buch Fractals Everywhere populär gemacht .

IFSs liefern Modelle für bestimmte Pflanzen, Blätter und Farne aufgrund der Selbstähnlichkeit, die häufig in verzweigten Strukturen in der Natur auftritt.

• System mit komplexer Basis
• Collage-Theorem
• Unendliche Kompositionen analytischer Funktionen
• L-System
• Fraktale Kompression

• Draves, Scott ; Erik Reckase (Juli 2007). „Der fraktale Flammenalgorithmus“ (PDF) . Archiviert vom Original (PDF) am 9. Mai 2008. Abgerufen am 17. Juli 2008 .
• Falconer, Kenneth (1990). Fraktale Geometrie: Mathematische Grundlagen und Anwendungen . John Wiley and Sons. S.  113–117, 136. ISBN 0-471-92287-0Die
• Barnsley, Michael ; Andrew Vince (2011). „Das Chaosspiel auf einem allgemeinen iterierten Funktionensystem“. Ergodic Theory Dynam. Systems . 31 (4): 1073–1079 . arXiv : 1005.0322 . Bibcode : 2010arXiv1005.0322B . doi : 10.1017/S0143385710000428 . S2CID 122674315 . 
• David, Claire (2019). „Fraktale Eigenschaften von Funktionen vom Weierstrass-Typ“ . Proceedings of the International Geometry Center . 12 (2): 43–61 . doi : 10.15673/tmgc.v12i2.1485 . S2CID  209964068 .

• Eine Einführung in die elementare Theorie unendlicher Kompositionen komplexer Funktionen