Um método numérico para encontrar as raı́zes
de um polinômio baseado no vetor gradiente.
Flaulles Boone Bergamaschi1
1
Universidade Estadual do Sudoeste da Bahia (UESB)
Cep 45.083-900- Vitória da Conquista – BA – Brasil
[email protected]
Abstract. This method is an alternative to the problem of finding roots of a
polynomial equation. He will be based on the gradient method used to find
maximum and minimum of a function of two variables.
Resumo. Este método é uma alternativa para o problema de encontrar raı́zes
de uma equação polinomial. Ele será baseado no método gradiente utilizado
para encontrar máximos e mı́nimos de uma função de duas variáveis.
1. Introdução
Em 1823 um jovem matemático Norueguês pôs fim a um problema que durava séculos:
o problema da quı́ntica. Niels Henrik Abel tinha apenas 21 anos quando conseguiu
demonstrar que não podemos obter uma fórmula geral (que utilize apenas as quatro
operações e extração de raı́zes) para obter as raı́zes de uma equação(do tipo polinomial) de
grau cinco. De forma independente outro jovem matemático estava obcecado pelo mesmo
problema. Évariste Galois, foi mais longe. Ele conseguiu mostrar quais equações poderiam ser resolvidas por fórmula e quais não poderiam. Para este feito Galois criou uma
ferramenta que mais tarde se transformou em um novo ramo na matemática: a teoria dos
grupos. A genialidade do feito de Galois impressionou e ainda impressiona matemáticos
do mundo todo. Mais detalhes desse feito veja em [Livio 2009] e [Eves 2004].
Hoje temos vários problemas onde somos levados a encontrar as raı́zes de uma
determinada equação polinomial de grau maior ou igual a cinco. Sabendo dos resultados de Abel e Galois, somos forçados a desenvolver métodos numéricos para o cálculo
dessas raı́zes. Em geral os métodos clássicos são baseados no seguinte princı́pio: dada
uma equação polinomial, construı́mos uma matriz chamada de matriz companheira.
Os autovalores dessa matriz serão as raı́zes da equação. Devido a grande aplicabilidade, este método é encontrado em algumas funções pré-definidas de softwares como
o Matlab([Hanselman 2003]), Maple e outros.
Tais métodos baseados no cálculo de autovalores em certos casos são vulneráveis a erros de arredondamento. Sua estabilidade depende do condicional da matriz
companheira. Assim, como alternativa vamos utilizar o vetor gradiente, que pode reduzir
tais erros e encontrar respostas mais confiáveis.
Nosso método consiste em criar uma função auxiliar a partir do polinômio dado
e encontrar seus pontos de mı́nimo. Estes serão as raı́zes reais ou complexas da equação
dada. Nesta busca vamos utilizar o método gradiente que é largamente utilizado na busca
de máximos e mı́nimos de funções de várias variáveis.
2. Estrutura do método
Antes de iniciar, lembramos que um polinômio de grau n mônico em C será do tipo:
p(x) = xn + an−1 xn−1 + · · · + a1 x + a0 com ai ∈ C para todo i = 0, · · · , n − 1. Estamos
interessados nas raı́zes desse polinômio, ou seja, onde p(x) = 0.
Lembramos também que todo polinômio de grau n em C tem no máximo n raı́zes
distintas em C(para mais detalhes veja em [Gonçalves 2006]).
Vamos considerar que um número complexa a + bi pode ser visto em R2 como
o par (a, b). O teorema abaixo nos dá uma região circular do plano onde todas as raı́zes
reais ou complexas estão.
Teorema 1: Seja p(x) = xn + an−1 xn−1 + · · · + a1 x + a0 um polinômio de grau
n e a0 6= 0. Se x é uma raiz de p, então
|x| ≤ L,
onde L =
1
max {|ai |1/(n−i) }
0≤i≤n−1
log(2)
Para a demonstração desse Teorema veja em [Bergamaschi 2006].
Dessa forma considere uma equação polinomial de grau n:
xn + an−1 xn−1 + · · · + a1 x + a0 = 0
onde ai ∈ C.
Substituindo x = a + bi em p(x) podemos separar a parte real e a parte imaginária
da seguinte forma: xn + an−1 xn−1 + · · · + a1 x + a0 = U (a, b) + V (a, b)i. Se queremos
p(x) = 0 então devemos ter:
U (a, b) + V (a, b)i = 0
.
Isto implica em U (a, b) = 0 e V (a, b) = 0. Onde podemos ter U 2 (a, b) = 0 e
V 2 (a, b) = 0. Portanto devemos encontrar os pontos de mı́nimo da função F (a, b) =
U 2 (a, b) + V 2 (a, b). Não demonstraremos, mas é possı́vel ver que os pontos de mı́nimo
de F serão as raı́zes da equação dada anteriormente.
Na busca por mı́nimos de F vamos utilizar o método gradiente. Mas devemos
lembrar que o método gradiente funciona somente com uma condição inicial, ou seja,
precisamos de um ponto inicial (x0 , y0 ) para iniciar o método. Assim vamos tomar a
região dada pelo Teorema 1 e espalhar de forma aleatória vários pontos nessa região.
Vamos iniciar o método em cada ponto. Dessa forma teremos uma grande chance de
encontrar os mı́nimos de F .
2.1. Método Gradiente
Vamos agora fazer algumas considerações sobre o vetor gradiente:
Seja f : D ⊂ R2 −→ R uma função derivável em D. Então podemos afirmar
que:
i) o vetor gradiente ∇f (x) aponta para uma direção onde f (x) é crescente.
ii) dentre todas as direções ao longo das quais f (x) cresce, a direção do gradiente
∇f (x) é a de crescimento mais rápido.
Tendo em mente esses resultados considere um ponto p0 qualquer em D. Pelo
item ii a direção −∇f (p0 )(direção contrária ao vetor gradiente) tem maior decrescimento.
Nosso objetivo é caminhar nesta direção para encontrar o mı́nimo de f (x). Para auxiliar
vamos definir a função g0 (t) = f (p0 − t∇f (p0 )).
Observe que a função g0 (t) é de uma variável. Podemos então, aplicar o método
da seção áurea(ou qualquer outro método para encontrar mı́nimos em uma dimensão) para
encontrar seu mı́nimo, digamos p1 .
Repetimos o processo para p1 , ou seja, definimos g1 (t) = f (p1 − t∇f (p1 )) e
encontramos seu mı́nimo p2 .
O processo segue até que a distância entre pn e pn−1 seja menor que um certo δ
fixado, ou seja kpi − pi−1 k < δ. Também podemos utilizar como critério de parada o
próprio vetor gradiente. Nesse caso, paramos o método se a norma do vetor gradiente em
pn for menor que um certo δ.
3. Exemplo
Para facilitar, vamos considerar o polinômio p(x) = x2 + 1. Utilizamos o Teorema 1 para
encontrar a região onde todas as raı́zes desse polinômio estão. Para isto vamos calcular:
√
1
1
L=
max {|ai |1/(n−i) }, com n = 2, ou seja, L =
M ax{ 1, 0}.
log(2) 0≤i≤n−1
log(2)
1
Onde temos L =
' 3, 321. Dessa forma temos que todos as raı́zes da
log(2)
equação estão dentro do cı́rculo de raio R = L e centro [0,0] esta será nossa região D.
Para encontrar essas raı́zes vamos construir a função F :
Tomando x = a + bi e calculando p(x) temos p(a + bi) = (a2 − b2 + 1) + 2abi.
Assim U (a, b) = a2 − b2 + 1 e V (a, b) = 2ab. Como F (a, b) = U 2 (a, b) + V 2 (a, b) temos
que:
F (a, b) = a4 + b4 + 2a2 b2 + 2a2 − 2b2 + 1
Sabemos que os pontos de mı́nimo de F são exatamente as raı́zes do polinômio.
Para encontrá-los vamos utilizar o método gradiente, ou seja, escolhemos um ponto na
região D e iniciamos o método. Dois problemas surgem agora: i) o método gradiente
pode divergir dependendo do ponto escolhido. ii) Dependendo da escolha dos pontos
iniciais podemos não ter todas as raı́zes.
Em relação a i) temos a seguinte conjectura: Dada F obtida da forma acima, ou
seja, a partir de uma equação polinomial o método gradiente sempre converge para algum
ponto de mı́nimo desde que o ponto escolhido não seja um ponto de mı́nimo/máximo
local. Fizemos esta conjectura porque até o momento temos apenas fortes indı́cios sobre
o resultado. Em relação a ii) devemos iniciar o método em vários pontos escolhidos de
alguma forma. A princı́pio vamos escolher de forma aleatória uma quantidade de pontos.
Isto pode aumentar muito o tempo de busca.
No exemplo acima aplicamos o método gradiente em dois pontos: (5,3) e
(−5, −3). Em ambos os casos, com poucas iterações temos os mı́nimos (0, 1) e (0, −1),
que são exatamente as raı́zes complexas de p(x) = x2 + 1, ou seja, ±i.
Observe as curvas de nı́vel na Figura 1. Nos pontos m1 = (0, 1) e m2 = (0, −1)
temos os zeros da função F que são exatamente as raı́zes de p(x) = x2 + 1.
m1
m2
Figura 1. Curvas de nı́vel F
Figura 2. Gráfico com curvas de nı́vel de F
4. Considerações finais
Para encontrar a função F recomendamos a utilização de um software com manipulação
algébrica, ou uma implementação para o Matlab baseada em vetores. Isto não é muito
difı́cil uma vez que estamos trabalhando com funções polinomiais.
Não poderı́amos também deixar de comentar sobre a forma aleatória de iniciar
o método gradiente. Sugerimos um número inicial de pontos dentro da região circular.
Caso o método não encontre todas as raı́zes, essa quantidade deverá ser aumentada gradativamente. Podemos controlar isso uma vez que sabemos a quantidade máxima de raı́zes.
Figura 3. Gráfico com curvas de nı́vel em 3D de F
Também devemos observar a multiplicidade de cada raı́z, pois a mesma pode ser
contada duas vezes, é o caso do polinômio p(x) = x2 − 2x + 1 que tem apenas uma única
raı́z.
Acreditamos que a conjectura enunciada no texto acima não seja de demonstração
complicada dada a forma relativamente simples de F .
5. Agradecimentos
Agradeço ao professor Márcio A. A. Bortoloti por conversas valiosas.
Referências
Bergamaschi, F. B. (2006). Comparando os teoremas que tratam sobre o limite dos zeros
de um polinômio. Ermac VI.
Eves, H. (2004). Introdução à história da Matemática. Unicamp, 1th edition.
Gonçalves, A. (2006). Introduçõ à álgebra. Impa, 5th edition.
Hanselman, D. (2003). Matlab Curso Completo. Prentice Hall, 1th edition.
Livio, M. (2009). A equação que ninguém conseguia resolver. Record, 1th edition.