MÉTODO DE HORNER
Una función de la forma
p ( x ) =a0 x N + a0 x N−1 +…+ aN + a N , (XII.1)
Donde las a i, llamadas los coeficientes de P, son constantes y a 0 ≠ 0 , se llama un polinomio de
grado N. La función cero, P(x)=0 para todos los valores de x, se considera un polinomio, pero
no se le asigna ningún grado.
Teorema XII.1 (Teorema fundamental de algebra)
Si P es un polinomio de grado N ≥1 entonces P(x)=0 tiene al menos una raíz (posible
compleja).
Corolario XII.2
Si p ( x ) =a0 x N + a0 x N−1 +…+ aN −1 x +a N es un polinomio de grado N ≥1 , entonces existen
constantes únicas x 1 , x 1 , … , x k , posiblemente complejas, y enteros positivos, m 1 ,m 2 , … ,m k
k
tales que ∑ mi =N y
i=1
p ( x ) =a0 ( x−x 1 )m ( x−x 2)m … ( x−x k )m . (XII.2)
1 2 k
El corolario afirma que los ceros de un polinomio son únicos y que si cada cero x 1es contado
tantas veces como su multiplicidad m 1 , entonces un polinomio de grado N tiene exactamente N
ceros.
Corolario XII.3
Sean P y Q polinomios a lo sumo de grado N. si x 1 , x 1 , … , x k , K > N ,son números distintos con
P ( x i) =Q ( x i) para i= 1,2,…,k, entonces P(x)=Q(x) para todo valor de x.
Para usar el procedimiento de Newton-Raphson en localizar aproximadamente los ceros de un
polinomio P, es necesario evaluar a P y a su derivada en valores específicos.
Como P y sus derivadas son polinomios, la eficiencia computacional requerirá que la evaluación
de estas funciones sea hecha de manera anidada. El método de Horner descrito en el siguiente
teorema incorpora esta técnica y como consecuencia requiere solamente de N multiplicaciones y
N sumas para evaluar un polinomio de enésimo grado arbitrario.
Teorema XII.4 (Método De Horner)
Sea
p ( x ) =a0 x N + a0 x N−1 +…+ aN −1 x +a N
Si
d 0=a0 y d k =a k + d k−1 x 0 ,
Para k =1,2 , … , N −1, N , entonces
d N =P( x¿¿ 0)¿
Además, si
Q ( x ) =d 0 x N−1 +d 1 x N−2 +…+ d N−2 x+ d N −1
Entonces
P ( x ) =( x−a¿¿ 0)Q( x )+d N ¿
Demostración: la primera parte de la demostración es obvia, debido a la definición de los
coeficientes d k (basta solo escribir el polinomio en forma anidada).
Veamos ahora la segunda parte. Por la definición de Q(x):
( x−a¿¿ 0)Q ( x )+ d N =(x−a¿¿ 0) ( d 0 x N−1 +d 1 x N−2 +…+ d N−2 x+ d N −1 ) + d N =¿ ¿ ¿
¿ ( d 0 x N + d 1 x N −1+ …+d N−2 x 2 +d N−1 x ) + ¿
−( d 0 x 0 x N−1 +d 1 x 0 x N −2 +…+ d N −2 x 0 x +d N−1 x0 ) + ¿
+d N =¿
¿ d 0 x N + ( d 1−d 0 x 0 ) x N −1+ …+ ( d N−2−d N−3 x 0 ) x 2 +¿
(d ¿ ¿ N −1−d N−2 x 0 )x +( d N −d N−1 x 0 )¿
Ahora, por las hipótesis d 0=a0 y d k −d k−1 x 0=ak , asique
( x−x ¿¿ 0)Q ( x ) +d N =a 0 x N +a1 x N−1 +…+ aN −1 x +a N =P ( x ) y d N =P (x 0)¿
Ejemplo 1.
Evaluar P ( x ) =2 x 4 −3 x 2+3 x−4 en x 0=−2 usando el método de Horner.
Usando el teorema XII.
d 0=2, d 1=2 (−2 ) +0=−4 ,
d 2=(−4 )(−2 ) −3=5 , d 3=5 (−2 ) +3=−7 ,
Y finalmente
P (−2 )=d 4=(−7 )(−2 ) −4=10
Además, el teorema XII nos dice
P ( x ) =( x+2 ) ( 2 x 3−3 x 2+5 x−7 ) +10
Cuando en el método de Horner se hacen los cálculos a mano, se construye primero una tabla,
que sugiere el nombre de división sintética con frecuencia aplicado a esta técnica. Para el
problema del ejemplo anterior, la tabla aparecía como:
coef . de x 4 coef . de x 3 coef . de x 2 coef . de x terminoconstante
a 0=2 a 1=0 a 2=−3 a 3=3 a 4=−4
x 0=−2 d 0 x 0=−4 d 2 x0 =8 d 2 x0 =−10 d 3 x0 =14
d 0=2 d 1=−4 d 2=5 d 3=−7 d 4 =10
Una ventaja adicional al usar el procedimiento de Horner es que, como
p ( x ) =( x−x 0 ) Q ( x ) +d N
Donde
Q ( x ) =d 0 x N−1 +d 1 x N−2 +…+ d N−2 x+ d N −1 ,
Diferenciando con respecto a x da
P ´ ( x ) =Q ( x ) + ( x−x 0 ) Q´ ( x)
P ( x 0 )=Q(x 0 )
Así, cuando se use el método de Newton-Raphson para encontrar un cero aproximado de un
polinomio P, ambos P y P´ pueden ser evaluados de esta manera. El algoritmo siguiente calcula
P ( x 0 ) y P ´ (x 0) usando el método de Horner.
Algoritmo de Horner
para evaluar el polinomio
P ( x ) =a0 x N + a1 x N−1 +…+a N −1 x+ a N
Y su derivada en x 0 :
Entrada: grado N; coeficientes a 0 , a1 , … , a N ; punto donde evaluar el polinomio x 0 ;
Salida: y=P ( x 0 ) y z=P ´ ( x 0 ) .
Paso 1: tomar
y=a0 ; ( calculando d 0 para P ) ;
z=a 0 ; ( calculando d 0 para Q ) ;
Paso 2: para
j=1,2 ,… , N−1tomar
y=x 0 y +a j ; ( calcular d j para P ) ;
z=x 0 z + y ; ( calcular d j para Q ) ;
Paso 3: tomar:
y=x 0 y +a N ; ( calcular d N para P ) ;
Paso 4: SALIDA (y,z); PARAR.
Un uso interesante del algoritmo de Horner es expresar el desarrollo de Taylor de un polinomio
alrededor de cualquier punto. Sea el polinomio P dado por (XII), y suponemos que buscados los
coeficientes c k de la ecuación.
P(x)= a 0 x N + a 1 x N −1+……. +a N −1 x + a N ,
= c 0 ( x−x 0 )N + c 1 ( x−x 0 )N −1 + ………+ c N−1 (x - x 0) + c N .
1
Es obvio por el teorema de Taylor de que c k = P(N− K)( x 0 ¿ , pasa k = 0,1,……., N,
( N −K ) !
Pero es nuestra intención un algoritmo mas eficiente. Claramente, c N = P¿ ¿, de modo que este
coeficiente se obtiene aplicado el algoritmo de Horner al polinomio P en el punto x 0. El
algoritmo también genera el polinomio:
P ( x )−P(x 0 )
Q(x) = = d 0 x N −1 + d 1 x N −2 + …….. + d N−2 x + d N−1 =
x−x 0
=c 0 ( x−x 0 )N −1 + c 1 ( x−x 0 )N−2 + ……..+ c N−1.
Esto demuestra que le segundo coeficiente, c N−1, se puede obtener aplicando el algoritmo de
Horner al polinomio Q con el punto x 0, ya que d N−1 = c N−1 = Q ( x 0 ¿ . El proceso se repite hasta
que se encuentren todos los coeficientes c k .
