1.2.4 Raízes de Equações — Métodos Abertos — Método de Halley

1. Introdução

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:
(eq1)


\( x_{{i+1}}=x_{{i}}-{\dfrac {u_{{i}}}{Q \left( u_{{i}} \right) }} \)

onde \(u_{{i}}={\dfrac {f_{{i}} \left( x \right) }{{\dfrac {d}{dx}}f_{{i}} \left( x \right) }} \) e \(Q\) é um polinômio.

O Método de Halley diz que se \(Q \) 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 \(g \) tal que
(eq2)


\( g={\dfrac {f \left( x \right) }{\sqrt {{\dfrac {d}{dx}}f \left( x\right) }}} \)

A função \(f \) é aquela cuja raiz tal que \(f(x) = 0 \) queremos encontrar. Agora derivamos a função g definida acima, gerando a expressão
(eq3)

\( {\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 \)

(eq4)

\( {\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 \(f \) e sua derivada na busca da raiz, usaremos as expressões derivadas de \(g \) , ou seja
(eq5)


\( x_{{n+1}}=x_{{n}}-{\dfrac {g \left( x_{{n}} \right) }{{\dfrac {d}{dx}}g \left( x_{{n}} \right) }}\)

onde
(eq6)

\( {\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,
(eq7)


\( {\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:
(eq8)


\( 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

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

4. Conclusões

O Método de Halley utiliza uma transformação \(g(f(x)) \) 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”.

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/.

References


[1] Ralston, Anthony and Rabinowitz, Philip, A First Course in Numerical Analysis.,(2nd ed.) McGraw-Hill and Dover, (2001), 401–402.


[2] http://math.fullerton.edu/mathews/n2003/Halley’sMethodMod.htm