El microscopio de Banach para encontrar un punto fijo

Autor original: Christiane Rousseau.

En esta viñeta mostramos cómo descubrir, comenzando con un pequeño juego, uno de los teoremas más potentes de las matemáticas: el teorema del punto fijo de Banach. Este teorema tiene fantásticas aplicaciones tanto dentro como fuera de las matemáticas. En la sección 3 discutiremos su fascinante aplicación a la compresión de imágenes.

Pero comencemos con nuestro juego y echemos una mirada a la famosa tapa de una caja de La vaca que ríe.

El pendiente derecho de la vaca es de nuevo una tapa de La vaca que ríe. Asociamos a cada punto de la tapa el correspondiente punto del pendiente derecho. Por supuesto, esto define una función de la tapa en sí misma que llamaremos $F$ . Por ejemplo, a la punta de la barbilla de la vaca le asociamos la punta de la barbilla de la vaca pequeña en el pendiente derecho, al centro del ojo derecho de la vaca le asociamos el centro del ojo derecho de la vca pequeña en el pendiente derecho, etc. Aquí va la pregunta: ¿hay algún punto que sea enviado a sí mismo en este proceso? Un tal punto, si existe, se denomina punto fijo. Si existe un punto fijo entonces no es ninguno de los que hemos mencionado antes y, además, deberá estar en el pendiente derecho. Pero este pendiente derecho es enviado al pendiente derecho de la vaca pequeña, etc. Visualmente podemos imaginar que estos pendientes derechos anidados convergen a un punto que llamaremos $A$ y que este punto $A$ es un candidato a solución de nuestra pregunta.

Ahora comencemos desde cualquier punto, por ejemplo la punta de la barbilla y llamémoslo $P_0$ . Entonces $P_0$ es enviado a $P_1=F(P_0)$ , que es la punta de la barbilla de la vaca pequeña en el pendiente derecho; $P_1$ es enviado a $P_2=F(P_1)$ , que es la punta de la barbilla de la vaca pequeña que aparece en el pendiente derecho, etc. Se observan tres cosas:

podemos continuar con el proceso un número infinito de veces y generar una sucesión $\{P_n\}$ , donde $P_{n+1}=F(P_n)$ .
Visualmente solo un número finito de puntos se la sucesión parecen diferentes, todos los demás no se pueden distinguir. Por supuesto, podemos hacer zoom y veremos más puntos, pero con cualquier zoom que elijamos solo diferenciaremos un número finito de puntos, los demás seguirán siendo indistinguibles.
Esta sucesión parece converger al mismo punto $A$ de antes.

Si hubiéramos tomado otro punto $Q_0$ y construido la sucesión $\{Q_n\}$ , donde $Q_{n+1}=F(Q_n)$ , habríamos visto que la sucesión $\{Q_n\}$ parecería converger al mismo punto $A$ . De hecho, esto de deduce del hecho de que el conjunto unipuntual $\{A\}$ es la intersección de los pendientes derechos cuyo diámetro tiende a $0$ .

¿Qué nos dice el teorema del punto fijo de Banach? Que la función $F$ tiene un único punto fijo, es decir, que existe un único punto $A$ del plano tal que $F(A)=A$ . Más aún, nos dice que si tomamos cualquier punto $P_0$ , la sucesión $\{P_n\}$ , donde $P_{n+1}=F(P_n)$ , converge a $A$ .

Pero, ¿por qué? ¿Habría ocurrido esto para cualquier función $F$ ? Por supuesto que no. Por ejemplo, una traslación en el plano no tiene puntos fijos. Y La función $G(x,y)=(x+(x^2-1),y)$ tiene dos puntos fijos $(\pm 1,0)$ . La función $F$ de nuestro juego tiene una propiedad especial: es una contracción. De hecho, su imagen es mucho más pequeña que el dominio. Si dos puntos $P$ y $Q$ están a cierta distancia, sus imágenes $F(P)$ y $F(Q)$ están más cerca de lo que están $P$ y $Q$ . Esto tiene sentido porque en ${\mathbb R}^2$ podemos medir la distancia entre dos elementos, ya que ${\mathbb R}^2$ es un espacio métrico. La propiedad contractiva de $F$ hace que cuando construimos la sucesión $\{P_n\}$ no importe la precisión que tomemos (ya sea mirando la sucesión desde lejos, o acercándonos, o a través de un microscopio, o a través incluso de un microscopio electrónico), ya que después de cierto $N$ , que depende de la precisión elegida, todos los elementos $P_n$ , $n>N$ , de la sucesión resultan indistinguibles. Dos elementos son distinguibles si la distancia entre ellos es mayor que cierta precisión. Veremos en la próxima sección que una sucesión con esta propiedad se llama sucesión de Cauchy. En ${\mathbb R}^2$ se tiene la propiedad de que toda sucesión de Cauchy tiene límite, por lo que decimos que ${\mathbb R}^2$ es un espacio métrico completo.

