Evaluación de Polinomios

Evaluacin de polinomios: Algoritmo de
Horner
ltima actualizacin el Sbado, 18 de Septiembre de 2010 11:25
Estamos tan acostumbrados a ver los polinomios expresados como suma de monomios,
que cuando tenemos que implementar un algoritmo para evaluarlos tendemos a

interpretar tal cual la expresin y a codificarla tal y como lo haramos a mano con ayuda
de una calculadora.
Por ejemplo para evaluar un polinomio como P(x)=3x3-2x2+5x-1, cuando x vale 7,
vamos calculando el primer monomio: primero sacamos 73, y lo multiplicamos por 3...
luego 72, y lo multiplicamos por -2... as sucesivamente, y luego lo sumamos todo.
Esto no supone mayor problema cuando evaluamos un polinomio sencillito para un solo
valor, como x=7, pero Y si necesitamos evaluar un polinomio una y otra vez para
montones de valores distintos de x?
Vamos a plantearnos cmo hacerlo lo mejor posible con la ayuda del esquema de
Horner, como de costumbre con un enfoque bsico. Simplemente pretendemos ilustrar
cmo a veces, un poco de anlisis y reflexin permiten construir algoritmos ms
eficientes.
El algoritmo de Horner propone una forma de evaluar los polinomios descritos como
una suma de monomios.
El algoritmo se basa en el Esquema de Horner, una forma de

reescribir los polinomios atribuida a William George Horner , un matemtico ingls del
siglo XIII, ms conocido por la invencin del zootropo , un aparato que mostraba
imgenes creando la ilusin de animacin. Digo atribuido porque aunque el algoritmo
lleva su nombre, y en efecto Horner lo describi, se sabe que el algoritmo haba sido
utilizado con anterioridad .
Pero hablaremos luego del esquema de Horner. Primero veamos cmo evaluaramos un
polinomio genrico sin conocer el esquema de Horner.
Tomemos como ejemplo el que hemos comentado al principio: P(x)=3x3-2x2+5x-1
Este polinomio est compuesto de cuatro monomios. Cada monomio es un coeficiente
que multiplica a una variable x, que est elevada a un nmero. Ese nmero es el grado
del monomio. El primer monomio es de grado 3 y el ltimo es de grado 0. Para
representar a un polinomio, podemos utilizar cualquier tipo de lista o vector que nos
permita almacenar los coeficientes, por ejemplo, sta: (vamos a utilizar C#, como de
costumbre)
double[] coeficientes={-1, 5, -2, 3}
Almacenamos los coeficientes al revs de como se escribe el polinomio, porque as

tenemos el coeficiente del monomio de grado 0 en la componente 0 del vector, y el
coeficiente del monomio de grado 3 en la posicin 3 del vector.
Bien... vamos a calcular el valor del polinomio para un valor cualquiera de x. Como
vamos a tener que elevar x al cuadrado y tambin al cubo, quiz fuera conveniente
definirnos un mtodo o funcin para calcular una potencia. Despus, basta con ir
recorriendo el vector, multiplicando cada coeficiente por la potencia de x elevado al
grado del monomio correspondiente, que por la forma en la que hemos almacenado los
coeficientes, corresponde con la posicin del vector. Bien... programmoslo:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//NOTA: ESTE ALGORITMO NO ES MUY BUENO

