Método de Newton para calcular raı́zes de

polinômios
Exercı́cio Computacional
MAP3122 - Quadrimestral 2020
Prof. Antoine Laurain

Seja f (x) = p(x)/q(x), onde p, q : R → R são duas funções diferenciáveis.

Questão 1. Verifique que o método de Newton para calcular uma raiz de f pode ser escrito na forma
1
xk+1 = xk − p0 (xk ) q 0 (xk )
. (1)
p(xk ) − q(xk )

Podemos usar esta propriedade para calcular todas as raı́zes de um polinômio

p(x) = an xn + an−1 xn−1 + · · · + a1 x + a0

com coeficientes ak reais ou complexos. Observe que um polinômio de ordem n sempre tem n raı́zes
complexas (não necessariamente distintas), esse é o teorema fundamental da álgebra. Chamamos então
de z1 , . . . , zn ∈ C as raı́zes complexas de p. A tarefa principal desse exercı́cio prático é de calcular uma
aproximação numérica de todas as raı́zes zk .
Começamos calculando uma raiz de p usando o método de Newton usual. Para calcular as outras
raı́zes, usamos o raciocı́nio seguinte. Primeiro, o polinômio p pode ser escrito como

p(x) = an (x − z1 )(x − z2 ) . . . (x − zn ).

Suponhamos que já temos a disposição as raı́zes z1 , z2 , . . . , z` , com 1 ≤ ` < n. Definimos

