Interpolação quadrática inversa

A interpolação quadrática inversa é um método para aproximar raízes de equações algébricas não lineares.

Método

O algoritmo inverso de Interpolação Quadrática é definido pela relação de recorrência:

$x_{n+1}={\frac {f_{n-1}f_{n}}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {f_{n-2}f_{n}}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

${}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},$

onde f_k = f(x_k). Como pode ser visto a partir da relação de recorrência, este método requer três valores iniciais: x₀, x₁ and x₂.

Explicação do Método

Nós usamos três iterações anteriores, x_n−2, x_n−1 and x_n, com os valores de suas funções, f_n−2, f_n−1 and f_n. Aplicando a fórmula de interpolação de Lagrange para fazer interpolação quadrática no inverso de f(x).

$f^{-1}(y)={\frac {(y-f_{n-1})(y-f_{n})}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {(y-f_{n-2})(y-f_{n})}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

${}+{\frac {(y-f_{n-2})(y-f_{n-1})}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n}.$

Estamos procurando por uma raiz de f(x) que possamos substituir y = f(x) = 0 na equação acima, o que resulta na fórmula de recorrência acima.

Comportamento

O comportamento assintótico é muito bom: em geral “x” _”n” converge rapidamente para a raiz, uma vez que está próxima. No entanto, o desempenho frequentemente é muito pobre se você não iniciar muito perto da raiz real. Por exemplo, se por acaso dois valores da função f_n−2, f_n−1 e f_n coincidem, o algoritmo falha completamente. Deste modo, a interpolação quadrática inversa é raramente utilizada como um algoritmo independente. A ordem dessa convergência é de aproximadamente 1.8, que pode ser provado pelo Método Secante de análise.

Comparação com outros métodos de encontrar raízes

Como foi observado na introdução, interpolação quadrática é usada em método de Brent. Também está intimamente relacionada com alguns outros métodos para encontrar raízes. Usando Interpolação linear ao invés de Interpolação Quadrática chegamos ao Método das secantes. Interpolando “f” em vez do inverso de “f” chegamos ao Método de Muller.

Veja também

• Interpolação Parabólica Sucessiva é um método relacionado a este tópico que utiliza parábolas para encontrar extremos em vex de raízes.

Referências

• James F. Epperson, An introduction to numerical methods and analysis, pages 182-185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1