Banach e seu microscópio para encontrar pontos fixos

Autor do original: Christiane Rousseau.
Neste artigo, começando com um pequeno jogo, vamos descobrir um dos mais potentes teoremas da matemática, a saber, o teorema do ponto fixo de Banach. Esse teorema tem aplicações maravilhosas tanto na matemática quanto em outras áreas. Na terceira parte deste artigo, veremos uma aplicação fascinante em compressão de imagens.

Vamos começar nosso jogo olhando mais de perto a famosa tampa de uma caixa de A Vaca Que Ri. (NT. A Vaca Que Ri é a marca de um queijo fundido comercializado em vários países, Brasil inclusive.)

O brinco na orelha direita da Vaca é novamente uma tampa da caixa de A Vaca Que Ri. A cada ponto da tampa pode-se associar o ponto correspondente no brinco da orelha direita. Obtém-se assim, com certeza, uma função da tampa nela mesma que chamaremos de $F$ . Por exemplo, associa-se a ponta do queixo da Vaca à ponta do queixo da pequena vaca do brinco. Associa-se o centro do olho direito da Vaca ao centro do olho direito da pequena vaca do brinco, etc. Eis agora a questão: Existe um ponto que é enviado nele mesmo por esse procedimento? Tal ponto, se existir, será chamado ponto fixo. Se um ponto fixo existir, ele não será nenhum dos pontos mencionados anteriormente. Além do mais, se um ponto fixo existir, ele deverá estar no brinco direito. Mas esse brinco direito é enviado para o brinco direito da vaca pequena, etc. Visualmente, percebe-se que esses brincos direitos encaixados parecem convergir para um ponto, que chamaremos de $A$ , e $A$ é um candidato para nossa solução.

Comecemos agora com um ponto qualquer, por exemplo, a extremidade do queixo da vaca, que chamaremos de $P_0$ . O ponto $P_0$ é enviado para $P_1=F(P_0)$ , que é a extremidade do queixo da pequena vaca no brinco direito. O ponto $P_1$ é enviado para $P_2=F(P_1)$ , que é a extremidade do queixo da pequena vaca no brinco direito, etc. Observamos três fatos:

Podemos continuar esse procedimento indefinidamente e construir assim uma sequência $\{P_n\}$ , com $P_{n+1}=F(P_n)$ .
Visualmente, é apenas um número finito de pontos que parecem ser distintos, os outros são indistinguíveis. Certamente pode-se dar um zoom e ver mais pontos. Mas, independentemente da potência do zoom, distinguiremos apenas um número finito de pontos, os outros parecerão sobrepostos
Essa sequência parece convergir para o ponto $A$ , definido anteriormente.

Se tivéssemos considerado outro ponto, $Q_0$ e construído a sequência $\{Q_n\}$ , com $Q_{n+1}=F(Q_n)$ , veríamos que a sequência $\{Q_n\}$ também parece convergir para o ponto $A$ . De fato, pode-se observar que isso ocorre porque o conjunto unitário $\{A\}$ é o conjunto intersecção de todos os brincos encaixados e seu diâmetro tende a $0$ .

O que o teorema do ponto fixo de Banach vai nos dizer? Vai nos dizer que, de fato, a função $F$ tem um único ponto fixo, isto é, existe um único ponto $A$ do plano tal que $F(A)=A$ . Além disso, o teorema estabelecerá que se considerarmos um ponto $P_0$ qualquer e construirmos a sequência $\{P_n\}$ , com $P_{n+1}=F(P_n)$ , a sequência $\{P_n\}$ vai convergir para $A$ .

