Iteração de ponto fixo

Se na aula passada nós conhecemos um tipo de equação não linear particular, a equação de ponto fixo \begin{equation}\label{eqpf} \phi(x) = x, \end{equation} e vimos uma forma de construir uma sequência que convergiu à solução dessa equação, não ficou claro por que essa estratégia faz sentido ou funcionou.

Para começar essa análise, vamos à primeira pergunta. Será que a equação \eqref{eqpf} sempre tem solução? No vídeo vimos um exemplo simples que já joga por terra essa esperança. Basta considerar a função $\phi(x) = x+1$. Fica claro que para essa função não pode haver ponto fixo.

De forma mais geométrica, $\phi$ ter ponto fixo pode ser interpretado como o gráfico de $\phi$ interceptar o gráfico de $y=x$. De forma analítica, podemos usar o teorema de Bolzano, aplicado à função $f(x) \equiv \phi(x)-x$. Ou seja, $\phi$ for contínua e se houver $[a,b]$ onde $f(a)\cdot f(b) <0$, certamente $f$ terá um zero e portanto $\phi$ terá ponto fixo. Outra condição que pode ser imposta é que $\phi(x) \in [a,b]$, sempre que $x\in [a,b]$. Se $\phi(a)=a$ ou $\phi(b)=b$ já teríamos um ponto fixo e o problema estaria encerrado. Caso isto não ocorra, então obrigatoriamente $\phi(a) > a$ e $\phi(b) < b$. Portanto a função $f$ troca de sinal no intervalo $[a,b]$ e, novamente, o teorema de Bolzano assegura a existência de um zero para $f$, ponto fixo de $\phi$.

A segunda pergunta é se a existência de ponto fixo é suficiente para garantir o êxito da iteração de ponto fixo, dada por \begin{equation}\label{ipf} x_{k+1} = \phi(x_k), \quad k=0,1,2,\ldots, \end{equation} para $x_0$ dado.

Essa pergunta pode ser escrutinada com o auxílio do teorema de Taylor. Seja $x_*$ seja o ponto fixo de $\phi$, e suponha que $\phi$ tenha a primeira derivada contínua em $[a,b]$, então $$ \phi(x) = \phi(x_*) + \phi'(\xi)(x-x_*),$$ para algum $\xi$ entre $x$ e $x_*$. Com isso, temos que \begin{equation}\label{erro} (x_{k+1} - x_*) = \phi(x_k) - \phi(x_*) = \phi'(\xi)(x_k-x_*), \end{equation} onde $\xi$ está entre $x_{k+1}$ e $x_*$ e usamos que $x_* = \phi(x_*)$. Logo, $$ |e_{k+1}| \equiv |x_{k+1} - x_*| \le |\phi'(\xi)| |x_k-x_*| = |\phi'(\xi)||e_k|. $$ Se $|\phi'(x)| \le M \lt 1,$ para todo $x\in[a,b]$, concluímos que a iteração é convergente, uma vez que $$ 0 \le \lim_{k\rightarrow \infty}|e_{k+1}| \le \lim_{k\rightarrow \infty} M^{(k+1)}|e_0| = 0. $$

O exemplo abaixo mostra um caso em que a iteração de ponto fixo é de fato convergente.

Nesta figura também conseguimos ver, geometricamente, como os iterandos são produzidos. A partir de $x_0$, escolhido arbitrariamente, é computado $\phi(x_0)$, cujo valor é obtido pela intersecção do segmento tracejado vertical partindo de $x_0$ e atingindo o gráfico de $\phi$, ou seja $y_1 = \phi(x_0)$. Para transpor esse valor, do eixo $y$ para o eixo $x$, buscamos o ponto de altura $y_1$ sobre a reta $y=x$, ou seja a intersecção de um segmento horizontal, partindo de $y_1$ no eixo $y$, com o gráfico da função $y=x$. Este ponto de intersecção tem como coordenada $x$ o valor $x_1 = y_1 = \phi(x_0)$. O processo é então repetido para obter os pontos seguintes.

Já o exemplo a seguir ilustra uma situação em que a sequência gerada diverge.

O que distinguiu os dois exemplos anteriores foi justamente a inclinação de $\phi$.

Por fim, quando temos convergência, a velocidade de convergência é ao menos linear. Isto é consequência de \eqref{erro}, uma vez que $$ \lim_{k\rightarrow \infty} \frac{x_{k+1}-x_*}{x_k-x_*} = \phi'(x_*).$$

O teorema a seguir sumariza todos esses resultados.

Teorema: Seja $\phi:[a,b]\rightarrow \mathbb{R}$. Se $\phi(x) \in [a,b]$ e existe $M\lt 1$, tal que $|\phi'(x)| \le M$, para todo $x \in [a,b]$, então existe um único $x_* \in [a,b]$ tal que $\phi(x_*) = x_*$. Além disso, a sequência gerada pela iteração de ponto fixo converge a $x_*$, para qualquer $x_0 \in [a,b]$, com taxa de convergência ao mínimo linear, satisfazendo $$ \lim_{k\rightarrow \infty} \frac{x_{k+1}-x_*}{x_k-x_*} = \phi'(x_*).$$

Sobre o teorema acima, existem condições mais fracas que garantem a convergência da iteração de ponto fixo. A função de iteração $\phi$ nem mesmo precisa ser diferenciável. Basta que $\phi$ seja uma contração, ou seja, que exista $0 \le L \lt 1$, tal que $$ |\phi(x) - \phi(y)| \le L |x-y|, $$ para todo $x$ e $y$. O teorema mais famoso sobre ponto fixo e contrações é o teorema do ponto fixo de Banach , um resultado muito importante, mas que já escapa ao alcance desta aula.

Ponto fixo em outros contextos

Essa conversa sobre ponto fixo começou pelo tratamento de um equação não linear particular. Pode parecer algo um tanto quanto restrito, não? Mas na verdade vários métodos iterativos se encaixam nessa estrutura da iteração de ponto fixo. Até agora vimos pelo menos um caso desses, o método de Newton. Lembre que a iteração de Newton é $$ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}. $$ Se definirmos $\phi(x) \equiv x - f(x)/f'(x)$, a iteração acima fica com a cara de uma iteração de ponto fixo para essa função $\phi$.

Outros métodos que veremos nesse curso que também podem ser interpretados como iterações de ponto fixo são os métodos de Jacobi e de Gauss-Seidel, assim como alguns métodos para resolução de equações diferenciais.

Referências

Anne Greenbaum e Timothy P. Chartier. Numerical Methods: Design, Analysis, and Computer Implementation of Algorithm. Princeton University Press, 2012.

A. Quarteroni e F. Saleri. Cálculo Científico com MATLAB e Octave. Springer, 2007.

1. Verifique que $\phi(x) = 3x^2-5$ tem dois pontos fixos. Determine-os analiticamente. A iteração de ponto fixo seria convergente a algum dos dois?

2. Se $x_*$ é ponto fixo de $\phi$ do exercício anterior, verifique $x_*$ também é ponto fixo de $\gamma(x) = 5 / (3x-1)$. Tente determinar $x_*$ através da iteração de ponto fixo aplicada a $\gamma$. Os dois pontos fixos podem ser obtidos assim? Justifique.

3. Se você digitar um número qualquer na calculadora e depois apertar incansavelmente a tecla da função seno, o que deve acontecer? Justifique. Lembre de ajustar a calculadora para trabalhar em radianos.