Teorema delle contrazioni e sistemi di funzioni iterate · 2011-04-11 · Il teorema delle...

$: Teorema delle contrazioni e sistemi di funzioni iterate · 2011-04-11 · Il teorema delle contrazioni, che \vive" nel contesto degli spazi metrici completi, a erma che una funzio-ne$
Teorema delle contrazioni e sistemi di

funzioni iterate

Luigi Orsina

Indice

Introduzione 5

Capitolo 1. Spazi metrici e teorema delle contrazioni 91. Definizioni ed esempi 92. Successioni di Cauchy e spazi metrici completi 133. Il teorema delle contrazioni 15

Capitolo 2. Insiemi compatti e distanza di Hausdorff 191. Insiemi compatti 192. La distanza di Hausdorff 213. Completezza di (K(X), h) 26

Capitolo 3. Sistemi di funzioni iterate 331. Da funzioni su X a funzioni su K(X) 332. Sistemi di funzioni iterate 413. Il teorema del collage 434. Sistemi di funzioni iterate con probabilita 51

Capitolo 4. Misura e dimensione di Hausdorff 551. La misura di Hausdorff 552. La dimensione di Hausdorff 60

Capitolo 5. La dimensione degli attrattori degli IFS 631. La dimensione box counting 632. Confronto tra box counting e Hausdorff 663. La dimensione di Hausdorff degli attrattori degli IFS 72

Strumenti e programmi 81

Indice analitico 95

3

Introduzione

Molti degli oggetti “reali” che ci circondano, come ad esempio nuvole,alberi, felci e broccoli ( ) condividono una notevole proprieta: ognuno di essie uguale all’unione di copie (ridotte in dimensioni) dell’oggetto originale. Adesempio, la struttura “tronco da cui si dipartono rami” di un albero e replicatanella struttura “ramo da cui si dipartono rametti”, e nella struttura “ramettida cui si dipartono foglie”. Analogamente, le foglie di una felce ne replicanola struttura globale, ed a loro volta sono costituite da microfoglie disposte inmodo da imitare la felce.

La felce (non vera!) come unione di copie di se stessa

Oggetti geometrici di questo tipo si dicono “autosimilari”: scopo di questoarticolo e spiegare (o, almeno, provare a spiegare. . .) come — usando la teoriadegli spazi metrici ed il teorema delle contrazioni — sia possibile costruirein maniera semplice alcuni insiemi autosimilari. Il verbo “costruire” assumequi due significati: in primo luogo vuol dire “costruire matematicamente”,vale a dire caratterizzare dal punto di vista matematico tali insiemi; in se-condo luogo vuol dire “costruire al computer”, ovvero indicare come dare unarappresentazione (approssimata) di tali oggetti.

Gli “attori principali” del nostro lavoro saranno essenzialmente due: il teo-rema delle contrazioni e la distanza di Hausdorff. Il teorema delle contrazioni,che “vive” nel contesto degli spazi metrici completi, afferma che una funzio-ne f che “contrae” le distanze (per la definizione rigorosa si veda il Teorema1.26 nel primo capitolo) ha un unico punto fisso, ovvero un elemento x dellospazio su cui e definita f tale che f(x) = x. Questo teorema, che ha notevo-li applicazioni ad esempio nella teoria delle equazioni differenziali ordinarie,

5

6 INTRODUZIONE

e fondamentale nel contesto che ci interessa grazie all’osservazione che unacontrazione porta sı punti in punti, ma anche insiemi in insiemi; ed essendocontinua, porta compatti in compatti. Usando la distanza di Hausdorff (siveda il secondo capitolo), che permette di misurare la distanza tra compattidi uno spazio metrico, avviene il “miracolo”: se f e una contrazione da unospazio metrico in se, allora la funzione F , definita da F (K) = {f(x) , x ∈ K}per ogni compatto K, e una contrazione dallo spazio dei compatti in se rispet-to alla distanza di Hausodrff. Siccome (si veda sempre il secondo capitolo) lospazio dei compatti di uno spazio metrico completo e a sua volta completo unavolta che vi si consideri la distanza di Hausdorff, e possibile applicare il teo-rema delle contrazioni ad F , e dedurre cosı l’esistenza di un unico “compattofisso” K, tale che F (K) = K.

Chiaramente, se x e il punto fisso di f , il compatto K = {x} e il compattofisso di F (e evidente che F ({x}) = {x}, e quindi per l’unicita del punto fissosi ha la tesi), cosicche — almeno in apparenza — non c’e alcun guadagnonel passaggio da funzioni su insiemi a funzioni di insiemi. Se pero, invece diavere una sola contrazione f , ne abbiamo due, siano esse f e g, allora risultaessere una contrazione (sullo spazio dei compatti, e rispetto alla distanza diHausdorff) la funzione

F (K) = f(K) ∪ g(K) .

Nuovamente, se x e il punto fisso di f , e y e il punto fisso di g, allora {x, y}e contenuto nel compatto fisso K di F (la dimostrazione di questo fatto emeno semplice della precedente, ed usa la caratterizzazione del punto fisso diuna contrazione). In generale, pero, {x, y} non e K. Infatti, se calcoliamoF ({x, y}) troviamo

F ({x, y}) = {x , y , f(y) , g(x)} ,

che contiene strettamente {x, y} (a meno che non si abbia x = y). Pertanto, equi avviene il secondo “miracolo”, l’insieme K e piu ricco dell’insieme ottenutodall’unione dei punti fissi di f e g. Quanto piu ricco qui non diciamo (per nonscoprire troppo le carte ), limitandoci ad affermare che vedremo nel terzocapitolo numerosi esempi di contrazioni definite su R2 che generano insiemiautosimilari geometricamente complessi come punti fissi. Daremo inoltre una“ricetta” (il cosiddetto teorema del Collage) per costruire (o, meglio, ricostrui-re) le contrazioni che generano come compatto fisso un insieme autosimilaredato, o che generano un compatto fisso che approssima bene (nel senso delladistanza di Hausdorff) un insieme “reale” come un albero o una felce.

Una volta “costruiti” gli insiemi autosimilari, ci occuperemo di calcolarnela dimensione. Prima di farlo, sara necessario introdurre (nel quarto capitolo)il concetto di misura di Hausdorff (sempre lui!), che estende al caso di dimen-sioni non intere la misura di Lebesgue. Partendo dalla misura di Hausdorff,

INTRODUZIONE 7

definiremo la dimensione di Hausdorff di un insieme, che coincidera con la di-mensione “classica” nel caso di oggetti “comuni” come punti, linee, quadrati,cubi, eccetera.

Nell’ultimo capitolo calcoleremo la dimensione di Hausdorff di alcuni degliinsiemi autosimilari costruiti nel terzo capitolo. Per farlo definiremo prima ilconcetto di dimensione box counting di un insieme, piu facile da calcolare delladimensione di Hausdorff, e poi dimostreremo due risultati: una formula che,sotto opportune ipotesi sulle contrazioni che generano l’insieme autosimilare,permette di calcolare a priori la dimensione box counting di un insieme, e suc-cessivamente un teorema che afferma, sotto le stesse ipotesi, che la dimensionebox counting e la dimensione di Hausdorff coincidono.

In appendice, infine, verra brevemente spiegato come creare, in TEX quasitutte le figure presenti in questi appunti.

I risultati presentati in questi appunti sono essenzialmente contenuti nellibro “Fractals everywhere” di Michael F. Barnsley (Academic Press, Boston,1993 – collocazione: III 7 367), al quale si rimanda, e nel quale e possibiletrovare una descrizione completa ed auto-contenuta della teoria degli insie-mi frattali (ben piu completa di quella che viene qui proposta). Altri testiconsultati sono “Techniques in Fractal Geometry” di Kenneth Falconer (JohnWiley & Sons, New York, 1997), “Fractal Geometry: Mathematical Founda-tions and Applications”, sempre di Falconer (John Wiley & Sons, New York,2003 – collocazione III 7 379), e l’articolo “Fractals and Self Similarity” diJohn E. Hutchinson, Indiana Math. J. 30 (1981). Per la parte sulla misuradi Hausdorff, si veda “Weakly differentiable functions: Sobolev spaces andfunctions of bounded variation” di William P. Ziemer (Springer, New York,1989 – collocazione II 15 1750 e Col 10 120).

Disclaimer: Nessun pixel ha subito danni permanenti durante la stesura di questi appunti.

CAPITOLO 1

Spazi metrici e teorema delle contrazioni

In questo capitolo daremo le definizioni di base degli strumenti che usere-mo: definiremo gli spazi metrici, gli spazi metrici completi, ed infine enunce-remo e dimostreremo il teorema delle contrazioni, risultato fondamentale nelnostro contesto.

1. Definizioni ed esempi

Definizione 1.1. Se X e un insieme, una distanza su X e una funzioned : X ×X → R+ tale che

(d1) d(x, y) ≥ 0 per ogni x e y in X; d(x, y) = 0 se e solo se x = y;(d2) d(x, y) = d(y, x) per ogni x e y in X;(d3) d(x, y) ≤ d(x, z) + d(z, y) per ogni x, y e z in X.

La proprieta (d3) viene detta disuguaglianza triangolare.Se d e una distanza su X, la coppia (X, d) si dice spazio metrico. La

funzione d viene anche chiamata metrica.

Esempio 1.2. Se X e un insieme qualsiasi, e una distanza su X la funzione

dd(x, y) =

{1 se x 6= y,0 se x = y.

La distanza dd viene detta metrica discreta.Se X = R, e una distanza su X la funzione d(x, y) = |x− y|. Se X = R2,

e una distanza su X la funzione

d2((x1, x2), (y1, y2)) =√

(x1 − y1)2 + (x2 − y2)2 ,

detta distanza euclidea. Se X = RN e p ≥ 1, sono distanze su X le funzioni

dp((x1, . . . , xN), (y1, . . . , yN)) =

( N∑i=1

|xi − yi|p) 1

p

.

Se X = C0([a, b];R), lo spazio delle funzioni continue da [a, b] in R, sonodistanze su X le funzioni

d∞(f, g) = maxx∈[a,b]

|f(x)− g(x)| ,

9

10 1. SPAZI METRICI E TEOREMA DELLE CONTRAZIONI

e

d1(f, g) =

∫ b

a

|f(x)− g(x)| dx .

– Esercizio 1.3. Si dimostri che le funzioni definite nell’Esempio 1.2sono effettivamente delle distanze (per dp si rimanda ad un testo di Analisi II).Successivamente, si interpreti geometricamente la disuguaglianza triangolareper la distanza euclidea in R2.

Esempio 1.4. Se X = R, non e una distanza la funzione d definita da

d(x, y) = |x2 − y2| .

Se X = S, lo spazio delle successioni {xn} di numeri reali, non sonodistanze su X le funzioni

d({xn}, {yn}) = maxn∈N|xn − yn| ,

d({xn}, {yn}) = supn∈N|xn − yn| ,

e

d({xn}, {yn}) =+∞∑n=1

|xn − yn| .

Se X = R([a, b];R), lo spazio delle funzioni integrabili secondo Riemannsu [a, b], non e una distanza la funzione definita da

d(f, g) =

∫ b

a

|f(x)− g(x)| dx .

– Esercizio 1.5. Si giustifichino le affermazioni dell’esempio preceden-te.

Definizione 1.6. Se (X, d) e uno spazio metrico, si chiama sfera apertadi centro x0 e raggio r > 0 l’insieme

Br(x0) = {x ∈ X : d(x, x0) < r} .

La sfera chiusa di centro x0 e raggio r > 0 e invece l’insieme

Br(x0) = {x ∈ X : d(x, x0) ≤ r} .

Un sottoinsieme A di uno spazio metrico (X, d) si dice aperto se, per ognix0 in A, esiste r = r(x0) > 0 tale che Br(x0) ⊆ A. Un sottoinsieme C di unospazio metrico (X, d) si dice chiuso se il suo complementare Cc = X \ C eaperto. Un sottoinsieme B di uno spazio metrico (X, d) si dice limitato seesiste x0 in X, e R > 0, tale che B ⊆ BR(x0).

1. DEFINIZIONI ED ESEMPI 11

Definizione 1.7. Se {xn} e una successione contenuta in uno spaziometrico (X, d), diremo che la successione xn converge ad x0 inX, e scriveremo

limn→+∞

xn = x0 , oppure xn(X,d)−→ x0 ,

se si halim

n→+∞d(xn, x0) = 0 .

L’ultima affermazione va intesa nel senso delle successioni di numeri reali: perogni ε > 0, esiste nε in N tale che 0 ≤ d(xn, x0) < ε per ogni n ≥ nε. Si notiche la definizione di convergenza a zero della successione {d(xn, x0)} coincidecon la definizione di convergenza a zero nello spazio metrico (R, | · |).

Teorema 1.8. Sia (X, d) uno spazio metrico, ed {xn} una successionecontenuta in X. Se la successione {xn} e convergente, allora il limite e unico.

Dimostrazione. E una semplice applicazione della disuguaglianza trian-golare. Supponiamo che la successione {xn} converga ad x0 e ad y0. Perdefinizione, si ha

limn→+∞

d(xn, x0) = 0 , e limn→+∞

d(xn, y0) = 0 .

Ma allora si ha0 ≤ d(x0, y0) ≤ d(xn, x0) + d(xn, y0) ,

e siccome la successione a destra e infinitesima, dal teorema dei carabinierisegue che d(x0, y0) = 0, e quindi che x0 = y0, come volevasi dimostrare. �

Esempio 1.9. E evidente dalla definizione che in (X, d) = (R, | · |) laconvergenza di una successione e la “solita” definizione di convergenza persuccessioni di numeri reali. Se (X, d) = (RN , d2), si vede facilmente che laconvergenza di successioni e equivalente alla convergenza (in (R, | · |)) com-ponente per componente. Lo stesso vale in (RN , dp), qualsiasi sia p ≥ 1. Se(X, d) = (C0([a, b],R), d∞), la convergenza per successioni di funzioni e laconvergenza uniforme.

– Esercizio 1.10. Si dimostrino le affermazioni dell’esempio preceden-te. Se (X, d) = (X, dd), come sono fatte le successioni convergenti?

Teorema 1.11. Sia (X, d) uno spazio metrico, e sia C un sottoinsieme diX. Allora C e chiuso e se solo se per ogni successione {xn} contenuta in C, econvergente in X ad x0, si ha che x0 appartiene a C.

Dimostrazione. Sia C chiuso e sia {xn} una successione contenuta inC e convergente ad x0; supponiamo per assurdo che x0 non appartenga a C.Pertanto, x0 appartiene a A = Cc, che per definizione e un aperto, cosiccheesiste r > 0 tale che Br(x0) ⊆ A, da cui segue che Br(x0) ∩ C = ∅. Questofatto e pero assurdo, dato che la successione {xn} e: 1) contenuta in C, e 2)


convergendo ad x0, si trova definitivamente a distanza minore di r da x0, equindi in Br(x0).

Supponiamo ora che C non sia chiuso, e costruiamo una successione conte-nuta in C e convergente ad un punto che non vi appartiene. Siccome C non echiuso, A = Cc non e un aperto, e quindi esiste x0 in A tale che le sfere Br(x0)non sono contenute in A, qualsiasi sia r > 0. In altre parole, per ogni r > 0esiste xr in C = Ac tale che xr appartiene a Br(x0). Se consideriamo ora lasuccessione {xn} ottenuta scegliendo r = 1

n, abbiamo che: 1) e contenuta in

C, e 2) converge ad x0, dato che d(xn, x0) <1n, e x0 non appartiene a C. �

Definizione 1.12. Siano (X, d) e (Y, d) sono due spazi metrici; dato x0appartenente ad X, una funzione f : X → Y si dice continua in x0 se, perogni successione {xn} contenuta in X e convergente ad x0 in X, si ha che lasuccessione {f(xn)} converge a f(x0) in Y . In formule:

∀{xn} ⊆ X : xn(X,d)−→ x0 , si ha f(xn)

(Y,d)−→ f(x0) ,

ovvero

∀{xn} ⊆ X : limn→+∞

d(xn, x0) = 0 , si ha limn→+∞

d(f(xn), f(x0)) = 0 .

Una funzione f che sia continua per ogni x0 in A, sottoinsieme di X, si dicecontinua in A.

Esempio 1.13. Se (X, d) = (Y, d) = (R, | · |), una funzione f : R → R econtinua (come funzione tra spazi metrici) se e continua (nel senso “classico”del termine).

– Esercizio 1.14. Si determinino tutte le funzioni continue tra (R, | · |)e (R, dd), e tra (R, dd) e (R, | · |).

– Esercizio 1.15. Sia (X, d) uno spazio metrico, e sia x0 in X fissato.Si dimostri che la funzione dx0 : X → R, definita da

dx0(y) = d(x0, y) , ∀y ∈ X ,

e continua tra (X, d) e (R, | · |). Suggerimento: si dimostri (usando due voltela disuguaglianza triangolare) che si ha

|d(x0, y)− d(x0, z)| ≤ d(y, z) , ∀y, z ∈ X .

Definizione 1.16. Dati (X, d) e (Y, d) due spazi metrici, una funzionef : X → Y si dice lipschitziana se esiste L ≥ 0 tale che

d(f(x), f(y)) ≤ Ld(x, y) , ∀x, y ∈ X .

Un esempio di funzione lipschitziana (con L = 1) e la funzione dx0 definita

nell’Esercizio 1.15. E facile dimostrare che una funzione lipschitziana e con-tinua (si usi la definizione di continuita, di lipschitzianita, ed il teorema deicarabinieri).

2. SUCCESSIONI DI CAUCHY E SPAZI METRICI COMPLETI 13

– Esercizio 1.17. Dimostrare che ogni funzione f da (X, dd) in se elipschitziana con L = 1.

2. Successioni di Cauchy e spazi metrici completi

Definizione 1.18. Sia (X, d) uno spazio metrico, e sia {xn} una successio-ne contenuta in X. La successione {xn} si dice di Cauchy, o fondamentale,se per ogni ε > 0 esiste nε in N tale che

0 ≤ d(xn, xm) < ε , ∀n, m ≥ nε .

Teorema 1.19. Sia (X, d) uno spazio metrico, e sia {xn} una successionecontenuta in X. Se {xn} e convergente, allora e di Cauchy.

Dimostrazione. Dal momento che {xn} e convergente, esiste x0 in Xtale che, per ogni ε > 0, esiste nε in N tale che

0 ≤ d(xn, x0) <ε

2, ∀n ≥ nε .

Siano ora n e m in N maggiori di nε. Allora, per la disuguaglianza triangolare,si ha

0 ≤ d(xn, xm) ≤ d(xn, x0) + d(xm, x0) <ε

2+ε

2= ε ,

e quindi la successione {xn} e di Cauchy. �

Il viceversa del Teorema 1.19 non e vero. Ad esempio, se consideriamo(X, d) = ((0, 1), | · |) e la successione xn = 1

n+1, allora abbiamo che {xn} e di

Cauchy perche converge a zero in (R, | · |), ma non converge in (X, d), dato cheil suo limite — che non puo essere altro che zero per unicita — non appartieneall’insieme.

– Esercizio 1.20. Come sono fatte le successioni di Cauchy di (X, dd)?

Esempio 1.21. Sia (X, d) = (C0([−1, 1],R), d1), e consideriamo la succes-sione {fn} definita da

fn(x) =

−1 se −1 ≤ x < − 1n,

nx se − 1n≤ x ≤ 1

n,

1 se 1n< x ≤ 1.

il cui grafico e


-1

1

− 1n

1n

-1

1

Se fissiamo n > m, allora la successione |fn − fm| vale

|fn(x)− fm(x)| =

0 se 1m< |x| ≤ 1,

1−m|x| se 1n≤ |x| ≤ 1

m,

(n−m)|x| se |x| ≤ 1n,

ovvero

− 1n

1n

1− mn

-1 1− 1m

1m

Pertanto,

d1(fn, fm) =

∫ 1

−1|fn(x)− fm(x)| dx =

1

m

(1− m

n

)=

1

m− 1

n.

Dal momento che la successione { 1n} e di Cauchy in (R, | · |) (perche e con-

vergente), ne segue che la successione {fn} e di Cauchy in (X, d). La suc-cessione {fn}, pero, non converge in (X, d) ad alcuna funzione. Per assurdo,supponiamo che esista una funzione f in C0([−1, 1],R) tale che

limn→+∞

d1(fn, f) = limn→+∞

∫ 1

−1|fn(x)− f(x)| dx = 0 .

Sia ora ε > 0, e sia n > 1ε. Allora, poiche le funzioni integrande sono positive,

si ha

0 ≤∫ 1

ε

|fn(x)− f(x)| dx ≤∫ 1

−1|fn(x)− f(x)| dx ,

3. IL TEOREMA DELLE CONTRAZIONI 15

e quindi, essendo fn(x) ≡ 1 in [ε, 1],

0 ≤∫ 1

ε

|1− f(x)| dx ≤∫ 1

−1|fn(x)− f(x)| dx .

Facendo tendere n all’infinito si ha, ricordando che l’ultima quantita tende azero per ipotesi,

0 ≤∫ 1

ε

|1− f(x)| dx ≤ 0 .