Mas por quê? Isso aconteceria para qualquer função $F$ ? É claro que não. Por exemplo, uma translação no plano não tem pontos fixos. E a função $G(x,y)=(x+(x^2-1),y)$ tem dois pontos fixos : $(\pm 1,0)$ . A função $F$ do nosso jogo tem uma propriedade especial. Ela é uma contração. De fato, sua imagem é muito menor do que seu domínio. Se dois pontos $P$ e $Q$ estiverem a certa distância um do outro, suas imagens $F(P)$ e $F(Q)$ estarão mais próximas uma da outra do que $P$ e $Q$ . Essa afirmação tem sentido porque em ${\mathbb R}^2$ podemos medir a distância entre dois elementos. Isso acontece porque ${\mathbb R}^2$ é um espaço métrico. O fato de $F$ ser uma contração garante que ao construirmos a sequência $\{P_n\}$ , qualquer que seja o elemento de partida escolhido (se vamos olhar a sequência de longe, de perto, ou através de um microscópio, ou através de um microscópio eletrônico), após algum $N$ , que depende desse elemento de partida, todos os elementos $P_n$ , $n>N$ , da sequência tornar-se-ão indistinguíveis. Dois elementos são distinguíveis se a distância ente eles estiver acima de certo valor. Veremos na próxima seção que uma sequência com essa propriedade chama-se sequência de Cauchy. Em ${\mathbb R}^2$ , toda sequência de Cauchy é uma sequência convergente. Dizemos que ${\mathbb R}^2$ é um espaço métrico completo.

1. O teorema do ponto fixo de Banach

Temos, agora, todos os ingredientes necessários para o caso geral e podemos enunciar o teorema.

Teorema (do ponto fixo de Banach). Seja $\mathcal{K}$ um espaço métrico completo no qual a distância entre dois pontos $P$ e $Q$ é representada por $d(P,Q)$ . Seja $F:\mathcal{K}\rightarrow \mathcal{K}$ uma contração, isto é, existe $c\in(0,1)$ tal que para todos $P,Q\in \mathcal{K}$ , tem-se

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

Então $F$ tem um único ponto fixo, isto é, existe um único $A\in \mathcal{K}$ tal que $F(A)=A$ .

Vamos definir todos os termos que aparecem nessa afirmação. Essa parte é mais formal e pode ser deixada de lado se você preferir concentrar-se nas fascinantes aplicações.
Sabemos o que é distância entre dois pontos $P$ e $Q$ em ${\mathbb R}^2$ . Como generalizar esse conceito para um conjunto $\mathcal{K}$ ?

Definição. Distância em um conjunto $\mathcal{K}$ é uma função $d:\mathcal{K}\times \mathcal{K}\rightarrow {\mathbb R}$ satisfazendo

Para todo $P,Q\in \mathcal{K}$ , $d(P,Q)\geq0$ ;
$d(P,Q)=0$ se, e somente se, if $P=Q$ ;
Para todo $P,Q,R\in \mathcal{K}$ , $d(P,Q)\leq d(P,R)+d(R,Q);$ (desigualdade triangular).

Sabemos que essas condições são satisfeitas pela distância euclidiana usual em ${\mathbb R}^2$ .

Recordemos agora a definição de sequência de Cauchy, que é a formalização do conceito de uma sequência que, pouco importando o grau de precisão escolhido, após um número finito de elementos, todos os demais tornam-se indistinguíveis. Vamos recordar também a definição de sequência convergente.

Definição.

Uma sequência $\{P_n\}$ de elementos de um espaço métrico $\mathcal{K}$ é uma sequência de Cauchy se, para todo $\epsilon>0$ , existe $N\in {\mathbb N}$ tal que para todos $n,m>N$ , then
$d(P_n,P_m)<\epsilon.$
Uma sequência $\{P_n\}$ de elementos de um espaço métrico $\mathcal{K}$ converge para um limite $A\in \mathcal{K}$ se, para todo $\epsilon>0$ , existe $N\in {\mathbb N}$ tal que para todo $n>N$ ,
$d(P_n,A)<\epsilon.$

Definição. Um espaço métrico $\mathcal{K}$ é um espaço métrico completo se toda sequência de Cauchy $\{P_n\}$ é um espaço métrico completo se toda sequência de Cauchy $\mathcal{K}$ converge para um elemento $A$ de $\mathcal{K}$ .

Como se demonstra o teorema do ponto fixo de Banach ? É fácil provar a unicidade do ponto fixo. De fato, suponha que $A$ e $B$ sejam dois pontos fixos. Então $F(A)=A$ e $F(B)=B$ . Além disso, se $F$ é uma contração, então

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

Portanto, $d(A,B)\leq c\;d(A,B)$ . A única solução é $d(A,B)=0$ , o que acarreta $A=B$ .

