Creare frattali con sistemi di funzioni iterate con un grafo diretto

Immagini di frattali create usando sistemi di funzioni iterate con un grafo diretto (DGIFSs) si possano trovare nella galleria. La categoria di DGIFSs contiene ed estende proprio la categoria di sistemi di funzioni iterate (IFSs) “standard”, quindi forniscono un buon metodo per creare frattali. Qui descriviamo brevemente la matematica usata.

Cos'è un frattale?

Una definizione precisa di un frattale non esiste. In parole semplici è ragionevole aspettarsi che un frattale sia simile a se stesso, anche se in modo approssimativo, con dettagli precisi, su scale diverse. (Usiamo “in modo approssimativo” qui per includere l'auto-somiglianza distorta di frattali come gli insieme di Julia così come l'esatta auto-somiglianza di frattali come il triangolo di Sierpiński.) Ciò significa che la sua forma, o parte della sua forma, viene ripetuta su scale sempre più piccole mentre l'ingrandiamo. Questa auto-somiglianza su scale diverse è presente in molte forme naturali che ci circondano. Ad esempio cavolfiori, alberi, montagne, coste, fulmini, nuvole, galassie a spirale, neuroni nel cervello, i sistemi circolatorio e respiratorio del nostro corpo, sono alcune forme frattali che si possano trovare in natura. L'insieme di Mandelbrot è un frattale perché ha questa proprietà, in quanto se ingrandiamo il suo bordo possiamo trovare copie, approssimativamente simili a se stesso, a scale sempre più piccole. Anche in questo caso si tratta solo di copie “approssimativamente simili” perché, per citare Bodil Branner dal suo articolo sull'insieme di Mandelbrot, “M contiene piccole copie di se stesso ... che a loro volta contengono copie più piccole di M e così via all'infinito. Questa osservazione potrebbe portare alla conclusione errata che M è auto-simile. In realtà, ogni insieme di mini-Mandelbrot ha il suo modello di decorazioni esterne, ognuna diversa dall'altra ...”.

Per di più per un frattale avere dettagli sul ridimensionamento è una proprietà importante, ad esempio il cerchio unitario, che è un insieme di Julia, non è un frattale in quanto non ha i dettagli richiesti. Comunque gli insiemi di Julia nella galleria sono tutti frattali.

La definizione di DGIFS garantisce che i loro attrattori (di solito) hanno componenti che sono simili a se stessi, anche se in modo approssimativo, con dettagli precisi, su scale diverse. Quindi questi componenti sono quasi sempre frattali.

L'insieme di Cantor, il triangolo di Sierpiński e la spugna di Menger sono ben noti esempi di frattali e ciascuno di essi può essere definito come l'attrattore di un IFS standard. Poiché un IFS standard è in realtà solo un DGIFS in cui il grafo diretto associato ha un solo vertice, la classe di IFSs standard è una sottoclasse della classe di DGIFSs. (Vedere i libri di Barnsley, Falconer, Peitgen et al e Edgar per descrizioni dettagliate degli IFS standard.) La definizione tecnica di un DGIFS e ulteriori informazioni si possano trovare nei riferimenti elencati di seguito, ma qui proviamo a spiegare, in modo approssimativo, cos'è un DGIFS.

La categoria dei DGIFSs è una categoria molto ampia di sistemi dinamici dove si usa un grafo diretto per imporre un ordine in cui le funzioni associate possono essere applicate. Se il grafo diretto ha n vertici le dinamiche di un DGIFS producono sempre un unico insieme di n componenti che è noto come un attrattore. Per comprendere i DGIFSs è utile iniziare considerando alcuni aspetti delle dinamiche del triangolo di Sierpiński che porta il nome del matematico polacco Waclav Sierpiński. Il triangolo di Sierpiński è l'attrattore di un 1-vertice DGIFS (un IFS standard) e per questo il triangolo di Sierpiński è un buon punto di partenza prima di spiegare la natura più generale di un n-vertice DGIFS con n ≥ 2.

Il triangolo di Sierpiński

