Sistema di funzioni iterate - Iterated function system

Triangolo di Sierpinski creato utilizzando IFS (colorato per illustrare una struttura autosimilare)

IFS colorati progettati utilizzando il software Apophysis e resi da Electric Sheep .

In matematica , i sistemi di funzioni iterate ( IFS ) sono un metodo per costruire frattali ; i frattali risultanti sono spesso auto-similari . I frattali IFS sono più legati alla teoria degli insiemi che alla geometria frattale. Sono stati introdotti nel 1981.

I frattali IFS , come vengono normalmente chiamati, possono essere di qualsiasi numero di dimensioni, ma sono comunemente calcolati e disegnati in 2D. Il frattale è costituito dall'unione di più copie di se stesso, ciascuna delle quali è trasformata da una funzione (da cui "sistema di funzioni"). L'esempio canonico è il triangolo di Sierpiński . Le funzioni sono normalmente contrattive , il che significa che avvicinano i punti e rendono le forme più piccole. Quindi, la forma di un frattale IFS è composta da diverse copie più piccole di se stesso possibilmente sovrapposte, ognuna delle quali è costituita anche da copie di se stesso, all'infinito . Questa è la fonte della sua natura frattale auto-similare.

Definizione

Formalmente, un sistema di funzioni iterate è un insieme finito di mappature di contrazione su uno spazio metrico completo . Simbolicamente,

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

è un sistema di funzioni iterate se ciascuna è una contrazione sullo spazio metrico completo . ${\displaystyle f_{i}}$${\displaystyle X}$

Proprietà

Costruzione di un IFS dal gioco del caos (animato)

IFS essendo realizzato con due funzioni.

Hutchinson (1981) ha mostrato che, per lo spazio metrico , o più in generale, per uno spazio metrico completo , un tale sistema di funzioni ha un unico insieme fisso compatto (chiuso e limitato) S . Un modo per costruire un insieme fisso è di partire da un insieme iniziale non vuoto chiuso e limitato S ₀ e iterare le azioni di f _i , assumendo S _{n +1} come unione delle immagini di S _n sotto la f _i ; assumendo quindi S come la chiusura dell'unione della S _n . Simbolicamente, l'unico insieme fisso (compatto non vuoto) ha la proprietà ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle X}$${\displaystyle S\subseteq X}$

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

L'insieme S è quindi l'insieme fisso dell'operatore di Hutchinson definito per via ${\displaystyle F:2^{X}\to 2^{X}}$${\displaystyle A\subseteq X}$

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

L'esistenza e l'unicità di S è una conseguenza del principio di mappatura delle contrazioni , così come il fatto che

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

per qualsiasi insieme compatto non vuoto in . (Per IFS contrattile questa convergenza avviene anche per ogni insieme chiuso limitato non vuoto ). Elementi casuali arbitrariamente vicini a S possono essere ottenuti dal "gioco del caos", descritto di seguito. ${\displaystyle A}$${\displaystyle X}$${\displaystyle A}$

Recentemente è stato dimostrato che gli IFS di tipo non contrattivo (cioè composti da mappe che non sono contrazioni rispetto ad alcuna metrica topologicamente equivalente in X ) possono produrre attrattori. Questi sorgono naturalmente negli spazi proiettivi, sebbene anche la rotazione irrazionale classica sul cerchio possa essere adattata.

La raccolta di funzioni genera un monoide in composizione . Se ci sono solo due di queste funzioni, il monoide può essere visualizzato come un albero binario , dove, ad ogni nodo dell'albero, si può comporre con l'una o l'altra funzione ( cioè prendere il ramo sinistro o destro). In generale, se ci sono k funzioni, allora si può visualizzare il monoide come un albero k- ario completo , noto anche come albero di Cayley . ${\displaystyle f_{i}}$

costruzioni

Felce di Barnsley , uno dei primi IFS

Spugna di Menger , un IFS tridimensionale.

IFS "albero" costruito con funzione non lineare Julia

A volte ogni funzione deve essere una trasformazione lineare , o più generalmente affine , e quindi rappresentata da una matrice . Tuttavia, gli IFS possono anche essere costruiti da funzioni non lineari, comprese le trasformazioni proiettive e le trasformazioni di Möbius . La fiamma frattale è un esempio di IFS con funzioni non lineari. ${\displaystyle f_{i}}$

L'algoritmo più comune per calcolare i frattali IFS è chiamato " gioco del caos ". Consiste nel selezionare un punto casuale nel piano, quindi applicare in modo iterativo una delle funzioni scelte a caso dal sistema di funzioni per trasformare il punto per ottenere un punto successivo. Un algoritmo alternativo consiste nel generare ogni possibile sequenza di funzioni fino a una data lunghezza massima e quindi nel tracciare i risultati dell'applicazione di ciascuna di queste sequenze di funzioni a un punto o forma iniziale.

Ciascuno di questi algoritmi fornisce una costruzione globale che genera punti distribuiti sull'intero frattale. Se viene disegnata una piccola area del frattale, molti di questi punti cadranno al di fuori dei confini dello schermo. Questo rende lo zoom in una costruzione IFS disegnata in questo modo poco pratico.

Sebbene la teoria dell'IFS richieda che ogni funzione sia contrattile, in pratica il software che implementa IFS richiede solo che l'intero sistema sia in media contrattile.

Sistemi di funzioni iterate partizionate

PIFS (sistemi di funzioni iterate partizionate), chiamati anche sistemi di funzioni iterate locali, offrono una compressione dell'immagine sorprendentemente buona, anche per fotografie che non sembrano avere il tipo di struttura auto-simile mostrata dai semplici frattali IFS.

Il problema inverso

Esistono algoritmi molto veloci per generare un'immagine da un insieme di parametri IFS o PIFS. È più veloce e richiede molto meno spazio di archiviazione per memorizzare una descrizione di come è stata creata, trasmettere tale descrizione a un dispositivo di destinazione e rigenerare nuovamente quell'immagine sul dispositivo di destinazione, piuttosto che memorizzare e trasmettere il colore di ciascun pixel nell'immagine .

Il problema inverso è più difficile: data un'immagine digitale arbitraria originale come una fotografia digitale, prova a trovare un insieme di parametri IFS che, se valutato per iterazione, produce un'altra immagine visivamente simile all'originale. Nel 1989, Arnaud Jacquin ha presentato una soluzione a una forma ristretta del problema inverso utilizzando solo PIFS; la forma generale del problema inverso rimane irrisolta.

A partire dal 1995, tutto il software di compressione frattale si basa sull'approccio di Jacquin.

Esempi

Il diagramma mostra la costruzione su un IFS da due funzioni affini. Le funzioni sono rappresentate dal loro effetto sul quadrato biunitario (la funzione trasforma il quadrato delineato nel quadrato ombreggiato). La combinazione delle due funzioni forma l' operatore Hutchinson . Vengono mostrate tre iterazioni dell'operatore, quindi l'immagine finale è del punto fisso, il frattale finale.

I primi esempi di frattali che possono essere generati da un IFS includono l' insieme di Cantor , descritto per la prima volta nel 1884; e le curve di de Rham , un tipo di curva autosimilare descritta da Georges de Rham nel 1957.

Storia

Gli IFS sono stati concepiti nella loro forma attuale da John E. Hutchinson nel 1981 e resi popolari dal libro di Michael Barnsley Fractals Everywhere .

Gli IFS forniscono modelli per alcune piante, foglie e felci, in virtù dell'autosomiglianza che spesso si verifica nelle strutture ramificate in natura.

—  Michael Barnsley et al.

Guarda anche

• Sistema a base complessa
• Teorema del collage
• Composizioni infinite di funzioni analitiche
• L-sistema
• Compressione frattale

Appunti

Riferimenti

• Draves, Scott ; Erik Reckase (luglio 2007). "L'algoritmo della fiamma frattale" (PDF) . Archiviato dall'originale (pdf) il 09-05-2008 . Estratto 17/07/2008 .
• Falconer, Kenneth (1990). Geometria frattale: fondamenti matematici e applicazioni . John Wiley e figli. pp.  113-117, 136 . ISBN 0-471-92287-0.
• Barnsley, Michael ; Andrew Vincent (2011). "Il gioco del caos su un sistema di funzioni iterate generali". Teoria Ergodica Dinamica. Sistemi . 31 (4): 1073-1079. arXiv : 1005.0322 . Bibcode : 2010arXiv1005.0322B .
• Per una panoramica storica e la generalizzazione: David, Claire (2019). "proprietà frattali delle funzioni di tipo Weierstrass" . Atti del Centro Internazionale di Geometria . 12 (2): 43-61.