Sistema di funzioni iterate

Esempio di costruzione iterata di un frattale

Un sistema di funzioni iterate (spesso abbreviato in IFS dall'inglese Iterated Function System) è un insieme di $n$ trasformazioni affini contrattive (che agiscono cioè sulla scala degli oggetti trattati. Pur avendo a che fare più con la teoria degli insiemi che con la geometria frattale vengono più spesso impiegati e citati in quest'ultimo campo.

Definizione formale

Formalmente, un sistema di funzioni iterate è un insieme finito di applicazione di contrazione $𝒮$ su uno spazio metrico completo.

In formula:

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

è un sistema di funzioni iterato se ogni $f_i$ è una contrazione sullo spazio metrico completo $X$.

Tipi

Normalmente, vengono utilizzati due tipi di algoritmi, la versione deterministica o quella casuale.

L'algoritmo deterministico consiste nel prendere un insieme di punti, che può essere una qualsiasi figura geometrica, e applicarvi ciascuna delle $n$ trasformazioni affini del sistema, per cui otteniamo $n$ serie di punti trasformati. A ognuno di essi riapplichiamo ognuna delle n funzioni, ottenendo $n_2$ nuove serie di punti. Continuiamo in questo modo iterando sui risultati, fino a quando l'unione di tutti gli insiemi ottenuti nell'ultima iterazione si avvicina sufficientemente alla figura che costituisce l'attrattore del sistema. Arriveremo sempre a questo attrattore, indipendentemente dal set di punti selezionato iniziale. Ogni IFS ha un attrattore caratteristico, che sarà un frattale autosimile, poiché è costruito su copie di se stesso, sempre più piccole. Normalmente, non ci vogliono molte iterazioni per ottenere questo insieme frattale.

L'algoritmo casuale è simile, ma invece di applicare le funzioni a un insieme di punti, li applichiamo a un singolo punto ancora e ancora, disegnando il risultato ogni volta. Assegniamo un valore di probabilità a ciascuna delle trasformazioni di sistema, tenendo conto che la somma totale dei valori di probabilità delle funzioni deve essere 1. In ogni iterazione dell'algoritmo, selezioniamo una delle trasformazioni con probabilità $p$. Per far questo è sufficiente ottenere un valore casuale compreso tra 0 e 1 e aggiungere le probabilità di ciascuna funzione una alla volta fino a ottenere un risultato maggiore del numero casuale ottenuto. Questa sarà la funzione selezionata.

I primi punti della serie vengono scartati. Poiché di solito sono molto lontani dall'attrattore, il resto viene tracciato fino a ottenere il disegno frattale corrispondente, il che avviene solitamente dopo un numero di iterazioni compreso tra 1000 e 5000.