1.3.5 Raízes de Equações – Raízes de Polinômios – O Método de Durand-Kerner

1. Introdução

O Método de Durand-Kerner, também chamado de Método de Weierstrass, é uma técnica numérica usada para obter todas as raízes de um polinômio, que atua de forma semelhante ao Método do Ponto Fixo, mas é generalizado para buscar todos os zeros da função polinomial.

2. Desenvolvimento do Método

Seja \(p(x) \) a função polinomial cujas raízes queremos encontrar. Sabemos que podemos escrever este polinômio como um produtório da função linear dependente de \(x \) e das suas raízes \(z_{k} \) :
(eq1)


\( p \left( x \right) = \left( x-z_{{1}} \right) \left( x-z_{{2}} \right) \ldots \left( x – z_{n} \right) =\prod _{i=1}^{n} (x-z_{{i}}) \)

Para encontrarmos a i-ésima raiz deste polinômio, podemos simplesmente isolá-la, gerando a seguinte expressão:
(eq2)


\( z_{{i}}=x-{\frac {p \left( x \right) }{\prod_{{j=1}{j\neq i}}^{n} ~(x-z_{{j}})}} \)

Note que podemos encontrar a i-ésima raiz, utilizando uma iteração que leva em conta a aproximação de todas as outras j-ésimas raízes. Sendo assim, podemos expressar o produtório acima como:
(eq3)

\( z_{{i}}=x-{\frac {p \left( x \right) }{\prod _{j=1}^{i-1} ~(x-z_{{j})} \prod _{j=i+1}^{n} ~(x-z_{{j}})}} \)

Permitindo-nos obter as raízes através da seguinte função de iteração:
(eq4)

\( z_{{i+1}}=z_{{i}}-{\frac {p \left( z_{{i}} \right) }{\prod _{j=1}^{i-1}(z_{{i}}-z_{{j}}) ~ \prod _{j=i+1}^{n} ~(z_{{i}}-z_{{j}})}}\)

Note que esta função não possui uma derivação baseada na fórmula de iteração do Método de Newton-Raphson, possuindo uma forma muito semelhante ao do Método do Ponto Fixo. Essa característica indica que o método nem sempre converge, sendo problemático para raízes múltiplas, uma vez é exigido que \(z_{i} \neq z_{j} \) .

A convergência do Método de Durand-Kerner também não possui taxa constante. Como não utiliza o critério de Newton, nem sempre converge quadraticamente, sendo que pode possuir esta taxa sob algumas circunstâncias, enquanto converge linearmente para outras. Um estudo sobre a convergência deste método pode ser encontrado no artigo “A convergence theorem for a method for simultaneous determination of all zeros of a polynomial”[1].

3. Implementação

 def duran_kerner(p, polDegree=1, x0=complex(1,1), errto=0.001, imax=500):
    """
    Return all roots of Polynom (using the Duran-Kerner Method)
 
    duran_kerner(p, polDegree=1, x0=1.0, errto=0.001, imax=100)
 
    * p: polynom where find the roots
    * polDegree: polynom degree
    * x0: initial estimative (complex)
    * errto: tolerated error
    * imax: max of iterations allowed
 
    return: a list with all roots of polynom
 
    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
    """
 
    def filt(l):
        r = l.real
        i = l.imag
        if abs(r) < errto:
            r = 0.0
        if abs(i) < errto:
            i = 0.0
        return complex(r, i)
 
    n = polDegree
    errno = errto + 1.0
    iterCount = 0
 
    if type(x0) == list:
        zold = x0[:] + abs(n-len(x0))*[ complex(0,0) ]
    elif type(x0) == complex:
        zold = [ x0+random() for i in xrange(n) ]
    else:
        zold = [ complex(random()*x0,random()*x0) for i in xrange(n) ]
 
    znew = n * [ complex(0, 0) ]
 
    while errno > errto and iterCount < imax:
        for i in xrange(len(zold)):
            prod = 1
 
            for w in (range(i) + range(i+1, len(zold))):
                elem = zold[i] - zold[w]
                while elem == 0:
                    elem += errto
                prod *= elem
 
            pz = p(zold[i])
            while pz == 0:
                pz += errto
 
            znew[i] = zold[i] - pz/prod
 
        errno = 0
        for i in xrange(len(znew)):
            if znew[i] != 0:
                t = abs(znew[i] - zold[i])/abs(znew[i])
                if errno < t:
                    errno = t
 
        zold = znew[:]
        iterCount += 1
    znew.sort(key=lambda r: r.real)
    return map(filt, znew)

Veja um exemplo da utilização desta função em http://www.sawp.com.br/code/rootfind/durankerner.py.

4. Conclusões

O Método de Durand-Kerner é simples de se implementar e possui a vantagem de não exigir funções adicionais para calcular as derivadas da função cujas raízes queremos descobrir. Além disso, permite ainda que todas as raízes sejam encontradas, sendo elas reais ou complexas.

Todavia, quando o polinômio possui raízes múltiplas, acaba por gerar um denominador zero na função de iteração. Para contornar este problema, a estratégia adotada na implementação acima foi acrescentar um fator na ordem do erro tolerado para a aproximação. Isso serve para que a divisão seja feita na ordem do erro, ao invés do zero, mas mantendo a aproximação sob um valor tolerável.

Outro problema encontrado ao utilizar o Método de Durand-Kerner em um programa real é que o produtório presente no denominador da Equação 4 produza valores que estão fora do intervalo suportado pela arquitetura (underflow e overflow aritmético).

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] P. Marica, A convergence theorem for a method for simultaneous determination of all zeros of a polynomial, l’institut mathematique Beograd, V.28(N.42),(1980), 158–168.
[2] http://home.roadrunner.com/~jbmatthews/misc/groots.htm