Il microscopio di Banach per trovare un punto fisso

Autore originario é Christiane Rousseau.
2 aprile 2012

In questa ‘vignette‘, mostreremo come, partendo da un piccolo gioco, si giunge a scoprire uno dei più potenti teoremi della matematica, ovvero il teorema del punto fisso di Banach. Tale teorema ha sorprendenti applicazioni all’interno della matematica e al di fuori di essa. Nella terza sezione discuteremo l’affascinante applicazione alla compressione di immagini.

Ma, partiamo con il nostro gioco e osserviamo il famoso coperchio della scatola di The Laughing Cow.

L’orecchino destro della mucca e di nuovo una Laughing Cow. Ad ogni punto del coperchio, associamo il punto corrispondente sull’orecchino destro. Questa è naturalmente una funzione dal coperchio in se stesso, che chiameremo $F$ . Per esempio, alla punta del mento della mucca associamo la punta del mento della piccola mucca sull’orecchino destro. Al centro dell’occhio destro della mucca associamo il centro dell’occhio destro della piccola mucca sull’orecchino destro, ecc. Ora ecco la domanda: esiste un punto che viene mandato in se stesso attraverso questo procedimento? Tale punto, se esiste, sarà detto punto fisso. Se esiste un punto fisso, allora non è nessuno dei punti che abbiamo elencato sopra. Inoltre, se esiste un punto fisso, esso dovrebbe giacere sull’orecchino destro. Tuttavia, tale orecchino destro viene mandato nell’orecchino destro della piccola mucca, e così via. Visivamente, possiamo constatare che questi orecchini destri contenuti uno dentro l’altro sembrano convergere ad un punto, che chiamiamo $A$ , e $A$ è un candidato per la nostra soluzione.

Ora, iniziamo con un qualsiasi punto, per esempio la punta del mento e chiamiamolo $P_0$ . Allora $P_0$ viene mandato in $P_1=F(P_0)$ , che è la punta del mento della piccola mucca sull’orecchino destro. Allora $P_1$ viene mandato in $P_2=F(P_1)$ , che è la punta del mento della mucca che appare sull’orecchino destro della piccola mucca, e così via. Osserviamo tre cose:

Possiamo continuare il procedimento per un numero infinito di volte e generare una successione $\{P_n\}$ , dove $P_{n+1}=F(P_n)$ .
Visivamente, solo un numero finito di punti della successione appaiono come distinti e tutti gli altri non possono essere distinti l’uno dall’altro. Naturalmente, possiamo zoomare e vedere più punti. Tuttavia, qualunque sia lo zoom che scegliamo, potremo ancora distinguere solo un numero finito di punti e gli altri non potranno essere distinti l’uno dall’altro.
Questa successione sembra convergere allo stesso punto $A$ di prima.

Se avessimo considerato un altro punto $Q_0$ e costruito la successione $\{Q_n\}$ , dove $Q_{n+1}=F(Q_n)$ , ci sarebbe parso che la successione $\{Q_n\}$ convergesse allo stesso punto $A$ . Infatti, possiamo osservare che ciò segue dal fatto che il singoletto $\{A\}$ è l’intersezione degli orecchini contenuti l’uno nell’altro il cui diametro tende a $0$ .

Cosa ci dice il teorema del punto fisso di Banach? Esso afferma infatti che la funzione $F$ ammette un unico punto fisso, nello specifico che esiste un unico punto fisso $A$ nel piano tale che $F(A)=A$ . Inoltre, esso asserisce anche che preso un qualsiasi punto $P_0$ e costruita la successione $\{P_n\}$ , dove $P_{n+1}=F(P_n)$ , allora la successione $\{P_n\}$ convergerà ad $A$ .