q(x) = (x − z1 )(x − z2 ) . . . (x − z` ).

Observamos que
p(x)
f (x) = = a1 (x − z`+1 ) . . . (x − zn ).
q(x)
Esta função f é um polinômio cujas raı́zes são exatamente z`+1 , z`+2 , . . . , zn . Assim, aplicando o método
de Newton para f , podemos achar uma nova raiz de p, diferente das raı́zes de p já calculadas. Como
f é da forma f = p/q, podemos usar a fórmula (1). Observamos que a derivada de q(x) satisfaz a
propriedade seguinte:
q 0 (x) 1 1 1
= + + ··· + . (2)
q(x) x − z1 x − z2 x − z`
Vamos usar a expressão (2) na iteração de Newton (1).
Cada nova raiz calculada com esse método tem um valor mais impreciso que a anterior, uma vez
que as raı́zes já calculadas contem erros, e são usadas no método de Newton para calcular uma nova
raiz, assim os erros vão se acumulando. Portanto, depois de aproximar uma raiz zk usando (1), vamos
recalcular uma nova aproximação de zk usando o método de Newton simples para o polinômio p. Para
inicializar essa iteração de Newton, use o valor zk obtido com o outro algoritmo.
O objetivo deste exercı́cio prático é de escrever uma função z=polyzeros(a), que calcula todas as
raı́zes de um polinômio p(x) = an xn + an−1 xn−1 + · · · + a1 x + a0 dado, onde a = [a0 , a1 , . . . , an ] é o
vetor dos coeficientes de p. A função z=polyzeros(a) tem o vetor a como entrada e o vetor das raı́zes
z = [z1 , . . . , zn ] como saı́da.

1
Figura 1: Comparação entre as 6 raı́zes do polinômio p(x) = 1.5x6 + 2x5 + 3x4 + 4x3 + 8x2 − 3x − 6
calculadas com a função [Link](p) (esquerda) e as raı́zes calculadas com a função z=polyzeros(a)
(direita).

Instruções, observações e dicas

• O programa deverá ser escrito em Python, usando o pacote numpy. O seu código deverá estar
bem comentado e estruturado. A entrada e a saı́da deverão ser feitas de forma a ajudar o usuário
a executar o programa e devem facilitar a análise dos resultados. Se o seu programa precisa de
arquivos de entrada, considere que os mesmos encontram-se na mesma pasta do executável, ou faça
de forma que solicite o caminho/nome do arquivo ao usuário.
• A entrega deverá conter um relatório (em .pdf), contendo a análise do problema estudado, e o
código usado para as simulações computacionais (arquivo .py). A entrega também deverá ser feita
em um arquivo compactado único.
• O uso de LATEX para escrever o relatório é fortemente incentivado. Os relatórios escritos em Latex
receberão um bónus de 0.5 pontos.
• Números complexos em Python têm a forma a+b*1j ou a+bj, onde a, b são valores numéricos.
• Para capturar as raı́zes complexas, você precisará usar valores iniciais complexos no método de
Newton.
• Para a inicialização do método de Newton, será melhor utilizar valores iniciais aleatórios. O
comando para isto é [Link]
• Um polinômio p poderá ser definido a partir de um vetor de coeficientes utilizando a função
numpy.poly1d. A derivada de um tal polinômio p poderá ser calculada com [Link]. O
valor de p em um ponto particular também poderá ser calculado usando a função [Link].
• Será necessário usar um critério de parada para o método de Newton. O módulo |p(xk )| de p(xk )
(cuidado, pois aqui p(xk ) é um número complexo) pode ser usado para um critério de parada da
seguinte maneira. A cada iteração, a condição |p(xk )| < ε é testada, onde ε é um valor pequeno
escolhido pelo usuário. Se |p(xk )| < ε é satisfeita, então paramos a iteração de Newton, caso
contrário, continuamos. Podemos escolher por exemplo ε = 10−16 ; experimente com outros valores
para ver se isto muda o resultado. Além disto, é necessário impor um número máximo de iterações
itmax para evitar um loop infinito. Um valor razoável para o método de Newton é itmax entre 7
e 10.
• Como usamos valores aleatórios para inicializar a iteração de Newton, acontece as vezes que o
algoritmo fornece valores errados ou valores do tipo NaN. Por isso, é aconselhável rodar algumas
vezes o programa para cada exemplo, para eliminar casos degenerados. Isso é particularmente
verdadeiro quando a ordem do polinômio fica maior e os resultados do programa se tornam mais
instáveis.
• Vamos testar o programa usando dois métodos:

2
 1. Escolha z1 , . . . , zn ∈ C, e calcule os coeficientes ak do polinômio p(x) = (x−z1 )(x−z2 ) . . . (x−
zn ). Depois use o programa com esses coeficientes. O programa deverá entregar as mesmas
raı́zes z1 , . . . , zn ∈ C, ou uma boa aproximação delas (ver Tabela 1).
2. Para um polinômio dado na forma p(x) = an xn +an−1 xn−1 +· · ·+a1 x+a0 , compare o resultado
obtido com sua função z=polyzeros(a) e com a função [Link](p) (ver Tabela 2).
• Os resultados de sua função z=polyzeros(a) e de [Link](p) devem ser plotados em duas
figuras diferentes, como na Figura 1. Cada raiz será representada por um ponto em cada figura.
O eixo horizontal representa a parte real das raı́zes, e o eixo vertical a parte imaginária. Deve-
se observar que as duas figuras fornecem visualmente os mesmos pontos para alguns exemplos.
Observe que quando os coeficientes a = [a0 , a1 , . . . , an ] são reais, as raı́zes complexas zk sempre são
conjugadas, i.e. para cada raiz da forma z = a + ib com b 6= 0, existe uma outra raiz conjugada
z = a − ib; esse fenômeno pode ser observado na Figura 1. Você deveria observar isso na suas
figuras também.

Forma do relatório

O relatório (em .pdf) será constituı́do dos seguintes elementos:

• Resposta à Questão 1.

• Testes e análise de erro:

– Escolha dois polinômios (de ordem entre 4 e 10) e para cada um destes polinômios, faça uma
análise de erro seguindo as instruções da Tabela 1. Comente os resultados.
– Escolha dois polinômios (de ordem entre 5 e 10) e para cada um destes polinômios, faça uma
análise de resı́duo do tipo da Tabela 2. Comente os resultados.
• Figuras: escolha três polinômios (de ordem entre 4 e 10) e plote as raı́zes obtidas com sua função
z=polyzeros(a) e com a função [Link](p) em duas figuras separadas, como na Figura 1.
Comente os resultados. Um ponto interessante, é de discutir a estabilidade do cálculo das raı́zes
com respeito à ordem dos polinômios, usando z=polyzeros(a) e [Link](p).

Critérios de Correção

• Questão 1 (0.3 pts)

• Implementação de z=polyzeros(a) (serão julgadas: a exatidão dos resultados e a eficiência da

implementação).
– Método de Newton para raı́zes de f (x) = p(x)/q(x). (1.6 pts)
– Método de Newton para refinamento das raı́zes de p(x). (1.6 pts)

• Código bem documentado: comentários, legibilidade. (1.5 pts)

• Testes e análise de erro (relevância dos testes, apresentação dos resultados e comentários).
– Análise de erro do tipo da Tabela 1. (1.5 pts)
– Análise de resı́duo do tipo da Tabela 2. (1.5 pts)

• Figuras (relevância dos testes, qualidade das figuras). (1 pts)

• Qualidade do relatório (relevância dos comentários e apresentação geral). (1 pts)
˙
• Uso de LATEX(0.5 pts extra)

• Será verificado se o programa entregue roda e produz saı́das consistentes com os resultados apre-
sentados no relatório.
• Em caso de atraso de até 48h, -2 pontos. Após isso, o EP não será aceito.

3
Tabela 1: Tabela comparando os erros cometidos usando as funções z=polyzeros(a) e [Link](p)
para um polinômio p conhecido cujas raizes são conhecidas. Para este tipo de tabela, escolha as raizes
exatas z1 , . . . , zk ∈ R, e considera o polinômio p(x) = (x − z1 )(x − z2 ) . . . (x − zn ). Como as raizes são
reais, é fácil ordenar as raizes obtidas com z=polyzeros(a) e [Link](p) para calcular os erros.
Pode usar tambem raizes complexas, mas fica mais difı́cil ordenar as raizes para calcular os erros.

raizes exatas polyzeros erro polyzeros [Link] erro [Link]

z1 z̃1 |z1 − z̃1 | ẑ1 |z1 − ẑ1 |
z2 z̃2 |z2 − z̃2 | ẑ2 |z2 − ẑ2 |
z3 z̃3 |z3 − z̃3 | ẑ3 |z3 − ẑ3 |
z4 z̃4 |z4 − z̃4 | ẑ4 |z4 − ẑ4 |

Tabela 2: Neste caso temos um polinômio dado na forma p(x) = an xn + an−1 xn−1 + · · · + a1 x + a0 , e
calculamos as raizes (que podem ser complexas) usando z=polyzeros(a) e [Link](p). Como as
raizes exatas não são conhecidas, não podemos calcular o erro cometido como na Tabela 1, mas podemos
calcular o resı́duo, que é simplesmente o valor do polinômio p em uma raiz aproximada. Se a raiz for
exata, o resı́duo vale zero, então o resı́duo deveria ser o mı́nimo possı́vel. Assim, o valor do résiduo
fornece uma informação sobre a precisão da aproximação da raiz.

polyzeros resı́duo polyzeros [Link] resı́duo [Link]

z̃1 |p(z̃1 )| ẑ1 |p(ẑ1 )|
z̃2 |p(z̃2 )| ẑ2 |p(ẑ2 )|
z̃3 |p(z̃3 )| ẑ3 |p(ẑ3 )|
z̃4 |p(z̃4 )| ẑ4 |p(ẑ4 )|