Iteração de ponto fixo
# Iteração de ponto fixo

Em análise numérica, iteração de ponto fixo é um método de se calcular pontos fixos de funções. Ponto fixo de dada função f{\textstyle f} é o número x$^∗${\textstyle x^{*}} que quando aplicado na função resulta nele mesmo, i.e. f(x$^∗$)=x$^∗${\textstyle f(x^{*})=x^{*}}. Dada uma aproximação inicial x$_0${\textstyle x_{0}} para $x^{*}$, o método consiste em iterar sucessivamente a função dada sobre x$_0${\textstyle x_{0}}. Ou seja, constrói-se a sequência x$_{n+1}$=f$^{n+1}$(x$_0$)=f$^n$(f(x$_0$)){\textstyle x_{n+1}=f^{n+1}(x_{0})=f^{n}(f(x_{0}))} sendo cada x$_n${\textstyle x_{n}} uma nova aproximação do ponto fixo x$^∗${\textstyle x^{*}}. Uma importante aplicação deste método aparece no cálculo numérico de soluções de equações de uma variável real.

## Descrição

Seja f:[a, b]⊂R→[a, b]{\textstyle f:[a, b]\subset \mathbb {R} \to [a, b]} uma função com um único ponto fixo x$^∗$∈[a, b]{\textstyle x^{*}\in [a, b]}, o qual buscamos determinar. A iteração do ponto fixo consiste em construirmos a sequência recursiva:
    $x_{n+1}=f(x_{n}),\quad n=0,1,2,\ldots ,$
sendo x$_0$∈[a, b]{\textstyle x_{0}\in [a, b]} uma aproximação inicial de x$^∗${\textstyle x^{*}}. Para certas funções, tem-se que a sequência $(x_{n})_{n}$ converge para o ponto fixo x$^∗${\textstyle x^{*}}. Por exemplo, o teorema da convergência enunciado abaixo, garante que a convergência do método do ponto fixo para contrações.

## Solução de equações

Existem diversas maneiras de usar o método para obter a raiz de uma função f(x){\textstyle f(x)}. A ideia fundamental é reescrever a equação f(x)=0{\textstyle f(x)=0} em uma equação equivalente da forma:
    $g(x)=x$
i.e., em um problema de ponto fixo. Se g(x){\textstyle g(x)} é uma função para a qual o método do ponto fixo converge, então a sequência:
    $x_{n+1}=g(x_{n}),\quad n=0,1,\ldots ,$
com x$_0${\textstyle x_{0}} uma aproximação inicial da solução, converge para o ponto fixo x$^∗${\textstyle x^{*}} da função g{\textstyle g}. Notemos que o ponto fixo x$^∗${\textstyle x^{*}} é também solução da equação $f(x)=0$.

### Exemplo

Há muitas maneiras de manipular uma equação de forma a utilizar o método do ponto fixo. É importante observar que, apesar da simplicidade do método, este pode não convergir dependendo da função (veja, abaixo, o Teorema da Convergência para condições suficientes de convergência). No seguinte exemplo, buscamos mostrar este fato.
Buscaremos aproximar a solução da equação xe$^x$=10{\textstyle xe^{x}=10} usando o método do ponto fixo. Notemos que essa equação é equivalente a $x=10e^{-x}$ e $x=ln\left({10 \over x}\right)$.
Ao efetuarmos o processo iterativo para a primeira equação, i.e. x$_{n+1}$=10e$^{−xn}${\textstyle x_{n+1}=10e^{-x_{n}}}, com $x_{0}=1$, obtemos a seguinte sequência:
$x_{0}=1$
$x_{1}=10e^{-1}=3.6787944$
$x_{2}=10e^{-3.6787944}=0.2525340$
$x_{3}=10e^{-0.2525340}=7.7682979$
$x_{4}=10e^{-7.7682979}=0.0042293$
$x_{5}=10e^{-0.0042293}=9.9577961$
E quando realizamos o processo com a outra equação, i.e. $x_{n+1}=ln\left({10 \over x_{n}}\right)$, e novamente iniciarmos o processo com $x_{0}=1$, a nova sequência se da por:
$x_{0}=1$
$x_{1}=ln\left({10 \over 1}\right)=2.3025851$
$x_{2}=ln\left({10 \over 2.3025851}\right)=1.4685526$
$x_{3}=ln\left({10 \over 1.4685526}\right)=1.9183078$
$x_{4}=ln\left({10 \over 1.9183078}\right)=1.6511417$
$x_{10}=1.7421335$
$x_{20}=1.7455151$
$x_{30}=1.745528$
$x_{31}=1.745528$
O teste realizado com as duas equações indica que, apesar delas serem equivalentes, a primeira não é convergente enquanto a segunda equação converge para o valor de $1.745528$ (que é a solução aproximada de xe$^x$=10{\textstyle xe^{x}=10}). As condições para que uma equação convirja para o valor de ponto fixo estão contidas no teorema de convergência.

