1.3.7 Raízes de Equações — Raízes de Polinômios — O Método de Jenkins-Traub
1. Introdução </p>
O Método de Jenkins-Traub é um algoritmo para busca dos zeros de uma função polinomial que utiliza três estágios de estimativas para aproximar as raízes.
É um método de convergência rápida, uma vez que utiliza o Método de Newton implicitamente no terceiro estágio de aproximação. Sendo assim, é considerado praticamente um padrão na busca de raízes de polinômios[1]. Por ser um algoritmo já projetado para ser implementado computacionalmente, produz soluções gerais, não importando se elas sejam de natureza complexa ou real.
Este algoritmo inicia a busca checando a existência de raízes muito pequenas. Após encontrá-las, tende à buscar raízes muito grandes. Isto cria um intervalo onde as demais raízes provavelmente estarão.
No segundo estágio, o algoritmo reajusta as aproximações das raízes complexas reescalando as variáveis. Nesta fase de execução, as raízes são refinadas uma por vez, e então esta aproximação é aplicada na função polinomial dividida por um fator linear. Desta forma, a fatoração que observaríamos do polinômio em fatores lineares, dividido pela aproximação linear, já produz uma segunda aproximação. Este processo é semelhante ao desenvolvido no Método de Durand-Kerner. </p>
2. Desenvolvimento do Método de Jenkins-Traub
Considere o polinômio
$$ P(z) = z^n + a_{n-1}z^{n-1} + \cdots + a_1z + a_0 = \prod_{j=1}^p (z = \alpha_j)^{m_j} $$
onde os termos são números complexos com e onde a raiz de têm multiplicidade , com , então temos que . Assim, teremos que
$$ P'(z) = \sum_{j=1}^{p} m_j P_j(z) $$
onde
$$ P_j(z) = \dfrac{P(z)}{z-\alpha_j} $$
onde , sabemos que itera sobre o intervalo .
O algoritmo de Jenkins-Traub gera uma sequência de polinômios iniciando com , onde cada outro polinômio para , tendo a forma
$$ H^{(\lambda)}(z) = \sum_{j=1}^{p} c_j^{(\lambda)} P_j(z) $$
com . Se escolhermos uma sequência tal que , isto é, que possua as taxas
$$ d_j^{(\lambda)} = \dfrac{c_j^{(\lambda)}{c_1^{(\lambda)} $$
com , então poderemos encontrar a sequência das aproximações de , utilizando a fórmula
$$ t_{\lambda + 1} = s_{\lambda} – \dfrac{P(s_{\lambda})}{U^{(\lambda+1)}(s_{\lambda} $$
onde é uma normalização de do tipo
$$ U^{(\lambda)} = \dfrac{H^{(\lambda)}(z)}{\sum_{j=1}^{p}c_j^{(\lambda)} $$
A partir dessas funções, o algoritmo utiliza três estágios de aproximação de novos polinômios para aplicar à interação de Newton. </p>
2.1. Primeiro estágio: processo sem deslocamento
Para , utilizamos . No caso, é uma variável escolhida como um polinômio de grau de aproximação
razoável.
2.2. Segundo estágio: processo com deslocamento fixo
Esta etapa da execução que determina as aproximações gerais das menores raízes dos polinômios. Isto é é feito, estimando-se aleatoriamente dentro de um círculo com centro no zero do plano complexo. Ou seja,
$$ s = e^{i\theta}\beta $$
onde é o raio que espera-se conter as menores raízes do polinômio. Esta etapa, normalmente é escolhida entre para o intervalo . </p>
2.3. Terceiro estágio: processo com deslocamento variável (adaptativo)
O polinômio agora é gerado utilizando-se a variável de deslocamento para os demais polinômios e será obtido utilizando-se a Equação 6. </p>
3. Implementação
O algoritmo de Jenkins-Traub, pela sua complexidade, possui um código um pouco mais elaborado, além de ser extenso demais para ser publicado neste artigo. Por questão de conveniência, ele não está presente aqui, estando disponível em
http://www.sawp.com.br/code/rootfind/jenkinstraub.tar.gz.
</p>
4. 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/.