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$ é o número $x^{\ast }$ que quando aplicado na função resulta nele mesmo, i.e. $f(x^{\ast })=x^{\ast }$. Dada uma aproximação inicial $x_0$ para $x^{\ast }$, o método consiste em iterar sucessivamente a função dada sobre $x_0$. Ou seja, constrói-se a sequência $x_{n+1}=f^{n+1}(x_0)=f^n(f(x_0))$ sendo cada $x_n$ uma nova aproximação do ponto fixo $x^{\ast }$. 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

Ilustração do método.

Seja $f:[a,b]\subset ℝ\to [a,b]$ uma função com um único ponto fixo $x^{\ast }\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),n=0,1,2,\dots ,$

sendo $x_0\in [a,b]$ uma aproximação inicial de $x^{\ast }$. Para certas funções, tem-se que a sequência $(x_n{)}_n$ converge para o ponto fixo $x^{\ast }$. 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)$. A ideia fundamental é reescrever a equação $f(x)=0$ em uma equação equivalente da forma:

$g(x)=x$

i.e., em um problema de ponto fixo. Se $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),n=0,1,\dots ,$

com $x_0$ uma aproximação inicial da solução, converge para o ponto fixo $x^{\ast }$ da função $g$. Notemos que o ponto fixo $x^{\ast }$ é 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 $x{e}^x=10$ usando o método do ponto fixo. Notemos que essa equação é equivalente a $x=10e^{-x}$ e $x=ln\left(\frac{10}{x}\right)$.

