1

Università degli Studi di L’Aquila Scuola di Specializzazione all’insegnamento

Secondario

Appunti del corso di

Didattica e fondamenti

dell’Analisi

Docente  A cura di
Prof. Francesco Leonetti  Cinzia Caniglia

Milena Cristiano Hilenia De Titta Lucia Di Biase Lucia Santarelli

Anno Accademico 2002-2003

DIMENSIONE BOX-COUNTING DI UN INSIEME

Consideriamo A ⊂ ℝ^{2}. Supponiamo, ad esempio, che A sia un segmento lungo 1 metro.

Quanti quadratini di lato δ = 10 cm= 0, 1 m occorrono per coprire A ?

La risposta è 10.

Quanti quadratini, questa volta di lato δ = 1 cm= 0, 01 m, mi occorrono per coprire A?

La risposta è 100. Se, in generale, indichiamo con N_{δ}(A) il numero di quadratini necessario per coprire il sottinsieme di ℝ^{2} considerato allora: nel primo caso: N_{δ}(A) = 10 = \frac{1}{\frac{1}{10}} = \frac{1}{δ} = (\frac{1}{δ})^{1}

nel secondo caso: N_{δ}(A) = 100 = \frac{1}{\frac{1}{100}} = \frac{1}{δ} = (\frac{1}{δ})^{1}.

Adesso supponiamo che A sia un quadrato di lato 1 metro.

Quanti quadratini di lato δ = 10 cm= 0, 1 m mi occorrono per coprire A?

La risposta è 100 = 10^{2}.

Quanti quadratini, questa volta di lato δ = 1 cm = 0, 01 m , mi occorrono per coprire A?

La risposta è 10000 = 100^{2}. Quindi: nel primo caso: N_{δ}(A) = 100 = \frac{1}{\frac{1}{100}} = \frac{1}{(\frac{1}{10})2} = \frac{1}{(0, 1)^{2}} =

\frac{1}{(δ)^{2}} = (\frac{1}{δ})^{2}

nel secondo caso: N_{δ}(A) = 10000 = 100^{2} = \frac{1}{(\frac{1}{100})2} =

\frac{1}{(0, 01)^{2}} = \frac{1}{(δ)^{2}} = (\frac{1}{δ})^{2}.

Possiamo osservare che nel caso del segmento N_{δ}(A) è uguale a 1 fratto il lato del quadratino elevato ad uno, mentre nel caso del quadrato N_{δ}(A) è uguale a 1 fratto il lato del quadratino elevato a due. Dall’ultimo esempio considerato esplicitiamo l’esponente:

N_{δ}(A) = (\frac{1}{δ})^{2}

Applicando il logaritmo in base e, che indichiamo con ”log”:

logN_{δ}(A) = log [(\frac{1}{δ})^{2}]

logN_{δ}(A) = 2 ∗ log (\frac{1}{δ})

da cui

2 = \frac{logN_{δ}(A)}{log (\frac{1}{δ})}

A questo punto possiamo dare la seguente definizione.

Definizione 1 ∀δ > 0 definiamo la reticolazione di ℝ^{2}

Q_{hk} = [hδ, (h + 1)δ] × [kδ, (k + 1)δ]

con h ∈ ℤ, k ∈ ℤ.

Definizione 2 Dato A ⊂ ℝ^{2} indichiamo con N_{δ}(A) il numero di δ -quadrati coordinati Q che intersecano A, cioé per cui Q ∩ A ≠ ∅

Ad esempio, se A é l’insieme rappresentato nella figura il numero di quadratini che contiene almeno un punto di A é 22.

Osservazione 1 Se A ⊂ ℝ^{2} limitato e non vuoto allora ∀δ > 0

1 ≤ N_{δ}(A) < +∞

Infatti: A non vuoto⇒ ∃x ∈ A : ⋃ Q = ℝ^{2} ∋ x ⇒ ∃Q̃ : Q̃ ∋ x ⇒ Q̃ ⋂ A ≠ ∅ A limitato⇒il numero di quadratini che intersecano A in almeno un punto é finito.

Definizione 3 Sia A ⊂ ℝ^{2} limitato e non vuoto. Se esiste

lim_{δ→0^{+}} \frac{log(N_{δ}(A))}{log (\frac{1}{δ})}

esso, per definizione, é la DIMENSIONE BOX-COUNTING di A.

Indicheremo la dimensione box-counting di un insieme A con ”dim_{B}(A)”.

Esempio 1

A = {(0, 0)}

Troviamo la dim_{B}(A). ∀δ ∈ (0, 1) si ha N_{δ}(A) = 4 quindi:

dim_{B}(A) = lim_{δ→0^{+}} \frac{log(N_{δ}(A))}{log (\frac{1}{δ})} = lim_{δ→0^{+}} \frac{log(4)}{log (\frac{1}{δ})} = 0

A = {[0, L] × {0}}

Troviamo la dim_{B}(A). ∀δ ∈ (0, 1) si distinguono i seguenti due casi.

1^{∘} CASO: nella reticolazione L cade esattamente all’estremità di un quadratino, cioé L é multplo di δ.

In tal caso ∃m ∈ ℤ tale che:

L = mδ ⇒ m = \frac{L}{δ}

Quindi:

N_{δ}(A) = (m + 2)2 = (\frac{L}{δ} + 2) 2 = ([\frac{L}{δ}] + 2) 2

dove con [\frac{L}{δ}] indichiamo la parte intera di \frac{L}{δ}. 2^{∘} CASO: nella reticolazione L non cade esattamente all’estremità di un quadratino, cioé L non é multplo di δ.

In tal caso ∃n ∈ ℤ tale che:

nδ < L < (n + 1)δ

n < \frac{L}{δ} < n + 1

Quindi:

N_{δ}(A) = (n + 2)2 = ([\frac{L}{δ}] + 2) 2

