1.3.6 Raízes de Equações — Raízes de Polinômios — O Método de Laguerre

1. Introdução

O método nomeado em homenagem ao matemático francês Edmond Laguerre, consiste em aproximar raízes de um polinômio $p(x)$ .

Ele possui a vantagem sobre o Método de Bairstow de possuir uma taxa de convergência superior em uma ordem — ou seja, converge cubicamente –, não importando a aproximação inicial dada.

Sendo baseado no Método de Newton, encontra a raiz real mais próxima da estimativa inicial. Contudo, ao contrário do primeiro, que pode não convergir, dependendo da aproximação inicial dada, o Método de Laguerre sempre irá convergir à uma raiz real, independendo de qual seja esta estimativa. Todavia, ele não permite que todas as raízes do polinômio sejam encontradas, além de não possuir garantia de convergência no caso do polinômios possuir raízes complexas. Por isso, uma abordagem interessante ao se trabalhar polinômios é utilizar o método de Bairstow para se encontrar suas raízes e, então, refinar a aproximação utilizando-se o método de Laguerre, uma vez que o primeiro possui uma taxa de convergência menor e costuma ser computacionalmente mais caro.

2. Desenvolvimento do Método de Laguerre

Seja o polinômio:

$eq1$

$$p \left( x \right) =C\prod _{i=1}^{n}x-x_{i}$$

Tomando seu logaritmo,

$eq2$

$$\ln \left( p \left( x \right) \right) =\ln \left( C \right) +\sum _ {i=1}^{n}\ln \left( x-x_{i} \right)$$

Chamaremos de $S_{1}$ a derivada da função acima,

$eq3$

$$S_{1}={\dfrac {d}{dx}\ln \left( p \left( x \right) \right) = \sum _{i=1}^{n} \left( \ln \left( x-x_{i} \right) \right)^{-1}$$

Tomando $S_{2}$ como a derivada segunda da mesma função:

$eq4$

$$S_{2}={\dfrac {d^{2}{d{x}^{2}}\ln \left( p \left( x \right)\right) = \sum _{i=1}^{n} \left( \ln \left( x-x_{i} \right) \right) ^{-2}$$

Podemos assumir que a raiz $x_1$ está a uma certa distância $a$ de um valor $x$ qualquer e que todas as outras estão à uma distância $b$ deste mesmo ponto. Ou seja:

$eq5$

$$a=x-x_{1}$$

$eq6$

$$b=x-x_{i}$$

onde $i = 2,3,\ldots,n$ .

Com estas expressões, podemos escrever $S\_{1}$ e $S\_{2}$ em termos de $a$ e $b$ :

$eq7$

$$S_{1}={a}^{-1}+{\dfrac {n-1}{b}$$

$eq8$

$$S_{2}={a}^{-2}+{\dfrac {n-1}{b}^{2}}$$

Isolando $b$ , podemos escrever $a$ em termos de $S\_{1}$ e $S\_{2}$ :

$eq9$

$$a={\dfrac {n}{S_{1}+\sqrt { \left( n-1 \right) \left( nS_{2}-{S_{1}}^{2} \right) }}$$

tomando $S\_{1}={\dfrac {\dfrac {d}{dx}p \left( x \right) }{p \left( x \right) }$ em $S\_{2}$ , uma vez que $S\_{2}={S\_{1}}^{2}-{\dfrac {\dfrac {d^{2}{d{x}^{2}}p \left( x \right) }{p \left( x \right) }$, teremos:

$$S_{2}={\dfrac { \left( {\dfrac {d}{dx}p \left( x \right) \right) ^{2}-p \left( x \right) {\dfrac {d^{2}{d{x}^{2}}p \left( x \right) }{\left( p \left( x \right) \right) ^{2}}$$

Desta forma, podemos obter $a$ em termos da função $f(x)$ e suas derivadas:

$eq10$

$$a={\dfrac {nf \left( x \right) }{\dfrac {d}{dx}f \left( x \right) + \sqrt {H \left( x \right) }}$$

onde $H \left( x \right) = \left( n-1 \right) \left( nS\_{2}-{S\_{1}}^{2}\right)$ , portanto $H(x)$ pode ser expresso como:

$eq11$

$$H \left( x \right) = \left( n-1 \right) \left( \left( n-1 \right) \left( {\dfrac {d}{dx}f \left( x \right) \right) ^{2}-nf \left( x \right) {\dfrac {d^{2}{d{x}^{2}}f \left( x \right) \right)$$

como $x\_{i+1}=x\_{i}-a$ , então

$eq12$

$$x_{i+1}=x_{i}-{\dfrac {nf \left( x_{i} \right) }{\dfrac {d}{dx}f \left( x_{i} \right) +\sqrt {H \left( x_{i} \right) }}$$

A Equação 12 é a usada pelo Método de Laguerre. </p>

3. Taxa de Convergência

A demonstração da taxa de convergência cúbica é muito semelhante àquela apresentada no artigo sobre o Método de Halley, já que ambas recebem a primeira e segunda derivada. Note que naquele artigo utilizamos Séries de Taylor para aproximar à função utilizada no algoritmo. Se seguirmos os mesmos passos com a função polinomial, obteremos a mesma expressão para o erro. </p>

4. Implementação

def laguerre(p, d1p, d2p, polDegree=1, x0=1.0, errto=0.001, imax=100):
    """
    Return the root of a function (using the Laguerre Method)

    laguerre(p, d1p, d2p, polDegree, x0=1.0, errto=0.001, imax=100)

    * p: Function where find the roots
    * d1p: analytic derivative of f
    * d2p: second derivative of f
    * polDegree: grau do polinomio 
    * 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
    """
    n = polDegree
    errno = errto + 1.0
    iterCount = 0
    xn = x0
    while errno > errto and iterCount < imax:
        x0 = xn
        px = p(x0)
        d1px = d1p(x0)
        d2px = d2p(x0)
        H = (n-1)*((n-1)*d1px*d1px - n*px*d2px)
        if fabs(d1px + sqrt(H)) > fabs(d1px - sqrt(H)):
            xn = x0 - n*px/(d1px + sqrt(H))
        else:
            xn = x0 - n*px/(d1px - sqrt(H))
        iterCount += 1
        if xn != 0:
            errno = fabs((xn-x0)/xn)
    return xn

Note que esta função pode ser utilizada também para aproximação de funções não-polinomiais com bastante sucesso. Alguns exemplos de utilização desta implementação estão em: http://www.sawp.com.br/code/rootfind/laguerre.py </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/.

References

[1] http://en.wikipedia.org/wiki/Laguerre%27s_method
[2] Ralston, Anthony and Rabinowitz, Philip, A First Course in Numerical Analysis.,$2nd ed.$ McGraw-Hill and Dover, $2001$, 380.