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 .
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:
$$ p \left( x \right) =C\prod _{i=1}^{n}x-x_{i} $$
Tomando seu logaritmo,
$$ \ln \left( p \left( x \right) \right) =\ln \left( C \right) +\sum _ {i=1}^{n}\ln \left( x-x_{i} \right) $$
Chamaremos de a derivada da função acima,
$$ 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 como a derivada segunda da mesma função:
$$ 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 está a uma certa distância de um valor qualquer e que todas as outras estão à uma distância deste mesmo ponto. Ou seja:
$$ a=x-x_{1}$$
$$ b=x-x_{i} $$
onde .
Com estas expressões, podemos escrever e em termos de e :
$$ S_{1}={a}^{-1}+{\dfrac {n-1}{b} $$
$$ S_{2}={a}^{-2}+{\dfrac {n-1}{b}^{2}} $$
Isolando , podemos escrever em termos de e :
$$ a={\dfrac {n}{S_{1}+\sqrt { \left( n-1 \right) \left( nS_{2}-{S_{1}}^{2} \right) }} $$
tomando em , uma vez que , 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 em termos da função e suas derivadas:
$$ a={\dfrac {nf \left( x \right) }{\dfrac {d}{dx}f \left( x \right) + \sqrt {H \left( x \right) }} $$
onde , portanto pode ser expresso como:
$$ 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 , então
$$ 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/.