1.2.4 Raízes de Equações — Métodos Abertos — Método de Halley
1. Introdução </p>
O Método de Halley é usado para busca de raízes de funções reais de uma variável que possuam primeira e segunda derivadas contínuas.
Inventado pelo físico Edmond Halley, é um algoritmo que consiste em aplicar o Método de Newton-Raphson duas vezes, gerando uma expressão com dependência da função, da primeira e da segunda derivada.
Apesar de exigir a dependência da primeira e segunda derivada, possui a vantagem de convergir a uma taxa cúbica à raiz, ao invés de quadrática, como no caso do Newton-Raphson.
2. Desenvolvimento do Método de Halley
Considere a função iteração abaixo:
$$ x_{i+1}=x_{i}-{\dfrac {u_{i}}{Q \left( u_{i} \right) } $$
onde e é um polinômio.
O Método de Halley diz que se for uma função linear, então é possível obter uma função iteração de terceira ordem, obedecendo a forma do método de Newton-Raphson[1].
Supondo uma função tal que
$$ g={\dfrac {f \left( x \right) }{\sqrt {\dfrac {d}{dx}f \left( x\right) }} $$
A função é aquela cuja raiz tal que queremos encontrar. Agora derivamos a função g definida acima, gerando a expressão
$$ {\dfrac {d}{dx}g \left( x \right) =\sqrt {\dfrac {d}{dx}f \left( x \right) }-\dfrac{1}{2}\,{\dfrac {f \left( x \right) {\dfrac {d^{2}{d{x}^{2}}f \left( x \right)}{ \left( {\dfrac {d}{dx}f \left( x \right) \right) ^{3/2}} $$
$$\Downarrow $$
$$ {\dfrac {d}{dx}g \left( x \right) =\dfrac{1}{2}\,{\dfrac {2\, \left( {\dfrac {d}{ dx}f \left( x \right) \right) ^{2}-f \left( x \right) {\dfrac {d^{2} {d{x}^{2}}f \left( x \right) }{ \left( {\dfrac {d}{dx}f \left( x\right) \right) ^{3/2}} $$
Agora usaremos a função de iteração do Método de Newton-Raphson. Contudo, ao invés de utilizarmos a função e sua derivada na busca da raiz, usaremos as expressões derivadas de , ou seja
$$ x_{n+1}=x_{n}-{\dfrac {g \left( x_{n} \right) }{\dfrac {d}{dx}g \left( x_{n} \right) }$$
onde
$$ {\dfrac {g \left( x_{n} \right) }{\dfrac {d}{dx}g \left( x_{n} \right) }=f \left( x \right) {\dfrac {1}{\sqrt {\dfrac {d}{dx}f\left( x \right) }}\left( \sqrt {\dfrac {d}{dx}f \left( x \right) }-1/2\,{\dfrac {f \left( x \right) {\dfrac {d^{2}{d{x}^{2}}f \left( x\right) }{ \left( {\dfrac {d}{dx}f \left( x\right) \right) ^{3/2}} \right) ^{-1}$$
A Equação 6 pode ser reescrita de uma forma mais simples,
$$ {\dfrac {g \left( x_{n} \right) }{\dfrac {d}{dx}g \left( x_{n} \right) }=2\,{\dfrac {f \left( x \right) {\dfrac {d}{dx}f \left( x \right) }{2\, \left( {\dfrac {d}{dx}f \left( x \right) \right) ^{2} – f \left( x \right) {\dfrac {d^{2}{d{x}^{2}}f \left( x \right) } $$
Aplicando a Equação 7 na iteração da Equação 5 geramos a expressão usada pelo Método de Halley:
$$ x_{n+1}=x_{n}-2\,{\dfrac {f \left( x \right) {\dfrac {d}{dx}f \left( x \right) }{2\, \left( {\dfrac {d}{dx}f \left( x \right) \right) ^{2}-f \left( x \right) {\dfrac {d^{2}{d{x}^{2}}f \left( x \right) } $$
3. Implementação </p>
def Halley(f, d1f, d2f, x0=1.0, errto=0.001, imax=100):
"""
Return the root of a function (using the Halley Method)
Halley(f, d1f, d2f, x0=1.0, errto=0.001, imax=100)
* f: Function where find the roots
* d1f: analytic derivative of f
* d2f: second derivative of f
* x0: next point (estimative)
* errto: tolerated error
* imax: max of iterations allowed
return: the 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/>
Dec 2009
"""
xn = x0
errno = errto + 1
iterCount = 0
while errno > errto and iterCount < imax:
x0 = xn
xn = xn - (2*f(xn)*d1f(xn))/(2*d1f(xn)*d1f(xn) - f(xn)*d2f(xn))
iterCount += 1
if xn != 0:
errno = fabs((xn-x0)/xn)
return xn
Um exemplo de utilização desta função pode ser encontrado em: http://www.sawp.com.br/code/rootfind/halley.py </p>
4. Conclusões
O Método de Halley utiliza uma transformação para aplicação do método de Newton-Raphson. Este tipo de abordagem é muito comum quando queremos criar uma função de iteração que acelere a convergência à raiz.
Existe uma generalização da abordagem utilizada por Halley para quando deseja-se construir um algoritmo de busca de raízes com taxa de convergência com ordem superior à três, conhecido como “Transformada de Householder”. </p> </p>
5. 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/.