O método do Ponto Fixo

\author{Prof. Doherty Andrade}
\date{}

\section{Introdução}
Estamos ainda interessados em resolver equações não lineares
$f(x)=0$, mas agora sob outro enfoque. Dizemos que $c$ é um ponto
fixo para $f$ se $f(c)=c$. Podemos sempre transformar o problema
$f(x)=0$ em um problema de determinar um ponto fixo. De fato, se
$f(x)=0$, então $x+f(x)= x$ e assim, tomando $\phi(x)= x+ f(x)$,
ficamos com o problema de ponto fixo $\phi(x)=x$. Por outro lado,
se temos $\phi(x)=x$, então $\phi(x)-x=0$. Logo, tomando $f(x)=
\phi(x)-x$ ficamos com o problema $f(x)=0$. Portanto, os problemas
determinar raiz e determinar ponto fixo são
equivalentes. Alertamos que a função $\phi$ deve ter propriedades importantes para o método funcionar.

Iterar é uma palavra de origem grega que significa repetir. Os
métodos iterativos são métodos baseados na repetição de um
procedimento.

\section{Métodos iterativos estacionários}
Um método iterativo estacionário de passo $s\geq 1$ é um método
que gera uma sequência $(x_n)$ dada por
$$x_{n+1}= \phi(x_{n-s+1}, x_{n-s+2}, \ldots,x_n).$$

Note que métodos iterativos de passo $s$ necessitam de $s$
informações anteriores. Um método estacionário de passo 1 é da
forma
$$x_{n+1}= \phi(x_n), n \geq 0.$$

Se $\phi$ muda a cada iteração, isto é,
$$x_{n+1}= \phi_{n+1}(x_{n-s+1}, x_{n-s+2}, \ldots,x_n)$$ o método
é dito não estacionário.

Os métodos iterativos geram uma sequência infinita $(x_k)$ que
converge para a solução, assim há a necessidade de critérios de
parada. Isto é, quando devemos interromper os cálculos. Dada um
tolerância $\varepsilon>0$, os seguintes critérios são comumente
utilizados como critérios de parada\index{critérios! de parada}:

\begin{enumerate}
\item $|f(x_k)|< \varepsilon$;
\item $|x_{k+1}-x_k|< \varepsilon$;
\item $\displaystyle\frac{|x_{k+1}-x_k|}{|x_{k+1}|}< \varepsilon$;
\item o método pára após $N$ iterações.
\end{enumerate}

\section{O método do ponto fixo}
O método das aproximações sucessivas ou o método do ponto fixo
gera uma sequência $(x_n)$ utilizando a seguinte lei
\begin{equation} \displaystyle x_{n+1}= \phi(x_n), n
\geq 0,
\end{equation}
onde a aproximação inicial $x_0$ é deve ser fornecida para iniciar
o procedimento.

Duas perguntas surgem no estudo dos métodos iterativos
estacionários de passo 1, como é o caso do método do ponto fixo:\\
(a) Quando a sequência $(x_n)$ converge?\\
(b) Se converge, com que velocidade?

O seguinte resultado responde à primeira pergunta.

Teorema 1 (Ponto Fixo) Seja $\phi:[a,b] \rightarrow [a,b]$ contínua com
$\phi^\prime $ contínua em $(a,b)$. Suponha que $|\phi^\prime
(x)|\leq M<1$ para algum $M \geq 0$ e todo $x \in (a,b)$. Então, para $x_0 \in [a,b]$ tem-se:

(a) $x_{n+1}=\phi(x_n)$ pertence ao intervalo $[a,b],\forall n \geq 0$.

(b) $\displaystyle\lim_{n \to \infty} x_n=c,$ para algum $c \in [a,b]$.

A demonstração do item (a) é óbvio. Para o item (b) notemos que se $x, y \in (a,b)$
então, pelo teorema do valor médio existe $\xi$ entre $x$ e $y$ tal que
$$\frac{\phi(y)-\phi(x)}{y-x}= \phi^\prime (\xi).$$

Donde segue
que $$|\phi(y)-\phi(x)| =|\phi^\prime (\xi)||y-x|\leq M|y-x|,$$ e
$\phi$ é uma contração.

Agora mostraremos que $x_n$ é uma sequência de Cauchy e portanto
convergente e, portanto, convergene em $\R$.

Primeiramente, notemos que por indução
$$|x_{n+1}-x_n| \leq M^n
|x_{1}-x_{0}|.$$

No caso geral,temos
\begin{eqnarray*}
|x_{n+k}-x_n|&= &|x_{n+k}-x_{n+k-1}+x_{n+k-1}-x_{n+k-2}+x_{n+k-2}-
\cdots – x_n|\\
&\leq & |x_{n+k}-x_{n+k-1}|+ |x_{n+k-1}-x_{n+k-2}|+ \cdots
+|x_{n+1}-x_{n}|\\
&\leq & M^{n+k-1}|x_1-x_0|+ M^{n+k-2}|x_1-x_0|+ \cdots +
M^{n}|x_1-x_0| \\
&\leq& \frac{M^n}{1-M}|x_1-x_0|.
\end{eqnarray*}