//este metodo calcula la potencia de x elevado a y
//multiplicando y veces x por si mismo.
private double potencia(double x, int y)
{
double resultado=1;
for (int i = 1; i <= y; i++)
{
resultado *= x;
}
return resultado;
}
//Calculando cada monomio y sumndolos
public double evaluar(double x)
{
double resultado = 0;
//en cada iteracin calculamos un monomio
//y sumamos. Empezamos por el de mayor grado
//y vamos bajando (dara igual al reves)
for (int i = grado; i >= 0; i--)
{
//La operacin potencia puede ser bastante costosa, y
//la calculamos incluso para aquellos coeficientes
//que pudieran ser 0.
resultado += coeficientes[i] * potencia(x, i);
}
return resultado;
}
Si nos paramos un momento a pensar las operaciones de suma y producto que estamos
haciendo, nos daremos cuenta rpidamente de que el algoritmo no es muy bueno. Por
qu? Pues porque invocamos varias vaces al mtodo potencia. En cada invocacin, se
calcula una potencia de x. En el caso del ejemplo, x3, luego x2, luego x1 y luego x0.
Ningn programador elegante hara semejante barbaridad, ya que en cada llamada a
potencia se entra en un bucle que multiplica x por s mismo un determinado nmero de
veces. Es decir... si nuestro polinomio fuera de grado 15, una llamada a potencia(x,15)
multiplicara x por s mismo 15 veces, y luego la llamada a potencia(x,14) de la

iteracin siguiente volvera a multiplicar x por s mismo 14 veces.
Es necesario darse cuenta de que xn=x(n-1)x cuando n>1 y aprovecharlo. En lugar de
utilizar ese mtodo potencia sera ms adecuado utilizar una variable que en cada vuelta
del bucle del mtodo evaluar fueramos multiplicando por s misma. As iramos
calculando la potencia de x a la vez que recorremos el vector de coeficientes. Vamos a
probar... utilizaremos una variable que llamaremos pot para calcular las potencias de x.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//Este algoritmo es mucho mejor

public double evaluar1(double x)
{
double pot = 1;
//en cada iteracin calculamos un monomio
//y sumamos. Empezamos por el de grado 1 y vamos
//subiendo
for (int i = 0; i <= grado; i++)
{
//Vamos calculando la potencia de x a memedida
//que vamos calculando los monomios.
resultado += coeficientes[i] * pot;
pot *= x;
}
return resultado;
}
Mucho mejor... con ste algoritmo de arriba, en cada iteracin del bucle for se realizan
slo dos multiplicaciones y una suma. Es decir, para nuestro polinomio de ejemplo, se
realizan cuatro vueltas del bucle, as que 8 multiplicaciones y cuatro sumas. En el
primer algoritmo, se realizaban 13 multiplicaciones y cuatro sumas. Si el polinomio
fuera mayor, por ejemplo de grado 15... con ste segundo algoritmo se realizan 30
multiplicaciones y 15 sumas, pero con el primero se realizan 134 multiplicaciones y
15 sumas !!! Como ves, hemos disminuido muchsimo el nmero de operaciones.
Bueno, pero todava lo podemos mejorar. Aqu es donde entra el algoritmo de Horner.
Vamos a retomar nuestro polinomio de ejemplo P(x)=3x3-2x2+5x-1, y vamos a separar
el coeficiente que no est multiplicado por x, el -1, y lo vamos a dejar a un lado.
Nos queda 3x3-2x2+5x Rpidamente nos damos cuenta de que sobre esa expresin
podemos sacar factor comn, y dejarla como (3x2-2x+5) x
Vale. Ahora cojamos el interior del parntesis (nos dejamos la x que multiplica en el
mismo lado que nos dejamos el -1), y volvamos a separar el coeficiente que no
multiplica a x (y nuevamente lo dejamos a un lado)... 3x2-2x Si sacamos factor comn,
nos queda (3x-2)x
Ahora reescribamos todo junto, el resultado al que hemos llegado y todo lo que nos
hemos dejado a un lado: ((3x-2)x +5)x-1. Simplemente, tenemos el mismo polinomio de
antes, pero escrito de otra forma. De la expresion como suma de monomios hemos
sacado la x como factor comn unas cuantas veces. No me crees?... Haz las
operaciones...
((3x-2)x -5)x-1 = ((3x2-2x) -5)x-1 = (3x2-2x -5)x-1 = (3x3-2x2 +5x)-1 = 3x3-2x2 +5x-1
--> Nuestro polinomio como nuevo.
Bueno... pues a esta forma de escribir los polinomios "((3x-2)x -5)x-1", en la cual, todas
las veces que aparece x no est elevado a ninguna potencia, se le denomina esquema de
horner. Realmente, x se va multiplicando por s mismo, pero sto se logra gracias a la
astuta parentizacin.
Pues bien, cuando implementamos un algoritmo que se basa en evaluar un polinomio
escrito segn el esquema de Horner, resulta que slo necesitamos una suma y una
multiplicacin por cada iteracin del bucle... y adems, al no realizarse operaciones de
potencia, los errores de redondeo cometidos son mucho menores.
RecapitulandoPara evaluar un polinomio segn el algoritmo de Horner, empezamos por
el coeficiente del monomio de mayor grado, y lo multiplicamos por x. Luego sumamos
el siguiente coeficiente y volvemos a multiplicar por x.... Luego sumamos el siguiente y
multiplicamos por x...... y as sucesivamente, hasta que sumamos el ltimo coeficiente y
paramos.
Vamos a poner todo juntito en una clase a la que llamaremos Polinomio. Le vamos a
poner un constructor y una funcin evaluar que utilice el esquema de Horner.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//esta clase es slo un ejemplo, para ilustrar