1. El teorema del punto fijo de Banach

Tenemos ya todos los ingredientes necesarios para enunciar el teorema en el caso general.

Teorema (teorema del punto fijo de Banach). Sea $\mathcal{K}$ un espacio métrico completo en el cual se denota por $d(P,Q)$ la distancia entre dos puntos $P$ y $Q$ y sea $F:\mathcal{K}\rightarrow \mathcal{K}$ una contracción, i.e. existe $c\in(0,1)$ tal que para cualesquiera $P,Q\in \mathcal{K}$ se tiene que

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

Entonces $F$ tiene un único punto fijo, i.e. existe un único $A\in \mathcal{K}$ tal que $F(A)=A$ .

Definimos ahora algunos de los términos que aparecen en el enunciado de este teorema. Esta parte es más formal y puede ser omitida si el lector prefiere concentrarse en las fascinantes aplicaciones del teorema.

Sabemos lo que es la distancia entre dos puntos $P$ y $Q$ de ${\mathbb R}^2$ . ¿Cómo lo generalizamos a un conjunto cualquiera $\mathcal{K}$ ?

Definición. Una distancia en un conjunto $\mathcal{K}$ es una función $d: \mathcal{K}\times \mathcal{K}\rightarrow {\mathbb R}$ que verifica

PAra cualesquiera $P,Q\in \mathcal{K}$ , $d(P,Q)\geq0$ ;
$d(P,Q)=0$ si y solo si $P=Q$ ;
Para cualesquiera $P,Q,R\in \mathcal{K}$ , $d(P,Q)\leq d(P,R)+d(R,Q);$ (desigualdad triangular.)

Es conocido que la distancia euclídea usual en ${\mathbb R}^2$ verifica estas propiedades.

Recordamos ahora la definición de sucesión de Cauchy, que es una formalización de la idea de uan sucesión para la cual todos los elementos posteriores a un número finito de ellos son indistinguibles, sea cual sea la preción elegida. También presentamos la definición de sucesión convergente.

Definición.

Una sucesión $\{P_n\}$ de elementos de un espacio métrico $\mathcal{K}$ es una sucesión de Cauchy si para todo $\epsilon>0$ , existe $N\in {\mathbb N}$ tal que para todos $n,m>N$ , se tiene que
$d(P_n,P_m)<\epsilon.$
Una sucesión $\{P_n\}$ de elementos de un espacio métrico $\mathcal{K}$ converge a un límite $A\in \mathcal{K}$ si para todo $\epsilon>0$ , existe $N\in {\mathbb N}$ tal que para todo $n>N$ , se tiene que
$d(P_n,A)<\epsilon.$

Definición. Un espacio métrico $\mathcal{K}$ es un espacio métrico completo si toda sucesión de Cauchy $\{P_n\}$ de elementos $\mathcal{K}$ converge a un elemento $A$ de $\mathcal{K}$ .

¿Cómo se prueba el teorema del punto fijo de Banach? La unicidad del punto fijo es fácil: supongamos que $A$ y $B$ son dos puntos fijos. Se tiene que $F(A)=A$ y $F(B)=B$ y como $F$ es una contracción

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

y, por tanto, $d(A,B)\leq c \;d(A,B)$ . La única solución es $d(A,B)=0$ , lo que nos da $A=B$ .

En cuanto a la existencia, la idea de la demostración es también sencilla y ya la hemos encontrado en nuestro juego de La vaca que ríe. Tomamos cualquier punto $P_0\in \mathcal{K}$ y construimos (como antes) la sucesión $\{P_n\}$ , donde $P_{n+1}=F(P_n)$ . Esta sucesión es de Cauchy y su límite es un punto fijo. (Por supuesto, probar estas dos afirmaciones requiere trabajo, pero omitimos los detalles técnicos; lo que es realmente importante es que la demostración es la misma en el caso general con un espacio métrico completo complicado que en el caso sencillo $\mathcal{K}={\mathbb R}$ .)

