Algoritmo de Horner

En el campo matemático del análisis numérico, el Algoritmo de Horner, llamado así por William George Horner, es un algoritmo para evaluar de forma eficiente funciones polinómicas de una forma monomial.

Dado el polinomio

p(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},

donde $a_{0},\ldots ,a_{n}$ son números reales, queremos evaluar el polinomio a un valor específico de $x\,\!$ , digamos $x_{0}\,\!$ .

Para llevar a cabo el procedimiento, definimos una nueva secuencia de constantes como se muestra a continuación:


$b_{n}\,\!$	$:=\,\!$	$a_{n}\,\!$
$b_{n-1}\,\!$	$:=\,\!$	$a_{n-1}+b_{n}x_{0}\,\!$
	$\vdots$
$b_{0}\,\!$	$:=\,\!$	$a_{0}+b_{1}x_{0}\,\!$

Entonces $b_{0}\,\!$ es el valor de $p(x_{0})\,\!$ .

Para ver cómo funciona esto, nótese que el polinomio puede escribirse de la forma

p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x)\cdots ))

Después, sustituyendo iterativamente la $b_{i}$ en la expresión,


$p(x_{0})\,\!$	$=\,\!$	$a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\dots ))$
	$=\,\!$	$a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(b_{n-1})\dots ))$
	$\vdots$
	$=\,\!$	$a_{0}+x_{0}(b_{1})\,\!$
	$=\,\!$	$b_{0}\,\!$

Aplicación

El algoritmo de Horner se usa a menudo para convertir entre distintos sistemas numéricos posicionales — en cuyo caso x es la base del sistema numérico, y los coeficientes a_i son los dígitos de la representación del número dado en la base x — y puede usarse también si x es una matriz, en cuyo caso la carga computacional se reduce aún más.

Eficiencia

La evaluación usando la forma monomial del polinomio de grado-n requiere al menos n sumas y (n²+n)/2 multiplicaciones, si las potencias se calculan mediante la repetición de multiplicaciones. El algoritmo de Horner sólo requiere n sumas y n multiplicaciones. (Minimizar el número de multiplicaciones es lo más deseable porque necesitan mucha carga computacional y son inestables comparadas con la suma).

Se ha demostrado que el algoritmo de Horner es óptimo, de modo que cualquier algoritmo que se use para evaluar un polinomio requerirá como mínimo el mismo número de operaciones. El hecho de que el número de operaciones requeridas es mínimo fue demostrado por Alexander Ostrowski en 1954, y que el número de multiplicaciones es mínimo por Victor Pan en 1966. Cuando x es una matriz, el algoritmo de Horner no es óptimo.

Historia

Aunque el método toma el nombre de William George Horner, quien lo describió en 1819, el método era ya conocido por Isaac Newton, en 1669, y por el matemático chino Ch'in Chiu-Shao en el siglo XIII.

Véase también

Regla de Ruffini
Algoritmo de Clenshaw para evaluar polinomios de la forma de Chebyshov
Algoritmo de De Casteljau para evaluar polinomios de la forma de Bézier

Referencias

William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. En Philosophical Transactions of the Royal Society of London, pp. 308-335, julio de 1819.
Donald Knuth. The Art of Computer Programming, Volumen 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Páginas 486–488 en la sección 4.6.4.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein. Introduction to Algorithms, Segunda Edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7. Problema 2-3 (pág 39) y pág 823, sección 30.1: Representation of polynomials.
Jesús María Sanz Serna. Diez Lecciones de Cálculo Numérico, Segunda Edición Revisada y Ampliada. Universidad de Valladolid, Secretariado de Publicaciones e Intercambio Editorial, 2010. ISBN 978-84-8448-552-0. Capítulo 1, pág 20-22. Método de Horner.

Datos: Q944658