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 ${\displaystyle 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.^[1]

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:^[1]

${\displaystyle 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 ${\displaystyle (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:

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle f(x)=0}$.^[1]

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 ${\displaystyle x=10e^{-x}}$ e ${\displaystyle 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 ${\displaystyle x_{0}=1}$, obtemos a seguinte sequência:

${\displaystyle x_{0}=1}$

${\displaystyle x_{1}=10e^{-1}=3.6787944}$

${\displaystyle x_{2}=10e^{-3.6787944}=0.2525340}$

${\displaystyle x_{3}=10e^{-0.2525340}=7.7682979}$

${\displaystyle x_{4}=10e^{-7.7682979}=0.0042293}$

${\displaystyle x_{5}=10e^{-0.0042293}=9.9577961}$

E quando realizamos o processo com a outra equação, i.e. ${\displaystyle x_{n+1}=ln\left({10 \over x_{n}}\right)}$, e novamente iniciarmos o processo com ${\displaystyle x_{0}=1}$, a nova sequência se da por:

${\displaystyle x_{0}=1}$

${\displaystyle x_{1}=ln\left({10 \over 1}\right)=2.3025851}$

${\displaystyle x_{2}=ln\left({10 \over 2.3025851}\right)=1.4685526}$

${\displaystyle x_{3}=ln\left({10 \over 1.4685526}\right)=1.9183078}$

${\displaystyle x_{4}=ln\left({10 \over 1.9183078}\right)=1.6511417}$

${\displaystyle .}$

${\displaystyle .}$

${\displaystyle .}$

${\displaystyle x_{10}=1.7421335}$

${\displaystyle x_{20}=1.7455151}$

${\displaystyle x_{30}=1.745528}$

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle x_{n+1}=\cos(x_{n})}$ com valor inicial ${\displaystyle 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:

${\displaystyle |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 ${\displaystyle [a,b]}$ tal que ${\textstyle f(x^{*})=x^{*}}$. Além disso, para qualquer ${\displaystyle x_{0}\in [a,b]}$, a sequência ${\displaystyle (x_{n})_{n}}$ dada por:

${\displaystyle x_{n+1}=f(x_{n}),\quad n=0,1,2,\ldots ,}$

converge para ${\textstyle x^{*}}$ quando ${\displaystyle n\to \infty }$.

Demonstração:

Existência. Caso ${\displaystyle f(a)=a}$ ou ${\displaystyle f(b)=b}$ o ponto fixo existe nos extremos. Caso contrário, então ${\displaystyle f(a)>a}$ e ${\displaystyle f(b)<b}$. Neste caso, seja:

${\displaystyle h(x)=f(x)-x}$

Como ${\displaystyle f}$ é uma função contínua, ${\displaystyle h}$ também é. Notemos que:

${\displaystyle h(a)=f(a)-a>0}$ e ${\displaystyle h(b)=f(b)-b<0}$

ou seja, ${\displaystyle h}$ troca de sinal no intervalo ${\displaystyle [a,b]}$. Logo, pelo Teorema do valor intermediário, garantimos a existência de um ponto ${\displaystyle x^{*}\in (a,b)}$ tal que ${\displaystyle h(x^{*})=0}$. Esse valor ${\displaystyle x^{*}}$ é um ponto fixo de ${\displaystyle f}$, uma vez que

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

Unicidade. Suponhamos que ${\displaystyle x^{*}}$ e ${\displaystyle x^{**}}$ sejam pontos fixos distintos de ${\displaystyle f}$. Então: ${\displaystyle |x^{*}-x^{**}|=|f(x^{*})-f(x^{**})|\leq \alpha |x^{*}-x^{**}|\Rightarrow \alpha \geq 1}$ o que é uma contradição.

Convergência. Seja ${\displaystyle (x_{n})_{n}}$ a sequência iterada ${\displaystyle x_{n+1}=f(x_{n})}$ com ${\displaystyle x_{0}\in [a,b]}$ e ${\displaystyle x^{*}}$ o ponto fixo de ${\displaystyle f}$. Então, temos: ${\displaystyle |x_{n+1}-x^{*}|=|f(x_{n})-f(x^{*})|\leq \alpha |x_{n}-x^{*}|,\quad n=1,2,\ldots }$ Isso implica que: ${\displaystyle |x_{n+1}-x^{*}|\leq \alpha ^{n}|x_{1}-x^{*}|,\quad n=1,2,\ldots }$ Como ${\displaystyle 0\leq \alpha <1}$, temos que ${\displaystyle x_{n}\to x^{*}}$ quando ${\displaystyle 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 ${\displaystyle |f'(x)|\leq \alpha <1}$ para todo ${\textstyle x}$, pois:

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

Teorema

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

Exemplo

Considerando o problema de encontrar a solução da equação ${\displaystyle cos(x)=x}$ analisando a equação como ponto fixo da função ${\displaystyle f(x)=cos(x)}$. A demonstração do Teorema do ponto fixo pode ser aplicado na função com o intervalo ${\displaystyle [a,b]=[1/2,1]}$.

Para provar que ${\displaystyle f([1/2,1])\subset [1/2,1]}$ basta analisar que ${\displaystyle f(x)}$ é decrescente no intervalo:

${\displaystyle 0,54}$ < ${\displaystyle cos(1)\leq cos(x)\leq cos(1/2)}$ < ${\displaystyle 0,88}$

${\displaystyle f([1/2,1])\subset [1/2,1]}$ é verdade pois ${\displaystyle [0.54,0.88]\subset [1/2,1]}$.

Agora para provar ${\displaystyle |f(x)-f(y)|\leq \alpha |x-y|,\alpha }$ < ${\displaystyle 1}$ observamos que ${\displaystyle f'(x)=-sen(x)}$, dessa forma temos a estimativa :

${\displaystyle -0,85}$ < ${\displaystyle -sen(1)\leq -sen(x)\leq -sen(1/2)}$ < ${\displaystyle -0,47}$

Assim temos que ${\displaystyle |f'(x)|}$ < ${\displaystyle 0,85}$ e dessa forma ${\displaystyle \alpha =0,85}$ < ${\displaystyle 1.}$

Agora observamos o processo numérico da sequência fazendo ${\displaystyle x^{(n+1)}=cos(x^{(n)})}$, iniciando com ${\displaystyle x^{(0)}=1}$, obtemos a sequência:

${\displaystyle x^{(1)}=cos(x^{(0)})=cos(1)=0,5403023}$

${\displaystyle x^{(2)}=cos(x^{(1)})=cos(0,5403023)=0,8575532}$

${\displaystyle x^{(3)}=cos(x^{(2)})=cos(0,8575532)=0,6542898}$

${\displaystyle x^{(4)}=cos(x^{(3)})=cos(0,6542898)=0,7934804}$

${\displaystyle x^{(5)}=cos(x^{(4)})=cos(0,7934804)=0,7013688}$

${\displaystyle .}$

${\displaystyle .}$

${\displaystyle .}$

${\displaystyle x^{(11)}=cos(x^{(10)})=cos(0,7442374)=0,7356047}$

${\displaystyle x^{(12)}=cos(x^{(11)})=cos(0,7356047)=0,7414251}$

${\displaystyle x^{(13)}=cos(x^{(12)})=cos(0,7414251)=0,7375069}$

${\displaystyle .}$

${\displaystyle .}$

${\displaystyle .}$

${\displaystyle x^{(41)}=cos(x^{(40)})=cos(0,7390852)=0,7390851}$

${\displaystyle x^{(42)}=cos(x^{(41)})=cos(0,7390851)=0,7390851}$

${\displaystyle x^{(43)}=cos(x^{(42)})=cos(0,7390851)=0,7390851}$

Verificamos que a sequência converge para o ponto fixo ${\displaystyle x=0,7390851}$.

Estabilidade e convergência

Consideremos uma função ${\displaystyle f(x)}$ com um ponto fixo em ${\displaystyle x^{*}=f(x^{*})}$ e observamos o processo iterativo:

${\displaystyle x^{(n+1)}=f(x^{(n)})}$

${\displaystyle x^{(0)}=x}$

Sendo possível a função ${\displaystyle f(x)}$ ser aproximada por seu polinômio de Taylor em torno do seu ponto fixo ${\displaystyle x^{*}}$, obteremos:

${\displaystyle f(x)=f(x^{*})+(x-x^{*})f'(x*)+O((x-x^{*})^{2}),n\geq 0}$

${\displaystyle f(x)=x^{*}+(x-x^{*})f'(x*)+O((x-x^{*})^{2})}$

${\displaystyle f(x)}$ ≈ ${\displaystyle x^{*}+(x-x^{*})f'(x^{*})}$

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

${\displaystyle x^{(n+1)}=f(x^{(n)})}$ ≈ ${\displaystyle x^{*}+(x-x^{*})f'(x^{*})}$

Dessa forma:

${\displaystyle (x^{(n+1)}-x^{*})}$ ≈ ${\displaystyle (x^{(n)}-x^{*})f'(x^{*})}$

Aplicando módulos de ambos os lados, obtemos:

${\displaystyle |x^{(n+1)}-x^{*}|}$ ≈ ${\displaystyle |x^{(n)}-x^{*}||f'(x^{*})|}$

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

• Se ${\displaystyle |f'(x)|}$ < ${\displaystyle 1}$ a distância entre ${\displaystyle x^{(n)}}$ e o ponto fixo ${\displaystyle x^{*}}$ está diminuindo a cada passo.
• Se ${\displaystyle |f'(x)|}$ > ${\displaystyle 1}$ a distância entre ${\displaystyle x^{(n)}}$ e o ponto fixo ${\displaystyle x^{*}}$ está aumentando a cada passo.
• Se ${\displaystyle |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 ${\displaystyle x^{*}}$ normalmente não é conhecido. Por conseguinte , o erro € ${\displaystyle =|x^{(n)}-x^{*}|}$ precisa ser calculado tendo como referência os valores obtidos para ${\displaystyle x^{(n)}}$ . Uma ferramenta frequentemente usada para estudar a evolução da diferença entre dois elementos da sequência é:

${\displaystyle \Delta _{n}=|x^{(n+1)}-x^{(n)}|}$

observando que ${\displaystyle x^{*}=\lim _{n\to \infty }x^{(n)}}$

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

Usando também as expressões:

${\displaystyle x^{(n+1)}}$ ≈ ${\displaystyle x^{*}+(x^{(n)}-x^{*})f'(x^{*})}$

${\displaystyle x^{(n)}}$ ≈ ${\displaystyle x^{*}+(x^{(n-1)}-x^{*})f'(x^{*})}$

Subtraindo uma expressão da outra:

${\displaystyle x^{(n+1)}-x^{(n)}}$ ≈ ${\displaystyle (x^{(n)}-x^{(n-1)})f'(x^{*})}$

Dessa maneira:

${\displaystyle x^{(N+k+1)}-x^{(N+k)}}$ ≈ ${\displaystyle (x^{(N+1)}-x^{(N)})(f'(x^{*}))^{k}}$

E obtemos:

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

${\displaystyle x^{*}-x^{(N)}}$ ≈ ${\displaystyle \sum _{k=0}^{\infty }(x^{(N+1)}-x^{(N)})(f'(x^{*}))^{k}}$

${\displaystyle x^{*}-x^{(N)}}$ ≈ ${\displaystyle (x^{(N+1)}-x^{(N)})}$${\displaystyle \left({1 \over 1-f'(x^{*})}\right),}$ ${\displaystyle |f'(x^{*})|}$ < ${\displaystyle 1}$

Aplicando o módulo, obtemos:

${\displaystyle |x^{*}-x^{(n)}|}$ ≈ ${\displaystyle |x^{(N+1)}-x^{(N)}|}$${\displaystyle \left({1 \over 1-f'(x^{*})}\right)}$

€_N ≈ ${\displaystyle \left({\Delta _{N} \over 1-f'(x^{*})}\right)}$

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

• Quando ${\displaystyle f'(x^{*})}$ < ${\displaystyle 0}$ , o esquema é alternante e o erro €_N pode ser estimado diretamente da diferença ${\displaystyle \Delta _{N}.}$
• Quando ${\displaystyle f'(x^{*})}$ > ${\displaystyle 0}$, o esquema é monótono e ${\displaystyle \left({1 \over 1-f'(x^{*})}\right)}$ > ${\displaystyle 1}$, pelo que o erro €_N é maior que a diferença ${\displaystyle \Delta _{N}}$. A relação será tão mais importante quanto mais próximo da unidade for ${\displaystyle f'(x^{*})}$, ou seja, quando mais lenta for a convergência.
• Como ${\displaystyle f'(x^{*})}$ ≈ ${\displaystyle \left({x^{(n+1)}-x^{(n)} \over x^{(n)}-x^{(n-1)}}\right)}$, temos

${\displaystyle |f'(x^{*})|}$ ≈ _{${\displaystyle \left({\frac {\Delta _{N}}{\Delta _{N-1}}}\right)}$}

E obtemos

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

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

Ver também

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

Referências

1. J., Faires (2008). Análise Numérica. [S.l.: s.n.] ISBN 9788522106011