La idea de la demostración no es solo sencilla e intuitiva, sino también muy potente: proporciona una manera de construir numéricamente el punto fijo $A$ . Esto explica las muchas aplicaciones de este teorema, que se pueden encontrar tanto en el aspecto teórico como en el aplicado.

2. Aplicaciones en análisis

Una de las aplicaciones teóricas más importantes del teorema del punto fijo de Banach es la demostración de la existencia y unicidad de soluciones de ecuaciones diferenciales suficientemente regulares. En este caso el espacio métrico completo $\mathcal{K}$ es un conjunto de funciones y la función $F$ transforma una función en otra función (frecuentemente se dice que $F$ es un operador). El truco es probar que si existe solución de la ecuación diferencial, esta es un punto fijo del operador $F$ .

Probablemente el lector haya estudiado ecuaciones difereciales sencillas y aprendido trucos para hallar fórmulas para las soluciones. Estas ecuaciones diferenciales son una excepción: en la mayor parte de las ecuaciones diferenciales no existe ninguna fórmula para la solución, de ahí la importancia de un teorema que asegure la existencia de solución. La no existencia de fórmulas para expresar la solución de la mayor parte de las ecuaciones diferenciales no debería sorprender al lector. De hecho, si se considera la sencilla ecuación diferencial

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

su solución viene dada por

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

El lector recordará de sus cursos de probabilidad o estadística que no existe fórmula para la primitiva de la función $e^{-x^2}$ , explicando así por qué se necesita trabajar con tablas cuando se estudia la distribución normal.

3. Aplicación a la compresión de imágenes

La mejor manera de almacenar una imagen en memoria es almacenar el color de cada píxel. Este método presenta dos problemas:

Requiera una enorme cantidad de memoria.
Si se intenta ampliar la imagen, for ejemplo para usarla en un póster de mayor tamaño, entonces los píxeles serán cuadrados más grandes y faltará la información de cómo rellenar los detalles en esos cuadrados.

¿Cuál es el principio de la compresión de imágenes? Codificar una cantidad de información menor a la que supondría la imagen orginal pero en hacerlo de una manera inteligente, de manera que el ojo no pueda captar que la imagen observada está deteriorada. Internet ha aumentado la necesidad de una buena compresión de imágenes. De hecho, las imágenes ralentizan de modo significativo la navegación en la red. Por tanto, para la navegación por internet es bueno tener las imágenes codificadas en archivos lo más pequeños posible. Cuando se mira una imagen en la pantalla de su ordenador no se percibe que la imagen ha sido deteriorada, pero si se trata de agrandarla o de usarla para un póster, entonces se ve que la calidad es pobre.

Existen diversos principios de compresión de imágenes; uno de los más familiares es JPEG, que se ha convertido en el estándar para fotografías digitales. La codificación de una imagen en formato JPEG es también un algoritmo matemático.

En esta viñeta nos centraremos en otro método, que ha permanecido más experimental. Este método, introducido por Barnsley, se denomina sistemas de funciones iteradas. La idea subyacente de este método es aproximar una imagen mediante objetos geométricos. Para tener suficientes objetos disponibles no nos limitamos a los objetos geométricos usuales, como son las líneas y las curvas suaves, sino que incluimos complejos objetos fractales como el helecho y la alfombra de Sierpiński (ver las figuras de la izquierda).

Explicaremos la idea del proceso de compresión en la alfombra de Sierpiński de la izquierda, que a priori parece un objeto complicado. ¿Cómo almacenarlo en la memoria del ordenador de una manera “económica”? La mejor solución es almacenar un programa para reconstruirla cuando se necesite.

Para contruir este programa se necesita comprender qué caracteriza a este objecto geométrico. Observemos la alfombra de Sierpiński: es la unión de tres alfombras de Sierpiński (es decir, 3 copias de sí misma), cuyas dimensiones (altura y anchura) son la mitad. De hecho, comenzando por la alfombra de Sierpiński podemos construir una segunda mediante el siguiente procedimiento:

Se encoge la alfombra de Sierpiński a la mitad de sus dimensiones desde el vértice inferior izquierdo.
Se hace una copia de esta segunda alfombra de Sierpiński y se pega a la derecha de ella.
Se hace una última copia de la segunda alfombra de Sierpiński y se pega en la parte superior.

La figura que se ha construido es idéntica a la alfombra de Sierpiński inicial. Por tanto, la alfombra de Sierpiński es el punto fijo de este proceso.