Essendo la funzione integranda continua e positiva, si ha che |1 − f(x)| ≡ 0in [ε, 1], e quindi che f(x) ≡ 1 in [ε, 1]. Per l’arbitarieta di ε, si ha chef(x) ≡ 1 in (0, 1]. Ripetendo il ragionamento nell’intervallo [−1, ε], si ottieneche f(x) ≡ −1 in [−1, 0). La funzione f non puo pertanto essere continua,dato che si ha

limx→0−

f(x) = −1 6= 1 = limx→0+ f(x) .

Definizione 1.22. Uno spazio metrico (X, d) tale che ogni successione diCauchy sia convergente viene detto spazio metrico completo.

Esempio 1.23. Lo spazio (X, dd) e completo, qualsiasi sia X (si veda l’E-sercizio 1.20). Sono completi gli spazi (R, | · |), (R2, d2) e (RN , dp), qualsiasisia p ≥ 1. Lo spazio (C0([a, b],R), d∞) e completo.

Altri esempi di spazi completi si ottengono grazie al seguente teorema.

Teorema 1.24. Sia (X, d) uno spazio metrico completo, e sia C un sot-toinsieme chiuso di X. Allora (C, d) e uno spazio metrico completo.

Dimostrazione. Sia {xn} una successione di Cauchy in (C, d). Chiara-mente, {xn} e anche una successione di Cauchy in (X, d), che e completo.Pertanto, esiste x0 in X tale che {xn} converge a x0 in (X, d). Essendo Cchiuso e {xn} contenuta in C e convergente ad x0, per il Teorema 1.11 x0 ap-partiene a C. Abbiamo cosı dimostrato che ogni successione {xn} di Cauchyin (C, d) e convergente in (C, d), e quindi (C, d) e completo. �

3. Il teorema delle contrazioni

Definizione 1.25. Sia (X, d) uno spazio metrico. Una funzione f : X →X si dice una contrazione se e lipschitziana di costante θ < 1; ovvero seesiste 0 ≤ θ < 1 tale che

d(f(x), f(y)) ≤ θ d(x, y) , ∀x, y ∈ X .

Se f e una contrazione, la costante di lipschitz θ si chiama anche fattore dicontrazione.

Se (X, d) e uno spazio metrico, e f : X → X e una funzione, un punto xdi X si dice punto fisso per f se si ha f(x) = x.


Se (X, d) e uno spazio metrico, e f : X → X e una funzione, definiamola funzione iterata n-sima di f come la funzione f (n) : X → X data da:f (1)(x) = f(x), e f (n)(x) = f(f (n−1)(x)) se n > 1.

Teorema 1.26. Sia (X, d) uno spazio metrico completo, e sia f : X → Xuna contrazione. Allora f ha un unico punto fisso.

Dimostrazione. Sia x0 in X qualsiasi. Definiamo x1 = f(x0) = f (1)(x0),x2 = f(x1) = f (2)(x0) e, per ricorrenza, xn = f(xn−1) = f (n)(x0). Si ha,essendo f una contrazione,

d(xn+1, xn) = d(f(xn), f(xn−1))≤ θd(xn, xn−1) = θ d(f(xn−1), f(xn−2))≤ θ2d(xn−1, xn−2) = θ2d(f(xn−2), f(xn−3))≤ θ3d(xn−2, xn−3) = . . .≤ . . .≤ θnd(x1, x0) .

Pertanto, se m < n, si ha (usando piu volte la disuguaglianza triangolare):

d(xn, xm)≤n−1∑k=m

d(xk+1, xk)

≤n−1∑k=m

θk d(x1, x0) ≤ θm1− θn−m

1− θd(x1, x0) ≤

θm

1− θd(x1, x0) .

Sia ora ε > 0, e sia nε in N tale che θnε < ε(1 − θ)d(x1, x0); si noti che talenε esiste perche la successione {θn} tende a zero essendo θ < 1. Pertanto, sen e m sono maggiori di nε si ha d(xn, xm) < ε, e quindi la successione {xn}e di Cauchy in (X, d), spazio metrico completo. Ne segue che esiste x in Xtale che {xn} converge ad x. Essendo f continua (in quanto lipschitziana), sene deduce che f(xn) converge a f(x) e quindi che f(xn−1) converge ad f(x)(essendo una sottosuccessione estratta). Ma f(xn−1) e per definizione xn, equindi f(xn−1) converge a x. Per l’unicita del limite, si ha f(x) = x, e quindix e un punto fisso per f .

Supponiamo ora che x e y siano punti fissi per f , e che quindi si abbiaf(x) = x e f(y) = y. Allora, essendo f una contrazione, si ha

0 ≤ d(x, y) = d(f(x), f(y)) ≤ θ d(x, y) ,

da cui segue 0 ≤ (1 − θ) d(x, y) ≤ 0. Essendo θ < 1, deve per forza essered(x, y) = 0, e quindi x = y, cosicche il punto fisso e unico. �

Osservazione 1.27. Si noti che il punto fisso x viene trovato come li-mite dello schema iterativo xn−1 7→ xn = f(xn−1), ovvero della successione{f (n)(x0)}, qualsiasi sia la scelta del punto iniziale x0. In altre parole, nonimporta “da dove partiamo”: se f e una contrazione, al limite dell’iterazionetroveremo l’unico punto fisso.

3. IL TEOREMA DELLE CONTRAZIONI 17

Inoltre, passando al limite per m tendente ad infinito nella formula chestima d(xn, xm), si ha

(1.1) d(xn, x) ≤ θn

1− θd(x1, x0) ,

e questa formula ci dice quanto velocemente {xn} converge a x.

Esempio 1.28. Se abbiamo a disposizione una calcolatrice con una discre-ta precisione, ed in grado di calcolare le funzioni trigonometriche in radianti,possiamo determinare il valore della soluzione dell’equazione cos(x) = x sem-plicemente: 1) settando la calcolatrice in radianti; 2) scrivendo “1” (o qualsiasialtro valore); 3) premendo ripetutamente il tasto “cos”. Con un po’ di pazien-za, alla fine si ottiene il valore 0.7390851332, che e un’approssimazione dellasoluzione esatta.

y = x

y = cos(x)

cos(x) = x

x

– Esercizio 1.29. Come mai troviamo un unico punto fisso — e comemai lo troviamo — premendo ripetutamente il tasto “cos”? La funzione cos(x)non e una contrazione! Il teorema di Lagrange ci dice:

|cos(x)− cos(y)| = |−sen(ξ)| |x− y| ,

con ξ compreso tra x e y. Maggiorando |−sen(ξ)| con 1, otteniamo che cos(x)ha L = 1 come costante di Lipschitz, e quindi non e una contrazione. Sepensate di aver “maggiorato troppo”, e che forse c’e speranza che cos(x) siauna contrazione, e sufficiente prendere x = π

2+ ε e y = π

2per avere che

cos(x)− cos(y)

x− y=

cos(π2

+ ε)

ε= −sen(ε)

ε,

e l’ultima frazione tende a −1 quando ε tende a zero, cosicche

L = supx, y∈R

| cos(x)− cos(y)||x− y|

= 1 ,

e la costante di lipschitzianita di cos(x).


Esempio 1.30. Sia

f(x, y) = (x2− y

4+ 3

4, x4

+ y2

+ 14) .

Si vede facilmente che f e una contrazione su R2 (quanto vale θ?), e quindiha un unico punto fisso, che e (1, 1). Nel disegno, si vede come partendo daun punto qualsiasi del piano, le iterate convergano al punto fisso.

Il limite x non dipende da x0

CAPITOLO 2

Insiemi compatti e distanza di Hausdorff

In questo capitolo, basandoci sui risultati ottenuti nell’ambito degli spazimetrici, introdurremo i concetti di insieme compatto e di distanza di Hau-sdorff. Dimostreremo inoltre la completezza dello spazio dei compatti di unospazio metrico completo rispetto alla distanza di Hausdorff.

1. Insiemi compatti

Definizione 2.1. Un sottoinsieme K di uno spazio metrico (X, d) si dicecompatto se da ogni successione {xn} contenuta in K si puo estrarre unasottosuccessione {xnk} convergente ad un punto x0 di K.

Un sottoinsieme A di uno spazio metrico (X, d) si dice totalmente limi-tato se per ogni ε > 0 esistono y1, y2, . . ., ynε in X tali che

A ⊆nε⋃i=1

Bε(yi) .

– Esercizio 2.2. Si dimostri che ogni insieme totalmente limitato eanche limitato. Suggerimento: detto R = max{d(yi, yj), i, j = 1, . . . , nε} =d(yi, yj), allora. . .

Esempio 2.3. In (X, dd) i compatti sono tutti e soli gli insiemi finiti.Infatti, se K ⊆ X e finito, e {xn} e una successione contenuta in K, esiste xin K, ed una successione {nk} di interi tale che xnk = x per ogni k, cosicche lasottosuccessione {xnk} converge a x (si noti che questo fatto e vero qualsiasisia lo spazio metrico). Viceversa, se K ⊆ X non e finito, e possibile trovareuna successione {xn} contenuta in K tale che xn 6= xm per ogni n 6= m. Maallora dd(xn, xm) = 1, e quindi la successione {xn} non e di Cauchy, ne loe ogni sua sottosuccessione, che quindi non puo convergere. Si noti che seK ⊆ X e infinito, allora K non e totalmente limitato: e sufficiente scegliereε = 1

2.

In (RN , d2) e invece ben noto che i compatti sono tutti e soli gli insiemichiusi e limitati.

Teorema 2.4. Sia (X, d) uno spazio metrico completo e sia K un sot-toinsieme di X. Allora K e compatto se e solo se e chiuso e totalmentelimitato.

19

20 2. INSIEMI COMPATTI E DISTANZA DI HAUSDORFF

Dimostrazione. Supponiamo che K sia chiuso e totalmente limitato, esia {xn} una successione contenuta in K. Siccome K e totalmente limitato, al-

lora K e contenuto nell’unione di un numero finito di sfere di raggio 1, B1(x(1)1 ),

. . ., B1(x(1)m1). Essendo infiniti i punti della successione {xn}, in almeno una

delle sfere ne cadono infiniti: supponiamo che sia B(1) = B1(x(1)1 ), e sia n1 il

primo indice tale che xn1 appartiene a B(1). Si dimostra facilmente che ancheB(1) ∩K e totalmente limitato. Pertanto, esiste un numero finito di sfere di

raggio 12, siano esse B 1

2(x

(2)1 ), . . ., B 1

2(x

(2)m2), tali che B(1)∩K e contenuto nella

loro unione. Come prima, esiste almeno una di queste sfere, e supporremo sia

B(2) = B 12(x

(2)1 ), che contiene infiniti punti della successione. Sia n2 il primo

indice maggiore di n1 tale che xn2 appartiene a B(2) ∩K. Ovviamente, si haB(2) ⊂ B(1). Proseguendo, costruiamo una successione {B(m)} decrescente disfere di raggio 1

2m−1 ,

B(1) ⊃ B(2) ⊃ B(3) ⊃ . . . ⊃ B(m) ⊃ . . . ,

ed una sottosuccessione {xn1 , xn2 , . . . , xnm , . . .}, con la proprieta che xniappartiene a B(i) per ogni i. Sia ora ε > 0, e sia mε tale che 1

2mε−2 < ε. Se s e

t sono maggiori di mε, allora sia xns che xmt appartengono a B(mε), e quindidistano tra di loro meno di 1

2mε−2 , ovvero meno di ε. Abbiamo cosı che lasottosuccessione {xnm} e di Cauchy in (X, d), che e completo. Ne segue cheesiste il limite di {xnm}, e che tale limite appartiene a K, essendo K chiuso(si veda il Teorema 1.11), cosicche K e compatto.

Viceversa, supponiamo che K sia compatto. Se {xn} e una successionecontenuta in K e convergente in X ad x0, allora da {xn} possiamo estrarreuna sottosuccessione convergente ad un punto y0 di K. Siccome tutte lesottosuccessioni estratte da una successione convergente hanno lo stesso limite,si ha che x0 = y0, e quindi x0 appartiene a K. Per il Teorema 1.11, K echiuso. Supponiamo ora che esista ε > 0 tale che K non sia ricopribile conun numero finito di sfere di raggio ε. Cio vuol dire che esiste (almeno) unasuccessione {xn} contenuta in K e tale che d(xi, xj) ≥ ε per ogni i 6= j.Se ne deduce quindi che la successione {xn} non e di Cauchy (e sufficienteprendere ε = ε nella definizione di successione di Cauchy), ne lo e ogni suasottosuccessione. Ma questo e assurdo perche, essendo K compatto, esistealmeno una sottosuccessione di {xn} convergente, e quindi di Cauchy. �

Teorema 2.5. Siano (X, d) e (Y, d) spazi metrici, e sia f : X → Ycontinua. Se K e compatto in (X, d), allora f(K) e compatto in (Y, d).

Dimostrazione. Sia {yn} una successione contenuta in f(K). Per ipo-tesi, esiste xn in K tale che f(xn) = yn per ogni n in N. La successione {xn},essendo contenuta nel compatto K, ammette una sottosuccessione {xnm} con-vergente ad x0 in K. Essendo f continua, la successione {ynm = f(xnm)},

2. LA DISTANZA DI HAUSDORFF 21

che e una sottosuccessione di {yn}, converge a f(x0), cha appartiene quindi af(K). �

Se lo “spazio di arrivo” e R (o meglio (R, | · |)), vale l’analogo del teoremadi Weierstrass per funzioni reali di variabile reale.

Teorema 2.6. Sia (X, d) uno spazio metrico, K un sottoinsieme compattodi X, e sia f : K → R una funzione continua. Allora f ammette massimo eminimo.

Dimostrazione. La dimostrazione ricalca le linee della dimostrazione delteorema di Weierstrass per funzioni reali di variabile reale. Sia infatti

M = supx∈K

f(x) ,

e sia {xn} una successione, contenuta in K e che esiste per le proprietadell’estremo superiore, tale che

limn→+∞

f(xn) = M .

Essendo {xn} contenuta in K, che e compatto, esiste una sottosuccessione,sia essa {xnk}, convergente a x0 appartenente a K. Essendo f continua, edessendo {f(xnk)} una sottosuccessione di {f(xn)}, si ha

f(x0) = limk→+∞

f(xnk) = limn→+∞

f(xn) = M ,

cosicche M e il massimo di f su K. La dimostrazione dell’esistenza del minimoe identica. �

2. La distanza di Hausdorff

Definizione 2.7. Se (X, d) e uno spazio metrico, definiamo K(X) l’insie-me

K(X) = {K ⊆ X : K e compatto in X, K 6= ∅} .

Siano (X, d) uno spazio metrico, e K appartenente a K(X). Se x0 appar-tiene a X, definiamo la distanza di x0 da K come

d(x0, K) = min{d(x0, y), y ∈ K} .

Si noti che, essendo d(x0, ·) una funzione continua (si veda l’Esercizio 1.15),l’esistenza del minimo e garantita dal Teorema 2.6.


K

Alcune distanze dall’insieme K (appartenente a K(R2, d2))

Teorema 2.8. Sia (X, d) uno spazio metrico, e sia K appartenente aK(X). Allora la funzione dK : X → R definita da

dK(x) = d(x,K) ,

e continua.

Dimostrazione. Sia {xn} una successione contenuta in X e convergentea x0, e sia {xnk} una sua sottosuccessione. Poiche d(xnk , K) e un minimo, perogni n in N esiste ynk appartenente a K tale che

(2.1) d(xnk , K) = d(xnk , ynk) ≤ d(xnk , y) , ∀y ∈ K .

Poiche la successione {ynk} e contenuta in K, che e compatto, esiste una sot-tosuccessione {ynkh} convergente ad y0, appartenente a K. Pertanto, usando

due volte l’Esercizio 1.15 e passando al limite in (2.1),

d(x0, y0) = limh→+∞

d(xnkh , ynkh ) ≤ limh→+∞

d(xnkh , y) = d(x0, y) .

e quindid(x0, y0) = min{d(x0, y), y ∈ K} = d(x0, K) .

Abbiamo cosı dimostrato che

(2.2) d(x0, K) = limh→+∞

d(xnkh , K) .

Dunque, da ogni sottosuccessione {xnk} estratta da {xn} si puo estrarre unasotto-sottosuccessione {xnkh} per la quale vale (2.2). Siccome il limite, che

e d(x0, K), non dipende dalla sottosuccessione estratta, tutta la successioneconverge a tale limite, ovvero:

d(x0, K) = limn→+∞

d(xn, K) ,

e quindi d(·, K) e una funzione continua. �


Definizione 2.9. Siano (X, d) uno spazio metrico, e K ed H appartenentia K(X). Definiamo la distanza (orientata) di K da H come

d(K,H) = max{d(x,H), x ∈ K} .

Per il Teorema 2.1, e per il Teorema 2.6, il massimo nella definizione didistanza orientata e raggiunto. Pertanto, esiste x in K tale che d(K,H) =d(x,H). Ricordando la definizione di distanza da H, esiste y in H tale ched(x,H) = d(x, y). Ne segue che, se K e H appartengono a K(X), alloraesistono x in K e y in H tali che

d(K,H) = d(x, y) .

K H

La linea tratteggiata piu scura indica d(K,H)

Si noti che la funzione d cosı definita non e una distanza. Infatti, seK ⊂ H si ha d(K,H) = 0 (dato che d(x,H) = 0 per ogni x in K), e quindiviene violata la (d1).

Definizione 2.10. Sia (X, d) uno spazio metrico completo. La distanzadi Hausdorff su K(X) e definita da

h(K,H) = max{d(K,H), d(H,K)} .

Teorema 2.11. La distanza di Hausdorff h : K(X)× K(X) → R+ e unadistanza. Pertanto, (K(X), h) e uno spazio metrico.

Dimostrazione. Che h(K,H) sia non negativa e evidente dalla defini-zione. Supponiamo ora di avere h(K,H) = 0. Allora, sempre per definizione,si ha d(K,H) = 0, e d(H,K) = 0. Dimostriamo ora che se d(K,H) = 0,allora K ⊆ H. Innanzitutto, per definizione di d(K,H) si ha d(x,H) = 0per ogni x in K. Siccome d(x,H) e un minimo, esiste y in H tale ched(x, y) = d(x,H) = 0, e quindi x = y. Pertanto, ogni x di K appartienead H, che e quello che si voleva dimostrare. In definitiva,

h(K,H) = 0 ⇒{d(K,H) = 0 ⇒ K ⊆ Hd(H,K) = 0 ⇒ H ⊆ K

}⇒ H = K .

La simmetria di h(K,H) e evidente, e quindi non rimane che dimostrare ladisuguaglianza triangolare. Dati H, K e L in K(X), iniziamo a dimostrare


che

(2.3) d(H,K) ≤ d(H,L) + d(L,K) .

Sia x in H. Allora si ha, per ogni z in L, per definizione e per la disuguaglianzatriangolare,

d(x,K) = min{d(x, y), y ∈ K}≤min{d(x, z) + d(z, y), y ∈ K}= d(x, z) + min{d(z, y), y ∈ K}= d(x, z) + d(z,K)≤ d(x, z) + max{d(z,K), z ∈ L} = d(x, z) + d(L,K) .

Pertanto, per ogni x in H e per ogni z in L, si ha

d(x,K) ≤ d(x, z) + d(L,K) ,

da cui, osservando che la quantita a sinistra non dipende da z, e prendendo ilminimo su z, si ha

d(x,K) ≤ min{d(x, z), z ∈ L}+ d(L,K) = d(x, L) + d(L,K) .

Predendo il minimo su x in K a sinistra, ed il massimo su x in K a destra, siha allora

d(H,K) = min{d(x,K), x ∈ H}≤max{d(x, L) + d(L,K), x ∈ H} = d(H,L) + d(L,K) ,

che e proprio la (2.3). In maniera analoga, si dimostra che

(2.4) d(K,H) ≤ d(K,L) + d(L,H) .

Usando sia la (2.3) che la (2.4), si ha allora

h(K,H) = max{d(K,H), d(H,K)}≤max{d(K,L) + d(L,H), d(H,L) + d(L,K)}≤max{d(K,L), d(L,K)}+ max{d(L,H), d(H,L)}= h(K,L) + h(L,H) ,

come volevasi dimostrare. �

– Esercizio 2.12. Si dimostri che se a e b sono numeri reali, allora

max{a, b} =a+ b+ |a− b|

2.

Successivamente, si dimostri che

max{a+ b, c+ d} ≤ max{a, d}+ max{b, c} .

– Esercizio 2.13. Si dimostri che se si parte da (X, dd) allora la distanzadi Hausdorff su K(X) e nuovamente la distanza discreta (sui sottoinsiemi finitidi X).


Definizione 2.14. Sia (X, d) uno spazio metrico, e A un sottoinsieme diX. Dato γ > 0, la dilatazione di γ dell’insieme A e l’insieme A + γ cosıdefinito:

A+ γ = {y ∈ X : d(x, y) ≤ γ, per qualche x di A} = {y ∈ X : d(y, A) ≤ γ} .

L’operazione di dilatazione non “distrugge” le proprieta dell’insieme.

Lemma 2.15. Sia (X, d) uno spazio metrico, e sia K in K(X). Allora K+εe chiuso per ogni ε > 0.

Dimostrazione. Sia {xn} una successione contenuta in K + ε e conver-gente in (X, d) a x0. Per definizione di K + ε, d(xn, K) ≤ ε per ogni n inN. Essendo la funzione x 7→ d(x,K) continua (per il Teorema 2.8) e {xn}convergente,

d(x0, K) = limn→+∞

d(xn, K) ≤ ε ,

e quindi x0 appartiene a K + ε. Dal Teorema 1.11 segue la tesi. �

Lemma 2.16. Sia (X, d) uno spazio metrico, siano K e H in K(X), e siaδ > 0. Allora

(K + δ) ∪ (H + δ) ⊆ (K ∪H) + δ .

Dimostrazione. Sia x in K + δ. Per definizione, d(x,K) ≤ δ, e quindi

d(x,K) = min{d(x, y), y ∈ K} ≤ δ .

Ma allora

d(x,K ∪H) = min{d(x, y), y ∈ K ∪H} ≤ min{d(x, y), y ∈ K} ≤ δ ,

cosicche x appartiene a (K∪H)+δ; pertanto, K+δ ⊆ (K∪H)+δ. Ripetendoil ragionamento con H + δ si trova H + δ ⊆ (K ∪H) + δ e quindi la tesi. �

Grazie alla dilatazione di un insieme, possiamo caratterizzare la distanzadi Hausdorff tra due compatti.

Lemma 2.17. Sia (X, d) uno spazio metrico, e siano H e K appartenentia K(X). Allora

h(K,H) ≤ ε ⇐⇒{K ⊆ H + ε ,H ⊆ K + ε .

Dimostrazione. Iniziamo col dimostrare che d(K,H) ≤ ε se e solo seK ⊆ H + ε. Se d(K,H) ≤ ε si ha, per definizione di d(K,H), e per ogni x inK,

d(x,H) ≤ max{d(x,H), x ∈ K} = d(K,H) ≤ ε ,

cosicche x appartiene a H + ε. In definitiva, K ⊆ H + ε, come volevasidimostrare. Supponiamo ora che K ⊆ H + ε; per ogni x in K si ha allora chex appartiene a H + ε, e quindi si ha d(x,H) ≤ ε. Prendendo il massimo al


variare di x in K si ottiene d(K,H) ≤ ε, come volevasi dimostrare. La tesi sidimostra allora facilmente, osservando che

h(K,H) ≤ ε ⇐⇒{d(K,H) ≤ ε ,d(H,K) ≤ ε ,

⇐⇒{K ⊆ H + ε ,H ⊆ K + ε .

�

Osservazione 2.18. Grazie al Lemma precedente, possiamo definire inmaniera equivalente la distanza di Hausdorff tra due insiemi compatti nelseguente modo:

h(H,K) = min{ε ≥ 0 : K ⊆ H + ε e H ⊆ K + ε} .Usando le dilatazioni, possiamo dimostrare in maniera semplice una delle

proprieta di h.

Lemma 2.19. Sia (X, d) uno spazio metrico, e siano H, K, I e J in K(X).Allora

h(H ∪K, I ∪ J) ≤ max{h(H, I), h(K, J)} .Dimostrazione. Sia δ = max{h(H, I), h(K, J)}. Siccome h(H, I) ≤ δ e

h(K, J) ≤ δ, si ha per il Lemma 2.17 che H ⊆ I + δ e K ⊆ J + δ. Pertanto,H ∪K ⊆ (I + δ) ∪ (J + δ), cosicche grazie al Lemma 2.16 si ha

H ∪K ⊆ (I ∪ J) + δ .

Scambiando H e K con I e J si ha I ∪ J ⊆ (H ∪K) + δ, e quindi, sempre peril Lemma 2.17, h(H ∪K, I ∪ J) ≤ δ, ovvero la tesi. �

Il prossimo risultato ci sara utile nel seguito.

Lemma 2.20. Sia {Kn} una successione in (K(X), h), convergente a K, esupponiamo che A in K(K) sia tale che A ⊆ Kn per ogni n maggiore di uncerto n0 in N. Allora A ⊆ K.

Dimostrazione. Sia ε > 0, e sia nε in N tale che h(Kn, K) < ε per ognin maggiore di nε. Per il Lemma 2.17 si ha allora che Kn ⊆ K + ε per talin. Essendo A contenuto in Kn per n ≥ n0, scegliendo n sufficiemente grandeabbiamo A ⊆ K+ε. Pertanto, se x e in A, si ha d(x,K) ≤ ε. Per l’arbitrarietadi ε si ha d(x,K) = 0, e quindi x appartiene a K (ricordando che d(x,K) eun minimo). �

3. Completezza di (K(X), h)

Sia (X, d) spazio metrico, e sia {Kn} una successione di compatti in K(X).La successione {Kn} e di Cauchy se, per ogni ε > 0, esiste nε in N tale cheper ogni n e m maggiori di nε si ha

h(Kn, Km) < ε ⇐⇒{Kn ⊆ Km + ε ,Km ⊆ Kn + ε .

3. COMPLETEZZA DI (K(X), h) 27

Sia ora {xn} una successione di X, con la proprieta che xn appartiene a Kn perogni n in N. Ovviamente, dall’essere {Kn} di Cauchy in K(X) non discendeche {xn} e di Cauchy in X: si pensi al caso in cui Kn = [−2, 2] per ogni n inN, e xn = (−1)n. Supponiamo ora di avere una successione {xnk} di Cauchy,con {nk} successione strettamente crescente di interi, tale che xnk in Knk perogni k: possiamo “estendere” questa successione ad una successione {xn}, chesia ancora di Cauchy e sia tale che xnk = xnk per ogni k e che xn appartienea Kn per ogni n? La risposta e positiva, ed e data dal seguente lemma.

Lemma 2.21. Sia (X, d) uno spazio metrico, e sia {Kn} una successionedi Cauchy in (K(X), h). Data una successione strettamente crescente di interi{nk}, e data una successione {xnk} di Cauchy in (X, d) e tale che xnk appar-tiene a Knk per ogni k in N, esiste una successione {xn} di Cauchy in (X, d),con la proprieta che xn appartiene a Kn per ogni n in N, e che xnk = xnk perogni k in N.

Dimostrazione. Per ogni n < n1, sia xn in An tale che

d(xn1 , xn) = min{d(x, xn1), x ∈ An} = d(xn1 , An) .

Scegliamo poi xn1 = xn1 e, per n compreso tra n1 + 1 e n2 − 1, sia xn in Antale che

d(xn2 , xn) = min{d(x, xn2), x ∈ An} = d(xn2 , An) .

In generale, scegliamo xnk = xnk , e, per n compreso tra nk + 1 e nk+1 − 1,scegliamo xn in An tale che

d(xnk+1, xn) = min{d(x, xnk+1

), x ∈ An} = d(xnk+1, An) .

Kn1K1

K2

K3

xn1

x1

x2

x3

Kn2

K5

K6

K7

xn2

x5

x6

x7

La scelta della successione {xn}

Ovviamente la successione cosı costruita coincide con {xnk} per ogni k inN, ed e tale che xn appartiene a An per ogni n in N, cosicche non resta che


dimostrare che e di Cauchy in (X, d). Sia ε > 0, e sia nε tale che

nk, nh ≥ nε ⇒ d(xnk , xnh) <ε

3,

en, m ≥ nε ⇒ h(An, Am) <

ε

3.

Un tale nε esiste perche la successione {xnk} e di Cauchy in (X, d), e perchela successione {An} e di Cauchy in (K(X), h). Siano ora m e n maggiori dinε, con m compreso tra nk−1 + 1 e nk, e n compreso tra nh−1 + 1 e nh. Allora

(2.5) d(xn, xm) ≤ d(xn, xnh) + d(xnh , xnk) + d(xnk , xm) .

Ora, dal momento che h(An, Anh) < ε3, si ha d(Anh , An) < ε

3, e quindi

d(x,An) <ε

3, ∀x ∈ Anh .

Scegliendo x = xnh , otteniamo d(xnh , An) < ε3. Per definizione di xn (che e

un punto di An che realizza il minimo in d(xnh , An)), si ha d(xnh , xn) < ε3. Un

discorso analogo dimostra che d(xnk , xm) < ε3. Ricordando che d(xnh , xnk) <

ε3

per ipotesi, ed usando la (2.5), si ha d(xn, xm) < ε, e quindi la tesi. �

Siamo pronti per dimostrare il teorema fondamentale.

Teorema 2.22. Sia (X, d) uno spazio metrico completo. Allora (K(X), h)e uno spazio metrico completo. Inoltre, se {Kn} e una successione di Cauchyin (K(X), h), allora l’insieme

K = limn→+∞

Kn ,

e cosı caratterizzato:

K = {x ∈ X : esiste una successione {xn ∈ Kn} che converge a x} .Dimostrazione. La dimostrazione e divisa in cinque passi: se K e l’in-

sieme definito nell’enunciato del teorema, allora

a) K e non vuoto;b) K e chiuso (e quindi (K, d) e uno spazio metrico completo);c) Per ogni ε > 0 esiste nε in N tale che K ⊆ An + ε per ogni n ≥ nε;d) K e totalmente limitato (e quindi, per b), e compatto);e) Kn converge a K nella metrica di Hausdorff h.

a) Dal momento che {Kn} e di Cauchy in (K(X), h), per ogni ε > 0 esistenε in N tale che h(Kn, Km) ≤ ε per ogni n e m maggiori di nε. Detto, perk in N, εk = 1

2k, sia nk = nεk ; ovviamente, non e restrittivo supporre che

{nk} sia strettamente crescente. Sia xn1 appartenente a Kn1 ; dal momentoche h(Kn1 , Kn2) <

12, esiste xn2 in Kn2 tale che d(xn1 , xn2) <

12. Infatti,

h(Kn1 , Kn2) <1

2⇒ d(Kn1 , Kn2) <

1

2⇒ d(xn1 , Kn2) <

1

2,


e quindi d(xn1 , xn2) <12, scegliendo xn2 in Kn2 che realizza il minimo. Suppo-

niamo ora di aver scelto xn1 , xn2 , . . ., xnk−1, con la proprieta che xnj appartiene

a Knj , e che

d(xnj−1, xnj) ≤

1

2j−1.

Allora, essendo h(Knk−1, Knk) <

12k−1 , con lo stesso ragionamento di prima

possiamo trovare xnk in Knk tale che d(xnk−1, xnk) <

12k−1 . In questa maniera

costruiamo una successione {xnk}, al variare di k in N, con la proprieta chexnk appartiene a Knk , e che

d(xnk−1, xnk) <

1

2k−1.

Dimostriamo ora che la successione {xnk} e di Cauchy in (X, d). Se h > k, siha infatti, per la disuguaglianza triangolare,

d(xnk , xnh) ≤h∑

j=k+1

d(xnj−1, xnj) ≤

h∑j=k+1

1

2j−1=

1

2k1− 1

2h−k

1− 12

=1

2k−1− 1

2h−1,

e quindi {xnk} e di Cauchy in (X, d) perche lo e in (R, | · |) la successione{ 12k−1} (dato che converge a zero). A questo punto applichiamo il Lemma

2.21, e costruiamo una successione {xn}, di Cauchy in (X, d), con la proprietache xn appartiene a Kn per ogni n in N. Essendo (X, d) completo per ipotesi,{xn} converge in (X, d) ad x0, che appartiene a K per definizione. Pertanto,K e non vuoto, come volevasi dimostrare.

b) Sia {xn} una successione contenuta in K, convergente in (X, d) ad un puntox0. Vogliamo dimostrare che x0 appartiene a K, cosicche K sara chiuso peril Teorema 1.11. Per definizione di K, per ogni n in N esiste una successione

{y(n)j }, con y(n)m in Km per ogni m, convergente a xn. La convergenza di xn a

x0 implica che esiste una successione crescente {ni} di numeri interi tale che

d(xni , x0) <1

i,

mentre la convergenza di {y(n)m } a xn implica che esiste una sottosuccessione{mi} tale che

d(y(ni)mi, xni) <

1

i.

Usando la disuguaglianza triangolare e le ultime due disuguaglianze, abbiamoche

d(y(ni)mi, x0) <

2

i,

e quindi

limi→+∞

y(ni)mi= x0 .


Consideriamo ora la successione {y(ni)mi } al variare di i. Ovviamente e di Cauchy

(dato che converge), e si ha — per definizione — y(ni)mi in Kni per ogni i.

Per il Lemma 2.21, esiste una successione di Cauchy {yn} che “estende” la

successione {y(ni)mi }, con la proprieta che yn appartiene a Kn per ogni n. Dalmomento che {yn} converge in (X, d) (essendo di Cauchy in uno spazio metrico

completo), e che la sua sottosuccessione {y(ni)mi } converge a x0, si ha che {yn}converge a x0, che quindi — per definizione di K — appartiene a K.

c) Sia ε > 0, e sia nε in N tale che h(Kn, Km) < ε per ogni n e m maggiori dinε, cosicche d(Kn, Km) < ε per gli stessi n e m, e quindi (per il Lemma 2.17)Km ⊆ Kn + ε. Vogliamo dimostrare che K ⊆ Kn + ε. Sia allora x0 in K,sia {xn ∈ Kn} una successione che converge a x0 in (X, d), e supponiamo chenε sia anche tale che m ≥ nε implica d(xm, x0) < ε. Essendo xm in Km, edessendo Km contenuto in Kn + ε, si ha che xm appartiene a Kn + ε per ognim ≥ nε. Dal momento che Kn + ε e chiuso (per il Lemma 2.15), il limite dellasuccessione {xm} appartiene a Kn + ε, e quindi x0 e in Kn + ε, come volevasidimostrare.

d) Supponiamo per assurdo che K non sia totalmente limitato. Pertanto,esiste ε > 0 ed una successione {xn} contenuta in K tale che d(xn, xm) ≥ εper ogni n 6= m in N. Per il punto c), esiste n sufficientemente grande tale cheK ⊆ Kn+ ε

3, cosicche per ogni n esiste un punto yn inKn tale che d(xn, yn) < ε

3.

Essendo Kn compatto, e {yn} contenuta in Kn, esiste una sottosuccessione{yni} convergente, e quindi di Cauchy. Pertanto, se i e j sono sufficientementegrandi, si ha d(yni , ynj) <

ε3. Ma allora, per la disuguaglianza triangolare, e

per la scelta di {xn},ε ≤ d(xni , xnj) ≤ d(xni , yni) + d(yni , ynj) + d(ynj , xnj) < ε ,

che e assurdo. Mettendo insieme il punto b) e il risultato appena trovato conil Teorema 2.4, si ha che K appartiene a K(X).

e) Usando c) ed il Lemma 2.17, per far vedere che {Kn} converge a K in(K(X), h) e sufficiente far vedere che per ogni ε > 0 esiste nε in N tale cheKn ⊆ K + ε per ogni n maggiore di nε. Sia allora ε > 0, e sia nε in N taleche h(Kn, Km) < ε

2per ogni n e m maggiori di nε. Dal Lemma 2.17 segue

allora che Km ⊆ Kn + ε2

per tali n e m. Sia ora n fissato e maggiore dinε e sia {nj} una successione strettamente crescente di interi, con n1 > n,tale che Knj−1

⊆ Knj + ε2j

per ogni j. Una tale successione si puo costruireusando il fatto che {Kn} e di Cauchy in (K(X), h) ed il Lemma 2.17. Essendon1 > n, e n > nε, si ha h(Kn, Kn1) <

ε2, e quindi Kn ⊆ Kn1 + ε

2(sempre

per il Lemma 2.17). Sia ora y in Kn; siccome y appartiene a Kn1 + ε2, esiste

xn1 in Kn1 tale che d(xn1 , y) < ε2. Siccome Kn1 ⊆ Kn2 + ε

22, esiste xn2 in Kn2

tale che d(xn1 , xn2) <ε22

. Proseguendo, esiste una successione {xnj}, con xnj


in Knj , tale che d(xnj−1, xnj) <

ε2j

per ogni j in N. Usando ripetutamente ladisuguaglianza triangolare come in a), si ha che d(y, xnj) < ε per ogni j in N,e che {xnj} e di Cauchy in (X, d). Per il Lemma 2.21, esiste una successione{xn}, di Cauchy in (X, d), che estende {xnj} e tale che xn appartiene a Kn

per ogni n. Essendo {xn} di Cauchy, converge in (X, d) ad un punto x0che, per definizione, appartiene a K. D’altra parte, siccome {xnj} convergeanch’essa a x0, dalla disuguaglianza d(y, xnj) < ε, e dall’Esercizio 1.15, segueche d(y, x0) ≤ ε, cosicche y appartiene a K + ε. Abbiamo cosı dimostrato,come volevamo, che se n ≥ nε, allora Kn ⊆ K + ε. �

Osservazione 2.23. Si noti che dal momento che (K(X), h) e completoper il Teorema precedente, le successioni di Cauchy sono tutte e sole quelleconvergenti. Ne segue che se {Kn} e una successione di compatti convergentea K, allora vale per K la caratterizzazione data dal Teorema: e l’insieme checontiene tutti i limiti di tutte le successioni {xn ∈ Kn} convergenti.

CAPITOLO 3

Sistemi di funzioni iterate

Dopo aver posto le basi teoriche nei precedenti capitoli, introdurremo (me-diante numerosi esempi) il concetto di sistema di funzioni iterate e di attrat-tore di un sistema di funzioni iterate; dimostreremo il teorema del Collage,che ci dara la possibilita, dato un insieme compatto, di costruire il sistema difunzioni iterate che lo genera (o che lo approssima) come attrattore.

1. Da funzioni su X a funzioni su K(X)

Sia (X, d) uno spazio metrico, e sia f : X → X una funzione continua.Per il Teorema 2.5, se K appartiene a K(X), allora f(K) appartiene a K(X).In altre parole, una funzione f continua da X in X genera una funzione F daK(X) in se definita da

F : K(X) → K(X)K 7→ f(K)

Quali proprieta della funzione f “eredita” la funzione F?

Teorema 3.1. Sia (X, d) uno spazio metrico, e sia f : X → X unafunzione lipschitziana di costante di lipschitz L. Allora la funzione F daK(X) in se definita da F (K) = f(K) e lipschitziana da (K(X), h) in se, concostante di lipschitz L.

Dimostrazione. Essendo f lispchitziana, si ha

d(f(x), f(y)) ≤ Ld(x, y) , ∀x, y ∈ X .

Siano ora K e H in K(X); iniziamo col dare una stima su d(f(K), f(H)). Perdefinizione,

d(f(K), f(H)) = maxz∈f(K)

minw∈f(H)

d(z, w) .

Dal momento che per ogni z in f(K) esiste x in K tale che z = f(x), e perogni w in f(H) esiste y in H tale che w = f(y), possiamo riscrivere, usandoil fatto che f e lipschitziana,

d(f(K), f(H)) = maxx∈K

miny∈H

d(f(x), f(y)) ≤ maxx∈K

miny∈H

Ld(x, y) = Ld(K,H) .

Invertendo il ruolo di K e H si ottiene d(f(H), f(K)) ≤ Ld(H,K) e quindi

h(f(K), f(H)) ≤ Lh(K,H) ,

33

34 3. SISTEMI DI FUNZIONI ITERATE


Se, oltre ad essere lipschitziana, la funzione f e anche una contrazione,allora anche la funzione F e una contrazione. Se (X, d) e completo, anche(K(X), h) lo e (per il Teorema 2.22) e quindi ha un unico “compatto fisso”(per il Teorema 1.26). Ovviamente, dato che anche f ha un unico punto fissox, e chiaro che il compatto invariante e l’insieme {x0}. Ed infatti, se partiamoda un qualsiasi insieme K0 e definiamo per ricorrenza Kn = F (n)(K0), alloraKn contiene le iterate n-sime (tramite f) dei punti di K0. Dal momento cheognuna delle iterate n-sime converge a x0 (si veda la dimostrazione del Teorema1.26, o l’Osservazione 1.27), l’insieme limite di Kn nella metrica di Hausdorff(che, sempre per la dimostrazione del Teorema 1.26, sappiamo essere l’insiemeinvariante) e proprio {x0} (essendo l’insieme costituito dall’unico limite disuccessioni {xn ∈ Kn}, si veda la dimostrazione del Teorema 2.22).

In definitiva, partendo da una contrazione non si “guadagna” molto pas-sando da X a K(X).

Supponiamo ora di avere non una, ma m contrazioni f1, . . ., fm di fattoridi contrazione L1, . . ., Lm rispettivamente. Dato che l’unione di un numerofinito di compatti e ancora un compatto, possiamo definire un’applicazione Fda K(X) in se nel modo seguente:

(3.1)

F : K(X) → K(X)

K 7→m⋃i=1

Fi(K) ,

dove Fi e la contrazione (di fattore contrattivo Li) da K(X) in se definita daFi(K) = fi(K) per ogni K in K(X).

Teorema 3.2. Sia (X, d) uno spazio metrico, e siano f1, . . ., fm contrazionidi X in se di fattori di contrazione L1, . . ., Lm. Allora la funzione F definitada (3.1) e una contrazione di K(X) in se, di fattore di contrazione

L = max{L1, . . . , Lm} < 1 .

Dimostrazione. Siano H e K in K(X). Usando piu volte il Lemma 2.19abbiamo

h(F (H), F (K)) = h

( m⋃i=1

Fi(H),m⋃j=1

Fj(K)

)≤ max

1≤i≤m{h(Fi(H), Fi(K))} .

Ricordando che le Fi sono contrazioni di fattore contrattivo Li si ha dunque

h(F (H), F (K)) ≤ max1≤i≤m

{Li h(H,K)} =(

max1≤i≤m

Li)h(H,K) = Lh(H,K) ,


1. DA FUNZIONI SU X A FUNZIONI SU K(X) 35

Se (X, d) e uno spazio metrico completo, e {fi}1≤i≤m sono contrazioni da Xin se, allora F , definita in (3.1) e una contrazione e quindi, per il Teorema 1.26ha un unico compatto invariante K, che puo essere ottenuto come limite (nellametrica di Hausdorff), della successione {Kn = F (n)(K0)} ottenuta iterando F

a partire da un compatto qualsiasi K0. E facile vedere che se xi e l’unico puntofisso di fi, allora {x1, . . . , xm} e contenuto in K. Infatti, se consideriamo

K0 = {xj}, per qualche j tra 1 e m, allora, dato che f(n)j (xj) = xj per ogni j,

xj ∈m⋃i=1

{fi(xj)} = F (K0) = K1 , xj ∈m⋃i=1

{f (2)i (xj)} ⊆ F (K1) = K2 ,

ed in generale

xj ∈m⋃i=1

{f (n)i (xj)} ⊆ F (Kn−1) = Kn .

Siccome la successione costante {xn = xj} e tale che xn appartiene a Kn perogni n, e converge a xj, dalla caratterizzazione di K come limite dei Kn, si hache xj appartiene a K, qualsiasi sia j tra 1 ed m.

L’osservazione fondamentale e la seguente: e vero che nell’insieme inva-riante ci sono tutti i punti fissi delle m contrazioni, ma non solo. L’insiemeK puo essere, in generale, molto piu ricco, come mostra il seguente esempio.

Esempio 3.3. Sia (X, d) = (R2, d2), e siano f1 : R2 → R2 e f2 : R2 → R2

definite da

f1(x, y) = (x2, y2) , f2(x, y) = f1(x, y) + (1

2, 12) .

E facile vedere che f1 e f2 sono contrazioni di fattore L1 = 12

= L2, cosı comee facile vedere che (0, 0) e (1, 1) sono i punti fissi di f1 e f2 (non c’e bisognodi iterare, basta calcolare!). Definita F da K(R2) in se come

F (K) = F1(K) ∪ F2(K) ,

sappiamo che F e una contrazione di fattore contrattivo L = 12. Essendo

(R2, d2) completo, anche (K(R2), h) lo e, e quindi F ha un unico compattoinvariante K, che contiene sia (0, 0) che (1, 1). Consideriamo ora l’insiemecompatto

D = {(x, y) ∈ R2 : 0 ≤ y = x ≤ 1} ,o, in altre parole, la diagonale che congiunge (0, 0) con (1, 1) nel quadrato[0, 1]× [0, 1]. Ovviamente,

F1(D) = D1 = {(x, y) ∈ R2 : 0 ≤ y = x ≤ 12} ,

e

F2(D) = D2 = {(x, y) ∈ R2 : 12≤ y = x ≤ 1} ,


cosicche

F (D) = F1(D) ∪ F2(D) = D .

Iterando F a partire da K0 = D, si ha pertanto Kn = F (n)(D) = D per ognin, e quindi K = D. In altre parole, il compatto invariante per F non si limitaai due punti (0, 0) e (1, 1), ma e tutta la diagonale D: un insieme ben piu“ricco” dell’unione dei due punti.

D’altra parte, che l’insieme invariante fosse la diagonale del quadrato po-teva essere anche dedotto “visivamente” disegnando sovrapposte le prime seiiterate di Q = [0, 1]× [0, 1] tramite F .

Alcune iterate di Q sotto l’azione di F .

Nel disegno sono rappresentate in rosso le immagini di Q tramite f1, ed in blule immagini di Q tramite f2.

Perche non e solo la coppia di punti (0, 0) e (1, 1) l’insieme invariante, mae la diagonale? Proviamo a vedere cosa accade se prendiamo K0 = {(0, 0)}.E vero che F1(K0) = K0 (l’origine non si muove), ma F2(K0) = {(1

2, 12)},

cosicche

K1 = F (1)(K0) = {(0, 0),(12, 12

)} ,

che ha “un punto in piu” rispetto a K0. Continuando, e calcolando le immaginidei due punti tramite f1 e f2, si ha

K2 = F (2)(K0) = {(0, 0),(14, 14

),(12, 12

),(34, 34

)} ,

e, continuando,

Kn = F (n)(K0) ={(

k2n, k2n

), k = 0, . . . , 2n − 1

}.


Dal momento che ogni x in [0, 1) si puo espandere in forma binaria come

x =+∞∑k=1

ak(x)

2k,

con ak in {0, 1} per ogni k, e non definitivamente uguale a 1, se definiamo

xn =n∑k=1

ak(x)

2k=kn(x)

2n,

allora kn(x) e un intero compreso tra 0 e 2n − 1, e quindi (xn, xn) appartienea Kn per ogni n. Poiche {(xn, xn)} converge a (x, x), tale punto appartieneall’insieme invariante K per il Teorema 2.22. In altre parole, siccome con-sideriamo due funzioni, e vero che una delle due lascia invariato un punto,ma l’altra ne aggiunge di nuovi, che poi l’azione combinata delle due funzioniprovvede a “moltiplicare” in numero, fino a “riempire” la diagonale.

Un altro modo di “recuperare” la diagonale del quadrato e il seguente:partiamo da (x0, y0) = (0, 0), disegniamo il punto (x0, y0) e lanciamo unamoneta: se esce testa, definiamo (x1, y1) = f1(x0, y0), mentre se esce crocedefiniamo (x1, y1) = f2(x0, y0); disegniamo (x1, y1) e, nuovamente, lanciamouna moneta, usando f1 o f2 per definire (x2, y2) a seconda se esca testa ocroce. Ripetendo l’operazione, dopo un numero abbastanza elevato di lanciavremo un’approssimazione dell’insieme invariante K (il perche cio sia verosara spiegato rigorosamente in seguito). Ad esempio, se lanciamo duecentovolte la moneta, abbiamo

La diagonale approssimata da 200 scelte casuali di f1 ed f2


Nel disegno, sono colorati in rosso i punti ottenuti scegliendo f1, e in blu quelliottenuti scegliendo f2. Si noti la differenza con il disegno precedente, dove inrosso erano rappresentate le immagini del quadrato Q = [0, 1]× [0, 1] tramitef1, ed in blu le immagini di Q tramite f2.

Esempio 3.4. Adesso complichiamo (o miglioriamo. . .) le cose: invece diconsiderare due contrazioni, ne consideriamo tre. Siano allora

f1(x, y) = (x2, y2) , f2(x, y) = f1(x, y) + (1

2, 12) , f3(x, y) = f1(x, y) + (1

2, 0) .

La funzione F da K(R2) in se definita da

F (K) =3⋃i=1

Fi(K) ,

e una contrazione di fattore L = 12, e possiede quindi un compatto invariante

K. In K troviamo i tre punti fissi delle tre contrazioni che definiscono F , valea dire (0, 0), (1, 1) e (1

2, 0). Come nel caso precedente, la situazione e pero

molto piu complessa. Ad esempio, la diagonale D del quadrato e sicuramentecontenuta in K, dato che, definendo D1 e D2 come prima, si ha

F (D) = F1(D) ∪ F2(D) ∪ F3(D) = D1 ∪D2 ∪D3 = D ∪D3 ,

dove

D3 = {(x, y) ∈ R2 : 0 ≤ y = x− 12≤ 1

2} .

Pertanto, D ⊂ F (D) = F (1)(D), da cui segue D ⊂ F (n)(D) per ogni n. Per ilLemma 2.20, D e un sottoinsieme dell’insieme invariante K. Non si ha, pero,D = K. Infatti, essendo F 1(D) = D ∪D3, abbiamo

F (2)(D) = F (F (1)(D)) = F (D ∪D3) = D ∪D3 ∪ F (D3) ,

da cui

F (3)(D) = F (F (2)(D)) = F (D ∪D3 ∪ F (D3)) = D ∪D3 ∪ F (D3) ∪ F (2)(D3) ,

e, iterando,

F (n)(D) = D ∪D3 ∪n−1⋃i=1

F (i)(D3) .

Pertanto, D3 e contenuto in F (n)(D) per ogni n maggiore di 1, e quindi D3

e contenuto in K; ed anche F (D3) e contenuto in F (n)(D) per ogni n ≥ 2, equindi e in K; ed anche F (2)(D3) . . .

Se ci facciamo aiutare dal caso, e scegliamo f1, f2 o f3 a seconda se otte-niamo {1, 2}, {3, 4} o {5, 6} lanciando un dado (volendo, si puo ricorrere aduna moneta da 3D, che come e noto ha altrettante facce), otteniamo la figuraseguente:


L’insieme K approssimato da 500 scelte casuali di f1, f2 e f3

Disegnando un po’ meglio, ovvero disegnando F (6)( ), dove e il triangolorettangolo di vertici (0, 0), (1, 0) e (1, 1), troviamo:

F (6)( )


L’insieme K limite (della cui complessita la figura qui sopra e solo unapallida imitazione) viene detto triangolo di Sierpinski. Da ora in poi,invece di chiamarlo K, lo chiameremo .

Una versione “piu ordinata” del triangolo di Sierpinski e l’insieme ,ottenuto come insieme invariante delle tre contrazioni

f1(x, y) = (x2, y2) , f2(x, y) = f1(x, y) + (1

2,√32

) , f3(x, y) = f1(x, y) + (1, 0) ,

a partire dal triangolo equilatero di vertici (0, 0), (1, 0) e (12,√32

). Ecco ildisegno della quinta iterata, colorando in rosso l’immagine di tramite f1, inblu l’immagine di tramite f2, ed in verde l’immagine di tramite f3.

F (5)( )

Esempio 3.5. A questo punto, complichiamo ulteriormente la faccendaaggiungendo una quarta trasformazione: f1(x, y) = (x

2, y2) , f2(x, y) = f1(x, y) + (1

2, 12) ,

f3(x, y) = f1(x, y) + (12, 0) , f4(x, y) = f1(x, y) + (0, 1

2) .

Come al solito, facciamo partire la macchina dell’iterazione casuale, questavolta usando un dado da 4 (questi esistono!), e lanciandolo 1000 volte:

2. SISTEMI DI FUNZIONI ITERATE 41

L’insieme K approssimato da 1000 scelte casuali di f1, f2, f3 e f4

Che cosa succede? Perche non si forma un insieme “bello”, ma solo unbanalissimo quadrato? La risposta e semplice: se chiamiamo Q il quadrato[0, 1]× [0, 1], allora F1(Q) = [0, 1

2]× [0, 1

2] , F2(Q) = [1

2, 1]× [1

2, 1] ,

F3(Q) = [12, 1]× [0, 1

2] , F4(Q) = [0, 1

2]× [1

2, 1] ,

e quindi F (1)(Q) = Q! In altre parole, Q e l’insieme invariante di F : ag-giungendo una contrazione in piu, abbiamo “distrutto” la complessita di , esiamo ripiombati nella monotonia delle figure geometriche a noi note.

Dopo tanti esempi, e venuto il momento di dare un po’ di rigorosita aquello che abbiamo fatto.

2. Sistemi di funzioni iterate

Definizione 3.6. Sia (X, d) uno spazio metrico completo. Un sistemadi funzioni iterate (detto anche IFS, iterated function system) su X e uninsieme F = {f1, . . . , fm} di contrazioni definite su X. Dato un sistema di


funzioni iterate, e definita F da K(X) in se come

F (K) =m⋃i=1

Fi(K) ,

l’insieme invariante K di F viene detto attrattore del sistema di funzioniiterate.

Pertanto, e l’attrattore del sistema di funzioni iterate definito da

f1(x, y) = (x2, y2) , f2(x, y) = f1(x, y) + (1

2,√32

) , f3(x, y) = f1(x, y) + (1, 0) ,

mentre la diagonale del quadrato Q = [0, 1] × [0, 1] e l’attrattore dell’IFSdefinito da

f1(x, y) = (x2, y2) , f2(x, y) = f1(x, y) + (1

2, 12) .

Cambiando le contrazioni, cambia l’attrattore, e chiaramente si perdono leproprieta di simmetria di oggetti come la diagonale, o : ad esempio, seconsideriamo le quattro contrazioni

f1(x, y) =1

10

(x− y

5x+ 3y

), f2(x, y) =

1

10

(−5x− 2y + 3

7y + 4

),

f3(x, y) =1

10

(6x− 2

−3x− 4y + 6

), f4(x, y) =

1

10

(x− 7y + 9x+ 2y − 3

),

e iteriamo cinque volte a partire dal quadrato unitario, troviamo

F (5)( )

che e meno gradevole a vedersi di . La cosa interessante e che le quattro “par-ti”, colorate in rosso, blu, verde e ciano, sono ottenibili una dall’altra tramiteuna trasformazione rigida. In altre parole, l’insieme K e unione di quattroparti diverse (nel caso di le tre parti erano uguali a meno di traslazioni)ognuna delle quali puo essere trasformata nell’altra mediante un movimentorigido del piano.

3. IL TEOREMA DEL COLLAGE 43

– Esercizio 3.7. Sapreste scrivere esplicitamente la trasformazioneche porta la parte ciano nella parte blu?

Definizione 3.8. Un insieme K in K(X) si dice autosimilare se esistonom trasformazioni f1, . . ., fm di X in se tali che

K = f1(K) ∪ . . . ∪ fm(K) .

Chiaramente ogni attrattore di un IFS e, per definizione, un insieme au-tosimilare.

3. Il teorema del collage

Supponiamo ora di aver sognato un oggetto meraviglioso: una scacchieraquattro per quattro, in cui ogni casella nera era — a sua volta — fatta da unascacchiera quattro per quattro, in cui ogni casella nera era — a sua volta — fat-ta da una scacchiera. . .. Risvegliatici da sonni agitati, e forti della definizionedi autosimilarita, ci siamo resi conto di aver sognato un insieme autosimilare,uguale all’unione di otto copie ridotte di se stesso, disposte simmetricamente“a scacchiera”. Pensiamo (crediamo, o speriamo) di aver sognato l’attrattoredi un IFS. Gia, ma di quale? Quali e quante sono le contrazioni che l’hannocreato (ammesso che l’abbiano creato!)? Abbiamo sotto mano il disegno che— ancora semiaddormentati — abbiamo buttato giu in fretta e furia:

Sara sufficiente scrivere le otto contrazioni che prendono il quadrato unitarioQ = [0, 1] × [0, 1] e lo “riducono” negli otto quadratini che formano il primolivello della scacchiera? Armati di carta e penna, scriviamo le otto funzioni

f1(x, y) = (x4, y4) , f2(x, y) = f1(x, y) + (1

2, 0) ,

f3(x, y) = f1(x, y) + (14, 14) , f4(x, y) = f1(x, y) + (3

4, 14) ,

f5(x, y) = f1(x, y) + (0, 12) , f7(x, y) = f1(x, y) + (1

2, 12) ,

f6(x, y) = f1(x, y) + (14, 32) , f8(x, y) = f1(x, y) + (3

4, 34) ,


e vediamo cosa succede disegnando le prime quattro iterazioni del quadratoQ, ovvero F (4)( ):

F (4)( )

Ha funzionato! Siamo contenti, ma ci viene un dubbio: abbiamo solo dise-gnato alcune delle iterazioni (le prime quattro), e sono “pochine” per saperese abbiamo costruito le cose in maniera corretta. Avremmo bisogno di unrisultato teorico che ci garantisca che quello che abbiamo fatto (la scacchierache avevamo immaginato era uguale ad otto copie riscalate di se stessa; abbia-mo scritto le otto contrazioni; il disegno che abbiamo ottenuto e una buonaapprossimazione dell’attrattore) ha senso.

Teorema 3.9. Sia (X, d) uno spazio metrico completo, e sia assegnatoF = {f1, . . . , fm} un sistema di funzioni iterate su X di fattore di contrazioneL < 1. Sia ε ≥ 0, e sia H in K(X) tale che

h(F (H), H) < ε .

Detto K l’attrattore di F , si ha allora

h(K,H) <ε

1− L.

Dimostrazione. E una semplice applicazione della dimostrazione delteorema delle contrazioni: partendo da K0 = H, e ripetendo la dimostrazione,


si ha

h(Kn+1, Kn) ≤ Ln h(K1, K0) = Ln h(F (H), H) < Ln ε ,

da cui

h(Kn, H) ≤n−1∑j=0

h(Kj+1, Kj) <n−1∑j=0

Lj ε = ε1− Ln

1− L<

ε

1− L.

Ricordando che Kn converge a K nella distanza h, e che la funzione h(·, H) econtinua (per l’Esercizio 1.15), si ha la tesi passando al limite. �

Le applicazioni del teorema precedente (detto teorema del Collage) sonodue. Se ε = 0, allora h(K,H) = 0, e quindi l’attrattore dell’IFS e proprioH – che sara quindi ben approssimato dalle iterazioni dell’IFS a partire daqualsiasi insieme del piano.

Ad esempio, consideriamo la cosiddetta curva di von Koch, che vienecostruita nel modo seguente: dato il segmento [0, 1], si levi il terzo centralee lo si sostituisca con due segmenti di lunghezza 1

3che formino un triangolo

equilatero. Si ripeta la procedura per ognuno dei quattro segmenti cosı otte-nuti, e cosı via. La curva limite (simile ad un fiocco di neve) e la curva di vonKoch.

La procedura di costruzione della curva di von Koch

E allora chiaro (dalla procedura), che la curva di von Koch e uguale all’unione(esatta) di quattro copie di se stessa, riscalate di un fattore un terzo. Duecopie (la prima e l’ultima) sono traslate, mentre le altre due sono ruotate (diπ3

e −π3

rispettivamente) e poi traslate. In simboli

f1(x, y) = (x3, y3) , f2(x, y) = (x

3+ 2

3, y3) ,

e

f3(x, y) = (x−√3y

6+ 1

3,√3x+y6

) , f4(x, y) = (x+√3y

6+ 1

2, −√3x+y6

+√36

)

Partendo da K0 = , ed iterando sei volte, otteniamo una buona approssima-zione della curva.


Un’approssimazione della curva di Von Koch: F (6)( )

Se nel teorema del Collage si ha ε > 0, e costruiamo un IFS ed un insiemeH che e “vicino” (nel senso della distanza di Hausdorff) alla propria pri-ma immagine tramite l’IFS, allora l’insieme H e una buona approssimazionedell’attrattore dell’IFS.

Quest’ultima applicazione ci fornisce una ricetta per trovare un sistemadi funzioni iterate che approssimi un insieme autosimilare non perfettamente“regolare” (come lo sono , o la scacchiera). Identifichiamo, anche approssi-mativamente, le parti autosimili, e scriviamo le contrazioni che portano tuttol’insieme nelle varie sotto-parti. Se in questa maniera “copriamo” quasi tuttol’insieme (a meno di una distanza di Hausdorff pari a ε), allora l’attrattore del-l’IFS che abbiamo scritto, attrattore che sappiamo disegnare con un computer,approssima l’insieme autosimile da cui eravamo partiti.

Ad esempio, supponiamo di voler disegnare la struttura dei rami un albero(bidimensionale. . .) come attrattore di un IFS. La struttura autosimilare eabbastanza evidente: dal tronco si dipartono (a diverse altezze e a diverseinclinazioni) rami verso destra e verso sinistra, ed ognuno dei due rami ha, asua volta, dei rametti (a destra ed a sinistra), che hanno sotto-rametti, e cosıvia. Pertanto, ogni ramo e una copia in miniatura di tutto l’albero.


La struttura dei rami di un albero (piu o meno. . .)

Cosa notiamo dal disegno? Che il primo ramo di sinistra e lungo circa un terzodi tutto l’albero, e ruotato (rispetto al tronco) di circa sessanta, sessantacinquegradi, ed e traslato verso l’alto di un quinto dell’albero; che il primo ramo didestra e lungo circa un quarto di tutto l’albero, che e ruotato (rispetto altronco) di meno quarantacinque gradi (o giu di lı), ed e traslato verso l’altodi circa un quarto dell’albero; ed infine che la parte di albero dai secondi ramiin su e una copia ridotta di circa un quarto dell’albero, traslata verso l’alto dicirca un terzo della lunghezza dell’albero. In definitiva, la situazione e questa:

L’albero come unione di copie di se stesso

Come si vede (un po’ barando, le immagini incollate sono opache. . .) le trecopie ridotte dell’albero lo ricoprono piu o meno interamente: spuntano solodei rametti qua e la: per il teorema del Collage, l’attrattore dell’IFS generatodalle tre contrazioni che abbiamo descritto e abbastanza vicino (nel senso dellamisura di Hausdorff) all’albero che abbiamo disegnato. Passando dalle paroleai numeri, e ricordando che la matrice che descrive una rotazione di un angoloθ (in senso antiorario) e data da

M =

(cos(θ) −sen(θ)sen(θ) cos(θ)

),

