0.1 Miscelânea — Enésima Raiz

1. Desenvolvimento do Método

Para obtermos uma função que retorne a raiz arbitrária de um número qualquer \(\phi \) , podemos supor que \(phi \) é uma constante que se relacione com o parâmetro de entrada \(x \) da seguinte forma:
(eq1)


\( x^n = \phi \)

onde \(n \) é um inteiro qualquer e \(\phi \) é um valor real positivo, isto é:

\(\phi > 0 \)

Através desta expressão, vamos supor uma função \(f(x) \) tal que
(eq2)


\( f(x) = x^n – \phi \)

A função \(f(x) \) possui algumas propriedades interessantes. A primeira delas é que sabemos que \(f(x) = 0 \) sempre, pois a Equação 1 é verdadeira. Além disso, \(f(x) \) pode ser facilmente derivada:
(eq3)


\( \dfrac{d}{dx}f(x) = nx^{n-1} \)

Desta forma, o problema de retirar a raiz \(n \) de \(\phi \) se reduz a um problema de busca do zero da função \(f(x) \) . Como temos \(f(x) \) e sua derivada, podemos utilizar o Método de Newton para encontrarmos esta raiz:
(eq4)

\( x_{k+1} = x_k – \dfrac{f(x)}{\frac{d}{dx}f(x)} \)

Assim,

\(x_{k+1} = x_k – \dfrac{x_k^n – \phi}{nx_k^{n-1}} \) \\
\(x_{k+1} = x_k – \dfrac{x_k}{n} + \dfrac{\phi}{x_k^{n-1}} \)

Simplificando a última equação, obtemos o algoritmo da enésima raiz:
(eq5)


\( x_{k+1} = \dfrac{1}{n} \left[ (n-1)x_k + \dfrac{\phi}{x_k^{n-1}} \right] \)

2. Implementação

def nth_root(x, n, errto = 1E-5):
    """
     Return the nth-root of a number.
 
     nth_root(x, n, errto = 1E-5)
 
     * x: Float value
     * n: nth-root
     * errto: tolerated aproximation error (default: 1E-5)
 
     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/
 
     Marc 2010
    """
 
    n = int(n)
    x = float(x)
    zold = x/2.0
    errno = errto + 1
 
    while errno > errto:
        znew = (1.0/n) * ((n-1)*zold + x/zold**(n-1))
        if zold != 0:
            errno = abs(znew - zold)/abs(znew)
        else:
            break
        zold = znew
 
    return znew

Disponível para download em http://www.sawp.com.br/code/misc/nth_root.py

3. 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] http://en.wikipedia.org/wiki/Nth_root_algorithm