## Teorema de convergência

Seja f:[a, b]→[a, b]{\textstyle f:[a, b]\rightarrow [a, b]} uma função contração, i.e. uma função que satisfaça:
    $|f(x)-f(y)|\leq \alpha |x-y|,\quad \alpha <1,\quad \forall x,y\in [a,b].$
Então, existe um único ponto x$^∗${\textstyle x^{*}} pertencente ao intervalo $[a,b]$ tal que f(x$^∗$)=x$^∗${\textstyle f(x^{*})=x^{*}}. Além disso, para qualquer $x_{0}\in [a,b]$, a sequência $(x_{n})_{n}$ dada por:
    $x_{n+1}=f(x_{n}),\quad n=0,1,2,\ldots ,$
converge para x$^∗${\textstyle x^{*}} quando $n\to \infty$.
Demonstração:
Existência. Caso $f(a)=a$ ou $f(b)=b$ o ponto fixo existe nos extremos. Caso contrário, então $f(a)>a$ e $f(b)<b$. Neste caso, seja:
    $h(x)=f(x)-x$
Como $f$ é uma função contínua, $h$ também é. Notemos que:
    $h(a)=f(a)-a>0$ e $h(b)=f(b)-b<0$
ou seja, $h$ troca de sinal no intervalo $[a,b]$. Logo, pelo Teorema do valor intermediário, garantimos a existência de um ponto $x^{*}\in (a,b)$ tal que $h(x^{*})=0$. Esse valor $x^{*}$ é um ponto fixo de $f$, uma vez que
    $h(x^{*})=f(x^{*})-x^{*}=x^{*}-x^{*}=0$
Unicidade. Suponhamos que $x^{*}$ e $x^{**}$ sejam pontos fixos distintos de $f$. Então: $|x^{*}-x^{**}|=|f(x^{*})-f(x^{**})|\leq \alpha |x^{*}-x^{**}|\Rightarrow \alpha \geq 1$ o que é uma contradição.
Convergência. Seja $(x_{n})_{n}$ a sequência iterada $x_{n+1}=f(x_{n})$ com $x_{0}\in [a,b]$ e $x^{*}$ o ponto fixo de $f$. Então, temos: $|x_{n+1}-x^{*}|=|f(x_{n})-f(x^{*})|\leq \alpha |x_{n}-x^{*}|,\quad n=1,2,\ldots$ Isso implica que: $|x_{n+1}-x^{*}|\leq \alpha ^{n}|x_{1}-x^{*}|,\quad n=1,2,\ldots$ Como $0\leq \alpha <1$, temos que $x_{n}\to x^{*}$ quando $n\to \infty$. Isso completa a demostração.

### Observações