Quanto à existência, a ideia da demonstração é igualmente simples: nós já a encontramos no jogo de A Vaca que Ri! Escolhemos um ponto qualquer $P_0\in \mathcal{K}$ e construímos (como antes) a sequência $\{P_n\}$ , com $P_{n+1}=F(P_n)$ . Essa é uma sequência de Cauchy e seu limite é um ponto fixo. ( É claro que provar essas duas afirmações requer algum trabalho, mas aqui vamos omitir os detalhes técnicos. O que importa é que a demonstração é a mesma quer no caso geral de um espaço métrico complicado, quer no caso simples de $\mathcal{K}={\mathbb R}$ .)

A ideia da demonstração não é apenas simples e intuitiva, mas é também muito potente. Ela nos fornece uma maneira de construir numericamente o ponto fixo $A$ . Isso explica o fato de muitas aplicações desse teorema serem encontradas tanto em questões teóricas como em suas aplicações.

2. Aplicações em Análise Matemática

Uma das aplicações teóricas muito importantes do teorema do ponto fixo de Banach é a demonstração da existência e unicidade de soluções de equações diferenciais suficientemente regulares. Nessa aplicação, o espaço métrico completo $\mathcal{K}$ é um conjunto de funções, e a função $F$ transforma uma função em outra função (dizemos muitas vezes que $F$ é um operador). O truque consiste em mostrar que uma solução da equação diferencial, se existir, é um ponto fixo do operador $F$ .

Talvez você tenha estudado equações diferenciais simples e aprendido artifícios para encontrar fórmulas para as soluções. Bem, essas equações diferenciais são exceções, pois para a maioria das equações diferenciais não existem fórmulas para a solução. Daí a importância de um teorema que garanta a existência de uma solução. Não lhe deve causar espanto que para a solução da maioria das equações diferenciais nenhuma fórmula pode ser dada. De fato, considere a simples equação diferencial

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

Sua solução é dada por

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

Você deve lembrar que no seu curso de Probabilidade ou de Estatística lhe contaram que não existe uma fórmula para a primitiva da função $e^{-x^2}$ , explicando, assim, porque é necessário trabalhar com tabelas quando se estuda a distribuição normal.

3. Aplicação à compressão de imagens

A melhor maneira de armazenar uma imagem na memória é armazenar a cor de cada pixel. Há dois problemas com esse método:

Exige uma quantidade enorme de memória.
Se tentarmos ampliar a imagem, para usá-la, por exemplo, num poster grande, os pixeis tornam-se quadrados grandes e não teremos suficientes informações para preencher os detalhes nesses quadrados.

Qual é o princípio da compressão de imagens? É codificar menos informação do que a imagem original, mas fazê-lo de uma maneira inteligente, de modo que os olhos não percebam que a imagem observada está deteriorada. A internet aumentou a necessidade de bons sistemas compressão de imagens. Imagens, de fato, diminuem significativamente a velocidade de navegação na internet. Portanto, para navegar na internet, é bom ter imagens codificadas em arquivos tão pequenos quanto possível. Quando você olha para a imagem na tela do seu computador você não percebe que ela foi deteriorada. Mas se você tentar ampliar essa imagem, ou imprimi-la num poster, você imediatamente percebe que a resolução da imagem é ruim.
Existem vários procedimentos de compressão de imagens e o mais comuns é o JPEG, que se tronou padrão para imagens digitais. A codificação de uma imagem em formato JPEG também é um algoritmo matemático.

Neste artigo vamos nos concentrar num outro método, que tem permanecido mais experimental. Esse método, introduzido por Barnsley, foi chamado sistema de funções iteradas. A ideia subjacente ao método é aproximar uma imagem por objetos geométricos. Para ter um número suficiente de objetos disponíveis, não nos limitaremos aos objetos geométricos usuais como retas e curvas, mas usaremos também figuras fractais complexas como a samambaia e o tapete de Sierpinski (veja as figuras à esquerda)

Vamos explicar a ideia do processo de compressão no tapete de Sierpinski, à esquerda. A priori, parece ser um objeto complicado. Como armazená-lo na memória de um computador de uma maneira econômica? A melhor maneira é armazenar um programa que o reconstruirá quando for necessário.

