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.
Descrição
Seja uma função com um único ponto fixo , o qual buscamos determinar. A iteração do ponto fixo consiste em construirmos a sequência recursiva:
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 Existem diversas maneiras de usar o método para obter a raiz 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 .
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 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.
thumb|180px|iteração do ponto fixo com valor inicial
Teorema de convergência 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 A desigualdade estrita é necessária. A condição é necessária. Determinar os pontos fixos de uma função é determinar a interseção entre as curvas e . A condição é satisfeita sempre que para todo , pois: .
Teste de convergência 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 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 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 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 <
Ver também Teorema do ponto fixo de Banach Método de Newton Método das secantes
Categoria:Análise numérica