Quindi in entrambi i casi ∀δ > 0 si ha N_{δ}(A) = 2 ([\frac{L}{δ}] + 2).

Ricordando che la parte intera soddisfa la seguente disuguaglianza:

[\frac{L}{δ}] ≤ \frac{L}{δ} < [\frac{L}{δ}] + 1

si ha:

[\frac{L}{δ}] + 2 ≤ \frac{L}{δ} + 2

e

\frac{L}{δ} + 1 < [\frac{L}{δ}] + 2

Quindi ∀δ con 0 < δ < 1:

\frac{2L}{δ} < 2 (\frac{L}{δ} + 1) < N_{δ}(A) ≤ 2 (\frac{L}{δ} + 2) < 2 (\frac{L}{δ} + \frac{2}{δ}) = \frac{2L + 4}{δ}

da cui, applicando il logaritmo in base e:

log (\frac{2L}{δ}) < logN_{δ}(A) < log (\frac{2L + 4}{δ})

Applicando le proprietà dei logaritmi:

log(2L)+log (\frac{1}{δ}) < logN_{δ}(A) < log(2L+4)+log (\frac{1}{δ})

dividendo per log (\frac{1}{δ}):

\frac{log(2L)}{log (\frac{1}{δ})} + 1 < \frac{logN_{δ}(A)}{log (\frac{1}{δ})} < \frac{log(2L + 4)}{log (\frac{1}{δ})} + 1

Poiché:

lim_{δ→0^{+}} (\frac{log(2L)}{log (\frac{1}{δ})} + 1) = 1

e

lim_{δ→0^{+}} (\frac{log(2L + 4)}{log (\frac{1}{δ})} + 1) = 1

Per il Teorema dei due carabinieri (o del confronto) abbiamo che anche:

lim_{δ→0^{+}} \frac{logN_{δ}(A)}{log (\frac{1}{δ})} = 1

Quindi:

dim_{B}(A) = lim_{δ→0^{+}} \frac{logN_{δ}(A)}{log (\frac{1}{δ})} = 1

A = [O, L] × [O, L]

Troviamo la dim_{B}(A). ∀δ ∈ (0, 1) si distinguono i seguenti due casi.

1^{∘} CASO: nella reticolazione L cade esattamente all’estremità di un quadratino, cioé L é multplo di δ.

In tal caso:

L = mδ ⇒ m = \frac{L}{δ}

Quindi:

N_{δ}(A) = (m + 2)^{2} = (\frac{L}{δ} + 2)^{2} = ([\frac{L}{δ}] + 2)^{2}

2^{∘} CASO: nella reticolazione L non cade esattamente all’estremità di un quadratino, cioé L non é multplo di δ.

In tal caso ∃n ∈ ℤ tale che:

nδ < L < (n + 1)δ

n < \frac{L}{δ} < n + 1

Quindi:

N_{δ}(A) = (n + 2)^{2} = ([\frac{L}{δ}] + 2)^{2}

Quindi in entrambi i casi ∀δ > 0 si ha N_{δ}(A) = ([\frac{L}{δ}] + 2)^{2}. Utilizzando la disuguaglianza dell parte intera ricordata nell’esempio 2, ∀δ con 0 < δ < 1 otteniamo:

\frac{L}{δ} < \frac{L}{δ} + 1 < [\frac{L}{δ}] + 2 < \frac{L}{δ} + \frac{2}{δ}

\frac{L}{δ} < [\frac{L}{δ}] + 2 < \frac{L + 2}{δ}

(\frac{L}{δ})^{2} < ([\frac{L}{δ}] + 2)^{2} < (\frac{L + 2}{δ})^{2}

da cui, applicando il logaritmo in base e, otteniamo:

log (\frac{L}{δ})^{2} < log ([\frac{L}{δ}] + 2)^{2} < log (\frac{L + 2}{δ})^{2}

Applicando le proprietà dei logaritmi:

logL^{2}+log(\frac{1}{δ})^{2} < log ([\frac{L}{δ}] + 2)^{2} < log(L + 2)^{2}+log(\frac{1}{δ})^{2}

logL^{2}+2log(\frac{1}{δ}) < log ([\frac{L}{δ}] + 2)^{2} < log(L + 2)^{2}+2log(\frac{1}{δ})

logL^{2}+2log(\frac{1}{δ}) < logN_{δ}(A) < log(L + 2)^{2}+2log(\frac{1}{δ})

Dividendo tutti i membri per log(\frac{1}{δ}) si ha:

\frac{logL^{2}}{log(\frac{1}{δ})} + 2 < \frac{logN_{δ}(A)}{log(\frac{1}{δ})} < \frac{log(L + 2)^{2}}{log(\frac{1}{δ})} + 2

Dato che:

lim_{δ→0^{+}} (\frac{logL^{2}}{log(\frac{1}{δ})} + 2) = 2

e

lim_{δ→0^{+}} (\frac{log(L + 2)^{2}}{log(\frac{1}{δ})} + 2) = 2

Per il Teorema dei due carabinieri (o del confronto) abbiamo che anche:

lim_{δ→0^{+}} \frac{logN_{δ}(A)}{log (\frac{1}{δ})} = 2

Quindi:

dim_{B}(A) = lim_{δ→0^{+}} \frac{logN_{δ}(A)}{log (\frac{1}{δ})} = 2

DIMENSIONE BOX-COUNTING DELL’INSIEME DI CANTOR Consideriamo un insieme A ⊂ ℝ^{2} la cui dimensione box-counting non è intera. Dato L > 0 consideriamo i seguenti insiemi:

Indichiamo con -E_{0} = ⋃_{i=1}^{1=4^{0}} Q_{i}^{0} dove Q_{i}^{0} per i = 1 é un quadrato chiuso di lato L = \frac{L}{3^{0}} -E_{1} = ⋃_{i=1}^{4=4^{1}} Q_{i}^{1} dove Q_{i}^{1} per i = 1, ..., 4 sono quadrati chiusi di lato \frac{L}{3}=\frac{L}{3^{1}} -E_{2} = ⋃_{i=1}^{16=4^{2}} Q_{i}^{2} dove Q_{i}^{2} per i = 1, ..., 16 sono quadrati chiusi di lato \frac{L}{9}=\frac{L}{3^{2}} ⋯ ⋯ ⋯ in generale al passo j -E_{j} = ⋃_{i=1}^{4^{j}} Q_{i}^{j} dove Q_{i}^{j} per i = 1, .., 4^{j} sono quadrati chiusi di lato \frac{L}{3^{j}} ottenuti a partire dai vertici dei quadrati del passo j-1. In tal modo si ottiene una successione decrescente di inisiemi compatti: E_{0} ⊃ E_{1} ⊃ E_{2} ⊃ E_{3} ⊃ .... ⊃ E_{j} ⊃ E_{j+1} ⊃ ...

Definizione 4 Costruita la successione E_{0}, E_{1}, E_{2}, E_{3}, ...., E_{j}, E_{j+1}, .... si definisce insieme di Cantor, l’insieme

A = ⋂_{n=0}^{+∞} E_{n}

Indichiamo con -V^{0} l’insieme contenente i vertici del quadrato Q_{i}^{0} per i=1, la cui cardinalità é 4 = 4 · 4^{0} -V^{1} l’insieme contenente i vertici dei quadrati Q_{i}^{1} per i=1,...,4, la cui cardinalità é 16 = 4 · 4^{1} -V^{2} l’insieme contenente i vertici dei quadrati Q_{i}^{2} per i=1,...,16, la cui cardinalità é 64 = 4 · 4^{2} ⋯ in generale al passo j -V^{j} l’insieme contenente i vertici dei quadrati Q_{i}^{j}, per i = 1, ..., 4^{j}, la cui cardinalità é 4 · 4^{j}

Osservazione 2 Osserviamo che ∀j, V^{j} ⊂ E_{s} ∀s ∈ {0, 1, ..., j} e che V^{j} ⊂ E_{r} ∀r > s, quindi ∀j V^{j} ⊂ E_{n} ∀n ≥ 0. Pertanto V^{j} ⊂ ⋂_{n=0}^{+∞} E_{n} = A.

Osservazione 3 Se a, b ∈ V^{j} con a ≠ b allora ∥ a−b ∥≥ \frac{L}{3^{j}}, ossia la distanza tra due vertici é maggiore o uguale del lato del quadratino.

Dato δ ∈ (0, \frac{L}{3}] allora ∃! j ≥ 1 tale che δ ∈ (\frac{L}{3^{j}+1}, \frac{L}{3^{j}} ].

Essendo δ ∈ (\frac{L}{3^{j}+1}, \frac{L}{3^{j}} ] possiamo scrivere:

\frac{L}{3^{j+1}} < δ ≤ \frac{L}{3^{j}}

dividendo tutto per L si ha:

\frac{1}{3^{j+1}} < \frac{δ}{L} ≤ \frac{1}{3^{j}}

capovolgendo le frazioni si ha:

3^{j+1} > \frac{L}{δ} ≥ 3^{j}

passando ai logaritmi si ottiene:

log3^{j+1} > log (\frac{L}{δ}) ≥ log3^{j}

applicando le proprietà dei logaritmi

(j + 1) log3 > log (\frac{L}{δ}) ≥ jlog3

e dividendo tutti i membri per log3 si ha:

j + 1 > \frac{log\frac{L}{δ}}{log3} ≥ j

Dato che \frac{L}{3^{j+1}} < δ ≤ \frac{L}{3^{j}} possiamo stimare N_{δ}(A) sapendo che V^{j−1} ⊂ A.

Indicando con F la famiglia contenente tutti i δ − quadratini che intersecano A almeno in un punto, risulta ⋃_{p∈F} P ⊃ A ⊃ V^{j−1}. Quindi ∀a ∈ V^{j−1} ∃P ∈ F : a ∈ P. Sia v ∈ V^{j−1} con v ≠ a, allora ∥ v − a ∥≥ \frac{L}{3^{j−1}}.

Se per assurdo v ∈ P, allora ∥ v − a ∥≤ \sqrt{2} · δ ≤ \sqrt{2} · \frac{L}{3^{j}} < 3 · \frac{L}{3^{j}} = \frac{L}{3^{j−1}} ≤∥ v − a ∥, quindi v ∉ P.

Riepilogando: ∀a ∈ V^{j−1} ∃P ∈ F : a ∈ P e ∀v ∈ V^{j−1} con v ≠ a risulta v ∉ P. Di conseguenza N_{δ}(A) = #F ≥ #V^{j−1} = 4 · 4^{j−1} = 4^{j}. Abbiamo pertanto una stima dal basso di N_{δ}(A):

4^{j} ≤ N_{δ}(A)

Determiniamo adesso una stima dall’alto di N_{δ}(A)

Sia Q_{i}^{j} = [x_{0}, x_{0} + \frac{L}{3^{j}}] × [y_{0}, y_{0} + \frac{L}{3^{j}}].

Si possono avere 4 casi:

I caso) il vertice (x_{0}, y_{0}) del quadrato coincide con la reticolazione sia lungo la direzione delle x sia lungo la direzione delle y

II caso) il vertice (x_{0}, y_{0}) del quadrato coincide con la reticolazione lungo la direzione delle x III caso) il vertice (x_{0}, y_{0}) del quadrato coincide con la reticolazione lungo la direzione delle y

IV caso) il vertice (x_{0}, y_{0}) del quadrato non coincide con la reticolazione in nessuna delle due direzioni

In tutti questi 4 casi si ha N_{δ}(Q_{i}^{j}) ≤ 16. Dato che per definizione A = ⋂_{j=0}^{+∞} E_{n} allora A ⊂ E_{n} ∀n, in particolare A ⊂ E_{j} = ⋃_{i=1}^{4^{j}} Q_{i}^{j}. Pertanto

N_{δ}(A) ≤ N_{δ}(E_{j}) ≤ ∑_{i=1}^{4^{j}} N_{δ}(Q_{i}^{j}) ≤ ∑_{i=1}^{4^{j}} 16 = 16 · 4^{j}

Concludendo abbiamo visto che: ∀δ ∈ (0, \frac{L}{3}] ∃! j ≥ 1 tale che \frac{L}{3^{j+1}} < δ ≤ \frac{L}{3^{j}} e che per tale j vale la stima

4^{j} ≤ N_{δ}(A) ≤ 16 · 4^{j}.

Dalla relazione

j + 1 > \frac{log\frac{L}{δ}}{log3} ≥ j

si ha

4^{j+1} > 4^{\frac{log \frac{L}{δ}}{log3}} ≥ 4^{j}.

Tenendo conto che

4^{\frac{log \frac{L}{δ}}{log3}} = e^{log(4^{\frac{log \frac{L}{δ}}{log3}} )} = e^{\frac{log \frac{L}{δ}}{log3} ·log4} = e^{log \frac{L}{δ}·\frac{log4}{log3}} = (e^{log \frac{L}{δ}})^{\frac{log4}{log3}} = (\frac{L}{δ})^{\frac{log4}{log3}} = (\frac{L}{δ})^{d}

dove

d = \frac{log4}{log3}

e che 4^{j} ≤ \frac{L^{d}}{δ^{d}} e 4^{j} > \frac{1}{4} · \frac{L^{d}}{δ^{d}} risulta:

\frac{1}{4} · \frac{L^{d}}{δ^{d}} < 4^{j} ≤ \frac{L^{d}}{δ^{d}}.

Pertanto ∀δ ∈ (0, \frac{L}{3}] si ha:

\frac{1}{4} · \frac{L^{d}}{δ^{d}} < N_{δ}(A) ≤ 16 · \frac{L^{d}}{δ^{d}}

passando ai logaritmi

log (\frac{1}{4} · \frac{L^{d}}{δ^{d}}) < logN_{δ}(A) ≤ log (16 · \frac{L^{d}}{δ^{d}})

e applicando le proprietà

log (\frac{L^{d}}{4})+log (\frac{1}{δ^{d}}) < logN_{δ}(A) ≤ log (16 · Ł^{d})+log (\frac{1}{δ^{d}}) .

Dato che ∀δ t.c. 0 < δ < min\{1, \frac{L}{3}\} risulta log (\frac{1}{δ}) > 0 dividendo per log (\frac{1}{δ}) si ha:

\frac{log(\frac{L^{d}}{4})}{log (\frac{1}{δ})}+\frac{d · log (\frac{1}{δ})}{log (\frac{1}{δ})} < \frac{logN_{δ}(A)}{log (\frac{1}{δ})} ≤ \frac{log(16L^{d})}{log (\frac{1}{δ})}+\frac{d · log (\frac{1}{δ})}{log (\frac{1}{δ})}

da cui

\frac{log(\frac{L^{d}}{4})}{log (\frac{1}{δ})} + d < \frac{logN_{δ}(A)}{log (\frac{1}{δ})} ≤ \frac{log(16L^{d})}{log (\frac{1}{δ})} + d

Poiché:

lim_{δ→0^{+}} log (\frac{1}{δ}) = +∞

allora si ha

lim_{δ→0^{+}} \frac{log(\frac{L^{d}}{4})}{log (\frac{1}{δ})} = 0

e analogamente

lim_{δ→0^{+}} \frac{log(16L^{d})}{log (\frac{1}{δ})} = 0

Per il Teorema dei carabinieri abbiamo che:

lim_{δ→0^{+}} \frac{logN_{δ}(A)}{log (\frac{1}{δ})} = d = \frac{log4}{log3}

Quindi:

dim_{B}(A) = lim_{δ→0^{+}} \frac{logN_{δ}(A)}{log (\frac{1}{δ})} = \frac{log4}{log3}

Vediamo, ora, un altro modo per costruire A, dove per A intendiamo l’insieme di Cantor in ℝ^{2} definito come:

A = ⋂_{n=1}^{+∞} E_{n}

Applicando una omotetia di centro 0 (origine degli assi) e fattore \frac{1}{3}, possiamo trasformare E_{0} in E_{1}, dove E_{0} è il quadrato di lato L ed E_{1} è l’insieme dei quattro quadratini riportati nella seguente figura:

Mostreremo, ora, come questa trasformazione sia possibile.

a) Sia

w_{1} : ℝ^{2} ⟶ ℝ^{2}

υ ⟶ \frac{1}{3}υ

ossia, w_{1} è l’applicazione che consente di ridurre di un fattore \frac{1}{3} la lunghezza del quadrato E_{0} e di ottenere in tal modo uno dei quattro quadratini di E_{1}, il numero 1 (in basso a sinistra, di lato \frac{L}{3} e con un vertice nell’origine).

b) Per avere il secondo quadratino di E_{1} (il numero 2) facciamo, come prima, un’omotetia di centro 0 e fattore \frac{1}{3} e poi trasliamo orizzontalmente il quadratino ottenuto di \frac{2}{3}L. Ossia, prima effettuiamo il rimpicciolimento di E_{0} e poi la traslazione di:

a = (\frac{2}{3}L, 0)

Ossia, essendo tale traslazione t_{a}:

t_{a} : ℝ^{2} ⟶ ℝ^{2}
υ ⟶ υ + a

possiamo definire w_{2} come la seguente composizione di funzioni:

w_{2} = t_{a} ∘ w_{1} : ℝ^{2} ⟶ ℝ^{2}