E para construir esse programa precisamos compreender o que caracteriza esse objeto geométrico. Observemos o tapete de Sierpinski: ele é a reunião de três tapetes de Sierpinski (isto é, três cópias de si mesmo) que têm a metade do seu tamanho (em largura e altura). De fato, começando com um tapete de Sierpinski, podemos construir um segundo tapete com o seguinte procedimento:

A partir do vértice inferior esquerdo, encolhemos o tapete de Sierpinski, até sua metade.
Fazemos uma segunda cópia desse meio tapete de Sierpinski e a colamos à direita da primeira.
Fazemos uma terceira cópia desse meio tapete de Sierpinski e a colamos acima das outras duas.

A segunda figura que construímos é idêntica ao nosso o tapete de Sierpinski inicial. Portanto o tapete de Sierpinski é o ponto fixo do processo.

Vamos escrever isso em termos matemáticos. Observe que o comprimento da base do tapete de Sierpinski é igual à sua altura. Então, podemos escolher eixos com origem no canto inferior esquerdo do tapete de Sierpinski e unidades nos eixos tais que a base e a altura tenham ambos comprimento $1$ .
Também construímos a seguinte transformação afim, definida em ${\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*}$

Se $S$ é o tapete de Sierpinski, temos

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

Será que existem outros subconjuntos $B$ do plano que têm a mesma propriedade, a saber :

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

Vamos fazer uma experiência e verificar que a resposta é não. Assim, caracterizamos nosso tapete de Sierpinski como sendo o único subconjunto B do plano que satisfaz (1). O que fizemos? Construímos uma função que associa um subconjunto $B$ do plano ao subconjunto $T_1(B)\cup T_2(B)\cup T_3(B)$ . Vamos chamar essa função de $W$ . Ela é definida por

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

e vimos que $S=W(S)$ , isto é, $S$ é um ponto fixo dessa função.

Dissemos que faríamos uma experiência para mostrar que o tapete de Sierpinski é o único ponto fixo dessa função.Tentemos com um quadrado $C_0$ como na Figura 1(a). Sua imagem é $C_1$ na Figura 1(b). Aplicamos o mesmo processo a $C_1$ e obtemos $C_2$ , $C_3$ – $C_5$ . (Figura 1 (c)-(f)).

Figura 1

Observamos três fatos:

Nenhum dos conjuntos $C_0$ , …, $C_5$ é um ponto fixo de $W$ .
Poderíamos ter continuado o processo indefinidamente, produzindo uma sequência infinita de conjuntos $\{C_n\}$ , com $C_{n+1}=W(C_n)$ .
A sequência $\{C_n\}$ parece convergir rapidamente para o tapete de Sierpinski. De fato, nossos olhos não conseguem distinguir $C_{10}$ de $S$ . Então, no lugar de $S$ , o programa de reconstrução da nossa imagem pode simplesmente produzir $C_{10}$ . E, se uma resolução melhor for necessária, usaremos o mesmo programa mandando-o parar em $C_{20}$ , ou $C_{30}$ . Assim, o mesmo pequeno programa pode reconstruir $S$ com precisão arbitrária.

Além disso, pode-se refazer essa experiência e ver que ela funciona com qualquer conjunto de partida. Um segundo exemplo com um pentágono é mostrado na Figura 2. As mesmas observações i, ii e iii acima podem ser aplicadas a esse exemplo.

Figura 2

Vimos que o teorema do ponto fixo de Banach se aplica às contrações em espaços métricos completos. Em (2) definimos a função $W$ para subconjuntos do plano. O espaço métrico $\mathcal{K}$ a ser considerado será o conjunto dos subconjuntos (fechados) limitados do plano. Vamos introduzir uma distância em $\mathcal{K}$ chamada distância de Hausdorff. A definição de distância de Hausdorff, $d_H(B_1,B_2)$ , entre dois subconjuntos $B_1$ e $B_2$ é uma fórmula obscura e complicada; por isso explicaremos essa noção de uma maneira diferente. Começaremos, explicando o significado que é dado à expressão

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

