Iteração de ponto fixo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo (desde setembro de 2014). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Em análise numérica, iteração de ponto fixo é um método de se calcular pontos fixos de funções iteradas. Ponto fixo de uma função f é o número x^* que quando aplicado na função resulta em f(x^*)=x^*. O método de ponto fixo tem grande importância para obter raízes de funções pois é de fácil análise. Este é fundamentado em efetuar uma sequência de de x_n
que convirja para a raiz x^*requerida. Para cada iteração é calculado uma nova aproximação para x^*. Mais especificamente, dada uma função f definida sobre números reais com valores reais e dado um ponto x_0 no domínio de f, o ponto fixo de iteração é

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

o qual resulta da sequência x_0, x_1, x_2, \dots que é esperado como convergente ao ponto x. Existem diversas maneiras de usar o método para obter a raíz de uma função f(x) transformando a função em uma equação do tipo x=g(x). Um exemplo para a realização desse procedimento é multiplicar a equação f(x)=0 por uma constante k e somar x de ambos os lados de modo a não perder a equivalência da equação original e obtendo, dessa forma, x=x+kf(x), e nesse caso, g(x)=x+kf(x).

Há muitas outras maneiras de manipular uma equação de forma a utilizar o método do ponto fixo. Apesar da simplicidade do método, não são todas equações que convergem para o ponto fixo. Existem algumas condições para que tal sequência convirja para o resultado. Uma ilustração do fato de que nem todo processo por meio do ponto fixo converge, está no seguinte exemplo, onde existem dois processos de obtenção do ponto fixo, ambos são derivados da mesma equação xe^x=10 . Essa equação é equivalente a x=10e^{-x} e x=ln\left({10 \over x}\right).

Ao efetuarmos o processo iterativo nas duas equações, primeiramente para a equação 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, 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. 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[editar | editar código-fonte]

Seja f:[a,b]\rightarrow [a,b] uma função real tal que
|f(x)-f(y)|\le \alpha|x-y|,   \alpha  < 1
Podemos dizer que f é uma contração, ou seja, a distância entre os dois pontos da abscissa é maior que os dois pontos da imagem. Além disso, existe um único ponto x^{*} pertencente ao intervalo [a,b] tal que f(x^{*})=x^{*}. Assim, a sequência x^{(n+1)}=f(x^{(n)}) é convergente sempre que x^{(0)} \in [a,b]. Considerando f(x) contínua vale o limite
x^{*}= \lim_{n \to \infty}x^{(n+1)} = \lim_{n \to \infty}f(x^{(n)})=f(\lim_{n \to \infty}x^{(n)})=f(x^{*})

A existência do ponto fixo é garantida pelo seguinte teorema:

  • (1) Se f(x) \in [a,b] para todo x\in [a,b] , f(x) terá um ponto fixo dentro do intervalo [a,b].

Demonstração:[editar | editar código-fonte]

Se f(a)=a ou f(b)=b o ponto fixo existe nos extremos. Do contrário, se f(a) > a e  f(b) < b , sendo a função h(x)=f(x)-x é contínua em [a,b], com
h(a)=f(a)-a>0 e h(b) = f(b) -b  < 0
é possível verificar que a função troca de sinal no intervalo dado e, dessa forma, através do 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
  • (2) Se f'(x) existir em (a,b) e existir um numero constante e positivo c<1 com |f'(x)| \leq c para todo  x \in (a,b) então o ponto fixo em [a,b] será o único existente neste intervalo fechado.

Demonstração:[editar | editar código-fonte]

Para demonstrar a unicidade do ponto fixo admitimos que os pontos x^* e x^{**} sejam pontos fixos no intervalo [a,b], logo eles devem ser iguais, uma vez que:

|x^*-x^{**}|=|f(x^*)-f(x^{**})| \le \alpha|x^*-x^{**}|

A desigualdade |x^*-x^{**}| \le \alpha|x^*-x^{**}| com \alpha
< 1 implica que |x^*-x^{**}|=0 .

A convergência da sequência pode ser demonstrada pela seguinte relação

|x^{(n+1)}-x^*|=|f(x^{(n)})-x^*|=|f(x^{(n)})-f(x^*)|\le\alpha|x^{(n)}-x^*|

Observando que

|x^{(n)}-x^*|\le\alpha|x^{(n-1)}-x^*|\le\alpha^2|x^{(n-2)}-x^*|\le...\le\alpha^n|x^{(0)}-x^*|

Portanto

\lim_{n \to \infty}|x^{(n)}-x^*|=0

e

\lim_{n \to \infty}x^{(n)}=x^*

Observações:[editar | editar código-fonte]

  1. A desigualdade estrita \alpha<1 é necessária.
  2. A condição f([a,b]) C [a,b].
  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'(x)\le\alpha<1em todo intervalo pois

|f(x)-f(y)|=|{\int_{x}^{y}} {f'(s)} ds| \le {\int_{x}^{y}} {|f'(s)|} ds \le {\int_{x}^{y}} {\alpha} ds =\alpha|x-y|, x<y

Teste de convergência[editar | editar código-fonte]

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:[editar | editar código-fonte]

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]) C [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]) C [1/2,1] é verdade pois [0.54,0.88] C [1/2,1].

Agora para provar |f(x)-f(y)|\le \alpha|x-y|,   \alpha < 1 observamos que f'(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'(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[editar | editar código-fonte]

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)}-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[editar | editar código-fonte]

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^\infty_{k = 0} (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^\infty_{k = 0} (x^{(N+k+1)}-x^{(N+k)})

x^* -x^{(N)}  \sum^\infty_{k = 0} (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}

Curiosidades[editar | editar código-fonte]

Broom icon.svg
Seções de curiosidades são desencorajadas pelas políticas da Wikipédia.
Ajude a melhorar este artigo, integrando ao corpo do texto os itens relevantes e removendo os supérfluos ou impróprios.

Desvantagem da utilização deste método: Necessidade da obtenção de uma função de iteração f(x). Sua convergência não é tão rápida quanto outros métodos iterativos.

Origem[editar | editar código-fonte]

Os babilônicos desenvolveram, por volta de 1500 a.C. , um algorítimo capaz de aproximar raízes quadradas de qualquer numero positivo. Dado um numero N , para encontrar sua respectiva raiz quadrada devemos assumir um valor inicial a_0 e calcular um certo valor b_0. Em seguida aplicava-se o algoritmo a_k=(a_{k-1}+b_{k-1})/2. Onde b_k=N/a_k. Para cada iteração encontramos uma raiz N cada vez mais aproximada. [1]

Utilidade[editar | editar código-fonte]

Na economia, principalmente, e em outras áreas do campo cientifico, serve para achar pontos de equilíbrio.

Método de Newton

Quando criamos um algoritmo iterativo a modo de se obter como resultado uma raiz de f(x)=0 no intervalo [a,b], a função é comumente modificada para x = x + kf(x). Para obtermos o método iterativo é necessário que a derivada da função g(x) seja muito pequena em módulo no intervalo dado. Sendo g'(x)=1+kf'(x), a escolha da constante k deve ser próxima ao valor -\left({1 \over f'(x)}\right). Isso nos nos leva ao Método de Newton utilizado para calcular raízes não lineares. Obtemos da seguinte forma: g(x)=x-\left({f(x) \over f'(x)}\right).

Ver também[editar | editar código-fonte]

Referências