c) Ora vogliamo ottenere il quadratino numero 4 di E_{1}; applichiamo lo stesso tipo di omotetia come prima e poi trasliamo verticalmente di

b = (0, \frac{2}{3}L)

Chiamando tale traslazione verticale con:

t_{b} : ℝ^{2} ⟶ ℝ^{2}

υ ⟶ υ + b

possiamo esprimere, allora, w_{3} nel seguente modo:

w_{3} = t_{b} ∘ w_{1} : ℝ^{2} ⟶ ℝ^{2}

d) Ora vogliamo ottenere il quadratino numero 3 di E_{1}. Allora, facciamo prima la solita omotetia, poi la traslazione orizzontale di \frac{2}{3}L e poi la traslazione verticale di \frac{2}{3}L.

w_{4} = t_{b} ∘ t_{a} ∘ w_{1} : ℝ^{2} ⟶ ℝ^{2} Ricapitolando, per passare da E_{0} a E_{1} abbiamo usato quattro trasformazioni:

w_{1}(x, y) = (\frac{1}{3}x, \frac{1}{3}y)

w_{2}(x, y) = (\frac{1}{3}x + \frac{2}{3}L, \frac{1}{3}y)

w_{3}(x, y) = (\frac{1}{3}x, \frac{1}{3}y + \frac{2}{3}L)

w_{4}(x, y) = (\frac{1}{3}x + \frac{2}{3}L, \frac{1}{3}y + \frac{2}{3}L)

w_{i} : ℝ^{2} ⟶ ℝ^{2}

Risulta, dunque, che E_{1} è la l’unione insiemistica dei quattro quadratini:

E_{1} = w_{1}(E_{0}) ∪ w_{2}(E_{0}) ∪ w_{3}(E_{0}) ∪ w_{4}(E_{0}) = ⋃_{i=1}^{4} w_{i}(E_{0})

A questo punto, introduciamo un operatore W che prenda una figura di ℝ^{2}, cioè un sottoinsieme di ℝ^{2}, e ad esso associ un altro sottoinsieme di ℝ^{2}:

W : ℘(ℝ^{2}) ⟶ ℘(ℝ^{2})

dove ℘(ℝ^{2}) rappresenta tutta la famiglia di tutti i sottoinsiemi di ℝ^{2}.

W prende, dunque, l’insieme B e gli associa la seguente unione insiemistica:

W (B) ⟶ w_{1}(B) ∪ w_{2}(B) ∪ w_{3}(B) ∪ w_{4}(B)

E_{1} è, dunque, il trasformato di E_{0} tramite W, ossia:

E_{1} = W (E_{0})

Mi chiedo, ora, se E_{2} sia il trasformato di E_{1} tramite W, cioè se

E_{2} = W (E_{1})

Dalla seguente figura si vede che applicando W ad E_{1} si ottiene proprio E_{2}:

Applicando, ora, W ad E_{2} si ottiene E_{3}:

Ricapitolando:

E_{0}
E_{1} = W (E_{0})
E_{2} = W (E_{1})
E_{3} = W (E_{2})
E_{n+1} = W (E_{n})

Si genera, dunque, una procedura di induzione; assegnato il primo insieme, stabiliamo la trasformazione W e così possiamo ottenere per induzione tutti gli E_{j}: possiamo far partire un ciclo di iterazioni.

È possibile effettuare simulazioni sul Pc ed osservare che da qualsiasi figura partiamo, applicando ripetutamente W, arriviamo sempre alla stessa figura finale che resta inalterata sotto l’azione di W; vale a dire che sia che partiamo, per esempio, da un rettangolo, che da una circonferenza, che da un triangolo, che da un segmento o da un punto, arriviamo sempre alla stessa figura finale. Dunque, per ogni B ⊂ ℝ^{2} B_{0} = B B_{n+1} = W (B_{n}) Per qualunqua scelta di B le simulazioni mostrano che B_{n} ⟶ B_{∞} dove il limite B_{∞} è sempre la stessa figura B̃. Per spiegare come B̃ possa essere sempre la stessa ci viene in aiuto il seguente teorema.

Teorema 1 (delle contrazioni) Sia (X, d) uno SPAZIO METICO COMPLETO. Sia G : X ⟶ X una CONTRAZIONE allora,

∃! x̄ ∈ X : G(x̄) = x̄

Inoltre:

∀ x_{0} ∈ X

sia y_{n} una successione così definita:

\{ \begin{matrix}y_{0} = x_{0} \\ y_{n+1} = G(y_{n}) \end{matrix}

Allora y_{n} ⟶ x̄.

Il teorema ci dice, dunque, che esiste un punto (ed è unico) dell’insieme in considerazione, che non è alterato dall’azione di G. Il teorema dice inoltre che si viene a generare una successione di punti di X convergente esattamente al punto unico con la proprietà di sopra. La simulazione descritta prima sul Pc ha forte analogia con questo teorema. In input avevamo una figura a piacere, in output, dopo un certo numero di iterazioni, trovavamo sempre la stessa figura finale. La risposta alla simulazione vista è proprio nel teorema delle contrazioni. Facciamo vedere che è così, cioè che G del teorema è la W della simulazione. X è un insieme, su esso è possibile dire quanto distano gli elementi, vale a dire che in esso è definita una metrica d:

d : X × X ⟶ ℝ
d(x, y) ≥ 0
d(x, y) = 0 ⟺ x = y
d(x, y) = d(y, x)

Il risultato della misura non dipende da quale elemento prendo per primo.

d(x, y) ≤ d(x, z) + d(z, y)

Tale relazione è la disuguaglianza triangolare. ESEMPI DI SPAZI METRICI Esempio 1 X = ℝ insieme dei numeri reali

d(x, y) = |x − y| d(2, 5) = |2 − 5| = 3 Esempio 2 X = Q = \{\frac{m}{n}; m ∈ Z, n ∈ Z, n ≠ 0\} Q è un sottoinsieme di ℝ

d(x, y) = |x − y|

Q con la metrica euclidea è ancora uno spazio metrico. A tale retta mancano tutti gli irrazionali che sono tantissimi. Se andiamo a zoommare sulla retta, vedremo ancora un tratto con tanti buchi, non riusciamo a vedere un tratto pieno.

Esempio 3 X = ℝ^{2} d(a, b) = \sqrt{(a_{1} − b_{1})^{2} + (a_{2} − b_{2})^{2}}

Esempio 4 X = {f : [a, b] ⟶ ℝ continua} d(f, g) distanza tra due funzioni.

Si prende un t dell’intervallo, e si individua, in tal modo un segmento verticale; poi si prende t_{1} e cosi via si ripete mantenendo sempre il segmento più lungo.

d(f, g) = sup_{t∈[a,b]} |f(t) − g(t)|

Definizione 5 Uno spazio metrico (X, d) è completo se ∀{y_{n}} ⊂ X, con {y_{n}} successione di Cauchy, ∃x̄ ∈ X : y_{n} → x̄ (ossia ogni successione di Cauchy in X converge).

Esempi

• (ℝ, d), dove, per x, y ∈ ℝ, d(x, y) = |x − y|, è completo;

• (ℚ, d), dove d(x, y) = |x − y|, non è completo;

• (ℝ^{2}, d), dove, per x = (x_{1}, x_{2}), y = (y_{1}, y_{2}) ∈ ℝ, d(x, y) = \sqrt{(x_{1} − y_{1})^{2} + (x_{2} − y_{2})^{2}}, è completo;

• (X, d), dove X = {f : [a, b] → ℝ t.c. f è una funzione continua}

e

d(f, g) = sup_{t∈[a,b]} |f(t) − g(t)|,

è completo.

Definizione 6 Sia (X, d) uno spazio metrico. Una funzione G : X → X è una contrazione se ∃α ∈ [0, 1) tale che d(G(x), G(y)) ≤ αd(x, y), ∀x, y ∈ X.

Applichiamo ora questi strumenti di analisi matematica per spiegare il motivo per cui a partire da una qualsiasi figura, applicando iterativamente W, dopo un certo numero di passi, si ottiene l’insieme di Cantor. L’idea è quella di considerare un opportuno spazio metrico completo in cui costruire una funzione che sia una contrazione e per la quale l’insieme di Cantor sia (l’unico) punto fisso.

L’insieme che consideriamo è

X = {B ⊂ ℝ^{2} : B ≠ ∅, B limitato, B chiuso},

ossia l’insieme dei compatti non vuoti di ℝ^{2}. Definiamo ora la distanza tra due elementi di X. Ricordiamo innanzitutto che per x ∈ ℝ^{2} e A ⊂ ℝ^{2}, si definisce la distanza tra x e A come segue

dist(x, A) = inf_{a∈A} dist(a, x).

Inoltre sia ε ≥ 0 e sia A ⊂ ℝ^{2}. Allora l’insieme

A_{ε} = {x ∈ ℝ^{2} : dist(x, A) ≤ ε}

è l’allargamento di A con parametro ε. Definizione 7 Siano A e B elementi di X.

d_{H}(A, B) = inf{ε ≥ 0 : A_{ε} ⊃ B, B_{ε} ⊃ A} definisce una distanza in X ed è chiamata Distanza di Hausdorff. Graficamente:

Osservazione 4 Per definire la distanza di Hausdorff è necessario che gli elementi di X siano non vuoti e limitati. Infatti esiste un allargamento di A se solo se A è non vuoto ed esso contiene B se B è limitato. Dunque, se A ≠ ∅ e B è limitato, allora ∃ε ≥ 0 : A_{ε} ⊃ B.

I seguenti risultati, di cui omettiamo la dimostrazione, costituiscono uno dei nuclei centrali del presente lavoro.

Teorema 2 Se

X = {B ⊂ ℝ^{2} : B ≠ ∅, B limitato , B chiuso }

e

d_{H}(A, B) = inf{ε ≥ 0 : A_{ε} ⊃ B, B_{ε} ⊃ A}

allora (X , d_{H}) è uno spazio metrico completo.

Teorema 3 Siano s_{i} : ℝ^{2} → ℝ^{2}, i = 1, ..., k contrazioni in (ℝ^{2}, d) (ossia ∀i = 1, ..., k ∃α_{i} ∈ [0, 1) : d_{ℝ^{2}}(s_{i}(a), s_{i}(b)) ≤ α_{i}d_{ℝ^{2}}(a, b), ∀a, b ∈ ℝ^{2}). Sia, per ogni B ⊂ ℝ^{2},

S(B) = ⋃_{i=1}^{k} s_{i}(B).

Allora S : X → X, ossia S manda compatti non vuoti in compatti non vuoti, e d_{H}(S(A), S(B)) ≤ αd_{H}(A, B), ∀A, B ∈ X, dove α = max(α_{1}, ..., α_{k}) ∈ [0, 1). In altre parole S è una contrazione in (X , d_{H}).

Corollario 1 Nelle ipotesi del Teorema 3, per il Teorema delle Contrazioni ∃!B̃ ∈ X : S(B̃) = B̃ e ∀B ∈ X, posto

\{ \begin{matrix}B_{0} = B \\ B_{n+1} = S(B_{n}) \end{matrix}

risulta

B_{n} → B̃, per n → +∞

ossia

lim_{n→+∞} d_{H}(B_{n}, B̃) = 0.

Poiché w_{1}, w_{2}, w_{3}, w_{4} sono contrazioni in (ℝ^{2}, d_{ℝ^{2}}),

W = ⋃_{i=1}^{4} w_{i}

è una contrazione nello spazio metrico completo (X , d_{H}). Dunque esiste un unico punto fisso al quale converge ogni successione di elementi di X ottenuta iterando la funzione W. Tale punto fisso è l’insieme di Cantor (in realà non lo abbiamo dimostrato!) e ciò spiega quanto avevamo ottenuto nelle simulazioni sul calcolatore.

Osservazione 5 Una funzione W costruita come sopra fa parte di una più ampia categoria di applicazioni, chiamate Iterated Function System ( IFS), che consiste nell’iterare un sistema di k funzioni che operano contemporaneamente.

APPLICAZIONI DEL TEOREMA DELLE CONTRAZIONI

Ã = W (Ã) con Ã insieme di Cantor. Esempio 4 Sia Q un quadrato di lato L.

Vogliamo determinare le contrazioni w_{i} : ℝ^{2} ⟶ ℝ^{2}, i = 1, …, k che fissano il quadrato:

w_{1}(Q) ∪ w_{2}(Q) ∪ ⋯ ∪ w_{k}(Q) = W (Q) = Q L’obiettivo è decomporre Q in tanti pezzi in modo che ciascuno sia la copia rimpicciolita di Q.

Ogni applicazione w_{i} è una contrazione perché manda Q in un quadratino piú piccolo. Per costruzione si ha che l’applicazione W, definita come segue:

W = ⋃_{1=0}^{k} w_{i},

ha Q come unico punto fisso. Calcoliamo esplicitamente le w_{i}.

w_{1}(x, y) = (\frac{1}{2}x, \frac{1}{2}y) omotetia di centro O = (0, 0) e fattore \frac{1}{2};

w_{2} = T_{(\frac{L}{2},0)} ∘ w_{1} con T_{(\frac{L}{2},0)}(x, y) = (x + \frac{L}{2}, y); w_{3} = T_{(0,\frac{L}{2})} ∘ w_{1} con T_{(0,\frac{L}{2})}(x, y) = (x, y + \frac{L}{2});

w_{4} = T_{(\frac{L}{2},\frac{L}{2})}∘w_{1} con T_{(\frac{L}{2},\frac{L}{2})}(x, y) = (x+ \frac{L}{2}, y+ \frac{L}{2}).

Esempio 5

Sia S un segmento di lunghezza L sull’asse delle x.

É possibile trovare un’applicazione W^{∗} che fissi il segmento S, cioé tale che W^{∗}(S) = S, il che é equivalente a trovare k contrazioni w_{1}^{∗}, …, w_{k}^{∗} tali che

w_{1}^{∗}(S) ∪ w_{2}^{∗}(S) ∪ ⋯ ∪ w_{k}^{∗}(S) = W^{∗}(S) = S.

Proviamo a dividere il segmento S in due parti, determinando w_{1}^{∗} e w_{2}^{∗} in modo che

w_{1}^{∗}(S) ∪ w_{2}^{∗}(S) = W^{∗}(S) = S.

w_{1}^{∗}(x, y) = (\frac{1}{2}x, \frac{1}{2}y) omotetia di centro O = (0, 0) e fattore \frac{1}{2}.

w_{2}^{∗} = T_{(\frac{L}{2},0)} ∘ w_{1}^{∗} traslazione T_{(\frac{L}{2},0)}(x, y) = (x + \frac{L}{2}, 0).

Il modo di trovare W^{∗} non è univoco: avrei potuto dividere il segmento in n parti trovando n contrazioni w_{i}^{∗}, i = 1, …, n.

Esempio 6

Consideriamo l’insieme O = (0, 0) costituito solo dal punto O.

Esistono k contrazioni w̄_{1}, …, w̄_{k} tali che

W̄ (O) = w̄_{1}(O) ∪ w̄_{2}(O) ∪ ⋯ ∪ w̄_{k}(O) = O?

Quali possono essere le contrazioni che ‘rimpiccioliscono’ il punto O? Non posso considerare l’identità perché questa non è una contrazione rispetto alla distanza di Hausdorff, d_{H}. Posso però considerare l’omotetia di centro O = (0, 0) e fattore \frac{1}{2}: essa é infatti, una contrazione che fissa il punto O.

w̃_{1}(O) = W̃ (O).

Sia T un triangolo equilatero di lato L.

Vogliamo trovare k contrazioni ˜ w̃_{1}, …, ˜ w̃_{k} : ℝ^{2} ⟶ ℝ^{2}, i = 1, …, k che lascino fisso il triangolo T:

˜w̃_{1}(T) ∪ ˜ w̃_{2}(T) ∪ ⋯ ∪ ˜ w̃_{k}(T) = ˜ W̃ (T) = T.

Consideriamo le seguenti contrazioni:

˜w̃_{1}(x, y) = (\frac{1}{2}x, \frac{1}{2}y) omotetia di centro O = (0, 0) e fattore \frac{1}{2}.

˜w̃_{2} = T_{(\frac{L}{2},0)}∘ ˜w̃_{1} con T_{(\frac{L}{2},0)}(x, y) = (x+\frac{L}{2}, 0) traslazione.

˜w̃_{3} = T_{(\frac{L}{4},\frac{\sqrt{3}}{4}L)} ∘ ˜ w̃_{1} con T_{(\frac{L}{4},\frac{\sqrt{3}}{4}L)}(x, y) = (x + \frac{L}{4}, y + \frac{\sqrt{3}}{4}L) traslazione.

˜w̃_{4} = T_{(\frac{3}{4}L,\frac{\sqrt{3}}{4}L)} ∘ R_{π} ∘ ˜ w̃_{1} con R_{π} rotazione di π intorno all’origine, in senso antiorario. Il triangolo T è fissato.

Sia T il triangolo di lato L e altezza \frac{\sqrt{3}}{2}L dell’esempio precedente.

Se consideriamo le tre mappe dell’esempio 4, ˜ w̃_{1}, ˜ w̃_{2}, ˜ w̃_{3} e definiamo

W^{∗∗}(A) = ˜ w̃_{1}(A) ∪ ˜ w̃_{2}(A) ∪ ˜ w̃_{3}(A)

possiamo osservare che, applicando W^{∗∗} alla figura di partenza, dopo n iterazioni otteniamo una figura che tende al Triangolo di Sierpinski.

64

Solo se partiamo dal triangolo di Sierpinski e gli applichiamo W^{∗∗} otteniamo il triangolo di Sierpinski come insieme fissato, in tutti gli altri casi si fissa una figura che tende al Triangolo di Sierpinski (conseguenza del teorema delle contrazioni).

COMPRESSIONE DI IMMAGINI

Un’applicazione delle IFS riguarda la compressione di immagini. Consideriamo, infatti, il seguente problema: abbiamo un’immagine sullo schermo da 80×80 pixels del computer

Per ottenere la figura dobbiamo fornire 6400 informazioni, per dire se ogni singolo pixel è spento o acceso. Il metodo delle IFS ci permette di ridurre considerevolmente il numero di informazioni da fornire per ottenere una figura.

Ad esempio, per il triangolo di Sierpinski è sufficiente dare i parametri da cui dipendono le ˜ w̃_{1}, ˜ w̃_{2}, ˜ w̃_{3}, che risultano essere 9 ( per ogni ˜ w̃_{i} un parametro è il fattore di contrazione, due parametri sono le traslazioni orizzontale e verticale). Infatti, dati i 9 parametri che individuano la funzione W, risulta ad essa associato in modo univoco il triangolo di Sierpinski. Pertanto abbiamo almeno due modi per identificare la stessa figura: il primo è fornire le 6400 informazioni relative ai pixels, il secondo modo è quello di vederla come punto fisso di W, la quale necessita di soli 9 parametri. Il secondo modo permette di ”comprimere” il numero di informazioni necessarie ed il fattore di compressione risulta essere

\frac{6400}{9} = 711.

Una volta compressa un’ immagine I tramite i parametri di una W (di cui tale immagine è l’unico punto fisso), ci chiediamo come è possibile riottenere I nel momento in cui volessimo manipolarla o semplicemente vederla, ossia ci chiediamo come è possibile ”decomprimerla”. Per decomprimere I utilizziamo quanto il teorema delle contrazioni ci dice: consideriamo una qualsiasi altra figura e le applichiamo la funzione W in modo iterativo. Otteniamo così, dopo un certo numero di iterazioni, una buona approssimazione della figura I, poiché quest’ultima è il limite di ogni successione costruita iterando W e il cui punto di partenza è una qualsiasi altra immagine. Possiamo concludere dunque che, per figure che sappiamo essere punti fissi di qualche W, riusciamo a farne una compressione e successivamente una decompressione.

Il problema è ora: riusciamo a comprimere in questo modo una figura qualsiasi o, in altri termini, considerata una figura qualsiasi, esiste una W per cui essa è punto fisso? Consideriamo ad esempio la figura

Riusciamo a decomporla come copie rimpicciolite di sé (utilizzando solo omotetie, traslazioni e rotazioni)? Sembra di no, una tale figura non sembra autosimile. Succede, però, che, anche se non risulta autosimile globalmente, lo è localmente.

Questo suggerisce un procedimento automatico di compressione di figure reali. Sia dunque

l’immagine iniziale i che vogliamo comprimere. Facciamo due copie della figura i da 80 × 80 pixels. Dividiamo la prima copia in 100 blocchi da 8×8 pixels.

Dividiamo laseconda copia in 25 blocchi da 16 × 16 pixels.

I blocchetti 8 × 8 sono indicati con D_{1}, …, D_{100}. I blocchetti 16 × 16 sono chiamati R_{1}, …, R_{25}. Sia D_{j} un blocchetto 8 × 8. Applichiamo a R_{1}, …, R_{25} un’omotetia di fattore \frac{1}{2} e confrontiamo i 25 risultati con D_{j}: scegliamo quello più ”simile” D_{j}. Associamo quindi ad ogni singolo D_{j} il più simile a sè degli R_{k} ridotti. E’ definita in questo modo un’applicazione che ad ogni D_{j} associa un unico R_{k}: l’indice k ∈ {1, …, 25} associato a questo j lo indichiamo con k(j). Dunque ad ogni D_{j} è associato R_{K(j)}. Indichiamo con W_{j} la applicazione lineare contrattiva (omotetia + traslazione) tale che W_{j}(R_{k(j)}) ≃ D_{j}

W_{j} : R_{k(j)} → D_{j}.

Inoltre ogni blocchetto è individuato tramite le coordinate del vertice inferiore sinistro; pertanto, per esplicitare l’applicazione W_{j}, abbiamo bisogno delle 2 coordinate del vertice inferiore sinistro di D_{j} e delle coordinate del vertice inferiore sinistro di R_{k(j)} associato. Se facciamo questo per ognuno dei 100 D_{j}, in totale abbiamo bisogno di 400 parametri. Con tale procedimento, otteniamo il seguente fattore di compressione

\frac{80 × 80}{400} = \frac{6400}{400} = 16.

Per decomprimere l’immagine operiamo come segue. Consideriamo una qualsiasi altra immagine a e applichiamo ad essa l’operatore H così definito: H(a) = W_{1}(a∩R_{k(1)})∪W_{2}(a∩R_{k(2)})∪...W_{100}(a∩R_{k(100)}).

Iteriamo H a partire da a:

a, H(a), H(H(a)), H(H(H(a)))...

Quello che succede, nelle simulazioni effettuate, è che, se partiamo dall’immagine a tutta nera, questa successione

a, H(a), H(H(a)), H(H(H(a)))...

tende all’immagine iniziale i, nonostante nessun risultato teorico, nessun teorema ci assicurano la convergenza della successione, tantomeno la convergenza proprio all’immagine i.

Nota: le simulazioni sono state effettuate con un procedimento di compressione leggermente diverso da quello descritto.