Iteração de ponto fixo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Esta página ou secçã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)
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.[1]

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

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]} para o qual buscamos determinar. A iteração do ponto fixo consiste em construirmos a sequência recursiva:[1]

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

Existem diversas maneiras de usar o método para obter a raíz 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.[1]

Exemplo[editar | editar código-fonte]

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

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

  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)|\le\alpha|x-y|} é satisfeita sempre que |f'(x)|\le\alpha<1 para todo {\textstyle x}, pois:

|f(x)-f(y)|=\left|{\int_{x}^{y}} {f'(s)} ds\right| \le {\int_{x}^{y}} {\alpha} ds = \alpha|x-y|,\quad (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. [2]

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