Ma perché? La stessa cosa avrebbe potuto accadere per una qualsiasi funzione $F$ ? Ovviamente no. Per esempio, una traslazione nel piano non ha punti fissi. E la mappa $G(x,y)=(x+(x^2-1),y)$ ammette i due punti fissi $(\pm 1,0)$ . La mappa $F$ del nostro gioco ha una proprietà speciale. Essa è una contrazione. Infatti, l’immagine è sempre più piccola del dominio. Se c’è una certa distanza tra due punti $P$ e $Q$ , allora le loro immagini $F(P)$ e $F(Q)$ sono più vicine tra loro di quanto non lo siano $P$ e $Q$ . Questa affermazione ha senso in quanto in ${\mathbb R}^2$ possiamo misurare la distanza tra due elementi. Questo perché ${\mathbb R}^2$ è uno spazio metrico. É la proprietà di essere una contrazione che garantisce che, quando costruiamo la successione $\{P_n\}$ , qualunque sia la soglia di precisione che consideriamo, (che guardiamo la successione da lontano, o da vicino, o attraverso un microscopio, o attraverso un microscopio elettronico), dopo un qualche $N$ che dipende dalla nostra tolleranza, tutti gli elementi $P_n$ , $n > N$ , della successione diventano indistinguibili. Due elementi sono distinguibili se la distanza tra loro è maggiore di una certa soglia. Richiameremo nella prossima sezione il fatto che una successione avente questa proprietà è detta successione di Cauchy. In ${\mathbb R}^2$ , abbiamo la proprietà che ogni successione di Cauchy è convergente. Diciamo che ${\mathbb R}^2$ è uno spazio metrico completo.

1. Il teorema del punto fisso di Banach

Abbiamo ora tutti gli strumenti per affrontare il caso generale e possiamo enunciare il teorema.

Teorema (del punto fisso di Banach). Sia $\mathcal{K}$ uno spazio metrico completo in cui la distanza tra due punti $P$ e $Q$ è denotata con $d(P,Q)$ . E sia $F:\mathcal{K}\to \mathcal{K}$ una contrazione, nello specifico esiste $c\in(0,1)$ tale che per ogni $P,Q\in \mathcal{K}$ , risulta

$d(F(P),F(Q))\leq c\;d(P,Q).$

Allora $F$ ha un unico punto fisso, più precisamente esiste un unico $A\in \mathcal{K}$ tale che $F(A)=A$ .

Definiremo tutti i termini che appaiono in questo enunciato. Questa parte è più formale e può essere saltata se il lettore preferisce concentrarsi sulle sue affascinanti applicazioni.

Sappiamo cos’è la distanza tra due punti $P$ e $Q$ in ${\mathbb R}^2$ . Come la generalizziamo all’insieme $\mathcal{K}$ ?

Definizione. Una distanza su un insieme $\mathcal{K}$ è una funzione $d:\mathcal{K}\times \mathcal{K}\to {\mathbb R}$ che soddisfa le seguenti proprietà

Per ogni $P,Q\in \mathcal{K}$ , $d(P,Q)\geq0$ ;
$d(P,Q)=0$ se e solo se $P=Q$ ;
Per ogni $P,Q,R\in \mathcal{K}$ , $d(P,Q)\leq d(P,R)+d(R,Q)$ (diseguaglianza triangolare).

Noi sappiamo che queste proprietà sono soddisfatte per l’usuale distanza euclidea in ${\mathbb R}^2$ .

Richiamiamo ora la definizione di successione di Cauchy, che è la formalizzazione del concetto di una successione per cui, qualunque soglia di precisione si scelga, dopo un numero finito di elementi, tutti gli altri elementi diventano indistinguibili. Richiamiamo anche la definizione di successione convergente.

Definizione.

Una successione $\{P_n\}$ di elementi di uno spazio metrico $\mathcal{K}$ è una successione di Cauchy se per ogni $\epsilon > 0$ , esiste $N\in {\mathbb N}$ tale che per ogni $n,m > N$ , risulta
$d(P_n,P_m) < \epsilon.$
Una successione $\{P_n\}$ di elementi di uno spazio metrico $\mathcal{K}$ converge ad un limite $A\in \mathcal{K}$ se per ogni $\epsilon > 0$ , esiste $N\in {\mathbb N}$ tale che per ogni $n > N$ , risulta
$d(P_n,A) < \epsilon.$

