1.2.8 Raízes de Equações — Métodos Abertos — Método de Newton Interpolado
1. Introdução
Uma vantagem deste método é que, assim como o Método de Newton, ele requer apenas que a função e a sua primeira derivada seja passada, sendo livre de derivadas superiores, como corre nos Métodos de Halley e de HouseHolder.
A idéia deste algoritmo está em utilizar o Método de Newton para uma primeira aproximação da raiz, seguida de uma interpolação inversa para refinar esta aproximação. Uma abordagem semelhante foi apresentada no artigo sobre busca de raízes com Interpolação Quadrática Inversa.
2. Desenvolvimento do Método
Pelo Método de Newton sabemos que uma raiz pode ser aproximada a partir da própria função e sua derivada a partir da fórmula:
$$ x_{n+1}=x_{n}-{\dfrac {f \left( x_{n} \right) }{\dfrac {d}{dx}f \left( x_{n} \right) } $$
Todavia, para facilitar a notação, vamos renomear as variáveis da Equação 1 de tal forma que e ,
implicando na expressão:
$$ x_{1}=x_{0}-{\dfrac {f \left( x_{0} \right) }{\dfrac {d}{dx}f \left( x_{0} \right) } $$
Aplicando a Equação 2 como primeira estimativa, dentro da mesma iteração podemos refinar a aproximação da raiz através da seguinte função:
$$ x_{2}=x_{1}-{\dfrac { \left( 5\, \left( {\dfrac {d}{dx}f \left( x_{0} \right) \right) ^{2}+3\, \left( {\dfrac {d}{dx}f \left( x_{1} \right) \right) ^{2} \right) f \left( x_{1} \right) }{ \left( \left( {\dfrac {d}{dx}f \left( x_{0} \right) \right) ^{2}+7\, \left( {\dfrac {d}{dx}f \left( x_{1} \right) \right) ^{2} \right) {\dfrac {d}{dx}f \left( x_{0} \right) } $$
Para simplificar esta fórmula, adotamos e , ou seja, , , , e , e substituímos na Equação 3:
$$ x_2=x_1-{\dfrac { \left( 5\,{df_{0}}^{2}+3\,{df_{1}}^{2} \right) f_{1}}{ \left( {df_{0}}^{2}+7\,{df_{1}}^{2} \right) df_{0}}$$
Esta função é de grande utilidade, uma vez que possui os mesmos requisitos do Método de Newton-Raphson — função e a sua primeira derivada — mas com eficiência superior. Sendo que a maioria dos métodos numéricos que buscam raízes são derivados a partir do Método de Newton, utilizando este recurso podemos aprimorar diversos algoritmos.
No artigo em que esta fórmula é apresentada, o autor demonstra a ordem de convergência do seu método, sendo que a análise da taxa de aproximação, pode ser encontrada no artigo An efficient Newton-type method with fifth-order convergence for solving nonlinear equations[1].
</p>
3. Implementação
def Newton5order(f, df, x0=1.0, errto=0.001, imax=500):
"""
Return the root of function (Interpolated Newton-Raphson for 5th order)
Newton5order(f, df, x0=1.0, errto=0.001, imax=500)
* f: Function where find roots
* df: derivative of f
* x0: next point (estimative)
* errto: tolerated error ( for aprox. )
* imax: max of iterations allowed
return: root next x0
Author: Pedro Garcia [sawp@sawp.com.br]
see: http://www.sawp.com.br
License: Creative Commons
<http ://creativecommons.org/licenses/by-nc-nd/2.5/br/>
Jan 2009
"""
errno = errto + 1
iterCount = 0
while errno > errto and iterCount < imax:
f0 = f(x0)
df0 = df(x0)
if df0 != 0:
x1 = x0 - f0/df0
else:
x1 = x0 - f0/errto
f1 = f(x1)
df1 = df(x1)
if (df0 * df0 + 7.0 * df1 * df1) * df0 != 0:
x2 = x1 - ((5.0 * df0 * df0 + 3.0 * df1 * df1) * f1) / \
((df0 * df0 + 7.0 * df1 * df1) * df0)
else:
x2 = x1
if x2 != 0:
errno = fabs((x2 - x0)/x2)
iterCount += 1
x0 = x2
return x2
Um exemplo de como utilizar esta função pode ser encontrado em http://www.sawp.com.br/code/rootfind/Newton5order.py </p> </p>
4. Copyright
Este documento é disponível sob a licença Creative Commons. As regras dos direitos de cópia deste conteúdo estão acessíveis em http://creativecommons.org/licenses/by-nc-nd/2.5/br/.