e supponendo che l’albero sia alto 1, abbiamo

f1(x, y) =

(1/6 −

√3/6√

3/6 1/6

) (xy

)+

(0

1/5

),

f2(x, y) =

( √2/8

√2/8

−√

2/8√

2/8

) (xy

)+

(0

1/4

),


e

f3(x, y) =

(3/4 00 3/4

) (xy

)+

(0

1/3

).

Se proviamo a disegnare l’attrattore, otteniamo pero un risultato non soddi-sfacente:

F (5)( )

Cosa manca? Mancano sia il tronco che i rami (la sostanza stessa dell’albero,insomma)! C’e pero un problema: che tronco e rami, presi singolarmente, sonosimili tra loro (un ramo e una versione ridotta del tronco), ma non sono similiall’albero. A meno che non si decida di prendere l’albero e schiacciarlo lungo ladirezione dell’asse x, rendendolo “magrissimo”, e quindi simile ad un segmento(che possiamo pensare come schematizzazione di un tronco). Dobbiamo alloraaggiungere una quarta contrazione:

f4(x, y) =

(1/1000 0

0 999/1000

) (xy

)+

(00

),

che riduce le dimensioni un una sola direzione, lasciando l’altra (quasi) indi-sturbata.

F (5)( )

Un analogo risultato otteniamo se lanciamo 2500 volte un dado da quattro,scegliendo ogni volta quale delle quattro contrazioni applicare.


F (5)( )

A questo punto, possiamo sbizzarrirci, ed introdurre dei parametri, comesegue.

L

βL

αL

δL

γL

θσ

εL

Dobbiamo quindi scrivere, oltre alla quarta contrazione che porta l’albero neltronco, e che rimane invariata, le tre contrazioni (supponendo L = 1):

f1(x, y) =

(α cos(θ) −α sen(θ)α sen(θ) α cos(θ)

) (xy

)+

(0β

),

f2(x, y) =

(γ cos(σ) γ sen(σ)−γ sen(σ) γ cos(σ)

) (xy

)+

(0δ

),

e

f3(x, y) =

(ε 00 ε

) (xy

)+

(0

1− ε

),

e poi provare diversi valori dei parametri α, β, γ, δ, ε, θ e σ. Se indichiamocon T (α, β, γ, δ, ε, θ, σ) e l’attrattore dell’IFS, ecco alcuni casi.


T (12 ,15 ,

12 ,

15 ,

45 ,

π3 ,

π3 )

T (35 ,15 ,

25 ,

310 ,

45 ,

π3 ,

π4 )

T ( 910 ,

15 ,

15 ,

25 ,

12 ,

π2 ,

π4 )

4. SISTEMI DI FUNZIONI ITERATE CON PROBABILITa 51

4. Sistemi di funzioni iterate con probabilita

Nelle pagine precedenti abbiamo visto due modi di “disegnare” l’attrattoredell’IFS: la prima approssimandolo con l’iterata n-sima di un sottoinsieme diR2 (ad esempio un quadrato, o un triangolo), la seconda partendo da un puntoqualsiasi del piano, scegliendo casualmente una delle m contrazioni del sistemadi funzioni iterato, calcolando l’immagine del punto tramite la contrazionescelta, e ripetendo questa operazione (a partire dal punto calcolato) per unnumero sufficientemente elevato di volte.

Mentre e chiaro dalla definizione stessa di attrattore K come limite delleiterate che il primo sistema “funziona”, non e immediatamente evidente perchefunzioni il secondo metodo. Per le iterate n-sime abbiamo infatti immagini diinsiemi “pieni” (come quadrati o triangoli), mentre il metodo probabilistico

calcola immagini di punti (che tutto sono tranne che “pieni”). E vero pero che— dal punto di vista della rappresentazione grafica al computer — dopo uncerto numero di iterazioni i “punti” (pixel) dello schermo non sono meno “pie-ni” dell’immagine di un quadrato: se, ad esempio, prendiamo l’IFS che genera

, e partiamo dal quadrato di lato 1, dopo n passaggi le immagini hanno lato2−n, ed il quadrato e diventato poco piu di un punto sullo schermo. E, vice-versa, nei disegni “casuali” che abbiamo fatto, ogni punto era rappresentatoda un cerchietto (“pieno”, dunque).

Sistemato il problema della non differente dimensione tra quadrati e pun-ti, rimane pero da capire per quale motivo scegliendo in maniera casua-le la contrazione da applicare ad ogni passo otteniamo un’approssimazionedell’attrattore.

Ricordiamo che se {f1, . . . , fm} e il sistema di funzioni iterate, l’attrattoreK e ottenuto come limite delle iterazioni a partire da qualsiasi compatto K0

iniziale. Se, in particolare, scegliamo K0 = {x0}, ovvero un punto, allora K1

e l’insieme delle immagini di x0 tramite le funzioni fi dell’IFS, K2 e l’insiemedelle immagini di questi punti, e cosı via. Se i punti sono tutti a due a duediversi, Kn sara composto da mn punti, ognuno dei quali e della forma

x = fjn ◦ fjn−1 ◦ · · · ◦ fj1(x0) ,

con j1, . . ., jn interi che variano tra 1 ed m. La successione {xn} di punticasuali che costruiamo scegliendo al passo n-simo una delle contrazioni fin ecalcolando xn = fin(xn−1) (partendo da x0), ha quindi la proprieta che xnappartiene a Kn = F (n)({x0}). In altre parole, scegliamo casualmente unodegli mn punti che compongono Kn.

Perche questa scelta va bene? Se rileggiamo la dimostrazione del Teore-ma delle contrazioni (si veda l’Osservazione 1.27, e la formula (1.1)), abbia-mo (chiamando θ il fattore di contrazione di F ) h(Kn, K) ≤ θn

1−θ h(K1, K0).


Ricordando la definizione di distanza di Hausdorff, si ha allora

d(Kn, K) ≤ θn

1− θh(K1, K0) ,

e quindi

max{d(x,K), x ∈ Kn} ≤θn

1− θh(K1, K0) .

Essendo xn in Kn, si ha allora

d(xn, K) ≤ θn

1− θh(K1, K0) ;

siccome d(x,K) e un minimo, esiste yn in K tale che

d(xn, yn) ≤ θn

1− θh(K1, K0) .

Se n e molto grande, abbiamo cosı che il punto “casuale” xn e vicino ad almenoun punto di K, ed e talmente vicino da risultarne indistinguibile una voltache xn sia rappresentato da un computer, e quindi da un pixel o, come nelnostro caso, da un cerchietto. In sostanza, con la scelta “casuale” del punto dadisegnare, anche se non stiamo disegnando esattamente i punti dell’attrattoreK, li stiamo comunque approssimando “bene”.

Ovviamente, abbiamo bisogno che la scelta della contrazione da applicaresia veramente “casuale” (vale a dire: se sono m contrazioni, su n iterazioniognuna deve essere scelta in media n

mvolte). Se cosı non e, rischiamo di non

ottenere una rappresentazione dell’attrattore: se ad esempio scegliamo semprela prima contrazione f1, e chiaro che stiamo approssimando solo l’unico puntofisso di f1.

Quello che possiamo fare, pero, e decidere che alcune contrazioni hannomaggiore probabilita di essere scelte. Ad esempio, per potremmo decideredi scegliere f1 due volte piu spesso di f2 e di f3. Una tale scelta porta evi-dentemente ad un aumento della densita dei punti iterati nella regione f1(K),raddoppiandola rispetto a quella dei punti nelle regioni f2(K) e f3(K). Pos-siamo cosı generare dei sistemi di funzioni iterate con probabilita, chesono della forma {(f1, p1), . . . , (fm, pm)} con fi una contrazione per ogni i e

m∑i=1

pi = 1 .

Scegliendo opportunamente i valori di delle proabilita, e colorando opportu-namente i punti, si possono ottenere effetti di colore differenti sulle rappresen-tazioni al computer degli attrattori di IFS.

4. SISTEMI DI FUNZIONI ITERATE CON PROBABILITa 53

Il triangolo di Sierpinski con p1 = 12 , p2 = 1

4 e p3 = 14

Il quadrato con densita p1 = 49 , p2 = 2

9 , p3 = 29 e p4 = 1

9

Una felce

CAPITOLO 4

Misura e dimensione di Hausdorff