Ao efetuarmos o processo iterativo para a primeira equação, i.e. $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(\frac{10}{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(\frac{10}{1}\right)=2.3025851$

$x_2=ln\left(\frac{10}{2.3025851}\right)=1.4685526$

$x_3=ln\left(\frac{10}{1.4685526}\right)=1.9183078$

$x_4=ln\left(\frac{10}{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 $x{e}^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.

iteração do ponto fixo $x_{n+1}=\cos (x_n)$ com valor inicial $x_1=-1.$

Teorema de convergência

Seja $f:[a,b]\to [a,b]$ uma função contração, i.e. uma função que satisfaça:

$|f(x)-f(y)|\le \alpha |x-y|,\alpha <1,\mathrm{\forall }x,y\in [a,b].$

Então, existe um único ponto $x^{\ast }$ pertencente ao intervalo $[a,b]$ tal que $f(x^{\ast })=x^{\ast }$. Além disso, para qualquer $x_0\in [a,b]$, a sequência $(x_n{)}_n$ dada por:

$x_{n+1}=f(x_n),n=0,1,2,\dots ,$

converge para $x^{\ast }$ quando $n\to \mathrm{\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^{\ast }\in (a,b)$ tal que $h(x^{\ast })=0$. Esse valor $x^{\ast }$ é um ponto fixo de $f$, uma vez que

$h(x^{\ast })=f(x^{\ast })-x^{\ast }=x^{\ast }-x^{\ast }=0$

Unicidade. Suponhamos que $x^{\ast }$ e $x^{\ast \ast }$ sejam pontos fixos distintos de $f$. Então: $|x^{\ast }-x^{\ast \ast }|=|f(x^{\ast })-f(x^{\ast \ast })|\le \alpha |x^{\ast }-x^{\ast \ast }|\Rightarrow \alpha \ge 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^{\ast }$ o ponto fixo de $f$. Então, temos: $|x_{n+1}-x^{\ast }|=|f(x_n)-f(x^{\ast })|\le \alpha |x_n-x^{\ast }|,n=1,2,\dots$ Isso implica que: $|x_{n+1}-x^{\ast }|\le {\alpha }^n|x_1-x^{\ast }|,n=1,2,\dots$ Como $0\le \alpha <1$, temos que $x_n\to x^{\ast }$ quando $n\to \mathrm{\infty }$. Isso completa a demostração.

Observações

1. A desigualdade estrita $\alpha <1$ é necessária.
2. A condição $f([a,b])\subset [a,b]$ é necessária.
3. Determinar os pontos fixos de uma função $f(x)$ é determinar a interseção entre as curvas $y=f(x)$ e $y=x$.
4. A condição $|f(x)-f(y)|\le \alpha |x-y|$ é satisfeita sempre que $|f^{\prime }(x)|\le \alpha <1$ para todo $x$, pois:

$|f(x)-f(y)|=\left|{\int }_x^y{f}^{\prime }(s)ds\right|\le {\int }_x^y\alpha ds=\alpha |x-y|,(x<y)$.

Teste de convergência

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

Teorema

Se $f\in [a,b]$ e $|f^{\prime }(x^{\ast })|$ < $1$, então $x^{\ast }$ é estável. Se $|f^{\prime }(x^{\ast })|$ > $1$ é instável e o teste é inconclusivo caso $|f^{\prime }(x^{\ast })|=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)\le cos(x)\le 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)|\le \alpha |x-y|,\alpha$ < $1$ observamos que $f^{\prime }(x)=-sen(x)$, dessa forma temos a estimativa :

$-0,85$ < $-sen(1)\le -sen(x)\le -sen(1/2)$ < $-0,47$

Assim temos que $|f^{\prime }(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^{\ast }=f(x^{\ast })$ 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^{\ast }$, obteremos:

$f(x)=f(x^{\ast })+(x-x^{\ast })f^{\prime }(x\ast )+O((x-x^{\ast }{)}^2),n\ge 0$

$f(x)=x^{\ast }+(x-x^{\ast })f^{\prime }(x\ast )+O((x-x^{\ast }{)}^2)$

$f(x)$ ≈ $x^{\ast }+(x-x^{\ast })f^{\prime }(x^{\ast })$

Substituindo o polinômio de Taylor da função na relação de recorrência obteremos:

$x^{(n+1)}=f(x^{(n)})$ ≈ $x^{\ast }+(x-x^{\ast })f^{\prime }(x^{\ast })$

Dessa forma:

$(x^{(n+1)}-x^{\ast })$ ≈ $(x^{(n)}-x^{\ast })f^{\prime }(x^{\ast })$

Aplicando módulos de ambos os lados, obtemos:

$|x^{(n+1)}-x^{\ast }|$ ≈ $|x^{(n)}-x^{\ast }||f^{\prime }(x^{\ast })|$

Podemos obter algumas conclusões através desta relação:

• Se $|f^{\prime }(x)|$ < $1$ a distância entre $x^{(n)}$ e o ponto fixo $x^{\ast }$ está diminuindo a cada passo.
• Se $|f^{\prime }(x)|$ > $1$ a distância entre $x^{(n)}$ e o ponto fixo $x^{\ast }$ está aumentando a cada passo.
• Se $|f^{\prime }(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^{\ast }$ normalmente não é conhecido. Por conseguinte , o erro € $=|x^{(n)}-x^{\ast }|$ 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^{\ast }=\underset{n\to \mathrm{\infty }}{\lim }{x}^{(n)}$

$x^{\ast }-x^{(N)}=(x^{(N+1)}-x^{(N)})+(x^{(N+2)}-x^{(N+1)})+(x^{(N+3)}-x^{(N+2)})+\mathrm{...}$ $=\sum _{k=0}^{\mathrm{\infty }}(x^{(N+k+1)}-x^{(N+k)})$

Usando também as expressões:

$x^{(n+1)}$ ≈ $x^{\ast }+(x^{(n)}-x^{\ast })f^{\prime }(x^{\ast })$

$x^{(n)}$ ≈ $x^{\ast }+(x^{(n-1)}-x^{\ast })f^{\prime }(x^{\ast })$

Subtraindo uma expressão da outra:

$x^{(n+1)}-x^{(n)}$ ≈ $(x^{(n)}-x^{(n-1)})f^{\prime }(x^{\ast })$

Dessa maneira:

$x^{(N+k+1)}-x^{(N+k)}$ ≈ $(x^{(N+1)}-x^{(N)})(f^{\prime }(x^{\ast }){)}^k$

E obtemos:

$x^{\ast }-x^{(N)}=$ $\sum _{k=0}^{\mathrm{\infty }}(x^{(N+k+1)}-x^{(N+k)})$

$x^{\ast }-x^{(N)}$ ≈ $\sum _{k=0}^{\mathrm{\infty }}(x^{(N+1)}-x^{(N)})(f^{\prime }(x^{\ast }){)}^k$

$x^{\ast }-x^{(N)}$ ≈ $(x^{(N+1)}-x^{(N)})$$\left(\frac{1}{1-f^{\prime }(x^{\ast })}\right),$ $|f^{\prime }(x^{\ast })|$ < $1$

Aplicando o módulo, obtemos:

$|x^{\ast }-x^{(n)}|$ ≈ $|x^{(N+1)}-x^{(N)}|$$\left(\frac{1}{1-f^{\prime }(x^{\ast })}\right)$

€_N ≈ $\left(\frac{{\Delta }_N}{1-f^{\prime }(x^{\ast })}\right)$

Ao analisarmos a relação $x^{(n+1)}-x(n)$ ≈ $(x^{(n)}-x^{(n-1)})f^{\prime }(x^{\ast })$, podemos concluir:

• Quando $f^{\prime }(x^{\ast })$ < $0$ , o esquema é alternante e o erro €_N pode ser estimado diretamente da diferença ${\Delta }_N.$
• Quando $f^{\prime }(x^{\ast })$ > $0$, o esquema é monótono e $\left(\frac{1}{1-f^{\prime }(x^{\ast })}\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^{\prime }(x^{\ast })$, ou seja, quando mais lenta for a convergência.
• Como $f^{\prime }(x^{\ast })$ ≈ $\left(\frac{x^{(n+1)}-x^{(n)}}{x^{(n)}-x^{(n-1)}}\right)$, temos

$|f^{\prime }(x^{\ast })|$ ≈ _{$\left(\frac{{\Delta }_N}{{\Delta }_{N-1}}\right)$}

E obtemos

€_N ≈ _{$\left(\frac{{\Delta }_N}{1-{\Delta }_{N-1}}\right)$}

Obs: Deve-se exigir que ${\Delta }_N$ < ${\Delta }_{N-1}$

Ver também

• Teorema do ponto fixo de Banach
• Método de Newton
• Método das secantes