In primo luogo, per il triangolo di Sierpiński, X = K(ℝ2), l'insieme di tutti i sottoinsiemi compatti non vuoti del piano reale, ℝ2. Un insieme compatto è chiuso e limitato in ℝ2, consultare il libro di Sutherland per le definizioni tecniche. Per i nostri scopi è sufficiente sapere che insiemi compatti sono (più o meno) sottoinsiemi del piano reale che giacciono dentro aree finite. Un aspetto importante di K(ℝ2) è che i suoi elementi sono insiemi anche se a volte li chiamiamo punti. Infatti ogni punto (x, y) appartiene a K(ℝ2) ma i tre insiemi in Figura 5 appartengono anche loro a K(ℝ2). Chiaramente K(ℝ2) è un enorme insieme (di insiemi).

triangolo

T0

un insieme compatto

A

un insieme compatto

B

Figura 5: Tre insiemi in K(ℝ2).

In secondo luogo la funzione, f: K(ℝ2) → K(ℝ2), per il triangolo di Sierpiński prende la forma

(1)     f(A) = f1(A) ∪ f2(A) ∪ f3(A)

dove A è qualsiasi elemento di K(ℝ2). Figura 6 mostra l'effetto su T0 delle tre funzioni separate, f1, f2 e f3, che insieme definiscono f. Ognuna di loro scala T0 per 0.5 e lo sposta, senza ruotarlo o rifletterlo. Dopo un'iterazione otteniamo

T1 = f(T0) = f1(T0) ∪ f2(T0) ∪ f3(T0).

La prima iterazione di f definita da f1, f2 e f3

Figura 6: La prima iterazione di f definita da f1, f2 e f3.

Proprio come la metrica euclidea può misurare una distanza tra due punti nel piano reale, ℝ2, esiste un'altra metrica di Hausdorff, che porta il nome del matematico tedesco Felix Hausdorff, che può misurare una distanza tra due elementi di K(ℝ2), (consultare i libri di Barnsley, Falconer, Peitgen et al e Edgar per la definizione della metrica di Hausdorff). Ad esempio la metrica di Hausdorff può misurare una distanza tra gli insiemi A e B in Figura 5. Una funzione f è una contrazione se per qualsiasi due insiemi A e B la distanza tra gli insiemi f(A) e f(B) è inferiore alla distanza tra A e B (rispetto alla metrica di Hausdorff). La funzione f, definita dall'Equazione (1) e Figura 6, è una contrazione. Il teorema delle contrazioni garantisce che per il sistema dinamico (K(ℝ2), f), la sequenza di iterazioni o l'orbita {f n(A0)} di qualsiasi punto di partenza A0 converge sempre ad un unico punto T di K(ℝ2), dove T è anche l'unico punto fisso di f, con f(T) = T. L'insieme T è il frattale noto come il triangolo di Sierpiński. T è anche conosciuto come l'attrattore del IFS perché tutte le orbite di punti in K(ℝ2) si avvicinano a T lungo le loro orbite.

I primi sei punti dell'orbita {f n(T0)} di T0 sotto f sono mostrati in Figura 7, dove si vede una versione leggermente sovrapposta del solito triangolo di Sierpiński.

Il triangolo iniziale

T0 = f 0(T0)

La prima iterazione del triangolo di Sierpiński

T1 = f(T0) = f 1(T0)

La seconda iterazione del triangolo di Sierpiński

T2 = f(T1) = f 2(T0)

La terza iterazione del triangolo di Sierpiński

T3 = f(T2) = f 3(T0)

La quarta iterazione del triangolo di Sierpiński

T4 = f(T3) = f 4(T0)

La quinta iterazione del triangolo di Sierpiński, un frattale

T5 = f(T4) = f 5(T0)

Figura 7: Ti per i = 0 a 5, le prime cinque iterazioni del triangolo di Sierpiński, un frattale.

Non possiamo disegnare il triangolo di Sierpiński ma solo versioni approssimative, per esempio un modo è di utilizzare punti lungo un'orbita. Infatti non abbiamo bisogno di iterare f molte volte prima che i triangoli diventano di dimensione inferiore alla distanza tra due pixel adiacenti di qualsiasi immagine digitale.

