Método de Horner – Algoritmos antiguos

Publicado por Andrea Navarro en

El método de Horner, también llamado la regla de Horner es un algoritmo que permite calcular el resultado de un polinomio para un determinado valor de x.

Método de Horner

Una página de «Los nueve capítulos sobre arte matemático»

El algoritmo tiene ese nombre por el matemático británico William George Horner aunque él no fue el primer en encontrar este método siendo conocido por un gran número de matemáticos de la antigüedad. Su primera aparición es en el libro matemático «Los nueve capítulos de el arte matemático», un libro realizado por varias generaciones de estudiosos en China entre los siglos I y II AC.

Otros conocedores de este algoritmo fueron el matemático chino del siglo XI Jia Xian, el matemático persa Sharaf al-Din al-Tusi en el siglo XII  y el matemático chino Zhu Shijie en el siglo XIV .

La eficiencia del método de Horner

Aunque la solución de un polinomio para un valor específico de x es una tarea sencilla el algoritmo reduce la cantidad de operaciones necesarias para llegar al resultado lo que la convierte en una técnica más eficiente y más deseable a la hora de programarla.

Llamando a el grado del polinomio g una resolución por sustituciones requiere hasta (g2+g)/2 multiplicaciones y g sumas mientras que el algoritmo de Horner solo requerirá g sumas y g multiplicaciones.

Veremos la diferencia para el siguiente polinomio de grado 4 y valor de x:

Método de Horner

Resolución por sustitución

Esta resolución es la manera clásica donde se sustituye la x por el valor deseado y luego se realizan las operaciones necesarias.

Método de Horner

Método de Horner

Colocamos los coeficientes del polinomio en una tabla junto con el valor de x que quiere evaluarse

Bajamos el primer coeficiente y lo multiplicamos por el valor de x colocando el resultado debajo del siguiente coeficiente en la tabla

Método de Horner

Sumamos los dos valores obteniendo un nuevo resultado parcial

Método de Horner

Repetimos la operación para cada coeficiente

Método de Horner

Método de Horner

Al llegar al último coeficiente obtenemos el resultado final

Método de Horner

resultadohorner

Podemos ver en este ejemplo como se ha reducido la cantidad de multiplicaciones necesarias ahorrando al sistema 6 operaciones extras.

Método de Horner – Algoritmo

Pseudocódigo para PSeint

Proceso Horner
	//Valor e x
	valorX=8;
	//Coeficientes del polinomio
	dimensionArreglo=5;
	Dimension coeficientes[dimensionArreglo];
	coeficientes[1]=4;
	coeficientes[2]=7;
	coeficientes[3]=3;
	coeficientes[4]=6;
	coeficientes[5]=2;
	
	resultado=0;
	//Recorrer los coeficientes
	Para i=1 Hasta dimensionArreglo Con Paso 1 Hacer
		//Multiplicar al valor parcial el valor de x más el coeficiente
		resultado= resultado * valorX + coeficientes[i];
	FinPara
	Escribir "Resultado: " resultado;
	
FinProceso

Código para C

#include<stdio.h>

int main(int argc, char** argv){

	//Valor de x
	float valorX=8;
	//Coeficientes del polinomio
	float coeficientes[]={4,7,3,6,2};
	float resultado=0;
	int i;

	//Recorrer los coeficientes
	for(i=0;i<(sizeof(coeficientes)/sizeof(float));i++){
	  //Multiplicar al valor parcial el valor de x más el coeficiente
	  resultado= resultado * valorX + coeficientes[i];
	}

	printf("Resultado %f\n",resultado);
	return 0;
}

Código para PHP

<?php

//Valor de x
$valorX=8;
//Coeficientes del polinomio
$coeficientes=array(4,7,3,6,2);
$resultado=0;
//Recorrer los coeficientes
for($i=0;$i<count($coeficientes);$i++)
{
	//Multiplicar al valor parcial el valor de x más el coeficiente
	$resultado= $resultado * $valorX + $coeficientes[$i];
}

echo "Resultado: ".$resultado;

Espero que les sirva!


Andrea Navarro

- Ingeniera en Informática - Docente universitaria - Investigadora