//el algoritmo de Horner. No tiene control de
//errores, excepciones ni ninguna otra funcionalidad
class Polinomio
{
//los coeficientes, de grado 0 a n
double[] coeficientes;
//una propiedad para obtener el grado
//del polinomio
int grado
{
get {return coeficientes.Length-1;}
}
/* Este constructor admite una serie variable de
* valores double, que representan a los coeficientes.
* El primero ser el coeficiente del monomio de mayor
* grado y el ltimo el coeficiente del monomio de grado 0.
*/
23 public Polinomio(params double[] coeficientes)

24 {
25
this.coeficientes = coeficientes;
26
//vamos a darle la vuelta, slo por comodidad
27
//as, nos quedamos con el coeficiente del monomio de
28
//grado 0 en la posicin 0 del vector, y el coeficiente
29
//del monomio de grado n en la posicin n.
30
Array.Reverse(this.coeficientes);
31 }
32
33 //Evaluar mediante el algoritmo
34 //de Horner
35 public double evaluar(double x)
36 {
37
38
//llegamos hasta el coeficiente
39
//del monomio de grado 1
40
for (int i = grado; i >= 1; i--)
41
{
42
//sumar un coeficiente
43
resultado += coeficientes[i];
44
//multiplicar el resultado por valor
45
resultado *= x;
46
}
47
//finalmente, sumamos el ltimo coeficiente
48
return resultado+coeficientes[0];
49 }
50
51 } //class
Para utilizarlo, basta con crear un nuevo polinomio, pasandole la lista de coeficientes,
tal cual se escriben en el polinomio, e invocar al mtodo evaluar. Por ejemplo:
1
2
3
4
//crear el polinomio
Polinomio p = new Polinomio(3, -2, 5, -1);
//evaluar para x=7
Console.WriteLine(p.evaluar(7));

Evaluación de Polinomios

Cargado por

Copyright:

Formatos disponibles

Evaluación de Polinomios

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Evaluación de Polinomios

Cargado por

Copyright:

Formatos disponibles

Evaluacin de polinomios: Algoritmo de

que cuando tenemos que implementar un algoritmo para evaluarlos tendemos a

El algoritmo se basa en el Esquema de Horner, una forma de

Almacenamos los coeficientes al revs de como se escribe el polinomio, porque as

//NOTA: ESTE ALGORITMO NO ES MUY BUENO

multiplicara x por s mismo 15 veces, y luego la llamada a potencia(x,14) de la

//Este algoritmo es mucho mejor

//esta clase es slo un ejemplo, para ilustrar

23 public Polinomio(params double[] coeficientes)

También podría gustarte