* A desigualdade estrita α<1{\textstyle \alpha <1} é necessária.
* A condição f([a, b])⊂[a, b]{\textstyle f([a, b])\subset [a, b]} é necessária.
* Determinar os pontos fixos de uma função f(x){\textstyle f(x)} é determinar a interseção entre as curvas y=f(x){\textstyle y=f(x)} e y=x{\textstyle y=x}.
* A condição |f(x)−f(y)|≤α|x−y|{\textstyle |f(x)-f(y)|\leq \alpha |x-y|} é satisfeita sempre que $|f'(x)|\leq \alpha <1$ para todo x{\textstyle x}, pois:
    $|f(x)-f(y)|=\left|{\int _{x}^{y}}{f'(s)}ds\right|\leq {\int _{x}^{y}}{\alpha }ds=\alpha |x-y|,\quad (x<y)$.

## Teste de convergência

Seja $f:[a,b]$ uma função $C^{0}[a,b]$ e $x^{*}\in (a,b)$ um ponto fixo de $f$. É dito que $x^{*}$ é um ponto fixo estável caso exista uma região$(x^{*}-\Delta x,x^{*}+\Delta x)$ chamada de bacia de atração tal que $x^{(n+1)}=f(x^{(n)})$ é convergente sempre que $x^{(0)}\in (x^{*}-\Delta x,x^{*}+\Delta x)$.

### Teorema

Se $f\in [a,b]$ e $|f'(x^{*})|$ < $1$, então $x^{*}$ é estável. Se $|f'(x^{*})|$ > $1$ é instável e o teste é inconclusivo caso $|f'(x^{*})|=1$.

### Exemplo

Considerando o problema de encontrar a solução da equação $cos(x)=x$ analisando a equação como ponto fixo da função $f(x)=cos(x)$. A demonstração do Teorema do ponto fixo pode ser aplicado na função com o intervalo $[a,b]=[1/2,1]$.
Para provar que $f([1/2,1])\subset [1/2,1]$ basta analisar que $f(x)$ é decrescente no intervalo:
$0,54$ < $cos(1)\leq cos(x)\leq cos(1/2)$ < $0,88$
$f([1/2,1])\subset [1/2,1]$ é verdade pois $[0.54,0.88]\subset [1/2,1]$.
Agora para provar $|f(x)-f(y)|\leq \alpha |x-y|,\alpha$ < $1$ observamos que $f'(x)=-sen(x)$, dessa forma temos a estimativa :
$-0,85$ < $-sen(1)\leq -sen(x)\leq -sen(1/2)$ < $-0,47$
Assim temos que $|f'(x)|$ < $0,85$ e dessa forma $\alpha =0,85$ < $1.$
Agora observamos o processo numérico da sequência fazendo $x^{(n+1)}=cos(x^{(n)})$, iniciando com $x^{(0)}=1$, obtemos a sequência:
$x^{(1)}=cos(x^{(0)})=cos(1)=0,5403023$
$x^{(2)}=cos(x^{(1)})=cos(0,5403023)=0,8575532$
$x^{(3)}=cos(x^{(2)})=cos(0,8575532)=0,6542898$
$x^{(4)}=cos(x^{(3)})=cos(0,6542898)=0,7934804$
$x^{(5)}=cos(x^{(4)})=cos(0,7934804)=0,7013688$
$x^{(11)}=cos(x^{(10)})=cos(0,7442374)=0,7356047$
$x^{(12)}=cos(x^{(11)})=cos(0,7356047)=0,7414251$
$x^{(13)}=cos(x^{(12)})=cos(0,7414251)=0,7375069$
$x^{(41)}=cos(x^{(40)})=cos(0,7390852)=0,7390851$
$x^{(42)}=cos(x^{(41)})=cos(0,7390851)=0,7390851$
$x^{(43)}=cos(x^{(42)})=cos(0,7390851)=0,7390851$
Verificamos que a sequência converge para o ponto fixo $x=0,7390851$.

## Estabilidade e convergência

Consideremos uma função $f(x)$ com um ponto fixo em $x^{*}=f(x^{*})$ e observamos o processo iterativo:
$x^{(n+1)}=f(x^{(n)})$
$x^{(0)}=x$
Sendo possível a função $f(x)$ ser aproximada por seu polinômio de Taylor em torno do seu ponto fixo $x^{*}$, obteremos:
$f(x)=f(x^{*})+(x-x^{*})f'(x*)+O((x-x^{*})^{2}),n\geq 0$
$f(x)=x^{*}+(x-x^{*})f'(x*)+O((x-x^{*})^{2})$
$f(x)$ ≈ $x^{*}+(x-x^{*})f'(x^{*})$
Substituindo o polinômio de Taylor da função na relação de recorrência obteremos:
$x^{(n+1)}=f(x^{(n)})$ ≈ $x^{*}+(x-x^{*})f'(x^{*})$
Dessa forma:
$(x^{(n+1)}-x^{*})$ ≈ $(x^{(n)}-x^{*})f'(x^{*})$
Aplicando módulos de ambos os lados, obtemos:
$|x^{(n+1)}-x^{*}|$ ≈ $|x^{(n)}-x^{*}||f'(x^{*})|$
Podemos obter algumas conclusões através desta relação:
* Se $|f'(x)|$ < $1$ a distância entre $x^{(n)}$ e o ponto fixo $x^{*}$ está diminuindo a cada passo.
* Se $|f'(x)|$ > $1$ a distância entre $x^{(n)}$ e o ponto fixo $x^{*}$ está aumentando a cada passo.
* Se $|f'(x)|=1$ a aproximação de primeira ordem não é suficiente para comprender o comportamento da sequência.

## Erro de truncamento e tolerância

Ao utilizar este método na prática, o valor do ponto fixo $x^{*}$ normalmente não é conhecido. Por conseguinte , o erro € $=|x^{(n)}-x^{*}|$ precisa ser calculado tendo como referência os valores obtidos para $x^{(n)}$ . Uma ferramenta frequentemente usada para estudar a evolução da diferença entre dois elementos da sequência é:
$\Delta _{n}=|x^{(n+1)}-x^{(n)}|$
observando que $x^{*}=\lim _{n\to \infty }x^{(n)}$
$x^{*}-x^{(N)}=(x^{(N+1)}-x^{(N)})+(x^{(N+2)}-x^{(N+1)})+(x^{(N+3)}-x^{(N+2)})+...$ $=\sum _{k=0}^{\infty }(x^{(N+k+1)}-x^{(N+k)})$
Usando também as expressões:
$x^{(n+1)}$ ≈ $x^{*}+(x^{(n)}-x^{*})f'(x^{*})$
$x^{(n)}$ ≈ $x^{*}+(x^{(n-1)}-x^{*})f'(x^{*})$
Subtraindo uma expressão da outra:
$x^{(n+1)}-x^{(n)}$ ≈ $(x^{(n)}-x^{(n-1)})f'(x^{*})$
Dessa maneira:
$x^{(N+k+1)}-x^{(N+k)}$ ≈ $(x^{(N+1)}-x^{(N)})(f'(x^{*}))^{k}$
E obtemos:
$x^{*}-x^{(N)}=$ $\sum _{k=0}^{\infty }(x^{(N+k+1)}-x^{(N+k)})$
$x^{*}-x^{(N)}$ ≈ $\sum _{k=0}^{\infty }(x^{(N+1)}-x^{(N)})(f'(x^{*}))^{k}$
$x^{*}-x^{(N)}$ ≈ $(x^{(N+1)}-x^{(N)})$$\left({1 \over 1-f'(x^{*})}\right),$ $|f'(x^{*})|$ < $1$
Aplicando o módulo, obtemos:
$|x^{*}-x^{(n)}|$ ≈ $|x^{(N+1)}-x^{(N)}|$$\left({1 \over 1-f'(x^{*})}\right)$
€$_N$≈ $\left({\Delta _{N} \over 1-f'(x^{*})}\right)$
Ao analisarmos a relação $x^{(n+1)}-x{(n)}$ ≈ $(x^{(n)}-x^{(n-1)})f'(x^{*})$, podemos concluir:
* Quando $f'(x^{*})$ < $0$ , o esquema é alternante e o erro €$_N$pode ser estimado diretamente da diferença $\Delta _{N}.$
* Quando $f'(x^{*})$ > $0$, o esquema é monótono e $\left({1 \over 1-f'(x^{*})}\right)$ > $1$, pelo que o erro €$_N$é maior que a diferença $\Delta _{N}$. A relação será tão mais importante quanto mais próximo da unidade for $f'(x^{*})$, ou seja, quando mais lenta for a convergência.
* Como $f'(x^{*})$ ≈ $\left({x^{(n+1)}-x^{(n)} \over x^{(n)}-x^{(n-1)}}\right)$, temos
$|f'(x^{*})|$ ≈ $_{(ΔN/ΔN−1){\displaystyle\left({\frac{\Delta_{N}}{\Delta_{N-1}}}\right)}}$
E obtemos
€$_N$ ≈ $_{(ΔN/1−ΔN−1){\displaystyle\left({\frac{\Delta_{N}}{1-\Delta_{N-1}}}\right)}}$
Obs: Deve-se exigir que $\Delta _{N}$ < $\Delta _{N-1}$