Definizione. Uno spazio metrico $\mathcal{K}$ è uno spazio metrico completo se ogni successione di Cauchy $\{P_n\}$ di elementi di $\mathcal{K}$ converge ad un elemento $A$ di $\mathcal{K}$ .

Come dimostriamo il teorema del punto fisso di Banach? L’unicità del punto fisso si prova facilmente. Infatti, supponiamo che $A$ e $B$ siano due punti fissi. Allora $F(A)=A$ e $F(B)=B$ . Inoltre, dal momento che $F$ è una contrazione, si ha

$d(F(A),F(B))\leq c\;d(A,B)$

e quindi $d(A,B)\leq c\;d(A,B)$ . La sola soluzione è $d(A,B)=0$ , che porta a $A=B$ .

Per quanto riguarda l’esistenza, l’idea di dimostrazione è anche semplice: l’abbiamo già trovata nel nostro gioco con The Laughing Cow! Prendiamo un qualsiasi punto $P_0\in \mathcal{K}$ e costruiamo (come prima) la successione $\{P_n\}$ , dove $P_{n+1}=F(P_n)$ . Allora, questa successione è di Cauchy e il suo limite è un punto fisso. (Naturalmente, dimostrare queste due affermazioni richiede un po’ di lavoro, ma noi salteremo i dettagli tecnici. Ciò che è importante è che la dimostrazione è la stessa sia nel caso generale di un complicato spazio metrico $\mathcal{K}$ sia nel caso semplice $\mathcal{K}={\mathbb R}^2$ .)

L’idea di dimostrazione non solo è semplice ed intuitiva, ma anche molto potente. Essa fornisce un modo di costruire numericamente il punto fisso $A$ . Questo spiega perché si possano trovare molte applicazioni di tale teorema sia sul versante teorico che su quello applicativo.

2. Le applicazioni in analisi

Un’applicazione molto importante del teorema del punto fisso di Banach è la prova dell’esistenza e dell’unicità delle soluzioni di equazioni differenziali sufficientemente regolari. In questa applicazione, lo spazio metrico completo $\mathcal{K}$ è un insieme di funzioni e la mappa $F$ trasforma una funzione in un’altra funzione (si dice che $F$ è un operatore). Il trucco è mostrare che una soluzione dell’equazione differenziale, se essa esiste, è un punto fisso dell’operatore $F$ .

Probabilmente avrai studiato semplici equazioni differenziali ed imparato trucchi per trovare formule per le soluzioni.
Bene, queste equazioni differenziali rappresentano un’eccezione e, per la maggior parte delle equazioni differenziali, non esiste alcuna formula risolutiva. Da qui l’importanza di un teorema che garantisca l’esistenza di una soluzione. Non dovresti essere sorpreso che non si abbia nessuna formula per le soluzioni della maggior parte delle equazioni differenziali. Infatti, considera la semplice equazione differenziale

$y'= e^{-x^2}.$

La sua soluzione è data da

$y=\int e^{-x^2}dx.$

Tu forse ricorderai di aver sentito in un corso di probabilità o di statistica che non esiste alcuna formula per la primitiva della funzione $e^{-x^2}$ , ciò spiega perché abbiamo bisogno di lavorare con le tavole quando studiamo la legge gaussiana.

3. Applicazione alla compressione di immagini

Il miglior modo di archiviare un’immagine in memoria consiste nel memorizzare il colore di ogni pixel. Questo metodo presenta due problemi:

esso richiede un’enorme quantità di memoria;
se cerchiamo di ingrandire l’immagine, ad esempio per farne un poster, i pixel diventeranno grandi quadrati e perderemo le informazioni su come riempire i dettagli in questi quadrati.

Qual è il principio della compressione di un’immagine? É codificare meno informazioni possibili dell’immagine originale, ma farlo in modo intelligente, così che l’occhio non possa percepire che l’immagine osservata è deteriorata.

