Algoritmo de Horner

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 polinomios 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 como 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 bi en la expresión (después de: "a1+" va x0 y no x),

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\,\!

Contenido

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 ai 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 (n2+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, e incluso antes por el matemático chino Ch'in Chiu-Shao en el siglo XIII.

Véase también

  • 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.

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Horner — puede estar haciendo referencia a: Algoritmo de Horner, regla matemática. William George Horner, matemático inglés. Síndrome de Claude Bernard Horner. James Horner, compositor de música de cine. Chris Horner, ciclista estadounidense …   Wikipedia Español

  • Análisis numérico — El análisis numérico o cálculo numérico es la rama de las matemáticas que se encarga de diseñar algoritmos para, a través de números y reglas matemáticas simples, simular procesos matemáticos más complejos aplicados a procesos del mundo real. El… …   Wikipedia Español

  • Anexo:Matemáticos importantes — En esta lista de matemáticos importantes se presenta una selección de matemáticos desde la antigüedad hasta el presente. La selección se orienta por los aportes científicos, utilizando como criterio para definir el grado de notoriedad la atención …   Wikipedia Español

  • Seki Kōwa — Kōwa Seki (Takakazu Seki) Matemático Japonés del Wasan. Nacimiento Marzo(?), 1642 Edo o Fujioka, Japón Fallecimi …   Wikipedia Español

  • Li Ye — Li Ye, también llamado Li Chi o Li Zhi[1] (1192 en Tahsing, hoy Pekín; 1279 en la provincia de Hopeh) fue un matemático chino del período de la dinastía Song. Contenido 1 Biografía 1.1 …   Wikipedia Español

  • División (matemática) — En matemática, la división es una operación aritmética de descomposición que consiste en averiguar cuántas veces un número (divisor) está contenido en otro número (dividendo). La división es la operación inversa de la multiplicación. Según su… …   Wikipedia Español

  • Matemática en el Islam medieval — Saltar a navegación, búsqueda Contenido 1 Valoración de la ciencia islámica 2 Desarrollos y contexto histórico 3 Otros ejemplos de desarrollo …   Wikipedia Español

  • 0,9 periódico — En matemáticas, 0,999... es el número decimal periódico que se demuestra denota[1] al número 1. En otras palabras, los símbolos 0,999... y 1 son dos representaciones distintas del mismo número real. Las demostraciones matemáticas de esta igualdad …   Wikipedia Español

  • Matemática en el islam medieval — Tratado de arte numeral de Joannis de Sacro Bosco. La matemática árabe se enriqueció en forma creciente a medida que los musulmanes conquistaron territorios. Con rapidez inusitada, el islamismo se expandió en todo el territorio que se extiende… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”