Expresemos ahora todo esto en términos matemáticos. Notar que la longitud de la base de la alfombra de Sierpiński es igual a su altura. Por tanto, podemos tomar ejes coordenados con origen en la esquina inferior izquierda de la alfombra de Sierpiński y con unidades de manera que la base y la altura tengan ambas longitud 1. Consideramos también la siguiente transformación afín definida en ${\mathbb R}^2$ :

$\begin{align*} 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{align*}$

Si $S$ es la alfombra de Sierpiński entonces se tiene que

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

¿Existen otros subconjuntos $B$ del plano que tengan la misma propiedad, es decir,

(1) $\begin{equation*}B=T_1(B)\cup T_2(B)\cup T_3(B)?\end{equation*}$

Experimentaremos y comprobaremos que no. Por tanto, hemos caracterizado la alfombra de Sierpiński como el único subconjunto $B$ del plano que satisface (1) ¿Qué hemos hecho para ello? Hemos construido una función que a cada subconjunto $B$ del plano le asocia el subconjunto $T_1(B)\cup T_2(B)\cup T_3(B)$ . Llamemos a esta función $W$ . Está definida por

(2) $\begin{equation*}B\mapsto W(B)=T_1(B)\cup T_2(B)\cup T_3(B),\end{equation*}$

y hemos observado que $S=W(S)$ , i.e. $S$ es un punto fijo de esta función.

Hemos dicho que probaríamos que la alfombra de Sierpiński es el único punto fijo de esta función. Probemos con un cuadrado $C_0$ como en la Figura 1(a). Su imagen es $C_1$ en la Figura 1(b). Aplicamos el mismo proceso a $C_1$ y obtenemos $C_2$ , $C_3$ – $C_5$ . (Figura 1 (c)-(f)).

Figura 1

Observamos tres hechos:

Ninguno de los conjuntos $C_0$ , …, $C_5$ es un punto fijo de $W$ .
Podríamos haber continuado el proceso indefinidamente produciendo la secuencia infinita de conjuntos $\{C_n\}$ , donde $C_{n+1}=W(C_n)$ .
La secuencia $\{C_n\}$ parece converger rápidamente a la alfombra de Sierpiński. De hecho, nuestro ojo no puede distinguir $C_{10}$ de $S$ . Por tanto, el programa que reconstruyera nuestra imagen podría producir simplemente $C_{10}$ en lugar de $S$ . Si necesitáramos una mejor resolución, entonces podríamos usar el mismo programa y hacerlo parar en $C_{20}$ o $C_{30}$ . Luego el mismo pequeño programa puede reconstruir $S$ a cualquier preción.

No solo eso: podemos comprobar que funciona con cualquir conjunto inicial que tomemos. Como segundo ejemplo iteremos el pentágono que aparece en la Figura 2. Las mismas observaciones (i), (ii) y (iii) anteriores se aplican también a este ejemplo.

Figura 2

Hemos visto que el teorema del punto fijo de Banach se aplica a contracciones en espacios métrico completos. Hemos definido la función $W$ (2) en subconjuntos del plano. Como espacio métrico tomaremos $\mathcal{K}$ como el conjunto de los subconjuntos acotados (cerrados) del plano. Introducimos una distancia en $\mathcal{K}$ llamada distancia de Hausdorff. La definición de distancia de Hausdorff $d_H(B_1,B_2)$ , entre dos subconjuntos $B_1$ y $B_2$ es una fórmula compicada y confusa, por lo que explicaremos el concepto de otra manera. Comencemos por explicar qué significado queremos darle a la expresión

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

(incluso sin haber definido qué es $d_H(B_1,B_2)$ ). Esto significará únicamente que si nuestro ojo tiene precisión $\epsilon$ , entonces no pouede distinguir $B_1$ de $B_2$ . En términos matemáticos, $d_H(B_1,B_2) \leq \epsilon$ significaría

(3) $\begin{equation*}\forall P\in B_1\;\exists Q\in B_2 \: d(P,Q)\leq \epsilon \quad\text{y}\quad \forall P'\in B_2\;\exists Q'\in B_1 \: d(P',Q')\leq \epsilon. \end{equation*}$

(Aquí $d$ es la distancia euclídea usual en $\mathbb R^2$ .) Esto permite dar la siguiente definición indirecta.