(mesmo que não tenhamos definido o significado de $d_H(B_1,B_2)$ ). A expressão nos diz que se nossos olhos tiverem uma precisão $\epsilon$ , eles não conseguirão distinguir $B_1$ de $B_2$ . Em termos matemáticos, $d_H(B_1,B_2) \leq \epsilon$ significa

(3) $\begin{equation*}\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. \end{equation*}$

(aqui $d$ é a distância euclidiana usual em $\mathbb R^2$ .) Isso nos permite dar a seguinte definição indireta.

Definição. A distância de Hausdorff entre dois conjuntos fechados e limitados $B_1$ e $B_2$ é o mínimo de todos os $\epsilon\geq0$ tais que a condição (3) é satisfeita.

Podemos nos convencer agora que a função $W$ é uma contração. De fato, suponha que $d_H(B_1,B_2)\leq \epsilon$ . Então podemos mostrar que $d_H(W(B_1),W(B_2))\leq \frac{\epsilon}{2}$ . Seja $P\in W(B_1)$ . Então existe $i\in \{1,2,3\}$ e $P_1\in B_1$ tais 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$ . sera $Q=T_i(Q_1)$ . Então $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}$ . Analogamente, se começarmos com $P'\in W(B_2)$ existe $Q'\in W(B_1)$ tal que $d(P',Q')\leq\frac{\epsilon}{2}$ .

Esse processo foi adaptado para a compressão de imagens reais (ver [K] ou [RS]. O método produz imagens de ótima qualidade quando a imagem original tem caráter fractal. No entanto o nível de compressão não é tão flexível, nem tão eficiente como o formato JPEG. Também, o processo de codificação (transformando a imagem em um programa para reconstruí-la) é ainda demasiadamente complexo para ter interesse prático. No entanto, a simplicidade da ideia juntamente com sua potência continua sendo impressionante e muito sedutora.

4. Uma aplicação surpreendente: o algoritmo PageRank

O sucesso de Google como instrumento de busca vem do seu algoritmo: o algoritmo PageRank. Nesse algoritmo calcula-se um ponto fixo de um operador linear em ${\mathbb R}^n$ que é uma contração e esse ponto fixo (que é um vetor) produz a ordenação das páginas. Na prática, o ponto fixo (que é um autovetor do autovalor 1) é calculado aproximadamente como $P_n$ para $n$ suficientemente grande. Convidamos o leitor interessado olhar os detalhes no artigo Como Google funciona ?

5. Conclusão

Vimos neste artigo como, a partir de um simples jogo, podemos descobrir ideias muito poderosas que podem levar a maiores avanços na matemática e na tecnologia. Quando procuramos uma solução única de um problema, é normal hoje em dia, em vários domínios da matemática, tentar ver se a solução do problema pode ser caracterizada como sendo o único ponto fixo de um operador especialmente construído para esse fim.

Vimos que a vantagem desse procedimento é que o teorema fornece um método eficiente e concreto de construir a solução como o limite de uma sequência porque a convergência é rápida.

Análise Matemática é o estudo de funções. Funções são geralmente definidas em conjuntos numéricos. Na análise de várias variáveis, generaliza-se a noção de funções para vetores que são elementos de ${\mathbb R}^n$ ? Mas por que parar nos elementos de ${\mathbb R}^n$ ? Vimos também que os matemáticos gostam de generalizar a noção de funções e se permitem defini-las, por exemplo, em conjuntos de conjuntos, em conjuntos de funções, etc. Análise em conjuntos de funções é atualmente um capítulo importante da análise moderna, chamada análise funcional que é standard em estudos de pós graduação.

Você está convidado a estabelecer um elo com algum processo iterativo que você tenha encontrado. Por exemplo, com os processos iterativos em dimensão 1, associados às sequências de Heron, para obter raízes quadradas. A convergência rápida das sequências geométricas pode igualmente ser compreendida sob o ponto de vista explicado neste artigo.

Bibliografia

[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.)

Este post está disponível em: Inglês, Francês, Italiano, Espanhol, Árabe, Khmer

Banach e seu microscópio para encontrar pontos fixos

Leave a Reply Cancel reply

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta

Banach e seu microscópio para encontrar pontos fixos

Share this:

Leave a Reply Cancel reply

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta