Briot Ruffini

Determina¸c˜ao de ra´ızes de polinˆomios:
M´etodo de Briot-Ruffini-Horner
Marina Andretta/Franklina Toledo
ICMC-USP

29 de outubro de 2012
Baseado no livro C´alculo Num´erico, de Neide B. Franco

Marina Andretta/Franklina Toledo (ICMC-USP)

sme0100 - C´ alculo Num´ erico I

29 de outubro de 2012

1 / 17

C´alculo do valor de um polinˆomio

Em qualquer m´etodo iterativo para determinar ra´ızes de um polinˆomio, ´e necess´ario calcular o valor do polinˆ omio P em um dado ponto x e, possivelmente, de suas derivadas.
Por isso, ´e necess´ario que este c´alculo seja feito da maneira mais precisa e computacionalmente econˆ omica poss´ıvel.

Marina Andretta/Franklina Toledo (ICMC-USP)

sme0100 - C´ alculo Num´ erico I

29 de outubro de 2012

2 / 17

C´alculo do valor de um polinˆomio

Para medir a eficiˆencia de algoritmos para calcular o valor de um polinˆomio, denotaremos por µ o tempo computacional de se calcular uma multiplica¸c˜ao e por α o tempo computacional de se calcular uma adi¸c˜ao.
Se P(x) ´e calculado da maneira tradicional, usando a f´ormula
P(x) = an x n + an−1 x n−1 + ... + a2 x 2 + a1 x + a0 , devemos calcular as potˆencias de x, fazendo x k = x(x k−1 ). O tempo computacional gasto com estas opera¸c˜ oes ´e (n − 1)µ.

Marina Andretta/Franklina Toledo (ICMC-USP)

sme0100 - C´ alculo Num´ erico I

29 de outubro de 2012

3 / 17

C´alculo do valor de um polinˆomio

O c´alculo dos termos da forma ak x k requerem nµ.
A soma dos termos requerem nα.
Ou seja, o tempo computacional total gasto para calcular P(x) ´e
(2n − 1)µ + nα.
Al´em disso, se for necess´ario calcular P (x), ser´a necess´aria, aproximadamente, a mesma quantidade de tempo computacional.

Marina Andretta/Franklina Toledo (ICMC-USP)

sme0100 - C´ alculo Num´ erico I

29 de outubro de 2012

4 / 17

M´etodo de Briot-Ruffini-Horner
O M´etodo de Briot-Ruffini-Horner consiste em calcular o valor de P(x) e
P (x) (e, possivelmente, derivadas de ordens superiores) usando a seguinte representa¸c˜ao de