Internet ha aumentato il bisogno di una buona compressione di immagini. Infatti, le immagini sono abbastanza ricorrenti nella navigazione sul web. Quindi, per la navigazione in internet, è opportuno avere immagini codificate in file che siano il più piccolo possibile. Quando guardi un’immagine sullo schermo del tuo computer non riesci a vedere che essa è stata deteriorata. Tuttavia, se provi ad ingrandirla o ad usarla per farne un poster, vedrai immediatamente che la qualità è bassa.

Esistono molti principi di compressione di immagini e uno dei più familiari è JPEG, che è diventato il formato standard per le foto digitali. Anche la codificazione di un’immagine in formato JPEG è un algoritmo matematico.

In questa ‘vignette‘, ci concentreremo su un altro metodo, che è rimasto più sperimentale. Tale metodo, introdotto da Barnsley, è stato chiamato sistema iterato di funzioni. L’idea che sta alla base del metodo è quella di approssimare un’immagine mediante oggetti geometrici. Per avere un numero sufficiente di oggetti disponibili, non ci limiteremo agli usuali oggetti geometrici che sono le rette e le curve lisce, ma includeremo complicati oggetti frattali come la foglia di felce e il tappeto di Sierpinski (si vedano le figure a sinistra).

Spiegheremo l’idea del processo di compressione sul tappeto di Sierpinski, che trovate qui a sinistra. Questo sembra a priori un oggetto complicato. Come archiviarlo nella memoria del computer, in maniera ottimale? Il miglior modo è archiviare un programma per ricostruirlo quando serve.

E per costruire tale programma, abbiamo bisogno di capire cosa caratterizza quest’oggetto geometrico.
Osserviamo il nostro tappeto di Sierpinski: è l’unione di tre tappeti di Sierpinski (più precisamente tre copie di se stesso), che sono grandi la metà (in larghezza e altezza). Infatti, partendo dal tappeto di Sierpinski, possiamo costruirne un secondo con il seguente procedimento:

Rimpiccioliamo il tappeto di Sierpinski alla metà della sua grandezza partendo dal vertice in basso a sinistra.
Facciamo una prima copia di questo piccolo tappeto di Sierpinski ed incolliamola a destra.
Facciamo una terza copia del piccolo tappeto di Sierpinski e incolliamola in alto.

La seconda figura che abbiamo costruito è identica al nostro tappeto di Sierpinski iniziale. Quindi il tappeto di Sierpinski è il punto fisso per questo processo.
Mettiamolo ora in termini matematici. Si noti che la lunghezza della base di un tappeto di Sierpinski è uguale alla sua altezza. Per questo possiamo scegliere un sistema di assi cartesiani con l’origine posta nell’angolo in basso a sinistra del tappeto di Sierpinski e l’unità di riferimento in modo che la base e l’altezza abbiano entrambe misura 1. Consideriamo anche le seguenti trasformazioni affini definite su ${\mathbb R}^2$ :

$\begin{aligned} T_1(x,y)&=\left(\frac{x}2,\frac{y}2\right),\\ T_2(x,y)&=\left(\frac{x}2+\frac12,\frac{y}2\right),\\ T_3(x,y)&=\left(\frac{x}2+\frac14,\frac{y}2+\frac12\right). \end{aligned}$

Se $S$ è il tappeto di Sierpinski, abbiamo

$S=T_1(S)\cup T_2(S)\cup T_3(S).$

Esistono altri sottoinsiemi $B$ del piano che hanno la stessa proprietà, nello specifico

(1) $B=T_1(B)\cup T_2(B)\cup T_3(B)?$

Proveremo e verificheremo che non ce ne sono! Così abbiamo caratterizzato il nostro tappeto di Sierpinski come l’unico sottoinsieme $B$ del piano tale che (1) è soddisfatta. Cos’abbiamo fatto? Abbiamo costruito una funzione che ad un sottoinsieme $B$ del piano associa il sottoinsieme $T_1(B)\cup T_2(B)\cup T_3(B)$ . Chiamiamo questa funzione $W$ . Essa è definita da

(2) $B\longmapsto W(B)=T_1(B)\cup T_2(B)\cup T_3(B),$

e abbiamo osservato che $S=W(S)$ , più precisamente $S$ è un punto fisso di questa funzione.

