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

Ilustração do método.

Seja ${\textstyle f:[a,b]\subset \mathbb {R} \to [a,b]}$ uma função com um único ponto fixo ${\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 ${\textstyle x_{0}\in [a,b]}$ uma aproximação inicial de ${\textstyle x^{*}}$. Para certas funções, tem-se que a sequência $(x_{n})_{n}$ converge para o ponto fixo ${\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 ${\textstyle f(x)}$. A ideia fundamental é reescrever a equação ${\textstyle f(x)=0}$ em uma equação equivalente da forma:

$g(x)=x$

i.e., em um problema de ponto fixo. Se ${\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 ${\textstyle x_{0}}$ uma aproximação inicial da solução, converge para o ponto fixo ${\textstyle x^{*}}$ da função ${\textstyle g}$. Notemos que o ponto fixo ${\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 ${\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. ${\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 ${\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.

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

Teorema de convergência

Seja ${\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 ${\textstyle x^{*}}$ pertencente ao intervalo $[a,b]$ tal que ${\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 ${\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

1. A desigualdade estrita ${\textstyle \alpha <1}$ é necessária.
2. A condição ${\textstyle f([a,b])\subset [a,b]}$ é necessária.
3. Determinar os pontos fixos de uma função ${\textstyle f(x)}$ é determinar a interseção entre as curvas ${\textstyle y=f(x)}$ e ${\textstyle y=x}$.
4. A condição ${\textstyle |f(x)-f(y)|\leq \alpha |x-y|}$ é satisfeita sempre que $|f'(x)|\leq \alpha <1$ para todo ${\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^{*})|$ ≈ _{$\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