F. Fasso`.    Universita` di Padova.    Laurea di I livello in Matematica.    Notebooks per il corso di Laboratorio Computazionale, a.a. 2006-2007.

5. Insiemi frattali

Lezione 13  -  16.5.7
1. Frattali classici

Insieme ternario di Cantor

Vogliamo:
- Scrivere una funzione che disegna l'approssimazione di ordine  n  dell'insieme ternario di Cantor.
- Scrivere una funzione che disegna le  prime n approssimazioni dell'insieme ternario di Cantor.

Si puo` procedere in molti modi, per lo piu` iterativi.

Procedura iterativo-funzionale
1) Si scrive una funzione "elementare" f che prende un segmento e ne produce due
2) Si applica iterativamente questa funzione, cioe` componendola con se stessa:   f(f(f(....f(s)))))

Come rappresentare i segmenti?
Un segmento e` costruito a partire dai suoi estremi, anzi, da una lista di due punti:
    Line[{P1,P2}]
(devono essere punti del piano perche` la grafica viene fatta nel piano)
- Allora identifichiamo un segmento con una lista di due punti:
           segmento = {P1,P2}

In questo modo, ogni approssimazione (Subscript[C, n]) del Cantor, che e` un unione di segmenti, diventa una lista di segmenti, cioe` una lista di coppie di punti:
              (Subscript[C, 0]) = { {P01,P02}  }                      (conviene rappresentare anche (Subscript[C, 0])in questo modo)
              (Subscript[C, 1]) = { {P11,P12} ,  {P13,P14}  }
              (Subscript[C, 2]) = { {P21,P22} , {P23,P24} ,  {P25,P26} , {P27,P28}  }
              ........
Lavoreremo pertanto su liste di coppie di punti ("liste di segmenti").

- Il problema di disegnare questi segmenti ce lo porremo solo alla fine.

Funzione elementare ("cantor1") per la costruzione dell'insieme di Cantor: 
        dato un segmento, produrne due rimuovendo il terzo centrale

Nel nostro approccio:
data una lista di due punti (=segmento) produrre una lista di due liste di due punti (= lista di due segmenti):
    cantor1 : {P1,P2} -> { {P1,P1+((P2 - P1)/3)} , {P2-((P2 - P1)/3),P2} } 
(si aggiunge cosi` una coppia di parentesi che andra` poi rimossa)

cantor1[{p1_, p2_}] := {{p1, 
          p1 + ((p2 - p1)/3)}, {p2 - ((p2 - p1)/3), p2}}

Per costruire le approssimazioni C1, C2, .... del Cantor, partiamo per esempio dal segmento {{0,1},{0,1}}

c1=cantor1[{ {0, 0}, {1, 0}}]

e iteriamo poi questa funzione elementare 1,2,3 .... volte

Ma attenzione: C1 costruita cosi` (e poi C2 ...) e` una lista di coppie di punti:
      C1 =  {{P1,P1+((P2 - P1)/3)},{P2-((P2 - P1)/3),P2}}
e   cantor1  agisce sugli elementi di questa lista, non sulla lista.
Per poter applicare cantor1 a C1  bisogna mapparla.

Map   (molto importante)

Se f e` (il nome di) una funzione di una variabile, allora 
     Map[f,{x1,x2,...}]
restituisce la lista
     {f[x1],f[x2],....}

Esempio:

Map[Sin, {1, 2, 3}]

Nota: le funzioni "listabili", quando applicate ad una lista, vengono automaticamente mappate su di essa:

Sin[{1, 2, 3}]

Definiamo allora una "funzione elementare mappata" come
         cantor2[lista]  =  Map[cantor1, lista]

cantor2[ls_] := Map[cantor1, ls]

c2 = cantor2[c1]

c3 = cantor2[c2]

Problema: la "funzione elementare" cantor1 agisce su liste di due punti , non su liste di liste di due punti. 
Dunque la "funzione elementare mappata" aggiunge un livello, che bisogna "sciogliere" con
    Flatten[ lista, 1]
Ridefiniamo cantor2 in modo da fare anche questa operazione:

cantor2[ls_]:=Flatten[ Map[cantor1, ls],1]

c2 = cantor2[c1]

c2 // Dimensions

Iterazione di una funzione. 
La composizione di una funzione con se` stessa si fa con il comando
       Nest[funzione, punto, numero di composizioni]
Esempio:
       Nest[f,p,0] = p
       Nest[f,p,1] = f[p]
       Nest[f,p,2] = f[f[p]]
       Nest[f,p,3] = f[f[f[p]]]

Scriviamo una funzione cantor3 che itera n volte cantor2, a partire da (Subscript[C, 0]).
Attenzione: cantor2 agisce su liste di segmenti. Dunque, al primo passo, non va applicata al segmento {{0,0},{1,0}}, ma ad una lista il cui solo elemento e` questo segmento. Possiamo dargli un nome (c0)

c0={ { {0, 0}, {1, 0}} };

cantor3[n_]:= Nest[ cantor2,c0 ,n]

cantor3[0]

cantor3[1]

cantor3[2]

cantor3[3]

Per semplificare un po' l'output, e velocizzarlo, conviene sostituire (Subscript[C, 0])con una lista di numeri reali, invece che interi.

c0={{ {0. , 0. }, {1. , 0. }}};

cantor3[3]

Figura:
-  Trasformiamo la lista di "segmenti" (= coppie di punti) in una lista di segmenti (= primitive grafiche). 
    Si fa mappandogli sopra  Line
-  Trasformiamo poi questa lista di primitive grafiche in un oggetto grafico con Graphics
-  Mostriamo infine l'oggetto grafico con Show

Scriviamo una funzione cantor4[n] che lo fa per la approssimazione n-ma

cantor4[n_]:= Show[  Graphics[   
                              Map[Line, cantor3[n]]
                          ] ]

cantor4[4]

Possiamo infine costruire una Table delle prime n approssimazioni del Cantor, per es per n=3

Table[ cantor4[k],{k, 0, 3}];

E` brutto: sono troppo distanti.

Trucco: per avvicinarli, possiamoridurre  l'AspectRatio.
Visto che ci siamo, fissiamo anche la dimensione dell'immagine.

cantor4[n_]:= Show[  Graphics[   Map[Line,  cantor3[n]]], 
                              AspectRatio -> 0.05,
                             ImageSize -> 500]

Table[ cantor4[k],{k, 0, 3}];

Table[cantor4[k], {k, 0, 6}];

Koch and Koch island (snowflake)

La curva di Koch e` un esempio di curva continua che non e` differenziabile in alcun punto. Si ottiene iterando la seguente trasformazione: 
       Si prende un segmento  ___   e lo si sostituisce con una poligonale    _/\_   formata da segmenti di uguale lunghezza
Si ripete poi questa costruzione su ciascun segmento della poligonale, etc.

Il "fiocco di neve" di Koch si ottiene procedendo allo stesso modo, ma partendo da un triangolo.

Scrivere delle funzioni che disegnano le approssimazioni n-me della curva di Koch e del fiocco di neve.

Suggerimento: procedere come per il Cantor ternario:
- lavorare su poligonali = liste di segmenti, con segmento = lista di due punti. 
- Si puo` per esempio scrivere delle funzioni:

koch1[segmento]: e` la funzione elementare che crea la poligonale base   _/\_   del koch a partire dal segmento ___ di vertici p e q
Prende gli estremi di un segmento
        (p,q)
e ritorna la poligonale  
       ( (p,p1),(p1,p2),(p2,p3),(p3,q) )  ) 
ove  
       p1=p+((q-p)/3), p3=p+2((q-p)/3), p2=((q + p)/2)+ ort, 
ove "ort" e` il vettore ortogonale a pq e lungo quel che si vuole (calcolarlo: va espresso in funzione di q e p).

Conviene calcolare   ort   una sola volta ogni chiamata di koch1. Questo si puo` fare per es. con un Module:
    \(\(\(koch1[{p_, q_}] := 
          Module[{}, 
\ \ \ \ \ \ \ \ \ \ \ \ \ \(\(\(ort =. \) ... \) ... \) .. \ ; 
\ \ \ \ \ \ \ \ \ \ \ \ \ \(p1 =. \) ... ; 
\ \ \ \ \ \ \ \ \ \ \ \ \ p2 = \  ... ; 
\ \ \ \ \ \ \ \ \ \ \ \ \ p3 = \  ... ; 
\ \ \ \ \ \ \ \ \ \ \ \ {{p, p1}, {p1, p2}, {p2, p3}, {p3, q}}];\)\(
\)
      \)\)
Questa non e` la notazione piu` compatta, ma e` molto leggibile.

Per scrivere una funzione che esegue piu` comandi uno dopo l'altro, e` meglio usare un  Module.
Il suo uso permette anche di definire variabili "locali".

Il comando
        Module[{simboli locali} ,
                comando1;
                comando2;
                ........;
                ultimo comando]
produce come output l'output dell'ultimo comando.

I simboli dichiarati nella lista di simboli locali sono "locali al modulo". 
La lista di simboli locali puo` essere vuota (ma deve esserci!)

NB: Dopo la lista dei simboli locali ci vuole una virgola
       I comandi devono essere separati da un punto e virgola 
       (ma Module produce un unico output)

Per spiegazioni sull'uso del Module vedere l'Help. Assicurarsi di capire i seguenti semplici esempi:

x = 2;

Module[{},
             x = 
          2 t; 
            Sin[x]]

x

x = 2;

Module[{x},
             x = 
          2 t; 
            Sin[x]]

x

t = 3;

Module[{x},
             x = 
          2 t; 
            Sin[x]]

x

Si puo` anche inizializzare un simbolo locale, cosa utile per esempio se viene fatta un'iterazione:

Module[{t = 1}, t]

t

Clear[x, t]

koch2: mappa   koch1  su una poligonale e produce la nuova poligonale

koch3: trasforma la poligonale in oggetto grafico, che puo` poi essere mostrato con Show

koch4[n,pol]: produce l'oggetto grafico per la n-ma iterazione di koch2 a partire da una poligonale pol.  Si puo` poi mostrarla con  Show

\(A\ seconda\ della\ scelta\ della\ poligonale\ iniziale, \ 
      si\ produce\ la\ koch\ \((se\ un\ segmento)\)\ o\ lo\ snowflake\ \((triangolo\ equilatero)\)\ etc\)

NB: Dare nomi simbolici (p,...) agli argomenti delle funzioni, e sceglierli numericamente solo al momento di creare i disegni. (Se no, viene un codice pesante ed inoltre diventa difficile variare, per esempio, la forma del triangolo, la poligonale di partenza, etc.

Esempio: per costruire la curva di Koch si parte da un segmento.

(chiamiamo koch[n] la funzione koch4[n,polinomiale che produce il Koch] )

koch[4];

koch[5];

koch va bene se se ne vuole costruire uno solo. Se si vuole costruire una successione di approssimazioni successive di koch conviene applicare iterativamente koch2 (i tempi diventano un po' lunghi) :

NB:
-  la self-similarity  e` evidentissima
- e` istruttivo ingrandire molto (moltissimo) la sesta o settima o ottava iterazione: appare con evidenza la struttura locale del koch

Esempio: per costruire la snowflake si parte da un triangolo

Lezione 15 -   18.5.7
3. The chaos game

Il gioco

Fissiamo tre punti nel piano:  (Subscript[P, 1]), (Subscript[P, 2]), (Subscript[P, 3])
Scegliamo un punto (Subscript[Q, 0]) all'interno del triangolo di vertici   (Subscript[P, 1]), (Subscript[P, 2]), (Subscript[P, 3]) (per esempio, isoscele)
Gettiamo un dado con tre facce, numerate 1,2,3: se il risultato e`  k   disegnamo il punto
     (Subscript[Q, 1 ])= punto di mezzo del segmento di estremi (Subscript[Q, 0]) e  (Subscript[P, k])      (k=1,2,3)
Iteriamo il gioco infinite volte: se alla n-ma prova il risultato e` (Subscript[k, n]), 
     (Subscript[Q, n])= punto di mezzo del segmento di estremi (Subscript[Q, n - 1]) e  \(TraditionalForm\`\(P\_k\)\_\(\_n\)\)      (k=1,2,3)

Esempio: f[n] mostra le prime n mani di un gioco.

P[1] = {0, 0};
P[2] = {1. , 0};
P[3] = { .5, (Sqrt[3.]) /2. }; 
    tb = {{0.5`, 0.5`}, {0.75`, 0.25`}, {0.625`, 
          0.5580127018922193`}, {0.8125`, 0.27900635094610965`}, {0.40625`, 
          0.13950317547305482`}, {0.703125`, 
          0.06975158773652741`}, {0.3515625`, 
          0.034875793868263706`}, {0.42578125`, 
          0.45045059882635113`}, {0.462890625`, 
          0.6582380013053949`}, {0.4814453125`, 
          0.7621317025449168`}, {0.49072265625`, 
          0.8140785531646777`}};
f[k_] := 
      ListPlot[Join[{P[1], P[2], P[3]},   Take[tb, k]], 
        AspectRatio -> Automatic, PlotRange -> {{0, 1}, {0, 1}}, 
        PlotStyle -> PointSize[ .03]]

f[10]

Domanda: 
- come si distribuiscono i punti nel triangolo? 
- la distribuzione limite ha proprieta` di regolarita?

Altra domanda: 
- cosa succede se si prende il dato iniziale esterno al triangolo?

Suggerimenti:

1. Numeri (pseudo) casuali
Si generano con   Random[ tipo, intervallo].
Per esempio    Random[Real,{0,1}],   Random[Integer{1,3}] ....

2.a. Si possono per esempio definire i tre vertici  come  componenti di una lista  
             P={..,..,..}
Allora una mano del chaos game e`  data da una funzione 
            game(Q)  =  punto medio del segmento di estremi  Q  e   P[[numero casuale estratto]] .

2.b. Oppure, e forse meglio, si possono definire i tre vertici come valori di una funzione P: 
            P[1]  =... ,  P[2] =....,  P[3] =....
Allora una mano del chaos game e`   
            game(Q)  =  punto medio del segmento di estremi  Q  e   P[numero casuale estratto] .

NB: \(Prendere\ i\ tre\ vertici\ in\ modo\ che\ il\ triagolo\ sia\), per esempio, equilatero .  Per esempio {0, 0}, {1, 0},{(1/2), ((Sqrt[3])/2)}.

3. Per creare la lista {Q,game(Q), game(game(Q)), .....} , con n iterazioni, si usa il comando  NestList[Q,game,n]

3. Definire inifne una funzione   play[Q,n]   che gioca n mani e fa il disegno (con ListPlot; al solito, aggiustare l'AspectRatio  e far si` che venga mostrato tutto il triangolo)

Conclusioni

Conclusione: 
- abbiamo una dinamica casuale
- in cui ogni dato iniziale tende asintoticamente ad un Sierpinski gasket.

Il Sierpinski gasket e` un attrattore per la dinamica. 
Un po' come un punto di equilibrio asintoticamente stabile per un'equazione differenziale: tutte le soluzioni vi tendono asintoticamente.
Qui, pero`, l'insieme limite ha una struttura (strana)

Inoltre, l'attrattore e` invariante per la dinamica: cioe`, gli evoluti di un punto che appartiene all'attrattore restano sull'attrattore.
Questo si capisce facilmente pensando al fatto che l'attrattore, cioe` il Sierpinski, e` costituito dai lati di tutti i triangoli ottenuti con il seguente procedimento iterativo:

(Questa e` in effetti ancora un'altra caratterizzazione del Sierpinski)

L'invarianza dell'attrattore e` facilmente verificata analiticamente. 
Puo` essere pero` utile mostrarla graficamente, evidenziando anche il fatto che le orbite tendono all'attrattore.

Esercizio: scrivere una funzione   f[n,p]   che gioca le prime  n  mani del chaos game con dato iniziale p e disegna gli n punti insieme alle prime n+1 approssimazioni del Sierpinski. 
Verificare poi, su poche iterate, che se il punto iniziale appartiene al Sierpinski cosi` fanno i suoi evoluti e che, se non vi appartiene, i suoi evoluti tendono al Sierpinski.

|Un'analisi del problema si trova, per esempio, in 
H.O. Peitgen, H. Jürgens, D. Saupe: Chaos and Fractals - New Frontiers of Science
Capitolo 6:  "The chaos game: how randomness creates deterministic shapes"
(E` un bel libro - voluminoso ma molto bello. Il livello matematico e` elementare, ma completo, ed inoltre e` spiegato come "fare")

Spiegazione

A lezione, abbiamo presentato i frattali "perfettamente simmetrici" come quegli insiemi che hanno una (a,k) autosimilarità: il frattale è fatto di a parti che assomigliano a copie ottenute riscalando di un fattore k

Questa idea si formalizza in una costruzione di oggetti frattali che va sotto il nome di Iterated Function System (IFS)

Esempio (la curva di Koch). Tutto comincia con l'intervallo [0,1]...

a = Table[{i, 0}, {i, 0, 1, 0.01}];
ListPlot[a, AspectRatio -> 1,  
        PlotRange -> {{-0.1, 1.1}, {-0.1, 0.7}}, 
        Axes -> False];

...e  con 4 contrazioni affini del piano:

R[θ_] :=  {{Cos[θ], -Sin[θ]}, {Sin[θ], Cos[θ]}};

F[1][{x_, y_}]:= N[{(x/3), (y/3)}]
F[2][{x_, y_}]:=N[R[(π/3)].{(x/3), (y/3)}+{(1/3), 0}]
F[3][{x_, y_}]:=N[ R[-(π/3)].{(x/3), (y/3)}+{(1/2), (1/((Sqrt[3]) 2))}]
F[4][{x_, y_}]:=N[ {(x/3), (y/3)}+{(2/3), 0}]

Le 4 contrazioni mandano il segmento [(0,0),(1,0)]  rispettivamente nei segmenti
                 [(1, 0), ((1/3), 0)] ,             [{(1/3), 0},{(1/2),((Sqrt[3])/2)}],                 [{(1/2),((Sqrt[3])/2)},{(2/3), 0}],                   [((2/3), 0), (1, 0)]
e dunque, applicandole tutte quante si trova ....

b = 
        Union[Map[F[1], a], Map[F[2], a], Map[F[3], a], 
          Map[F[4], a]];
ListPlot[b, AspectRatio -> Automatic,  
        PlotRange -> {{-0.1, 1.1}, {-0.1, 0.3}}, 
        Axes -> False];

Cosa succede se iteriamo il processo?

c=Union[Map[F[1],b],Map[F[2],b],Map[F[3],b],Map[F[4],b]];
ListPlot[c, 
        AspectRatio -> Automatic,  
        PlotRange -> {{-0.1, 1.1}, {-0.1, 0.3}}, 
        Axes -> False];

d = 
        Union[Map[F[1], c], Map[F[2], c], Map[F[3], c], 
          Map[F[4], c]];
ListPlot[d, AspectRatio -> Automatic,  
        PlotRange -> {{-0.1, 1.1}, {-0.1, 0.3}}, 
        Axes -> False];

e = 
        Union[Map[F[1], d], Map[F[2], d], Map[F[3], d], 
          Map[F[4], d]];
ListPlot[e, AspectRatio -> Automatic,  
        PlotRange -> {{-0.1, 1.1}, {-0.1, 0.3}}, 
        Axes -> False];

E se invece di prendere molti punti iniziali in [0,1] si sceglie un punto qualsiasi dello spazio e si applicano in molte volte le mappe F[i] scegliendole di volta in volta in modo random? E` l'idea del "gioco del caos".