sábado, 16 de abril de 2011

CN 04–Cálculo do valor de um polinômio pelo método de Horner

Os computadores realizam as operações aritméticas obedecendo a uma ordem hierárquica. Primeiro as exponenciações da esquerda para direita, depois as multiplicações e divisões também da esquerda para a direita finalmente as somas e subtrações também da esquerda para a direita. Os parênteses são usados para inverter a ordem hierárquica. Por exemplo,

clip_image002

O computador vai primeiro dividir B por C e somar A ao resultado obtido. O que equivale a seguinte fórmula

clip_image004

A ordem hierárquica das operações pode ser invertida usando um par de parênteses

clip_image006

Neste caso, a presença dos parênteses obriga que a soma seja realizada antes da divisão. Assim, depois de realizada a soma o resultado é dividido por C. Isso equivale a

clip_image008

Entre parênteses a hierarquia continua valendo.

O calculo de valores de polinômios é ubíquo na computação numérica. As funções transcendentais são calculadas usando a série de Taylor correspondente truncada de forma a garantir uma precisão suficiente. Por exemplo,

clip_image010

No Java as funções raiz quadrada, exponencial, logaritmo neperiano, seno, cosseno, tangente, já estão pré-programadas.

No cálculo polinômios o número de operações aritméticas envolvidas cai significativamente se o polinômio for escrito de forma diferente. Por exemplo, se o polinômio a seguir

clip_image012

for escrito da seguinte forma

clip_image014

Observado esta última forma de calcular polinomiais chega-se ao seguinte algoritmo

image

Este esquema é conhecido como esquema de Horner e

clip_image030

No caso de um polinômio de grau n com todos os coeficientes não nulos o esquema de Horner envolve n multiplicações e n adições.

Nenhum comentário:

Postar um comentário