Como $M<1$ segue que $M^n \to 0$ e portanto $|x_{n+k}-x_n| \to 0$
quando $n \to \infty$. Assim, a sequência é de Cauchy em
$\mathbb{R}$, sendo convergente para algum $c \in [a,b]$.

Agora vamos provar que $c =\lim x_n$ é solução de $x=\phi(x)$. De
fato, $$c= \lim_{n \to \infty} x_{n+1}= \lim_{n \to \infty}
\phi(x_{n})= \phi( \lim_{n \to \infty}x_{n})=\phi(c).$$ Assim, $c$
é solução do problema de ponto fixo $x= \phi(x)$.

Provar que $c$ é a única solução é fácil, pois se $c$ e $c_1$ são
soluções, então
$$ |c- c_1|= | \phi(c)- \phi(c_1)| \leq M|c-c_1|,$$ como $M<1$,
seque que $c=c_1.$

Para responder à segunda pergunta vamos precisar da seguinte
definição.

Definição: Dado uma sequência $(x_n)$ convergente para $\alpha$ seja
$E_n= x_n-\alpha.$ Se existe um real $p \geq 1$ e $c \neq 0$ tais
que
$$ \lim_{n \to \infty} \frac{|E_{n+1}|}{|E_n|^p}=c,$$
dizemos que a ordem de convergência da sequência é $p$. Se $p=1$
dizemos que a ordem de convergência é linear, se $p=2$ dizemos que
a ordem de convergência da sequência é quadrática.

Dizemos que um método iterativo é de ordem $p$ para a raiz
$\alpha$ , se ele gera uma sequência que converge para $\alpha$
com ordem de convergência $p$.

Teorema 2: Sob as hipóteses do Teorema do Ponto Fixo, a ordem de
convergência de $x_{n+1}= \phi(x_n), n \geq 0$, gerada pelo método
do ponto fixo, é $p=1$.

De fato, pelo teorema do valor médio, existe $\xi_n$ entre
$x_{n-1}$ e $c$ tais que
$$x_n-c= \phi(x_{n-1})- \phi(c)= \phi^\prime(\xi_n)(x_{n-1}-c).$$
Assim,
$$
\frac{|x_n-c|}{|x_{n-1}-c|}= |\phi^\prime(\xi_n)|.
$$
Fazendo $n \to \infty$, obtemos

$$ \lim_{n \to \infty}\frac{|x_n-c|}{|x_{n-1}-c|}=
|\phi^\prime(c)|.$$ Isto responde à segunda pergunta.

Note que $\phi(x)=x$ tem solução quando os gráficos de $y=\phi(x)$
e $y=x$ se cruzam.

Exemplo 1: A equação $x^3-x-5=0$ pode ser
reescrita como $x=x^3-5=0$ ou $x= (x+5)^{\frac 13}$ ou ainda $x=
\displaystyle \frac{5}{x^2-1}.$ A forma da equação a ser escolhida
depende da raiz a ser localizada e se a função satisfaz às
condições do Teorema do Ponto Fixo.

Exemplo 2: A equação $\ln x-x+2=0$ pode ser
reescrita como $x=\displaystyle\underbrace{\ln x+2}_{=\phi(x)}$ ou
$x= \displaystyle\underbrace{\exp(x-2)}_{=\phi_1(x)}$. A equação
$\ln x-x+2=0$ possui solução nos intervalos $(0,1)$ e $(3,4)$.
Observe que $|\phi^\prime (x)|= \vert \frac 1x \vert < 1$ em
$(3,4)$ e $|\phi_1^\prime (x)|= \phi_1 (x)< 1$ em $(0,1)$.

\subsection{O algoritmo}
Dado $f(x)=0$ escreva como $\phi(x)=x$. Seja $x_0$ aproximação
inicial, $\varepsilon>0$ tolerância. Faça:

1. Se $|f(x_0)| < \varepsilon$ faça $c= x_0$ e pare.

2. $k=1$.

3. $x_1=\phi(x_0)$.

4. Se $|f(x_1)|<\varepsilon$ ou $|x_1-x_0|< \varepsilon$ faça
$c=x_1$ e pare.

5. $x_0=x_1$

6. $k=k+1$ e volte ao passo 3.

\subsection{Método Prático}

Uma maneira prática de utilizar o
método das aproximações sucessivas é dispor os cálculos em uma
tabela como mostrado a seguir na tabela.

Nesse exemplo,
$f(x)=2+\ln(x)=0$ e $\phi(x)=\exp(x-2)=x$ no intervalo
$[0.1,1.5]$. Note que
$|\phi^\prime(x)| <1$ no intervalo.