Il macchinario dietro un IFS standard, come quello che produce il triangolo di Sierpiński, può essere generalizzato a un n-vertice DGIFS usando la struttura di un grafo diretto (digrafo). Un grafo diretto consiste in un insieme finito di vertici (nodi) con un insieme di archi orientati che collegano vertici ad altri vertici in direzioni specifiche. Funzioni, contrazioni tipo f1, f2 e f3 in Equazione (1) sopra, vengono assegnate a tutti gli archi del grafo diretto che poi fornisce una regola che governa l'ordine in cui le funzioni possono essere applicate. Nel caso più semplice di un IFS standard, qual'è un 1-vertice DGIFS con un grafo diretto composto da un solo vertice, in cui tutti gli archi sono loop, non c'è alcuna restrizione sull'ordine in cui le funzioni possono essere applicate. Se il grafo diretto ha n vertici si può dimostrare, utilizzando il teorema delle contrazioni, che avrà un unico attrattore con n componenti.

Un DGIFS con 4 vertici basato sul triangolo di Sierpiński

Un esempio di un DGIFS è l'immagine DGIFS5. Per questo quadro il sistema dinamico prende la forma ((K(ℝ2))4, f) dove (K(ℝ2))4 = (K(ℝ2), K(ℝ2), K(ℝ2), K(ℝ2)) e f è una funzione costituita dalle funzioni f1, f2 e f3 di Figura 6, che vengono applicate seguendo la struttura di un grafo diretto con 4 vertici (mostrato in Figura 8). Poichè f è una contrazione (utilizzando una metrica derivata dalla metrica di Hausdorff) il teorema delle contrazioni garantisce l'esistenza di un unico attrattore con 4 componenti T = (T1, T2, T3, T4) dove i componenti Ti sono elementi di K(ℝ2). Ogni componente Ti assomiglia al triangolo di Sierpiński T perché tutte le singole funzioni usate sono f1, f2 e f3 di Figura 6 come si può vedere nella Figura 9. Infatti l'immagine etichettata DGIFS5 è un'illustrazione di T1.

Adesso se mettiamo T0 = (T0, T0, T0, T0) = (T0,1, T0,2, T0,3, T0,4) dove T0 è il triangolo in Figura 7, la notazione per la sua orbita {f n(T0)} è

T0 = (T0,1, T0,2, T0,3, T0,4)

T1 = f(T0) = (T1,1, T1,2, T1,3, T1,4)

T2 = f(T1) = f2(T0) = (T2,1, T2,2, T2,3, T2,4)

e cosi via.

Come nel caso del triangolo di Sierpiński, la sequenza di iterazioni o l'orbita {f n(A0)} di qualsiasi punto di partenza A0 = (A0,1, A0,2, A0,3, A0,4) converge sempre all'attratore T dove T è l'unico punto fisso di f con f(T) = T.

Il grafo diretto con 4 vertici utilizzato per creare l'immagine DGIFS5

Figura 8: Il grafo diretto con 4 vertici utilizzato per creare l'immagine DGIFS5.

Le figure 8 e 9 illustrano il modo in cui la funzione f è derivata dalle funzioni f1, f2 e f3 usando un grafo diretto con 4 vertici. Specificamente la funzione f1 è assegnata agli archi e1, e4, e7 e e10 nel grafo diretto di Figura 8. La funzione f2 è assegnata agli archi e2, e5, e8 e e11. La funzione f3 è assegnata agli archi e3, e6 e e9. Per complicare ulteriormente le cose, esiste una convenzione che richiede che le funzioni mappano nella direzione opposta agli archi a cui sono associate nel grafo diretto. Questa convenzione risulta essere utile per la teoria ma significa ad esempio che l'arco e1 va nella direzione dal vertice v1 a v4 nella Figura 8 ma la funzione f1 mappa dal vertice v4 a v1 nella Figura 9.

La prima iterazione di f che utilizza un grafo diretto con 4 vertici

Figura 9: La prima iterazione di f che utilizza il grafo diretto con 4 vertici di Figura 8.

I primi componenti Ti,1, per i = 0 a 5, delle prime 5 iterazioni di T0 sono mostrati in Figura 10, dove le funzioni f1, f2 e f3 sono state leggermente modificate per l'utilizzo nel grafo diretto con alcuni minori cambiamenti degli spostamenti e del fattore di scala 0.5.

Il triangolo iniziale per il primo componente

T0,1

La prima iterazione del primo componente dell'attrattore di un IFS con un grafo diretto con 4 vertici, basato sul triangolo di Sierpiński

T1,1

La seconda iterazione del primo componente dell'attrattore di un IFS con un grafo diretto con 4 vertici, basato sul triangolo di Sierpiński

T2,1

La terza iterazione del primo componente dell'attrattore di un IFS con un grafo diretto con 4 vertici, basato sul triangolo di Sierpiński

T3,1

La quarta iterazione del primo componente dell'attrattore di un IFS con un grafo diretto con 4 vertici, basato sul triangolo di Sierpiński

T4,1

Un componente del triangolo di Sierpiński frattale, creato con un sistema di funzioni iterate (IFS) con un grafo diretto.

T5,1

Figura 10: Ti,1 per i = 0 a 5, le prime cinque iterazioni del primo componente frattale dell'attrattore di un DGIFS con 4 vertici.

Confrontando la Figura 10 con la Figura 7, anche se le singole funzioni sono quasi uguali, si vede che il grafo diretto rompe la simmetria del triangolo di Sierpiński originale.

Quello che segue è un elenco di tutte le immagini nella categoria DGIFS. Le immagini denominate Cloud 7, DGIFS7c, DGIFS7d e DGIFS11a sono componenti di 2-vertice DGIFS attrattori. Static 1, Static 2, Static 3 e Strings sono componenti di 3-vertice DGIFS attrattori. L'immagine DGIFS5 è un'illustrazione di un componente di un attrattore di un DGIFS strettamente collegato con il triangolo di Sierpiński, come descritto sopra. Le immagini Light on a Lake, DGIFS8b, Intersection, Red City, Ruins e Light over Waterloo sono componenti di 5-vertice DGIFS attrattori.

Altre immagini che utilizzano un grafo diretto nello stesso modo descritto sopra, ovvero per limitare l'ordine in cui vengono applicate le funzioni associate, sono Veiled Grid (creata con funzioni trigonometriche) e Planetary Disk, Planetary Disk 2, Lunar Disk e K Disk (create con trasformazioni di Möbius).

Animazioni frattali create con DGIFSs

Due video frattali realizzati con sistemi di funzioni iterate con un grafo diretto (DGIFSs) sono su YouTube.

Uno è un'animazione (4m 08s) dell'immagine Light on a Lake in versione 1080p e in versione 4K. La colonna sonora (pianoforte) è “An Amalgamation Waltz 1839” di Joep Beving.

L'altro video è un'animazione (5m) dell'immagine Red City in versione 1080p e in versione 4K. La colonna sonora “Red City Moves” (pianoforte e archi) è disponibile su alcuni servizi di streaming musicale.

Riferimenti

La ricerca che segue dimostra che un DGIFS produce qualcosa di diverso e nuovo rispetto a un IFS standard. Questa ricerca ha fornito la motivazione per creare le immagini dei frattali DGIFS che si possano trovare nella galleria.

G. C. Boore, Directed Graph Iterated Function Systems, Ph.D. thesis, School of Mathematics and Statistics, St Andrews University, (2011).

research-repository.st-andrews.ac.uk/handle/10023/2109

G. C. Boore, Some new classes of directed graph IFSs, (2014).

arxiv.org/abs/1402.6092

G. C. Boore and K. J. Falconer, Attractors of directed graph IFSs that are not standard IFS attractors and their Hausdorff measure, Math. Proc. Camb. Phil. Soc. 154 (2013), 324-349.

doi.org/10.1017/S0305004112000576

Questo libro descrive la matematica alla base di un DGIFS e un IFS standard (1-vertice).

G. A. Edgar, Measure, Topology, and Fractal Geometry, Springer-Verlag, New York, (2000).

Gli articoli di Graeme Boore su arXiv includono questo articolo che tratta di misure autosimilari (con un grafo diretto).

G. C. Boore, The qth packing moments and the packing Lq-spectra of directed graph self-similar measures, (2017).

arxiv.org/abs/1704.07252