Definición. La distancia de Hausdorff entre dos conjuntos cerrados y acotados $B_1$ y $B_2$ es el mínimo de todos los $\epsilon\geq0$ tales que se satisface (3).

Ahora debemos convencernos de que la función $W$ es una contracción. Supongamos que $d_H(B_1,B_2)\leq \epsilon$ . Entonces podemos probar que $d_H(W(B_1),W(B_2))\leq \frac{\epsilon}{2}$ . Sea $P\in W(B_1)$ ; se tiene que existen $i\in \{1,2,3\}$ y $P_1\in B_1$ tales que $P=T_i(P_1)$ . Como $d_H(B_1,B_2)\leq \epsilon$ , existe $Q_1\in B_2$ tal que $d(P_1,Q_1)<\epsilon$ . Sea $Q=T_i(Q_1)$ ; entonces $Q\in W(B_2)$ y $d(P,Q)= d(T_i(P_1),T_i(Q_1))=\frac12 d(P_1,Q_1)\leq\frac{\epsilon}{2}$ . Análogamente, si comenzamos con $P'\in W(B_2)$ entonces existe $Q'\in W(B_1)$ tal que $d(P',Q')\leq\frac{\epsilon}{2}$ .

Este proceso se ha adaptado a la compresión de imágenes reales (ver [K] o [RS]). El método produce imágenes de lata calidad cuando la imagen tiene carácter fractal. Sin embargo, la tasa de compresión no es tan buena ni tan flexible como en el formato JPEG. El proceso de codificación (transformar la imagen en un programa para reconstruirla) resulta todavía demasiado tedioso como para ser de interés práctico. Sin embargo, la simplicidad de la idea junto con su potencia siguen siendo llamativas.

4. Una aplicación sorprendente: el algoritmo PageRank

El éxito de Google como motor de búsqueda proviene de su algoritmo: el algoritmo PageRank. En este algoritmo se calcula el punto fijo de un operador lineal en ${\mathbb R}^n$ que es una contracción y cuyo punto fijo (que es un vector) produce la ordenación de las páginas. En la práctica, el punto fijo (que es un vector propio de valor propio $1$ ) se calcula aproximadamente como $P_n$ para $n$ suficientemente grande. Invitamos al lector a leer los detalles en la viñeta Cómo funciona Google.

5. Conclusión

En esta viñeta hemos probado cómo comenzando con un simple juego podemos descubrir ideas muy potentes que pueden llevar a importantes avances matemáticos y tecnológicos. En muchos campos de las matemáticas cuando se busca solución única a un problema, se ha convertido en un método estándar tratar de probar que dicha solución se puede caracterizar como el único punto fijo de un operador especialmente construido para ese propósito.

Hemos visto que la ventaja de esta aproximación es que el teorema proporciona un método práctico y eficiente para construir el objeto solución como el límite de una sucesión, ya que la convergencia es rápida.

El análisis matemático consiste en estudiar funciones. Las funciones se definen habitualmente sobre números. En el cálculo en varias variables se generaliza la noción de funciones a vectores que son elementos de ${\mathbb R}^n$ . ¿Por qué parar simplemente con elementos de ${\mathbb R}^n$ ? Hemos visto que a los matemáticos les gusta generalizar la nocion de función y definirlas, por ejemplo, en conjuntos de conjuntos, en conjuntos de funciones, etc. Hacer análisis en conjuntos de funciones se ha convertido en un importante capítulo del análisis moderno, llamado análisis funcional, materia estándar en los estudios de grado.

Se invita al lector a establecer el vínculo con cualquier otro proceso iterativo que conozca. Por ejemplo, el proceso iterativo en dimensión 1 asociado a la sucesión de Herón para hallar raíces cuadradas. La rápida convergencia geométrica se puede entender también desde el punto de vista presentado aquí.

Bibliografía

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

[K] J. Kominek, Advances in fractal compression for
multimedia applications, Multimedia Systems Journal, vol. 5,
n $^{o}$ 4, 1997, 255–270.

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

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

[RS] C. Rousseau and Y. Saint-Aubin, Mathematics and
technology, SUMAT Series, Springer-Verlag, 2008 (A French version of the book, Mathéematiques et technologie, exists, published in the same series.)

El microscopio de Banach para encontrar un punto fijo

Related

Leave a Reply Cancel reply

Receive notice of every new vignette.

Search

Meta

El microscopio de Banach para encontrar un punto fijo

Share this:

Related

Leave a Reply Cancel reply

Receive notice of every new vignette.

Search

Meta