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 é o número que quando aplicado na função resulta nele mesmo, i.e. . Dada uma aproximação inicial para , o método consiste em iterar sucessivamente a função dada sobre . Ou seja, constrói-se a sequência sendo cada uma nova aproximação do ponto fixo . 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 uma função com um único ponto fixo para o qual buscamos determinar. A iteração do ponto fixo consiste em construirmos a sequência recursiva:[1]

sendo uma aproximação inicial de . Para certas funções, tem-se que a sequência converge para o ponto fixo . 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 . A ideia fundamental é reescrever a equação em uma equação equivalente da forma:

i.e., em um problema de ponto fixo. Se é uma função para a qual o método do ponto fixo converge, então a sequência:

com uma aproximação inicial da solução, converge para o ponto fixo da função . Notemos que o ponto fixo é também solução da equação .[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 usando o método do ponto fixo. Notemos que essa equação é equivalente a e .

Ao efetuarmos o processo iterativo para a primeira equação, i.e. , com , obtemos a seguinte sequência:

E quando realizamos o processo com a outra equação, i.e. , e novamente iniciarmos o processo com , a nova sequência se da por:

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 (que é a solução aproximada de ). 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 com valor inicial

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

Seja uma função contração, i.e. uma função que satisfaça:

Então, existe um único ponto pertencente ao intervalo tal que . Além disso, para qualquer , a sequência dada por:

converge para quando .

Demonstração:

Existência. Caso ou o ponto fixo existe nos extremos. Caso contrário, então e . Neste caso, seja:

Como é uma função contínua, também é. Notemos que:

e

ou seja, troca de sinal no intervalo . Logo, pelo Teorema do valor intermediário, garantimos a existência de um ponto tal que . Esse valor é um ponto fixo de , uma vez que

Unicidade. Suponhamos que e sejam pontos fixos distintos de . Então: o que é uma contradição.

Convergência. Seja a sequência iterada com e o ponto fixo de . Então, temos: Isso implica que: Como , temos que quando . Isso completa a demostração.

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

  1. A desigualdade estrita é necessária.
  2. A condição é necessária.
  3. Determinar os pontos fixos de uma função é determinar a interseção entre as curvas e .
  4. A condição é satisfeita sempre que para todo , pois:

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

Seja uma função e um ponto fixo de . É dito que é um ponto fixo estável caso exista uma região chamada de bacia de atração tal que é convergente sempre que .

Teorema:[editar | editar código-fonte]

Se e < , então é estável. Se > é instável e o teste é inconclusivo caso .

Exemplo: Considerando o problema de encontrar a solução da equação analisando a equação como ponto fixo da função . A demonstração do Teorema do ponto fixo pode ser aplicado na função com o intervalo .

Para provar que basta analisar que é decrescente no intervalo:

< <

é verdade pois .

Agora para provar < observamos que , dessa forma temos a estimativa :

< <

Assim temos que < e dessa forma <

Agora observamos o processo numérico da sequência fazendo , iniciando com , obtemos a sequência:

Verificamos que a sequência converge para o ponto fixo .

Estabilidade e convergência[editar | editar código-fonte]

Consideremos uma função com um ponto fixo em e observamos o processo iterativo:

Sendo possível a função ser aproximada por seu polinômio de Taylor em torno do seu ponto fixo , obteremos:

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

Dessa forma:

Aplicando módulos de ambos os lados, obtemos:

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

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

observando que

Usando também as expressões:

Subtraindo uma expressão da outra:

Dessa maneira:

E obtemos:

<

Aplicando o módulo, obtemos:

N

Ao analisarmos a relação , podemos concluir:

  • Quando < , o esquema é alternante e o erro €N pode ser estimado diretamente da diferença
  • Quando > , o esquema é monótono e > , pelo que o erro €N é maior que a diferença . A relação será tão mais importante quanto mais próximo da unidade for , ou seja, quando mais lenta for a convergência.
  • Como , temos

E obtemos

N

Obs: Deve-se exigir que <

Curiosidades[editar | editar código-fonte]

Broom icon.svg
Se(c)çõ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 . 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 , para encontrar sua respectiva raiz quadrada devemos assumir um valor inicial e calcular um certo valor . Em seguida aplicava-se o algoritmo . Onde . Para cada iteração encontramos uma raiz 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 no intervalo , a função é comumente modificada para . Para obtermos o método iterativo é necessário que a derivada da função seja muito pequena em módulo no intervalo dado. Sendo , a escolha da constante deve ser próxima ao valor . Isso nos nos leva ao Método de Newton utilizado para calcular raízes não lineares. Obtemos da seguinte forma: .

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

Referências