Che vuol dire “dimensione di un insieme”? Che cosa intendiamo quan-do diciamo che un segmento “ha dimensione uno”? O che un quadrato “hadimensione due”? Intuitivamente, diciamo che un segmento ha dimensioneuno perche ha solo la lunghezza, e non ha ne larghezza, ne la profondita.Analogamente, un quadrato ha dimensione due perche e lungo, largo, ma non“spesso”. Mentre, invece, un cubo ha tre dimensioni perche si “estende” in tredirezioni. La cosa che — forse — non si nota quando si dice che un segmentoha dimensione uno, e che non si dice dove “vive” il segmento. Per esempio,non si specifica se sia un sottoinsieme di R, o di R2, o di RN con N qualsiasi.Un segmento ha dimensione uno sia se e [1, 1], sia se e [−1, 1] × {0}, sia see [−1, 1] × {(0, . . . , 0). Analogamente, un quadrato ha dimensione due an-che se “vive” in un piano di R3, o in un iperpiano di RN , e cosı un cubo hadimensione tre anche se e in R4, o in R5.

In altre parole, l’idea che abbiamo di “dimensione”, l’idea intuitiva di“dimensione”, fa sı che essa sia una caratteristica “intrinseca” dell’oggetto chestiamo considerando, indipendentemente da “dove” lo stiamo considerando.Quello che faremo in seguito sara di dare alcuni modi per calcolare — perogni sottoinsieme di RN — un numero s (che potra essere anche non intero) eche sara indipendente dalla dimensione N dello spazio ambiente, ma dipenderasolo dall’insieme che stiamo considerando.

1. La misura di Hausdorff

Da ora in poi lavoreremo nello spazio metrico (X, d) = (RN , d2), ovvero inRN dotato della metrica euclidea.

Definizione 4.1. Sia A un sottoinsieme di RN . Il diametro di A edefinito come

diam(A) = sup{d2(x, y), x, y ∈ A} .Si vede abbastanza facilmente che se diam(A) = r < +∞, allora A ⊂ Br(x0),qualsiasi sia x0 in A, e quindi A e limitato. Si vede altrettanto facilmenteche se A = Br(x0), allora diam(A) = 2r (cosicche il nome di “diametro” egiustificato).

– Esercizio 4.2. Si giustifichino le ultime due affermazioni.

55

56 4. MISURA E DIMENSIONE DI HAUSDORFF

Definizione 4.3. Dato A sottoinsieme di RN e δ > 0, un δ-ricoprimentodi E e una famiglia {Ei}i∈N, al piu numerabile, tale che

diam(Ei) ≤ δ , e A ⊆⋃i∈N

Ei .

E chiaro che se {Ei} e un δ-ricoprimento di A, allora {Ei} e un δ′-ricoprimentodi A per ogni δ′ > δ. In altre parole, piu e piccolo δ, meno sono i δ-ricoprimentidi A.

Definizione 4.4. Sia s ≥ 0 un numero reale. Definiamo α(0) = 1 e

α(s) =πs2

Γ( s2

+ 1), ∀s > 0 ,

dove

Γ(t) =

∫ +∞

0

e−x xt−1 dx ,

e la funzione gamma di Eulero.

Riguardo alla funzione gamma, osserviamo che

Γ(12) =

∫ +∞

0

e−x√xdx =

[x = y2

dx = 2y dy

]= 2

∫ +∞

0

e−y2

dy =√π ,

e che

Γ(1) =

∫ +∞

0

e−x dx = −e−x∣∣x=+∞x=0

= 1 .

Inoltre, integrando per parti, e se t ≥ 0,

Γ(t+ 1) =

∫ +∞

0

e−x xt dx =

[du = e−x v = xt

u = −e−x dv = t xt−1

]= −t e−x xt

∣∣x=+∞x=0

+ t

∫ +∞

0

e−x xt−1 dx = tΓ(t) ,

che, combinato con Γ(1) = 1, implica che Γ(n) = (n − 1)! per ogni n in N,cosicche la funzione Γ interpola il fattoriale.

Quanto ad α(s), si ha

α(1) =

√π

Γ(32)

=

√π

12

Γ(12)

= 2 ,

e

α(2) =π

Γ(2)= π ,

e

α(3) =π√π

Γ(52)

=π√π

32Γ(3

2)

=π√π

34Γ(1

2)

=4

3π ,

1. LA MISURA DI HAUSDORFF 57

cosicche α(s) e, almeno per s = 1, s = 2 ed s = 3, la lunghezza, l’area ed ilvolume, di B1(0) in R, R2 ed R3 rispettivamente. Si puo dimostrare che, ingenerale, α(N) e la “misura N -dimensionale” della sfera B1(0) in RN .

Definizione 4.5. Sia s ≥ 0, sia A un sottoinsieme di RN , e sia δ > 0.Definiamo

Hsδ(A) = inf

{∑i∈N

α(s)

(diam(Ei)

2

)s, {Ei} δ-ricoprimento di A

}.

Se A e fissato, e δ < δ′, si vede facilmente che Hsδ′(A) ≤ Hs

δ(A), e quindi —come funzione di δ — Hs

δ(A) e decrescente. Esiste allora

Hs(A) = limδ→0+

Hsδ(A) = sup{Hs

δ (A), δ > 0} .

Si noti che si ha 0 ≤ Hs(A) ≤ +∞. Dato A sottoinsieme di RN , e s ≥ 0, laquantita Hs(A) si dice misura (esterna) di Hausdorff s-dimensionale diA.

Il seguente teorema raccoglie alcune delle proprieta della misura di Hau-sdorff.

Teorema 4.6. La misura di Hausdorff e tale che:

(1) Se A ⊆ B, allora Hs(A) ≤ Hs(B).(2) Se s = 0, allora

H0(A) =

{#(A) se A e finito,+∞ se A non e finito.

Il numero #(A) e, per definizione, il numero degli elementi di A.(3) Se s > N , ed A e limitato, allora Hs(A) = 0 per ogni sottoinsieme A

di RN .(4) Se s = 1 e A e un segmento contenuto in RN , allora H1(A) e la

lunghezza del segmento. Analogamente, H2(A) e l’area di A se A euna “figura piana” in RN , e H3(A) e il volume di A se A e un “solido”tridimensionale in RN .

Dimostrazione. Dimostriamo solo le prime tre affermazioni (rimandan-do al libro di Ziemer citato nell’Introduzione per l’ultima). Per quanto ri-guarda (1), e chiaro che se {Ei} e un δ-ricoprimento di B, allora e anche unδ-ricoprimento di A. Si ha allora, per ogni δ > 0, e per definizione di Hs(B),

Hsδ(A) ≤ Hs

δ(B) ≤ Hs(B) ,

e quindi la tesi passando al limite su δ tendente a zero da destra nel primomembro.

Per (2), se s = 0, dalla definizione si ha che

H0δ(A) = inf {#{Ei}, {Ei} δ-ricoprimento di A} .


Se A = {x1, . . . , xm}, allora {Ei} = {xi} e un δ-ricoprimento di A per ogniδ > 0, cosicche H0

δ(A) ≤ m per ogni δ > 0. D’altra parte, se

δ = min{d2(xi, xj), i 6= j = 1, . . . , m} ,allora ogni δ-ricoprimento di A deve contenere almeno m insiemi, e quindiH0δ(A) ≥ m per ogni δ ≤ δ.

x1

x2

x3

x4

x5δ

Ogni δ-ricoprimento contiene almeno m insiemi.

Si ha allora che H0δ(A) = m per ogni δ ≤ δ, e quindi H0(A) = m. Se,

invece, A contiene infiniti punti, allora A contiene almeno una successione{yn} costituita da infiniti punti distinti. Ma allora, per (1),

H0(A) ≥ H0({y1, . . . , yn}) = n ,

da cui H0(A) = +∞ per l’arbitrarieta di n.Per dimostrare la (3), iniziamo a calcolare Hs(Q1), dove Q1 = [0, 1]N .

Fissato n in N, ricopriamo Q1 con Nn cubetti Qm1,...,mN di lato 1n:

Qm1,...,mN =[m1

N, m1+1

N

]× · · · ×

[mNN, mN+1

N

],

con m1, . . ., mN interi compresi tra 0 e N−1. Essendo diam(Qm1,...,mN ) =√Nn

,

gli nN cubetti sono un δn-ricoprimento di Q, con δn =√Nn

. Pertanto,

0 ≤ Hsδn(Q1) ≤ α(s)

nN∑i=1

(√N

2n

)s= α(s)

(√N

2

)s1

ns−N.

Facendo tendere n ad infinito, osservando che δn tende a zero, ed usandol’ipotesi s > N , si ha

0 ≤ Hs(Q1) ≤ 0 ,

1. LA MISURA DI HAUSDORFF 59

e quindi Hs(Q1) = 0. Analogamente, si ha Hs(QR) = 0 per ogni cubo QR dilato R > 0. Se A e limitato, allora A e contenuto in BR(0) per un opportunoR. Essendo BR(0) un sottoinsieme del cubo Q2R centrato nell’origine e lato2R, si ha (per (1)),

0 = Hs(A) ≤ Hs(BR(0)) ≤ Hs(Q2R) = 0 ,

e quindi Hs(A) = 0, come volevasi dimostrare. �

Abbiamo chiamato la funzione di insieme Hs (definita sulle parti di RN),“misura esterna”.

Definizione 4.7. Una funzione di insieme µ∗, definita sull’insieme P(X)delle parti di X, si dice misura esterna se

(1) µ∗(E) ≥ 0 per ogni E in P(X), e µ∗(∅) = 0;(2) per ogni famiglia al piu numerabile {Ei} contenuta in P(X), si ha

µ∗( +∞⋃

i=1

Ei

)≤

+∞∑i=1

µ∗(Ei) .

Data una misura esterna µ∗, un insieme E di P(X) si dice misurabile secondoµ∗ se si ha

µ∗(A) = µ∗(A ∩ E) + µ∗(A ∩ Ec) , ∀A ∈ P(X) .

Data una misura esterna µ∗, allora

Aµ∗ = {E ∈ P(X) : E e µ∗-misurabile}e un σ-algebra (ovvero, una famiglia di insiemi che contiene l’insieme vuoto,ed e chiusa rispetto al complementare e alle unioni numerabili). La restrizionedi µ∗ a Aµ∗ viene detta misura, ed e tale che

µ∗( +∞⋃

i=1

Ei

)=

+∞∑i=1

µ∗(Ei) ,

per ogni famiglia {Ei} al piu numerabile di insiemi disgiunti.

Esempio 4.8. La funzione di insieme Hs e — effettivamente — una misuraesterna. Se s e un numero intero, la restrizione diHs agli insiemiHs-misurabilie la misura di Lebesgue s-dimensionale (con questa frase si precisa il senso del-la (4) del Teorema 4.6). Vediamo, nel caso particolare di H0, che le proprietadella misura esterna sono soddisfatte. Ovviamente, H0(A) e positivo, e si an-nulla se A = ∅ (che non ha punti). Sia ora {Ei} una famiglia al piu numerabiledi sottoinsiemi di RN . Se la serie

+∞∑i=1

H0(Ei)


diverge, non c’e nulla da dimostrare. Supponiamo pertanto che converga;essendo H0(Ei) un numero intero per ogni i, l’unica possibilita e che H0(Ei)sia diverso da zero, e finito, solo per un numero finito di indici. Supponiamoche gli insiemi ad avere misura H0 diversa da zero siano i primi n, cosiccheEi = ∅ per ogni i > n. Ma allora l’unione degli Ei e un insieme finito, la cuicardinalita e al piu la somma delle cardinalita dei primi n insiemi (dato chequalche punto puo appartenere a piu di uno degli Ei). Come sono fatti gliinsiemi H0-misurabili? Deve valere

H0(A) = H0(A ∩ E) +H0(A ∩ Ec) , ∀A ⊆ RN .

Essendo A = (A ∩ E) ∪ (A ∩ Ec), chiaramente si ha

H0(A) ≤ H0(A ∩ E) +H0(A ∩ Ec) ,

e quindi non rimane che dimostrare la disuguaglianza inversa:

H0(A) ≥ H0(A ∩ E) +H0(A ∩ Ec) .

Se H0(A) = +∞, non c’e nulla da dimostrare. Supponiamo pertanto che Asia finito. Ma allora sia A∩E che A∩Ec sono insiemi finiti, e sono disgiunti,cosicche la somma delle loro cardinalita e la cardinalita dell’unione, ovvero A.Non avendo fatto alcuna ipotesi su E, ne segue che ogni sottoinsieme E diRN e misurabile secondo H0, e quindi che la σ-algebra AH0 non e altro cheP(RN).

2. La dimensione di Hausdorff

Il seguente risultato permette di definire “intrinsecamente” la dimensionedi un insieme tramite la misura Hs.

Teorema 4.9. Sia A un sottoinsieme limitato di RN . Allora esiste ununico numero reale s, con 0 ≤ s ≤ N tale che

Hs(A) =

{0 se s > s,

+∞ se s < s.

Dimostrazione. Dimostriamo che se s ≥ 0 e tale che Hs(A) < +∞,allora Hs′(A) = 0 per ogni s′ > s. Sia dunque C = Hs(A), e sia s′ > s. Perdefinizione,

C = limδ→0+

Hsδ(A) = sup{Hs

δ(A), δ > 0} .

Essendo C < +∞, si ha Hsδ(A) ≤ C < +∞ per ogni δ > 0. Per definizione di

estremo inferiore, fissato ε > 0 esiste un δ-ricoprimento {Ei,ε} di A tale che

0 ≤ α(s)∑i∈N

(diam(Ei)

2

)s≤ Hs

δ(A) + ε ≤ C + ε .

2. LA DIMENSIONE DI HAUSDORFF 61

Per tale ricoprimento si ha

0 ≤ Hs′

δ (A)≤α(s′)∑i∈N

(diam(Ei,ε)

2

)s′=α(s′)

α(s)

(δ

2

)s′−s [α(s)

∑i∈N

(diam(Ei,ε)

2

)s]

≤ (C + ε)α(s′)

α(s)

(δ

2

)s′−s.

ovvero,

0 ≤ Hs′

δ (A) ≤ C δs′−s ,

per qualche costante C indipendente da δ. Facendo tendere δ a zero si trovaHs′(A) = 0, come volevasi dimostrare.

Per concludere la dimostrazione, definiamo

s = inf{s ≥ 0 : Hs(A) = 0} .Osserviamo innanzitutto che l’estremo inferiore e ben definito dato per la (3)del Teorema 4.6 si ha Hs(A) = 0 per ogni s > N , e che quindi 0 ≤ s ≤ N .Inoltre, se s > s allora — per definizione di estremo inferiore — esiste s′

appartenente a [s, s] tale che Hs′(A) = 0 < +∞. Per quanto dimostrato inprecedenza, Hs(A) = 0. Se, invece, s < s, e Hs(A) < +∞, allora (sempreper quanto visto prima), Hs′(A) = 0 per ogni s′ > s, e quindi per ogni s′

in (s, s), contraddicendo cosı la definizione di estremo inferiore. Pertanto,Hs(A) = +∞, e la dimostrazione del teorema e conclusa. �

Osservazione 4.10. Osserviamo esplicitamente che se s ≥ 0 e tale cheHs(A) > 0, allora Hs′(A) = +∞ per ogni s′ < s. Infatti, se per assurdosi avesse Hs′(A) < +∞ per qualche s′ < s, allora (per la prima parte delladimostrazione del teorema precedente) seguirebbe che Hs(A) = 0, il che none.

Definizione 4.11. Sia A un sottoinsieme di RN . Il numero reale s deter-minato dal teorema precedente viene detto dimensione di Hausdorff di A,e si indica con

dimH(A) = s .

Osservazione 4.12. Se s = dimH(A), allora Hs(A) puo essere qualsiasinumero in [0,+∞), oppure piu infinito. Ad esempio, se A = ∅ allora H0(A) =0, se A = [0, 1] allora H1(A) = 1, mentre HN(RN) = +∞. Se pero unsottoinsieme A di RN e tale che esiste s ≥ 0 per cui 0 < Hs(A) < +∞, alloradimH(A) = s. Dal punto (4) del Teorema 4.6 segue allora che la dimensionedi Hausdorff di un segmento e 1, di una “figura piana” e 2, e di un “solidotridimensionale” e 3.


Osservazione 4.13. Sia A ⊆ RN , e sia s = dimH(A) ≤ N . Sia M > Ne definiamo A′ = A × {0N+1, . . . , 0M}. In altre parole, A′ e l’insieme A“immerso” in RM . Dimostriamo che dimH(A′) = s, cosicche la dimensione diHausdorff di un insieme non dipende dallo spazio ambiente. Se s > s, si haHs(A) = 0 (con ricoprimenti contenuti in RN). Pertanto, per ogni δ > 0 si haHsδ(A) = 0, e quindi per ogni ε > 0 esiste un δ-ricoprimento {Ei,ε} (in RN) di

A tale che

α(s)∑i∈N

(diam(Ei,ε)

2

)s≤ ε .

Dal momento che {E ′i,ε}, con E ′i,ε = Ei,ε×{0N+1, . . . , 0M} e un δ-ricoprimento

di A′ in RM (il diametro di Ei,ε e lo stesso di E ′i,ε), allora

α(s)∑i∈N

(diam(E ′i,ε)

2

)s≤ ε ,

da cui segue Hsδ(A

′) = 0 (in RM) e quindi Hs(A′) = 0. Pertanto, Hs(A′) = 0per ogni s > s, e quindi dimH(A′) ≤ s. Se per assurdo fosse dimH(A′) < s,allora esisterebbe s′ < s tale che Hs′(A′) = 0. Pertanto, Hs′

δ (A′) = 0 per ogniδ > 0, e quindi per ogni ε > 0 esiste un δ-ricoprimento {E ′i,ε} di A′ tale che

α(s′)∑i∈N

(diam(E ′i,ε)

2

)s′≤ ε .

Scrivendo

E ′i,ε = F(1)i,ε × F

(2)i,ε × · · · × F

(N)i,ε × F

(N+1)i,ε × · · · × F (M)

i,ε ,

si vede facilmente che {Ei,ε}, definito da

Ei,ε = F(1)i,ε × F

(2)i,ε × · · · × F

(N)i,ε ,

e un δ ricoprimento di A in RN , dato che diam(Ei,ε) ≤ diam(E ′i,ε). Pertanto,

α(s′)∑i∈N

(diam(Ei,ε)

2

)s′≤ α(s′)

∑i∈N

(diam(E ′i,ε)

2

)s′≤ ε ,

da cui Hs′

δ (A) = 0, e quindi Hs′(A) = 0. Essendo s′ < dimH(A), si ha unassurdo per definizione di dimH(A).

CAPITOLO 5

La dimensione degli attrattori degli IFS

In questo capitolo daremo un metodo per calcolare la dimensione di Hau-sdorff dei compatti autosimilari che abbiamo costruito nel Capitolo 3 comeattrattori di IFS.

1. La dimensione box counting

Sia A = [0, 1] il segmento unitario in R. Nel capitolo precedente, abbiamodetto (non dimostrato. . .) che la dimensione di Hausdorff di A e 1, essendoH1(A) = 1 (si veda l’Osservazione 4.12). Di nuovo, che vuol dire “dimensio-ne”? Diamo qui una seconda idea per misurare la dimensione di un insieme(come vedremo, dara una stima “dall’alto” della dimensione di un insieme).Sia allora n in N, e consideriamo un “ricoprimento” efficiente di A con seg-menti di lunghezza 1

n. “Efficiente” qui significa che nel ricoprire A si tenta

di ridurre al minimo le sovrapposizioni tra i vari segmenti. Ad esempio, seconsideriamo

[0, 1n) , [ 1

n, 2n) , . . . [n−2

n, n−1

n) , [n−1

n, 1] ,

e chiaro che il ricoprimento e disgiunto, e quindi la sovrapposizione tra i seg-menti e vuota. Quanti segmenti sono stati necessari? Basta contarli: sono n.Se, invece di considerare il segmento A = [0, 1] in R, consideriamo il segmentoA = [1, 2]× {1} in R2, quanti quadratini di lato 1

nservono per ricoprire A in

maniera efficiente? Anche in questo caso, si vede facilmente che sono necessarin quadratini.

A

1 2 1 2

A

Per ricoprire A servono n quadrati

Se considerassimo A = [2, 3] × {0} × {1} in R3, nuovamente servirebbero ncubi di lato 1

nper ricoprire efficientemente A. E se A = [0, 2]? In questo caso,

servono 2n segmenti (o quadrati, o cubi) di lato 1n. Se il segmento e lungo

L, servono ([L] + 1)n “oggetti” di lato 1n

per ricoprirlo efficientemente ([x] e

63

64 5. LA DIMENSIONE DEGLI ATTRATTORI DEGLI IFS

la parte intera di x). Cosa “non cambia” cambiando lo spazio in cui vive ilsegmento, o la sua lunghezza? In ogni caso, serve una quantita proporzionalead n di oggetti di lato 1

n(la costante di proporzionalita dipendendo dalla

lunghezza del segmento) per un ricoprimento efficiente.Se, invece di ricoprire un segmento con “oggetti”, ricopriamo un quadrato

in R2, ad esempio [1, 2]× [1, 2], quanti “oggetti” servono? E presto detto: seil lato del quadratino e 1

n, servono n2 quadratini, o n2 cubetti.

1 2

1

2

1 2

1

2

Per ricoprire un quadrato servono n2 quadrati

Se il quadrato e [0, 2]× [2, 4], servono 4n2 “oggetti” per un ricoprimento effi-ciente. In generale, serve una quantita proporzionale ad n2 di oggetti di lato1n

(la costante di proporzionalita dipendendo dall’area del quadrato) per unricoprimento efficiente di un quadrato (o di un rettangolo, o di un triangolo).

Se ricoprissimo cubi con “oggetti” di lato 1n, troveremmo che serve una

quantita proporzionale ad n3 di oggetti (la costante di proporzionalitadipendendo dal volume del cubo) per un ricoprimento efficiente.

A questo punto e chiaro cosa sta accadendo: un segmento, che ha dimen-

sione 1, necessita di (un numero proporzionale a) n 1 oggetti; un quadrato,

che ha dimensione 2, necessita di (un numero proporzionale a) n 2 ogget-ti; un cubo, che ha dimensione 3, necessita di (un numero proporzionale a)

n 3 oggetti. In sostanza, l’esponente cui viene elevato n e la dimensione delsegmento (o del quadrato, o del cubo).

Come possiamo rendere rigorosa questa “tecnica” di calcolo della dimen-sione?

Definizione 5.1. Sia A un sottoinsieme limitato di RN e sia δ > 0.Definiamo

N (A, δ) = min{m ∈ N : A puo essere ricoperto da m ipercubi di lato δ} .

Chiaramente N (A, δ) e ben definito: essendo A limitato, A e contenuto in unipercubo di lato sufficientemente grande, e gli ipercubi sono ricopribili da unnumero finito di ipercubi di lato δ; dunque, esistono ricoprimenti finiti di Afatti da ipercubi di lato δ, cosicche l’insieme che serve a definire N (A, δ) none vuoto, e quindi ha minimo perche e un sottoinsieme di N.

1. LA DIMENSIONE BOX COUNTING 65

Dato A sottoinsieme di RN , definiamo la dimensione box counting diA come il numero

dimbc(A) = limδ→0+

− log(N (A, δ))

log(δ),

ovviamente se il limite esiste (il che non e detto).

Esempio 5.2. Per quanto detto in precedenza, se A e un segmento dilunghezza L, allora

N (A, δ) =[L] + 1

δ,

e quindi dimbc(A) = 1. Se A e un rettangolo di lati L1 ed L2, allora

N (A, n) =([L1] + 1) ([L2] + 1)

δ2,

e quindi dimbc(A) = 2. Analogamente, dimbc(A) = 3 se A e un “solido”. Chesuccede se A = ? In questo caso i ricoprimenti sono complicati dalla strut-tura di , ma possiamo farci guidare dalla definizione di come attrattore diun sistema di funzioni iterate. Ed infatti, se prendiamo la n-sima iterazionedel quadrato unitario Q = [0, 1]× [0, 1]:

F (5)(Q)


e chiaro (dalla definizione stessa di ) che il ricoprimento dato da Kn =F (n)(Q) e il piu efficiente possibile se il lato del quadrato e 1

2n. Di quanti

quadrati di lato 12n

e composto Kn? Di nuovo, e facile calcolarli: K1 e l’unione

di 3 quadrati di lato 12

(le immagini di Q tramite f1, f2 e f3), K2 da 9 quadrati

di lato 14, ed in generale, Kn da 3n quadrati di lato 1

2n. Pertanto,

N ( , 2−n) = 3n ,

da cui segue

limn→+∞

− log(N ( , 2−n))

log(2−n)= lim

n→+∞

n log(3)

n log(2)=

log(3)

log(2).

In altre parole, sulla successione δn = 2−n il limite − log(N ( , δ))/ log(δ)esiste e vale log(3)/ log(2). D’altra parte, se δ > 0 e un reale qualsiasi (minoredi 1), esiste m in N tale che 2−m ≤ δ < 2−m+1. Pertanto,

3m−1 = N ( , 2−m+1) ≤ N ( , δ) ≤ N ( , 2−m) = 3m ,

e quindi

(m− 1) log(3) ≤ log(N ( , δ)) ≤ m log(3) .

Essendo −m log(2) ≤ log(δ) < −(m− 1) log(2), si ha

m− 1

m

log(3)

log(2)≤ − log(N ( , δ))

log(δ)≤ m

m− 1

log(3)

log(2).

Facendo tendere δ a zero (cosicche m tende ad infinito), si ha (per il teoremadei carabinieri)

limδ→0+

− log(N ( , δ))

log(δ)=

log(3)

log(2)= dimbc( ) .

– Esercizio 5.3. Calcolare la dimensione box counting di e dellacurva di Von Koch.

2. Confronto tra box counting e Hausdorff

Che legame c’e tra la dimensione box counting di un insieme e la suadimensione di Hausdorff?

Teorema 5.4. Sia A un sottoinsieme limitato di RN . Allora

dimH(A) ≤ dimbc(A) .

Dimostrazione. Sia s = dimbc(A). Per definizione

s = limδ→0+

− log(N (A, δ))

log(δ).

2. CONFRONTO TRA BOX COUNTING E HAUSDORFF 67

Sia ε > 0, e sia δε > 0 tale che

s− ε ≤ − log(N (A, δ))

log(δ)≤ s+ ε , ∀δ ≤ δε .

Pertanto,

1

δs−ε≤ N (A, δ) ≤ 1

δs−ε, ∀δ ≤ δε .

Ricordando la definizione di N (A, δ), fissato δ ≤ δε esiste un ricoprimento{Ei,δ} “efficiente” di A costituito da Mδ = N (A, δ) ipercubi di lato δ, conδ−(s−ε) ≤ Mδ ≤ δ−(s+ε). Essendo il diametro di un ipercubo di lato δ pari adδ = δ

√N , e chiaro che {Ei,δ} e un dδ-ricoprimento di A. Pertanto, se s > s,

0 ≤ Hsdδ

(A)≤α(s)

Mδ∑i=1

(diam(Ei,δ)

2

)s=α(s)

Mδ∑i=1

(δ

√N

2

)s= α(s)

(√N

2

)sMδ δ

s

≤α(s)

(√N

2

)sδs−(s+ε) .

Scegliendo ε > 0 tale che s+ε < s, si ha, per qualche costante C indipendenteda n,

0 ≤ Hsdδ

(A) ≤ C δs−(s+ε) , ∀δ ≥ δε .

Facendo tendere δ a zero, si ha che dδ tende a zero, e quindi Hs(A) = 0.Pertanto,

(s,+∞) ⊆ {s ≥ 0 : Hs(A) = 0} ,

e quindi

dimH(A) = inf{s ≥ 0 : Hs(A) = 0} ≤ inf (s,+∞) = s = dimbc(A) ,


Il teorema precedente e utile quando si vuole stimare dall’alto la dimensio-ne di Hausdorff di insiemi trovati come attrattori di sistemi di funzioni iterate.Infatti, il calcolo dell’Esempio 5.2, puo essere ripetuto per un qualsiasi sistemadi funzioni iterate: se {f1, . . . , fm} e un sistema di funzioni iterate di fattoredi contrazione L, e se Kn = F (n)( ), allora Kn e l’unione di mn oggetti didiametro minore o uguale a Ln, e quindi N (K,Ln) ≈ mn, da cui

limn→+∞

− log(N (K,Ln))

log(Ln)= lim

n→+∞−n log(m)

n log(L)= − log(m)

log(L).


Ragionando come nell’Esempio 5.2, si vede che tale valore e il limite lungotutta la successione, e quindi

dimbc(K) = − log(m)

log(L).

C’e, pero, almeno un errore nel calcolo che abbiamo fatto. Supponiamo diavere cinque contrazioni di fattore 1

2: le quattro che generano il quadrato

dell’Esempio 3.5, piu

f5(x, y) = f1(x, y) + (14, 14) .

Se il calcolo precedente fosse giusto, dettoK l’attrattore del sistema di funzioniiterate {f1, . . . , f5}, si avrebbe

dimbc(K) = − log(5)

log(12)

=log(5)

log(2)> 2 .

In altre parole, se la formula fosse giusta, K avrebbe dimensione box countingmaggiore di 2, pur essendo un sottoinsieme di R2: questo non puo essereperche, essendo K contenuto in = [0, 1]× [0, 1], si ha

N (K, δ) ≤ N ( , δ) = δ−2 ,

da cui dimbc(K) ≤ 2. In effetti, e facile vedere che la quinta contrazione nonmodifica nulla rispetto alle prime 4: partendo da , si ha F (1)( ) = , equindi K = (che sappiamo avere dimensione box counting proprio 2).

Dov’e l’errore? Abbiamo sbagliato nello stimare N (Kn, δ): essendo Kn =, servono 4n quadrati di lato δ = 1

2nper ricoprire Kn, e non 5n, come si vede

facilmente dal disegno.

F (5)( )


Bastano meno quadrati perche le cinque immagini di tramite f1, . . ., f5 nonsono disgiunte tra di loro: si sovrappongono (e anche di parecchio!) cosiccheuna delle cinque applicazioni non influisce sul calcolo della dimensione boxcounting. Nel caso di , invece, le tre immagini del quadrato unitario sonodisgiunte, e quindi Kn, visto come unione di quadrati, e un ricoprimento“ottimale” di (se consideriamo quadrati di lato δ = 1

2n).

Inoltre, abbiamo commesso un altro errore: quando diciamo che un sistemadi funzioni iterate ha fattore di contrazione L, intendiamo che il massimo deifattori di contrazione L1, . . ., Lm delle funzioni f1, . . ., fm che formano ilsistema di funzioni iterate e uguale a L. Supponiamo che f1(x, y) = (x

2, y2),

e f2(x, y) = (1, 1). Come sistema di funzioni iterate, la coppia {f1, f2} hacome fattore di contrazione L = 1

2. Pero, pur essendo le immagini di

disgiunte, l’insieme invariante per F e K = {(0, 0), (1, 1)} che ha dimensionebox counting 0, mentre la formula ci darebbe dimbc(K) = 1. Ovviamente, quiil problema e che le due contrazioni hanno fattori di contrazione diversi (unoe addirittura 0). Lo stesso accade se consideriamo l’attrattore del sistema difunzioni iterate generato da

f1(x, y) = (x2, y2) , f2(x, y) = (x

3+ 1

2, y3

+ 13) .

F (5)( )

E chiaro dal disegno che la dimensione box counting dell’attrattore K non puoessere 1, ma sara strettamente minore.

Infine, un terzo problema: una contrazione e un’applicazione qualsiasi daRN in se, che sia lipschitziana di costante minore di 1; quindi, non e dettoche l’immagine di un quadrato sia un quadrato (o un rettangolo, un rombo:qualcosa, insomma, di paragonabile). Tutte le contrazioni che abbiamo consi-derato avevano questa proprieta (essendo delle similitudini), ma non e dettoche cio sia vero in generale.


In definitiva, se vogliamo poter calcolare “a priori” la dimensione box coun-ting di un attrattore di un sistema di funzioni iterate, dobbiamo fare delleipotesi aggiuntive.

Teorema 5.5. Sia {f1, . . . , fm} un sistema di funzioni iterate su RN ,e sia F la funzione da K(RN) in se costruita a partire dall’IFS. Supponiamoche:

(1) fi = Li x + Bi, con 0 < Li < 1 e Bi un vettore di RN (e quindi fi euna similitudine);

(2) esiste Qr, ipercubo di lato r, tale che F (Qr) ⊆ Qr;(3) se Qr e come sopra, allora fi(Qr) ∩ fj(Qr) = ∅ per ogni i 6= j.

Allora, detto K l’attrattore del sistema di funzioni iterate, si ha dimbc(K) = s,dove s e l’unica soluzione positiva dell’equazione

m∑i=1

Lsi = 1 .

Osservazione 5.6. Se valgono le (2) e (3) del teorema precedente, e seLi = L per ogni i, allora s e tale che mLs = 1, e quindi

s = dimbc(K) = − log(m)

log(L),

che e la formula che avevamo trovato (sbagliando. . .) in precedenza.

Osservazione 5.7. Che esista un unico valore s ≥ 0 tale chem∑i=1

Lsi = 1 ,

si vede abbastanza facilmente usando il teorema di esistenza degli zeri. Infatti,posto

G(s) =m∑i=1

Lsi ,

si ha

G(0) = m ≥ 1 , lims→+∞

G(s) = 0 .

Essendo G continua, esiste almeno un valore s tale che G(s) = 1. Inoltre,

G′(s) =m∑i=1

Lsi log(Li) < 0 ,

dato che 0 < Li < 1 per ogni i. Ne segue che G e strettamente decrescente equindi che s e unico.


Dimostrazione. Iniziamo con l’osservare che, essendo fi una similitudinedi fattore contrattivo Li, allora l’immagine tramite fi di un quadrato Qr dilato r e un quadrato di lato Li r e, viceversa, la controimmagine tramite fi diun quadrato Qr di lato r e un quadrato di lato L−1i r. Pertanto, se A e uninsieme limitato qualsiasi, si ha

N (A, δ) = N (fi(A), Liδ) ,

o, equivalentemente,

(5.1) N (fi(A), δ) = N (A,L−1i δ) .

Sia ora K l’attrattore del sistema di funzioni iterate. Dal momento che, perla (2), F (Qr) ⊆ Qr, la successione Kn = F (n)(Qr) e tutta contenuta in Qr, equindi K ⊆ Qr. Essendo fi(Qr) ∩ fj(Qr) = ∅ per la (3), ne segue che

fi(K) ∩ fj(K) = ∅ , ∀i 6= j .

Siccome le fi sono continue, l’insieme fi(K) e un compatto per ogni i. Dalmomento che fi(K) e fj(K) sono disgiunti, si ha

dij = min{d2(x, y), x ∈ fi(K), y ∈ fj(K)} > 0 , ∀i 6= j ,

perche se il minimo fosse zero, esisterebbe x nell’intersezione dei due insiemi,che e invece vuota. Pertanto, se definiamo δ il minimo delle distanze dij al

variare di i e j (con i 6= j), e scegliamo δ < δ, si ha che se un ipercubo di lato δinterseca uno degli insiemi fi(K), allora e disgiunto da tutti gli insiemi fj(K),con i 6= j. In altre parole, un ricoprimento “efficace” di K con ipercubi dilato δ si ottiene considerando gli ipercubi che ricoprono efficacemente f1(K),insieme a quelli che ricoprono efficacemente f2(K), e cosı via, fino a quelli chericoprono efficacemente fm(K). Pertanto, se δ < δ, si ha, per (5.1),

N (K, δ) =m∑i=1

N (fi(K), δ) =m∑i=1

N (K,L−1i δ) .

Da questa relazione, segue che se s e come nell’enunciato del teorema, allora

(5.2) limδ→0+

δsN (K, δ) = M ∈ (0,+∞) .

Per dare un’idea del perche cio accada (la dimostrazione rigorosa e troppocomplicata. . .), dimostriamo la (5.2) nel caso in cui Li = Lj = L per ogni i ej (come per esempio accade per ). Allora, posto G(δ) = N (K, δ), si ha

G(δ) = mG(L−1 δ) .

Iterando questa formula, si ha

G(L) = mG(1) , G(L2) = mG(L) = m2G(1) , . . . , G(Ln) = mnG(1) .

Se s e tale che mLs = 1, allora mn = L−ns e quindi

(Ln)sG(Ln) = G(1) .


Dal momento che Ln tende a zero abbiamo (almeno lungo una successioneinfinitesima) che (5.2) e soddisfatta.

Una volta che la (5.2) e vera, la tesi segue in maniera semplice dalleproprieta dei logaritmi:

limδ→0+

− log(N (K, δ))

log(δ)= lim

δ→0+− log(δsN (K, δ))− s log(δ)

log(δ)= s ,


Osservazione 5.8. Lo stesso risultato dimostrato in precedenza vale se,invece della condizione (3), si assume la condizione piu debole che l’intersezionefi(Qr) ∩ fj(Qr) abbia misura N -dimensionale nulla se i 6= j.

3. La dimensione di Hausdorff degli attrattori degli IFS

Nella sezione precedente abbiamo trovato una stima dall’alto della di-mensione di Hausdorff dell’attrattore di un sistema di funzioni iterate in ter-mini delle dimensione box counting; inoltre, grazie al Teorema 5.5, sappiamocalcolare la dimensione box counting degli attrattori di IFS definiti tramitesimilitudini (che sono piu o meno tutti quelli che abbiamo visto. . .). Rimaneaperto, e sara compito delle prossime pagine, il problema di stimare dal bas-so la dimensione di Hausdorff degli attrattori, chiedendoci in particolare secoincida con la dimensione box counting.

Esempio 5.9. Sia

K = {1, 12, 13, 14, . . . , 1

n, . . .} .

Dimostriamo che dimH(K) = 0. Siano s > 0, e sia δ > 0. Allora esiste nδ inN tale che tutti gli elementi di K a partire dall’nδ-mo in poi sono contenutiin (−δ, δ), e quindi K e contenuto nell’unione di un intervallo di diametro 2δ,e di nδ intervalli di diametro piccolo a piacere (che sono necessari per coprirei primi nδ punti 1, 1

2, . . ., 1

nδ), sia esso ad esempio 2δ2/s. Pertanto,

0 ≤ Hsδ(K) ≤ α(s) δs + α(s)nδδ

2 .

Essendo nδ ≈ δ−1, si ha

0 ≤ Hsδ(K) ≤ α(s) δs + α(s) δ ,

da cui segue Hs(K) = 0 facendo tendere δ a zero. Essendo s > 0 arbitrario,ne segue che dimH(K) = 0. Calcoliamo ora la dimensione box counting di K.Sia 0 < δ < 1

2, e sia k in N tale che

1

k(k + 1)< δ ≤ 1

k(k − 1).

Chiaramente, se S e un segmento lungo δ, S puo coprire al piu uno dei punti in{1, 1

2, . . . , 1

k}, dal momento che la distanza tra due qualsiasi di questi punti

3. LA DIMENSIONE DI HAUSDORFF DEGLI ATTRATTORI DEGLI IFS 73

e almeno 1k(k−1) , che e maggiore di δ. Pertanto, servono almeno k segmenti di

lunghezza δ per ricoprire K, e quindi N (K, δ) ≥ k. D’altro canto, e possibilericoprire [0, 1

k] con k + 1 segmenti di lunghezza δ (perche δ > 1

k(k+1), che e la

distanza massima tra i punti di tale intervallo), mentre {1, 12, . . . , 1

k} puo

essere ricoperto con k − 1 intervalli di lunghezza δ (perche sono k − 1 punti).Pertanto, N (K, δ) ≤ 2k. Ma allora,

log(k)

log(k(k + 1))≤ − log(N (K, δ))

log(δ)≤ log(2k)

log(k(k − 1)).

Facendo tendere δ a zero (e quindi k ad infinito), per il teorema dei carabinierisi ha

limδ→0+

− log(N (K, δ))

log(δ)=

1

2= dimbc(K) ,

cosicche dimH(K) < dimbc(K).

Ovviamente l’esempio precedente non rientra nel caso degli attrattori diIFS (non essendo K compatto, non puo essere l’attrattore di un sistema difunzioni iterate), ma e comunque interessante per capire la differenza tra ladimensione di Hausdorff e la dimensione box counting. Rimane pero in piedila domanda: che succede per l’attrattore di un IFS? Sono uguali o no?

La risposta (non semplice da dare) e positiva, e, come vedremo, richiederanuovamente delle ipotesi aggiuntive sul sistema di funzioni iterate. Il primorisultato ci permette di stimare dal basso dimH(K).

Teorema 5.10. Sia K in K(RN). Supponiamo che esista una misura µconcentrata su K tale che µ(K) > 0, ed esistano C > 0, s > 0 e ε > 0, taliche

(5.3) µ(E) ≤ C (diam(E))s , ∀E : diam(E) ≤ ε

Allora dimH(K) ≥ s.

Dimostrazione. Sia δ < ε, e sia {Ei} un δ-ricoprimento di K. Allora

0 < µ(K) ≤ µ

( +∞⋃i=1

Ei

)≤

+∞∑i=1

µ(Ei) ≤ C+∞∑i=1

(diam(Ei))s .

Pertanto si ha

α(s)+∞∑i=1

(diam(Ei)

2

)s≥ α(s)

2sCµ(K) > 0 ,

e quindi, per l’arbitrarieta del δ-ricoprimento,

Hsδ(K) ≥ α(s)

2sCµ(K) > 0 , ∀δ < ε .


Ricordando che, come funzione di δ, Hsδ(K) e decrescente, si ha Hs(K) > 0, e

quindi la tesi. �

Supponiamo ora di avere un sistema di funzioni iterate per il quale val-gono le ipotesi del Teorema 5.5, cosicche sappiamo calcolare la dimensionebox counting dell’attrattore K. Vogliamo fare vedere che, in questo caso, epossibile costruire una misura su K che soddisfa le ipotesi del Teorema 5.10con s = s, la dimensione box counting di K.

Iniziamo con un lemma tecnico.

Lemma 5.11. Sia r > 0, e sia {Qi} una famiglia di ipercubi di RN conla proprieta che esistono 0 < a1 < a2 tali che ogni ipercubo Qi contieneun ipercubo di lato a1r, ed e contenuto in un ipercubo di lato a2r, e chel’intersezione tra due ipercubi della famiglia ha misura N -dimensionale nulla.Allora ogni ipercubo Q2r di lato 2r interseca al piu q dei Qi, e si ha

q ≤(

2(1 + a2)

a1

)N.

Dimostrazione. Se Qi interseca Qr, allora Qi e contenuto nell’ipercuboche ha lo stesso centro di Qr e lato 2r(1 + a2).

QrQi

2ra2r

2r + 2a2r

Ogni cubo che interseca Qr . . .

Pertanto, se q ipercubi di {Qi} intersecano Qr, ognuno di essi contiene unipercubo di lato a1r, ed e contenuto in un ipercubo di lato 2r(1+a2). Pertanto,essendo i Qi disgiunti a meno di insiemi di misura N -dimensionale nulla, lasomma delle misure N -dimensionali degli ipercubi di lato a1r non puo esseresuperiore alla misura N -dimensionale dell’ipercubo di lato 2r(1 + a2) che licontiene, e quindi

q (a1r)N ≤ (2r(1 + a2))

N ,


da cui si ottiene

q ≤(

2(1 + a2)

a1

)N,


Il secondo risultato tecnico ci dice come costruire una misura su oggettiottenuti tramite suddivisioni di un insieme iniziale.

Lemma 5.12. Sia A un sottoinsieme compatto di RN , e sia E0 = A. Per kin N, sia Ek una famiglia finita disgiunta di compatti contenuti in A tali che

(1) ogni E in Ek e contenuto in un insieme di Ek−1;(2) ogni E in Ek contiene un numero finito di insiemi di Ek+1;(3) si ha

limk→+∞

max{diam(E), E ∈ Ek} = 0 .

Sia µ definita nella maniera seguente: µ(A) e assegnata, con 0 < µ(A) < +∞;definiamo poi µ sugli insiemi di E1 in maniera tale che

µ(A) =∑Ei∈E1

µ(Ei) ,

e, proseguendo, definiamo µ sugli insiemi di Ek in modo tale che se E1, . . ., Eksono insiemi di Ek contenuti in un insieme E di Ek−1, allora

µ(E) =k∑i=1

µ(Ei) .

µ(E0)

µ(E1)µ(E1)

µ(E2)µ(E2) µ(E2)µ(E2)

Suddivisione di insiemi e misure

Definiamo Ek l’unione di tutti gli insiemi di Ek, e definiamo µ(E) = 0 seE ∩ Ek = ∅. Pertanto, se E e l’unione di tutte le famiglie Ek, e di tutti isottoinsiemi di RN \ Ek, abbiamo che la funzione µ e definita su E . Alloraesiste una misura µ, definita su tutto RN , che estende µ, ed il cui supporto econtenuto nell’intersezione degli Ek.


Dimostrazione. Se E e un sottoinsieme di RN , definiamo

µ(E) = inf

{∑i

µ(Ei), E ⊆⋃i

Ei e Ei ∈ E

}.

Se E appartiene ad E , si ha chiaramente µ(E) = µ(E) (perche abbiamo de-finito µ su E tramite suddivisioni). Inoltre, essendo µ(RN \ Ek) = 0 percostruzione, se E e un sottoinsieme di RN disgiunto da Ek per qualche k,allora µ(E) = 0, e quindi il supporto di µ e contenuto in Ek per ogni k, edunque nell’intersezione. La dimostrazione del fatto che µ sia effettivamenteuna misura e lasciata al lettore. . . �

Esempio 5.13. Sia A = [0, 1], sia Ek la famiglia degli intervalli della forma

Ej = [ j2k, j+1

2k) , j = 0, 1, . . . , 2k − 1 ,

ed osserviamo che Ek soddisfa la (1), la (2) e la (3) del lemma precedente.Se E e in Ek, definiamo µ(E) = 1

2k, cosicche le condizioni sulle suddivisioni

della misura sono soddisfatte. Pertanto, a partire da µ definita su E , possiamocostruire una misura µ definita su R. Se I = (a, b) e un intervallo contenutoin [0, 1], allora

µ(I) = inf

{∑i

µ(Ei), I ⊆⋃i

Ei e Ei ∈ E

}= (b− a) ,

e quindi µ coincide con la misura di Lebesgue sugli intervalli. Questa informa-zione e sufficiente per caratterizzare µ esattamente come la misura di Lebesgue(concentrata su [0, 1]).

Possiamo ora dimostrare il risultato che ci permette di stimare dal bassola dimensione di Hausdorff di un attrattore di IFS.

Teorema 5.14. Sia {f1, . . . , fm} un sistema di funzioni iterate definitosu RN , e supponiamo che soddisfi le ipotesi del Teorema 5.5 (o, per la (3),dell’Osservazione 5.8). Detto K l’attrattore dell’IFS, e posto s = dimbc(K),si ha dimH(K) ≥ s.

Dimostrazione. Per il Teorema 5.10, dobbiamo costruire una misura µsu K che soddisfi (5.3) con s = s, ricordando che s e tale che

m∑i=1

Lsi = 1 .

Sia ora Qr l’ipercubo delle ipotesi (2) e (3) del Teorema 5.5, che quindi e taleche

F (Qr) =m⋃i=1

Fi(Qr) ⊆ Qr ,


con unione disgiunta. Pertanto, se definiamo K0 = Qr, e Kn = F (n)(Qr),abbiamo che {Kn} e una successione decrescente di insiemi in K(RN), e Kn

e l’unione disgiunta di mn compatti Kn,j1,...,jn con j1, . . ., jn interi compresitra 1 e m, e

Kn,j1,...,jn = (Fjn ◦ Fjn−1 ◦ . . . ◦ Fj2 ◦ Fj1)(Qr) .

Se definiamo En come la famiglia degli insiemi Kn,j1,...,jn , e chiaro che En sod-disfa le ipotesi (1), (2) e (3) del Lemma 5.12. In particolare, la (3) e veraperche il diametro di Kn,j1,...,jn e dato da Lj1 · · ·Ljn r, cosicche

0 ≤ diam(Kn,j1,...,jn) ≤ (max{L1, . . . , Lm})n r ,e la quantita a destra e infinitesima essendo Li < 1 per ogni i. Definiamo

µ(Kn,j1,...,jn) = (Lj1 · · ·Ljn)s ,

ed osserviamo che (essendo le unioni disgiunte)

µ(Kn) =∑

1≤j1,...,jn≤m

(Lj1 · · ·Ljn)s =

( m∑j1=1

Lsj1

)· · ·( m∑jn=1

Lsjn

)= 1 ,

e che, essendo

(Lj1 · · ·Ljn)s =m∑

jn+1=1

(Lj1 · · ·Ljn Ljn+1)s ,

si ha

µ(Kn,j1,...,jn) =m∑

jn+1=1

µ(Kn,j1,...,jn,jn+1) .

Dal momento che µ soddisfa le ipotesi di “suddivisione” del Lemma 5.12, epossibile estendere µ ad una misura µ, definita su RN , ed il cui supporto econtenuto nell’intersezione dei Kn, che e l’attrattore K dell’IFS.

Verifichiamo ora che µ soddisfa le ipotesi del Teorema 5.10. Sia Q unipercubo di lato 2r, e sia data una successione {jh} di interi compresi tra 1ed m. Sia k il primo intero per il quale si ha

(5.4) min{L1, . . . , Lm} r ≤ Lj1 · · ·Ljk r ≤ r .

Si noti che k dipende dai valori Li (e quindi dalla successione {jh}), e puoquindi variare. Sia ora S l’insieme delle k-ple j1, . . ., jk tali che valga (5.4), esia

T = {(Fjk ◦ · · · ◦ Fj1)(Qr), (j1, . . . , jk) ∈ S} .Gli insiemi contenuti in T sono ipercubi disgiunti tra loro. Siano infatti A eB in T , con A 6= B. Allora

A = (Fjk ◦ · · · ◦ Fj1)(Qr) , B = (Fih ◦ · · · ◦ Fi1)(Qr) ,


con (j1, . . . , jk) e (i1, . . . , ih) in S. Supponiamo che sia h = min{h, k}.Allora esiste `, compreso tra 1 e h, tale che j` 6= i`. Se cosı non fosse, ovverose gli indici coincidessero fino ad h, allora k = h; infatti, non puo essere k > hperche k e il primo intero per cui vale (5.4) (e quindi (5.4) non puo valere,per la stessa successione di indici, per h < k). Ma se k = h, allora A = B,il che non e. Pertanto, ad un certo punto, gli indici differiscono. Siccomecontrazioni diverse “disgiungono” gli insiemi (per l’ipotesi (3) del teorema),A e B sono “disgiunti al passo `” e quindi disgiunti. Inoltre, gli ipercubi diT hanno un lato pari a Lj1 · · ·Ljk r, e quindi contengono un ipercubo di latomin{L1, . . . , Lm} r = a1r, e sono contenuti in un ipercubo di lato r = a2 r.Per il Lemma 5.11, l’ipercubo Q di lato 2r interseca al piu q degli ipercubi diT , con

q ≤(

2(1 + a2)

a1

)N=

(4

min{L1, . . . , Lm}

)N= q0 .

Se definiamoQ =

⋃Qi∈T : Q∩Qi 6=∅

Qi ,

alloraQ = Q ∪ (Q \ Q) ,

e l’insieme Q \ Q non interseca nessuno degli ipercubi di T . Supponiamo di

aver dimostrato che esiste k tale che Q \ Q ha intersezione vuota con Ek.Allora si ha (per definizione di µ)

µ(Q) ≤∑

Qi∈T : Q∩Qi 6=∅

µ(Qi) + µ(Q \ Q) =∑


µ(Qi) .

D’altra parte, se Qi e in T , allora Qi corrisponde ad una k-pla j1, . . ., jk diindici, cosicche Qi e in Ek, e quindi

µ(Qi) = (Lj1 · · ·Ljk)s .Pertanto, ricordando (5.4),

µ(Q) ≤∑


(Lj1 · · ·Ljk)s ≤ q01

rsrs = C rs .

Sia ora E un insieme di diametro uguale ad r. Allora E e contenuto in unipercubo Q di lato 2r e quindi

µ(E) ≤ µ(Q) ≤ C rs = C (diam(E))s .

Sono pertanto soddisfatte le ipotesi del Teorema 5.10, e quindi la dimensionedi Hausdorff di K e maggiore di s.

Rimane quindi da dimostrare che Q \ Q ha intersezione vuota con Ek perqualche k. Definiamo k il massimo delle lunghezze delle k-ple j1, . . ., jk in S, e


sia E in Ek. Se E intersecasse Q\Q, allora E sarebbe disgiunto da tutti i Qi diT che intersecano Q, ma intersecherebbe Q. Cio pero non e possibile, perche,essendo E contenuto in Ek, e contenuto in (e quindi interseca) almeno uno deiQi di T (dato che o e uno di essi, o proviene da uno di essi come immaginetramite iterate di F ), che quindi avrebbe intersezione non vuota con Q. �

Esempio 5.15. Per chiarire la dimostrazione precedente, consideriamo ,che e l’attrattore dell’IFS generato da tre contrazioni di fattore 1

2. Partiamo

da Qr = Q1 = [0, 1]× [0, 1], e costruiamo la successione Kn delle iterate di Q1

tramite F . Essendo s = log(3)log(2)

, la misura µ e definita su Kn,j1,...,jn come segue:

µ(Kn,j1,...,jn) =

(1

2n

)s=

1

3n.

Essendo Kn l’unione di 3n quadrati disgiunti (di lato 2−n), e chiaro cheµ(Kn) = 1 per ogni n. Se ora consideriamo un quadrato Q di lato 2r, laformula (5.4) si semplifica: dato che Ljh = 1

2per ogni jh, si tratta solo di

scegliere k tale cher

2≤ 1

2k≤ r .

In questa maniera,

S = {(j1, . . . , jk), jh ∈ {1, . . . , m} per ogni h} ,e

T = {Qi : Qi e uno dei quadrati la cui unione e Kk} .A questo punto, al piu 64 quadrati di T intersecano Q, e chiaramente Q\Q haintersezione vuota con Ek = Kk, dato che abbiamo “cancellato” da Kk tutti iquadrati che intersecano Q.

Strumenti e programmi

Che ci si creda o no, le uniche figure di questi appunti “costruite” senzausare TEX sono nel Capitolo 3 (a vedere la qualita del disegno si direbbe: perfortuna!). Tutti gli altri oggetti (ed in special modo le approssimazioni F (n)

degli attrattori di sistemi di funzioni iterate) sono disegnati usando softwarereperibili nella distribuzione standard del TEX (quando sono stati scritti gliappunti, la distribuzione era la TEX Live 2010, reperibile on line all’indirizzohttp://www.tug.org/texlive/).

Il pacchetto software utilizzato si chiama tikz (dal tedesco: “TikZ istkein Zeichenprogramm”, “tikz non e un programma di disegno”), corredatoda un manuale di piu di 700 (!) pagine. Le possibilita di disegno (o di “nondisegno”, secondo l’autore) sono pressoche infinite, agevolate da una serie dicomandi semplici (come draw o rectangle, circle e simili), e dalla possibilitadi specificare le coordinate dei punti usando il sistema cartesiano. Ad esempio,con i comandi

\begin{tikzpicture}[scale=2]

\draw [fill=red] (0,0) -- (1,0) -- (1,1) -- (0,1) -- cycle;

\draw [fill=blue] (1,0) -- (2,0) -- (2,1) -- (1,1) -- cycle;

\draw [fill=green] (1,1) -- (2,1) -- (2,2) -- (1,2) -- cycle;

\end{tikzpicture}

si disegnano tre quadrati di diversi colori:

con la possibilita di aggiungere etichette e comandi standard del TEX. Adesempio,

\begin{tikzpicture}[scale=2]

\draw [fill=red] (0,0) -- (1,0) -- (1,1) -- (0,1) -- cycle;

81

82 STRUMENTI E PROGRAMMI

\draw [fill=blue] (1,0) -- (2,0) -- (2,1) -- (1,1) -- cycle;

\draw [fill=green] (1,1) -- (2,1) -- (2,2) -- (1,2) -- cycle;

\draw (0,0) node[below]{$(0,0)$};

\draw (2,0) node[below]{$(2,0)$};

\draw (2,2) node[above]{$(2,2)$};

\draw [fill=black] (0.5,0.5) circle (0.05)

node[above]{$(\frac12,\frac12)$};

\draw [fill=white,color=white] (3/2,1/2) circle (0.05)


\draw [fill=magenta] (1+1/2,1.5) circle (0.05)


\end{tikzpicture}

completa il disegno cosı:

(0, 0) (2, 0)

(2, 2)

(12, 12) (3

2, 12)

(32, 32)

Si noti che il programma calcola correttamente sia 3/2 che 1+1/2, e che ri-conosce i colori. Inoltre, e molto preciso nel “posizionare” gli oggetti graficisulla pagina. Ad esempio:

\begin{tikzpicture}[

scale=20,

spy using outlines={magnification=12, size=2cm, connect spies}

]

\draw [ultra thin] (0.000,0.000) circle (0.001);

\draw [ultra thin] (0.003,0.000) circle (0.001);

\spy on (0.030,0.000) in node [left] at (0.2,0.0);

\end{tikzpicture}

crea il seguente disegno:

STRUMENTI E PROGRAMMI 83

Si noti che l’ingrandimento e automatico (e fornito dal pacchetto aggiuntivo“spy”, da caricarsi a parte col comando \usetikzpackage{spy}).

Pertanto, dovendo disegnare innumerevoli quadratini e/o triangolini di va-ri colori per rappresentare le approssimazioni degli attrattori, la scelta di tikzera, in un certo senso, obbligata. D’altra parte, pero, per disegnare l’appros-simazione di ordine 6 di , sono necessari 36 = 729 oggetti, ed e chiaro che“scriverli” tutti diventa istantaneamente un’impresa improba (a dire il vero,lo e gia per i 9 oggetti dell’approssimazione di ordine 2. . .).

In sostanza, se da un lato tikz fornisce gli strumenti “per disegnare”,non e possibile usarlo senza ricorrere a qualche altro ausilio informatico che“generi” i comandi corretti, con le corrette coordinate. A ben vedere, generareun’approssimazione di ordine qualsiasi di un attrattore e cosa semplice:

(1) partire da un insieme iniziale di punti (ad esempio, i quattro verticidel quadrato [0, 1]× [0, 1]);

(2) calcolare le immagini di tali punti tramite le contrazioni dell’IFS (adesempio, le tre contrazioni che generano );

(3) sostituire all’insieme dei punti iniziali il nuovo insieme di punti etornare a (2), oppure. . .

(4) . . .fermarsi quando si e raggiunta l’n-sima iterazione e formattare idati in maniera che tikz possa disegnarli.

A questo punto, ognuno puo scegliere il proprio linguaggio di programma-zione preferito e scrivere il programma che esegue i calcoli . Chi scrive hausato REBOL (reperibile gratuitamente all’indirizzo http://www.rebol.com).

REBOL e un linguaggio di programmazione specificamente pensato per trat-tare liste di dati; e, ad esempio, ottimo per estrarre informazioni da una paginaweb. I comandi principali usati nei programmi che seguono sono:

• pick lista posizione: data una lista [a1 a2 . . . an], estrae l’elementoche occupa la posizione specificata; ad esempio, pick [1 3 5 7] 3

da come risultato 5.• first lista: e uguale a pick lista 1.• length? lista: restituisce la lunghezza della lista.• last lista: e uguale a pick lista (length? lista).• select lista elemento: restituisce l’elemento di lista successivo ad ele-

mento. Ad esempio, select [1 [2 3] 2 [4 5] 3 [6]] 2 da comerisultato [4 5].• next lista: restituisce la lista ottenuta a partire dall’elemento succes-

sivo a quello selezionato; ad esempio next select [1 [2 3] 2 [4

5] 3 [6]] 2 da come risultato [3 [6]].• reduce lista: data una lista [a1 a2 . . . an], composta di variabili,

restituisce una lista i cui elementi sono i valori delle variabili; se, adesempio, a = 1 e b = 2, allora reduce [a b] = [1 2].


• rejoin lista: e come reduce, solo che restituisce la stringa ottenutaconcatenando i valori delle variabili in lista; ad esempio, se a = 3,allora rejoin [‘ci sono ’ a ‘ persone’] da come risultato ‘ci

sono 3 persone’.• append lista a: data una lista [a1 a2 . . . an], restituisce la lista

[a1 a2 . . . an a]. Se lista e una stringa ‘stringa’, allora append

‘stringa’ ‘appesa’ restituisce la stringa ‘stringaappesa’.• copy/part lista lunghezza: restituisce i primi lunghezza elementi di

lista (che puo anche essere una stringa); ad esempio, copy/part [1

2 3 4] 2 da come risultato [1 2].• skip lista lunghezza: restituisce la lista (che puo anche essere una

stringa) privata dei primi lunghezza elementi; ad esempio, skip [1 2

3 4] 2 da come risultato [3 4].

REBOL [‘Sistemi di funzioni iterate’]

;=== FUNZIONI ===

; calcola A*X+Btrasforma: func [

matricevettore/local temp x temp y

][; calcola a11*x + a12*y + b1temp x: ((pick matrice 1) * (pick vettore 1))temp x: ((pick matrice 2) * (pick vettore 2)) + temp xtemp x: (pick matrice 5) + temp x; calcola a21*x + a22*y + b2temp y: ((pick matrice 3) * (pick vettore 1))temp y: ((pick matrice 4) * (pick vettore 2)) + temp ytemp y: (pick matrice 6) + temp yreturn reduce [temp x temp y]

]

; scrive un numero con ’posti’ cifre decimaliformato decimale: func [

valoreposti/local cifra indice nuovo valore segno

temp lungh temp stringa zeri][

temp stringa: copy ‘1’for indice 1 posti 1 [

append temp stringa ‘0’]


; ‘1’ seguito da tanti zeri quanti i postinuovo valore: to-integer ((to-integer temp stringa) * valore); moltiplicato e arrotondatoeither (nuovo valore < 0) [

segno: ‘-’nuovo valore: abs nuovo valore

][segno: ‘ ’

]; scopre se la stringa inizia con ’-’ o con ’ ’temp stringa: copy ‘’until [

cifra: to-integer remainder nuovo valore 10nuovo valore: to-integer ((nuovo-valore - cifra) / 10)temp stringa: rejoin [cifra temp stringa]nuovo valore = 0

]; si ferma quando il numero = zeroif ((length? temp stringa) <= posti) [

zeri: posti + 1 - (length? temp stringa)temp stringa: rejoin [

copy/part ‘0000000000’ zeritemp stringa

]]; calcola gli zeri inizialitemp lungh: (length? temp stringa) - postireturn to-string rejoin [

segnocopy/part temp stringa temp lungh‘.’skip temp stringa temp lungh

]; costruisce la stringa con ’posti’ cifre decimali

]

; crea una stringa con il vettore e le parentesiscrive vettore: func [

vettoredecim

][return rejoin [

‘(’(formato decimale (pick vettore 1) decim)‘, ’(formato decimale (pick vettore 2) decim)‘)’

]


]

;=== FORME ===

; il formato: stringa di tikz con ’ pi ’ per i punti; e ’ colore ’ per il colore, seguita dagli n puntiforme: [

‘quadrato’[

‘\draw [shape= colore ]p1 --p2 --p3 --p4 --

cycle;^/’[0.0 0.0][1.0 0.0][1.0 1.0][0.0 1.0]

]]

;=== IFS ===

; formato di A (2x2) e B (1x2):; [a 11 a 12 a 21 a 22 b 1 b 2]ifs: [

‘equisierpinski’[

[0.5 0.0 0.0 0.5 0.00 0.000][0.5 0.0 0.0 0.5 0.25 0.433][0.5 0.0 0.0 0.5 0.50 0.000]

]]

colori bordo: [‘gray!50’ ‘#1!80’]

;=== SCELTE ===

forma scelta: ‘quadrato’ifs scelto: ‘equisierpinski’livello max: 4tipo: 1; 1 = colori in sequenza; 2 = colori ’a blocchi’; 3 = randomcolore bordo: 2; 1 = bordo grigio


; 2 = stesso colore della formadecimali: 6sovrapposto: 1; 1 = si disegna solo l’ultima iterazione; 2 = si sovrappongono le iterazioni

;=== PROGRAMMA ===

stringa da cambiare: copy first select forme forma scelta; la stringa di comandi tikzpunti iniziali: copy next select forme forma scelta; i punti della forma sceltatrasformazioni: copy select ifs ifs scelto; l’ifs sceltopunti: copy reduce [punti iniziali]; copiamo i punti iniziali per non perderli

for livello 1 livello max 1 [; punti calcolati precedentementepunti livello: pick punti livellotemp punti: copy [ ]; calcoliamo l’immagine dei punti tramite l’ifsforeach trasformazione trasformazioni [

foreach punto punti livello [append temp punti reduce [

trasforma trasformazione punto]

]]append punti reduce [temp punti]

]

; stringa iniziale del TeXstringa tex: copy ‘\tikzset{

shape/.style={draw= bcolore ,ultra thin,fill=#1!80

}}\definecolor{col01}{rgb}{1.0,0.0,0.0};\definecolor{col02}{rgb}{0.0,1.0,0.0};\definecolor{col03}{rgb}{0.0,0.0,1.0};\definecolor{col04}{rgb}{0.0,1.0,1.0};\definecolor{col05}{rgb}{1.0,0.0,1.0};\definecolor{col06}{rgb}{1.0,1.0,0.0};\definecolor{col07}{rgb}{0.5,0.2,0.3};


\definecolor{col08}{rgb}{0.2,0.5,0.3};\definecolor{col09}{rgb}{0.5,0.3,0.2};\definecolor{col10}{rgb}{0.3,0.5,0.2};\definecolor{col11}{rgb}{0.2,0.3,0.5};\definecolor{col12}{rgb}{0.3,0.2,0.5};\definecolor{col13}{rgb}{0.6,0.3,0.1};\definecolor{col14}{rgb}{0.1,0.3,0.6};\definecolor{col15}{rgb}{0.3,0.1,0.6};’

; lista dei colori possibili (vedere sopra)colori: [

‘col01’ ‘col02’ ‘col03’ ‘col04’ ‘col05’‘col06’ ‘col07’ ‘col08’ ‘col09’ ‘col10’‘col11’ ‘col12’ ‘col13’ ‘col14’ ‘col15’

]

; quante sono le contrazioni dell’ifs?num trasform: length? trasformazioni; e quanti i punti della forma?max interno: length? punti iniziali

; stabiliamo come colorare il bordobordo colore: pick colori bordo colore bordoreplace/all stringa tex ‘ bcolore ’ bordo colore

; o solo l’ultima, o tutte le iterazionieither (sovrapposto = 1) [

min sovrapposti: 1][

min sovrapposti: livello max + 1]

; ciclo esterno (ne servono due per la colorazione)for sovrapposti min sovrapposti (livello max + 1) 1 [

; scegliamo l’insieme delle forme da disegnarepunti disegno: copy (pick punti sovrapposti); quante sono le forme (non i punti)?max esterno: (length? punti disegno) / max interno; divisione in parti (per la colorazione)parti: max esterno / num trasform

for esterno 1 max esterno 1 [; o colori in sequenza, o a blocchi, o random...switch tipo [

1 [colore: 1 + (mod (esterno - 1) num trasform)]2 [colore: 1 + to-integer ((esterno - 1) / parti)]3 [colore: random num trasform]


]; ...ma sempre tra 1 e 15colore: 1 + (mod (colore - 1) 15); copiamo la stringa tikztempor stringa: copy stringa da cambiare; cambiamo il colore con quello calcolato soprapunto colore: pick colori colorereplace/all tempor stringa ‘ colore ’ punto colore; sostituiamo ’ pi ’ con le coordinate con i decimali giustifor interno 1 max interno 1 [

nome punto: rejoin [‘ p’ interno ‘ ’]posizione: interno + ((esterno - 1) * max interno)punto: pick punti disegno posizionecoord punto: scrive vettore punto decimalireplace/all tempor stringa nome punto coord punto

]; scriviamo la stringa in coda al TeXappend stringa tex tempor stringa

]]

nome file: rejoin [‘IFSS/’ifs scelto‘-’forma scelta‘-’livello max‘-’tipo‘.tex’

]

; pronto per l’input!write to-file nome file stringa tex

Il prossimo programma disegna invece n punti di un IFS con probabilita. Inquesto caso, le matrici delle contrazioni hanno un parametro in piu; per , sihanno ad esempio tre contrazioni con probabilita 33, 66 e 100: il che vuol direche la prima contrazione sara scelta 33 volte su 100, la seconda 66− 33 = 33volte su 100, e la terza 100 − 66 = 34 volte su 100. Per determinare qualecontrazione scegliere, si costruisce la seguente funzione (nel caso di ):

G(x) = χ[1,33](x) + 2χ[34,66](x) + 3χ[67,100](x) ,

e si estrae un numero casuale x tra 1 e 100: G(x) assume cosı il valore 1, 2o 3, e si usa la contrazione corrispondente. Nel programma si usa la seguente


definizione di funzione caratteristica dell’intervallo [α, β], con α e β interi:

χ[α,β](x) = [min{1,max{β − α + 1− |2x− α− β|, 0}}] ,dove come al solito [·] indica la parte intera.

1

α βα−1 β+1

Il grafico di min{1,max{β − α+ 1− |2x− α− β|, 0}}Una volta assegnate le probabilita, si tratta quindi di costruire la funzione Gcome sopra. Per farlo, si usa una delle caratteristiche interessanti del linguag-gio REBOL. Infatti, viene prima definita la funzione caratteristica (con treparametri) che non fa altro che calcolare la funzione χ[a,b](x), e successivamen-te si costruisce la stringa alfanumerica funzione_probabili che inizia conprobabile: func [ics], e prosegue concatenando stringhe della forma

1 * (caratteristica 1 33 ics),2 * (caratteristica 34 66 ics),

e cosı via. Alla fine viene eseguito il comando do funzione_probabili chenon fa altro che prendere la stringa funzione_probabili ed eseguirla comefosse un programma REBOL. Siccome la stringa e formata in modo da esse-re un corretto programma REBOL, il risultato e che viene creata la funzioneprobabile[ics], che vale 1 se ics e compreso tra 1 e 33, 2 se ics e compresotra 34 e 66, e cosı via. In altre parole, all’inizio dell’esecuzione del programmala funzione probabile non esiste, ma viene “creata” in corso d’opera a partiredai parametri probabilistici delle contrazioni dell’IFS. Una volta costruita talefunzione, il programma e molto semplice.

REBOL [‘Random IFS’]

; === FUNZIONI ===; La stessa di primatrasforma: func [

...]

; La stessa di prima


formato decimale: func [...

]

; La stessa di primascrive vettore: func [

...]

; funzione caratteristica di [alfa, beta]; vedere commenticaratteristica: func [

alfabetaics/local temp

][temp: abs ((2 * ics) - alfa - beta)temp: beta - alfa + 1 - temptemp: max 0 temptemp: min 1 tempreturn to-integer temp

]

; === IFS ===; A (2x2), B (2x1), P (1x1); [a 11 a 12 a 21 a 22 b 1 b 2 p]ifs: [

‘equisierpinski’[

[0.5 0.0 0.0 0.5 0.00 0.000 33][0.5 0.0 0.0 0.5 0.25 0.433 66][0.5 0.0 0.0 0.5 0.50 0.000 100]

]]

; === PROGRAMMA ===; dati inizialiifs scelto: ‘equisierpinski’; quanti punti disegnare?max punti: 1000; raggio del cerchio di ogni puntoraggio: 0.001

trasformazioni: select ifs ifs sceltoprobabili: copy [0]

foreach trasformazione trasformazioni [


append probabili last trasformazione]; il vettore con tutte le p i

funzione probabili: copy ‘probabile: func [ics][’for indice 1 ((length? probabili) - 1) 1 [

append funzione probabili rejoin [‘(’indice‘ * (caratteristica ’((pick probabili indice) + 1)‘ ’(pick probabili (indice + 1))‘ ics)) + ’

]]append funzione probabili ‘0]’; il prossimo comando ’crea’ la funzione ’probabile[ics]’; spiegato in precedenzado funzione probabili

; la stessa - o quasi - di primastringa tex: copy ‘\tikzset{

shape/.style={draw=gray!50,ultra thin,fill=#1

}}\definecolor{col01}{rgb}{1.0,0.0,0.0};; ...; come prima; ...\definecolor{col15}{rgb}{0.3,0.1,0.6};’

colori: [‘col01’ ‘col02’ ‘col03’ ‘col04’ ‘col05’‘col06’ ‘col07’ ‘col08’ ‘col09’ ‘col10’‘col11’ ‘col12’ ‘col13’ ‘col14’ ‘col15’

]

; il programma vero e proprio, molto semplice; parte da un punto P 0, sceglie una trasformazione random; calcola P 1 e lo aggiunge alla lista dei punti da disegnare; definisce P 0 = P 1 e riparte; si ferma dopo max punti iterazionipunto iniziale: [0 0]for contatore 1 max punti 1 [


mappa scelta: probabile (random 100)mappa random: pick trasformazioni mappa sceltanuovo punto: trasforma mappa random punto inizialeappend stringa tex rejoin [

‘\draw [shape=’(pick colori (1 + (mod (mappa scelta - 1) 15)))‘] ’(scrivi vettore nuovo punto 5)‘ circle (’(formato decimale raggio 4)‘);^/’

]punto iniziale: nuovo punto

]

nome file: rejoin [ifs scelto‘-’max punti‘.tex’

]

write rejoin [%Random IFSS/ nome file] stringa tex

Indice analitico

δ-ricoprimento, 56K(X), 21σ-algebra, 59REBOL, 83tikz, 81

attrattore di un IFS, 42

calcolo della dimensione box counting diIFS, 70

calcolo della dimensione di Hausdorff diIFS, 76

caratterizzazione dei compatti, 19caratterizzazione dei limiti in (K(X), h),

31compattezza, 19completezza, 15completezza di (K(X), h), 28confronto fra dimensione di Hausdorff e

dimensione box counting, 66continuita e compattezza, 20contrazione, 15contrazioni su (K(X), h), 34convergenza in (X, d), 11curva di von Koch, 45

diametro di un insieme, 55dilatazione, 25dimensione box counting, 65

dimensione box counting di , 65dimensione di Hausdorff, 61distanza, 9distanza da un punto, 12, 21distanza di Hausdorff, 23distanza di Hausdorff e convergenza, 26distanza di Hausdorff e dilatazioni, 25distanza orientata, 23

disuguaglianza triangolare, 9

estensione di sottosuccessioni, 27

fattore di contrazione, 15funzione continua, 12funzione gamma, 56funzione lipschitziana, 12funzioni da K(X) in se, 33

IFS del quadrato, 40IFS della curva di von Koch, 45IFS della diagonale, 35

IFS di , 38IFS di un albero, 49insieme aperto, 10insieme autosimilare, 43insieme chiuso, 10insieme invariante, 34insieme limitato, 10insieme misurabile, 59insiemi chiusi e convergenza, 11insiemi chiusi in spazi completi, 15iterata n-sima, 16

metrica discreta, 9metrica euclidea, 9misura, 59misura di Hausdorff, 57misura esterna, 59

punto fisso, 15

sfera aperta, 10sfera chiusa, 10similitudine, 70sistema di funzioni iterate (IFS), 41

95

96 INDICE ANALITICO

sistema di funzioni iterate conprobabilita, 52

spazio metrico, 9stima dal basso della dimensione di

Hausdorff, 73successione di Cauchy, 13suddivisione di una misura, 75

teorema del Collage, 44teorema delle contrazioni, 16teorema di Weierstrass, 21totale limitatezza, 19triangolo di Sierpinski, 40

unicita del limite, 11

Teorema delle contrazioni e sistemi di funzioni iterate · 2011-04-11 · Il teorema delle...

Documents

Transcript of Teorema delle contrazioni e sistemi di funzioni iterate · 2011-04-11 · Il teorema delle...