Abbiamo annunciato che avremmo verificato che il tappeto di Sierpinski è l’unico punto fisso di questa funzione.

Proviamo con un quadrato $C_0$ come in Figura 1(a). La sua immagine è $C_1$ in Figura 1(b). Applichiamo lo stesso procedimento a $C_1$ e otteniamo $C_2, C_3, \dots, C_5$ (Figura 1(c)-(f)).

Osserviamo tre cose:

Nessuno degli insiemi $C_0, \dots, C_5$ è un punto fisso di $W$ .
Avremmo potuto continuare il procedimento all’infinito, quindi producendo una successione infinita di insiemi $\{C_n\}$ , per la quale $C_{n+1}=W(C_n)$ .
La successione $\{C_n\}$ sembra convergere rapidamente al tappeto di Sierpinski. Infatti, il nostro occhio non riesce a distinguere $C_{10}$ da $S$ . Quindi, invece di $S$ nella nostra immagine, il programma che ricostruisce la nostra immagine può semplicemente produrre $C_{10}$ . E, se avessimo bisogno di una risoluzione migliore, potremmo usare lo stesso programma e chiedergli di arrestarsi a $C_{20}$ o $C_{30}$ . Perciò lo stesso programma molto semplice può produrre una ricostruzione, qualsiasi sia la precisione desiderata!

Non solo, possiamo verificare anche che il processo funziona per ogni insieme iniziale! Un secondo esempio che itera un pentagono è mostrato in Figura 2. Le medesime osservazioni (i), (ii) e (iii) valgono anche per questo esempio.

Abbiamo visto che il teorema del punto fisso di Banach si applica alle contrazioni su spazi metrici completi. Abbiamo definito la funzione $W$ in (2) sui sottoinsiemi dello spazio. Come spazio metrico, consideriamo $\mathcal{K}$ : l’insieme dei sottoinsiemi (chiusi) limitati dello spazio. Introdurremo una distanza su $\mathcal{K}$ detta distanza di Hausdorff. La definizione della distanza di Hausdorff $d_H(B_1,B_2)$ , tra due sottoinsiemi $B_1$ e $B_2$ consiste in una formula complicata e oscura, quindi spieghiamo il concetto in un altro modo. Iniziamo spiegando il significato che intendiamo dare all’affermazione

$d_H(B_1,B_2)\leq \epsilon$

(anche se non abbiamo definito cos’è $d_H(B_1,B_2)$ !) Vorrebbe dire semplicemente che se il nostro occhio ha una precisione di $\epsilon$ , esso non riuscirà a distinguere tra $B_1$ e $B_2$ . In termini matematici, allora $d_H(B_1,B_2)\leq \epsilon$ dovrebbe significare che

(3) $\forall P\in B_1\;\exists Q\in B_2\; d(P,Q)\leq \epsilon \quad\text{e}\quad \forall P'\in B_2\;\exists Q'\in B_1\; d(P',Q')\leq \epsilon$

(Qui $d$ è l’usuale distanza euclidea su ${\mathbb R}^2$ .) Ciò permette di dare una definizione indiretta.

Definizione. La distanza di Hausdorff tra due insiemi chiusi e limitati $B_1$ e $B_2$ è il minimo di tutti gli $\epsilon\geq0$ tali che (3) è soddisfatta.

Possiamo ora convincerci che la funzione $W$ è una contrazione.
Infatti, supponiamo che $d_H(B_1,B_2)\leq \epsilon$ . Allora possiamo dimostrare che $d_H(W(B_1),W(B_2))\leq \frac{\epsilon}{2}$ . Sia $P\in W(B_1)$ . Quindi esistono $i\in \{1,2,3\}$ e $P_1\in B_1$ tali che $P=T_i(P_1)$ . Poiché $d_H(B_1,B_2)\leq \epsilon$ , esiste $Q_1\in B_2$ tale che $d(P_1,Q_1)\leq\epsilon$ . Sia $Q=T_i(Q_1)$ . Allora $Q\in W(B_2)$ e $d(P,Q)= d(T_i(P_1),T_i(Q_1))=\frac12 d(P_1,Q_1)\leq\frac{\epsilon}{2}$ . Allo stesso modo se partiamo da $P'\in W(B_2)$ allora esiste $Q'\in W(B_1)$ tale che $d(P',Q')\leq\frac{\epsilon}{2}$ .

Questo procedimento è stato adattato alla compressione di immagini reali (si vedano i riferimenti [2] o [5]). Il metodo produce immagini di alta qualità quando l’immagine ha un carattere frattale. Comunque la qualità della compressione non è buona e flessibile come nel formato JPEG. Inoltre, il processo di codificazione (che trasforma l’immagine in un programma per ricostruirla) è ancora troppo noioso per avere qualche interesse pratico. In ogni caso, la semplicità di quest’idea, unita alla sua forza, resta abbastanza suggestiva.

4. Una sorprendente applicazione: l’algoritmo PageRank

Il successo di Google come motore di ricerca è dovuto al suo algoritmo: l’algoritmo PageRank. Mediante tale algoritmo, viene calcolato un punto fisso di un operatore lineare su ${\mathbb R}^n$ che è una contrazione e questo punto fisso (che è un vettore) dà l’ordine delle pagine. In pratica, il punto fisso (che è un autovettore dell’autovalore $1$ ) è calcolato approssimativamente come $P_n$ per $n$ sufficientemente grande. Invitiamo il lettore interessato a guardare i dettagli nella ‘vignette‘ dal titolo Come funziona Google?.

5. Conclusioni

Quello che abbiamo imparato in questa ‘vignette‘ è come, partendo da un semplice gioco, siamo riusciti a scoprire idee molto potenti che possono condurre a scoperte matematiche e tecnologiche. Quando si cerca l’unica soluzione di un problema, è ormai diventato un metodo standard in molti domini della matematica provare a vedere se la soluzione del problema può essere caratterizzata come l’unico punto fisso di un operatore appositamente costruito per quello scopo.

Abbiamo visto che il vantaggio di questo approccio sta nel fatto che il teorema fornisce un metodo pratico efficiente per costruire l’oggetto soluzione come il limite di una successione, dato che essa converge rapidamente.

L’Analisi è lo studio di funzioni. Le funzioni sono solitamente definite su numeri. In analisi multivariata, generalizziamo la nozione di funzione su vettori che sono elementi di ${\mathbb R}^n$ . Ma perché fermarci agli elementi di ${\mathbb R}^n$ ? Abbiamo anche sperimentato che ai matematici piace generalizzare la nozione di funzione, definendola, per esempio, su insiemi di insiemi e su insiemi di funzioni, ecc. Fare analisi su insiemi di funzioni è ormai diventato un importante capitolo dell’analisi moderna, detto analisi funzionale, che è una materia standard nei corsi di laurea.

Sei invitato a fare il collegamento con alcuni dei processi iterativi che hai incontrato. Per esempio, potrebbero essere i processi iterativi in una dimensione associati alla successione di Erone per ottenere le radici quadrate. La rapida convergenza geometrica può anche essere letta dal punto di vista qui presentato.

Riferimenti bibliografici

[1] M. F. Barnsley, Fractals everywhere, San Diego, Academic Press, 1988.

[2] J. Kominek, Advances in fractal compression for multimedia applications, Multimedia System Journal, vol. 5, n. 4, 1997, 255 – 270.

[3] C. Rousseau, Point fixe de Banach (in francese), Accromath 5, hiver-printemps 2010 (www.accromath.ca).

[4] C. Rousseau, How Google works? Klein vignette (www.kleinproject.org).

[5] C. Rousseau and Y. Saint-Aubin, Mathematics and technology, SUMAT Series, Springer-Verlag, 2008 (Esiste una versione francese del libro, Mathématiques et technologie, pubblicato all’interno della stessa serie.)

PDF

Il microscopio di Banach per trovare un punto fisso

Related

Lascia una rispostaCancella risposta

Condividi:

Related

Lascia una rispostaCancella risposta