Avaliação de polinômio - Método de Horner

A necessidade de obter o valor de um polinômio P(x) em um ponto x = a, aparece frequentemente em vários problemas provenientes das Ciências e das Engenharias. Geralmente calculamos um polinômio dessa forma:

Ou seja, para avaliar o P(x) de grau n, em x = a, são necessárias n(n + 1)/2 multiplicações e n adições. Computacionalmente falando um algoritmo para resolver esse tipo de problema, utilizando essa forma de resolução, tem complexidade quadrática O(n²). Para ficar claro vejamos o exemplo abaixo.

É fácil perceber no exemplo acima que fizemos 15 multiplicações e 5 adições.

É possível fazer melhor ? SIM!

Em uma aula de cálculo numérico na faculdade um professor me apresentou o método de Horner. Computacionalmente ele é muito interessante pois requer um algoritmo de complexidade linear O(n) para realizar a avaliação de um polinômio P(x). Você pode se perguntar: “Uai, que diferença isso vai me trazer ? Sendo que sempre trabalho com polinômios pequenos de no máximo grau 5, ou seja, a diferença entre utilizar um algoritmo de complexidade quadrática para um de complexidade linear quando se tem uma entrada pequena é quase imperceptível.” "This is for children". Essas coisas de polinômio com grau 1, 2, 3 você trabalha no ensino médio, coisa de fraldinha, merendeira. Em Engenharia a “parada é bruta fi”, é coisa monstruosa, experimenta pegar um polinômio de grau 50 ou maior, e aí ? Fazer 1225 multiplicações é mais rápido que 50 ?

O método de Horner consiste em reescrever o polinômio de forma a evitar potências, como mostra a figura abaixo:

Exemplo:

Um pseudocódigo para implementação do método de Horner:

Input: n-grau do polinômio, x-valor que quero avaliar, c-vetor dos coeficientes.

Output: s-ordenada P(x).

y = c(1);

for(i = 2, i <= n+1, i++){

y = y * x * c(i);

}

s=y;

Posted in: método de horner