Método de Horner

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Algoritm for polynomial evaluation

En matemáticas e informática, el método de Horner (o esquema de Horner) es un algoritmo para la evaluación de polinomios. Aunque lleva el nombre de William George Horner, este método es mucho más antiguo, ya que el propio Horner lo ha atribuido a Joseph-Louis Lagrange, y se puede rastrear muchos cientos de años atrás hasta los matemáticos chinos y persas. Después de la introducción de las computadoras, este algoritmo se volvió fundamental para calcular eficientemente con polinomios.

El algoritmo se basa en la regla de Horner:

{displaystyle {begin{aligned}a_{0}&+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+cdots +a_{n}x^{n}\&=a_{0}+x{bigg (}a_{1}+x{Big (}a_{2}+x{big (}a_{3}+cdots +x(a_{n-1}+x,a_{n})cdots {big)}{Big)}{bigg)}.end{aligned}}}

Esto permite la evaluación de un polinomio de grado $n$ con sólo $n$ multiplicaciones y $n$ Adiciones. Esto es óptimo, ya que hay polinomios de grado $n$ que no se puede evaluar con menos operaciones aritméticas.

Alternativamente, el método de Horner también se refiere a un método para aproximar las raíces de polinomios, descrito por Horner en 1819. Es una variante del método de Newton-Raphson más eficiente para Cálculo manual mediante la aplicación de la regla de Horner. Fue ampliamente utilizado hasta que las computadoras se generalizaron alrededor de 1970.

Evaluación de polinomios y división larga

Dado el polinomio

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

Donde $a_{0},ldotsa_{n}$ son coeficientes constantes, el problema es evaluar el polinomio a un valor específico $x_{0}$ de $x.$

Para esto, se define recursivamente una nueva secuencia de constantes de la siguiente manera:

{displaystyle {begin{aligned}b_{n}&:=a_{n}\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\(1)quad quad quad &~~~vdots \b_{1}&:=a_{1}+b_{2}x_{0}\b_{0}&:=a_{0}+b_{1}x_{0}.end{aligned}}}

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

Para ver por qué esto funciona, el polinomio se puede escribir en la forma

{displaystyle p(x)=a_{0}+x{bigg (}a_{1}+x{Big (}a_{2}+x{big (}a_{3}+cdots +x(a_{n-1}+x,a_{n})cdots {big)}{Big)}{bigg)}.}

Así, sustituyendo iterativamente al $b_{i}$ en la expresión,

{displaystyle {begin{aligned}p(x_{0})&=a_{0}+x_{0}{Big (}a_{1}+x_{0}{big (}a_{2}+cdots +x_{0}(a_{n-1}+b_{n}x_{0})cdots {big)}{Big)}\&=a_{0}+x_{0}{Big (}a_{1}+x_{0}{big (}a_{2}+cdots +x_{0}b_{n-1}{big)}{Big)}\&~~vdots \&=a_{0}+x_{0}b_{1}\&=b_{0}.end{aligned}}}

Ahora, se puede probar que;

{displaystyle (2)quad quad quad p(x)=(b_{1}+b_{2}x+b_{3}x^{2}+b_{4}x^{3}+cdots +b_{n-1}x^{n-2}+b_{n}x^{n-1})(x-x_{0})+b_{0}}

Esta expresión constituye la aplicación práctica de Horner, ya que ofrece una forma muy rápida de determinar el resultado de;

{displaystyle p(x)/(x-x_{0})}

siendo b₀ (que es igual a p(x₀)) el resto de la división, como se demuestra en los siguientes ejemplos. si x₀ es una raíz de p(x), entonces b₀ = 0 (lo que significa que el resto es 0), lo que significa que puedes factorizar p(x) con (x-x₀).
Para encontrar los valores b consecutivos, comienza determinando b_n, que es simplemente igual a a_n. Luego, avanza hasta los otros b & 39; s, usando la fórmula;

{displaystyle b_{n-1}=a_{n-1}+b_{n}x_{0}}

hasta llegar a b₀.

Ejemplos

Evaluate ${displaystyle f(x)=2x^{3}-6x^{2}+2x-1}$ para ${displaystyle x=3.}$

Usamos la división sintética de la siguiente manera:

 x₀. x³ x² x¹ x⁰3 −6 2 −1
6 0 6
- No.
2 0 2 5

Las entradas en la tercera fila son la suma de las de las dos primeras. Cada entrada en la segunda fila es el producto de la x-valor (3 en este ejemplo) con la entrada de tercera fila inmediatamente a la izquierda. Las entradas en la primera fila son los coeficientes del polinomio a evaluar. Entonces el resto de $f(x)$ on division by $x-3$ 5.

Pero por el teorema del resto polinomio, sabemos que el resto es $f(3)$ . Así $f(3)=5$

En este ejemplo, si $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ podemos ver que $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$ , las entradas en la tercera fila. Así que la división sintética se basa en el método de Horner.

Como consecuencia del teorema de los restos polinomios, las entradas en la tercera fila son los coeficientes del polinomio de segundo grado, el cociente de $f(x)$ on division by $x-3$ . El resto es 5. Esto hace que el método de Horner sea útil para la división polinomio larga.

Divide ${displaystyle x^{3}-6x^{2}+11x-6}$ por ${displaystyle x-2}$ :

 2 −6 11 −6
2 - 8 6
- No.
1 −4 3 0

El cociente es ${displaystyle x^{2}-4x+3}$ .

Vamos ${displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5}$ y ${displaystyle f_{2}(x)=2x-1}$ . Divide $f_1(x)$ por $f_{2},(x)$ usando el método de Horner.

 0,5 0 3 5
2 -2 -1 1
- No.
2 -2 -1 1 -4

La tercera fila es la suma de las dos primeras filas, dividida por 2. Cada entrada en la segunda fila es el producto de 1 con la entrada de la tercera fila a la izquierda. La respuesta es

{frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{frac {4}{2x-1}}.

Eficiencia

La evaluación usando la forma monomio de un polinomio de grado n requiere como máximo n adiciones y (n² + n)/2 multiplicaciones, si las potencias se calculan por multiplicación repetida y cada monomio se evalúa individualmente. (Esto se puede reducir a n sumas y 2n − 1 multiplicaciones evaluando las potencias de x iterativamente). Si los datos numéricos se representan en términos de dígitos (o bits), entonces el algoritmo ingenuo también implica almacenar aproximadamente 2n veces el número de bits de x (el polinomio evaluado tiene una magnitud aproximada x ⁿ, y también se debe almacenar xⁿ). Por el contrario, el método de Horner requiere solo n sumas y n multiplicaciones, y sus requisitos de almacenamiento son solo n veces el número de bits de x. Alternativamente, el método de Horner se puede calcular con n sumas y multiplicaciones fusionadas. El método de Horner también se puede extender para evaluar las primeras derivadas k del polinomio con sumas y multiplicaciones kn.

El método de Horner es óptimo, en el sentido de que cualquier algoritmo para evaluar un polinomio arbitrario debe usar al menos tantas operaciones. Alexander Ostrowski demostró en 1954 que la cantidad de adiciones requeridas es mínima. Victor Pan demostró en 1966 que el número de multiplicaciones es mínimo. Sin embargo, cuando x es una matriz, el método de Horner no es óptimo.

Esto supone que el polinomio se evalúa en forma de monomio y no se permite el preacondicionamiento de la representación, lo que tiene sentido si el polinomio se evalúa solo una vez. Sin embargo, si se permite el preacondicionamiento y el polinomio se va a evaluar muchas veces, entonces son posibles algoritmos más rápidos. Implican una transformación de la representación del polinomio. En general, un polinomio de grado n se puede evaluar usando solo ⌊n/2⌋+2 multiplicaciones y n sumas.

Evaluación paralela

Una desventaja de la regla de Horner es que todas las operaciones dependen secuencialmente, por lo que no es posible aprovechar el paralelismo de nivel de instrucción en las computadoras modernas. En la mayoría de las aplicaciones donde la eficiencia de la evaluación de polinomios importa, muchos polinomios de bajo orden se evalúan simultáneamente (para cada píxel o polígono en gráficos por computadora, o para cada cuadrícula en una simulación numérica), por lo que no es necesario encontrar el paralelismo dentro de un evaluación de un solo polinomio.

Sin embargo, si uno está evaluando un solo polinomio de muy alto orden, puede ser útil dividirlo de la siguiente manera:

{displaystyle {begin{aligned}p(x)&=sum _{i=0}^{n}a_{i}x^{i}\&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+cdots +a_{n}x^{n}\&=left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+cdots right)+left(a_{1}x+a_{3}x^{3}+a_{5}x^{5}+cdots right)\&=left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+cdots right)+xleft(a_{1}+a_{3}x^{2}+a_{5}x^{4}+cdots right)\&=sum _{i=0}^{lfloor n/2rfloor }a_{2i}x^{2i}+xsum _{i=0}^{lfloor n/2rfloor }a_{2i+1}x^{2i}\&=p_{0}(x^{2})+xp_{1}(x^{2}).\end{aligned}}}

De manera más general, la suma se puede dividir en k partes:

{displaystyle {begin{aligned}p(x)&=sum _{i=0}^{n}a_{i}x^{i}\&=sum _{j=0}^{k-1}x^{j}sum _{i=0}^{lfloor n/krfloor }a_{ki+j}x^{ki}\&=sum _{j=0}^{k-1}x^{j}p_{j}(x^{k})\end{aligned}}}

donde las sumas internas pueden evaluarse usando instancias paralelas separadas del método de Horner. Esto requiere un poco más de operaciones que el método básico de Horner, pero permite la ejecución SIMD de k vías de la mayoría de ellas. Los compiladores modernos generalmente evalúan los polinomios de esta manera cuando es ventajoso, aunque para los cálculos de punto flotante esto requiere habilitar las matemáticas reasociativas (no seguras).

Aplicación a la multiplicación y división de coma flotante

El método Horner es un método rápido y eficiente en código para la multiplicación y división de números binarios en un microcontrolador sin multiplicador de hardware. Uno de los números binarios que se multiplican es representado como un polinomio trivial, donde (utilizando la notación anterior) ${displaystyle a_{i}=1}$ , y $x = 2$ . Entonces, x (o x a algún poder) se factora repetidamente. En este sistema de numeral binario (base 2), $x = 2$ , por lo que los poderes de 2 se factoran repetidamente.

Ejemplo

Por ejemplo, para encontrar el producto de dos números (0.15625) y m:

{displaystyle {begin{aligned}(0.15625)m&=(0.00101_{b})m=(2^{-3}+2^{-5})m=(2^{-3})m+(2^{-5})m\&=2^{-3}(m+(2^{-2})m)=2^{-3}(m+2^{-2}(m)).end{aligned}}}

Método

Para encontrar el producto de dos números binarios d y m:

1. Se inicializa un registro con el resultado intermedio d.

2. Comenzar con la menor cantidad (derecha) no cero en m.

2b. Contar (a la izquierda) el número de posiciones de bits al siguiente bit más significativo no cero. Si no hay bits más significativos, entonces tome el valor de la posición actual del bit.

2c. Usando ese valor, realizar una operación de desplazamiento izquierdo por ese número de bits en el registro conteniendo el resultado intermedio

3. Si todos los bits no cero fueron contados, entonces el registro de resultado intermedio ahora tiene el resultado final. De lo contrario, añadir d al resultado intermedio, y continuar en el paso 2 con el siguiente bit más significativo en m.

Derivación

En general, para un número binario con valores bits ( $d_{3}d_{2}d_{1}d_{0}$ ) el producto es

{displaystyle (d_{3}2^{3}+d_{2}2^{2}+d_{1}2^{1}+d_{0}2^{0})m=d_{3}2^{3}m+d_{2}2^{2}m+d_{1}2^{1}m+d_{0}2^{0}m.}

En esta etapa del algoritmo, se requiere que los términos con coeficientes de valor cero se eliminen, de modo que solo se cuenten los coeficientes binarios iguales a uno, por lo que el problema de la multiplicación o división por cero no es un problema, a pesar de esto implicación en la ecuación factorizada:

{displaystyle =d_{0}left(m+2{frac {d_{1}}{d_{0}}}left(m+2{frac {d_{2}}{d_{1}}}left(m+2{frac {d_{3}}{d_{2}}}(m)right)right)right).}

Todos los denominadores son iguales a uno (o el término está ausente), por lo que esto se reduce a

=d_{0}(m+2{d_{1}}(m+2{d_{2}}(m+2{d_{3}}(m)))),

o equivalente (de acuerdo con el "método" descrito anteriormente)

=d_{3}(m+2^{-1}{d_{2}}(m+2^{-1}{d_{1}}(m+{d_{0}}(m)))).

En matemática binaria (base 2), la multiplicación por una potencia de 2 es simplemente una operación de cambio de registro. Por lo tanto, multiplicar por 2 se calcula en base 2 mediante un desplazamiento aritmético. El factor (2⁻¹) es un cambio aritmético a la derecha, un (0) no da como resultado ninguna operación (ya que 2⁰ = 1 es el elemento de identidad multiplicativo), y un (2¹) da como resultado un cambio aritmético a la izquierda. El producto de multiplicación ahora se puede calcular rápidamente usando solo operaciones de cambio aritmético, suma y resta.

El método es particularmente rápido en los procesadores que admiten un desplazamiento y suma acumulada de una sola instrucción. En comparación con una biblioteca de punto flotante de C, el método de Horner sacrifica algo de precisión; sin embargo, nominalmente es 13 veces más rápido (16 veces más rápido cuando se usa el formato de "dígito con signo canónico" (CSD)) y utiliza sólo el 20% del espacio de código.

Otras aplicaciones

El método de Horner se puede usar para convertir entre diferentes sistemas numéricos posicionales, en cuyo caso x es la base del sistema numérico y ai son los dígitos de la representación base-x de un número dado, y también se pueden usar si x es una matriz, en cuyo caso la ganancia en eficiencia computacional es aún mayor. Sin embargo, para tales casos se conocen métodos más rápidos.

Búsqueda de raíz de polinomio

Usando el algoritmo de división larga en combinación con el método de Newton, es posible aproximar las raíces reales de un polinomio. El algoritmo funciona como sigue. Dado un polinomio $p_{n}(x)$ grado $n$ con ceros $<math alttext="{displaystyle z_{n}<z_{n-1}<cdots zn.zn− − 1.⋯ ⋯ .z1,{displaystyle z_{n} detectz_{n-1}<img alt="{displaystyle z_{n}<z_{n-1}<cdots$ hacer algunas adivinanzas iniciales $x_{0}$ tales que $<math alttext="{displaystyle z_{1}z1.x0{displaystyle z_{1}<img alt="{displaystyle z_{1}$ . Ahora se dan los siguientes dos pasos:

Usando el método de Newton, encontrar el cero más grande $z_{1}$ de $p_{n}(x)$ usando la conjetura $x_{0}$ .
Usando el método de Horner, dividir $(x-z_{1})$ para obtener $p_{n-1}$ . Volver al paso 1 pero utilizar el polinomio $p_{n-1}$ y la suposición inicial $z_{1}$ .

Estos dos pasos se repiten hasta que se encuentran todos los ceros reales para el polinomio. Si los ceros aproximados no son lo suficientemente precisos, los valores obtenidos se pueden usar como conjeturas iniciales para el método de Newton pero usando el polinomio completo en lugar de los polinomios reducidos.

Ejemplo

Polínomial root finding using Horner's method

Considere el polinomio

{displaystyle p_{6}(x)=(x+8)(x+5)(x+3)(x-2)(x-3)(x-7)}

que se puede expandir a

p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040.

Desde arriba sabemos que la raíz más grande de este polinomio es 7 por lo que somos capaces de hacer una conjetura inicial de 8. Utilizando el método de Newton el primer cero de 7 se encuentra como se muestra en negro en la figura a la derecha. Siguiente $p(x)$ se divide por $(x-7)$ para obtener

{displaystyle p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720}

que se dibuja en rojo en la figura a la derecha. El método de Newton se utiliza para encontrar el mayor cero de este polinomio con una suposición inicial de 7. El mayor cero de este polinomio que corresponde al segundo mayor cero del polinomio original se encuentra en 3 y se círculo en rojo. El grado 5 polinomio está dividido por $(x-3)$ para obtener

{displaystyle p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240}

que se muestra en amarillo. El cero para este polinomio se encuentra en 2 de nuevo usando el método de Newton y está encerrado en un círculo amarillo. Ahora se utiliza el método de Horner para obtener

{displaystyle p_{3}(x)=x^{3}+16x^{2}+79x+120}

que se muestra en verde y se encontró que tiene un cero en −3. Este polinomio se reduce aún más a

{displaystyle p_{2}(x)=x^{2}+13x+40}

que se muestra en azul y produce un cero de −5. La raíz final del polinomio original se puede encontrar utilizando el cero final como una suposición inicial para el método de Newton, o reduciendo $p_{2}(x)$ y resolver la ecuación lineal. Como se puede ver, se encontraron las raíces esperadas de −8, −5, −3, 2, 3 y 7.

Diferencia dividida de un polinomio

El método de Horner puede ser modificado para calcular la diferencia dividida ${displaystyle (p(y)-p(x))/(y-x).}$ Dado el polinomio (como antes)

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

proceda de la siguiente manera

{displaystyle {begin{aligned}b_{n}&=a_{n},&quad d_{n}&=b_{n},\b_{n-1}&=a_{n-1}+b_{n}x,&quad d_{n-1}&=b_{n-1}+d_{n}y,\&{} vdots &quad &{} vdots \b_{1}&=a_{1}+b_{2}x,&quad d_{1}&=b_{1}+d_{2}y,\b_{0}&=a_{0}+b_{1}x.end{aligned}}}

Al finalizar, tenemos

{displaystyle {begin{aligned}p(x)&=b_{0},\{frac {p(y)-p(x)}{y-x}}&=d_{1},\p(y)&=b_{0}+(y-x)d_{1}.end{aligned}}}

Esta computación de la diferencia dividida está sujeta a menos error redondeado que evaluación $p(x)$ y $p(y)$ por separado, en particular cuando ${displaystyle xapprox y}$ . Sustitución $y=x$ en este método da ${displaystyle d_{1}=p'(x)}$ , el derivado de $p(x)$ .

Historia

algoritmo de Qin Jiushao para resolver la ecuación polinomio cuadrática

-x^{4}+763200x^{2}-40642560000=0

resultado: x=840

El artículo de Horner, titulado "Un nuevo método para resolver ecuaciones numéricas de todos los órdenes, por aproximación continua", se leyó ante la Royal Society de Londres, en su reunión del 1 de julio de 1819., con una secuela en 1823. El artículo de Horner en la Parte II de Philosophical Transactions of the Royal Society of London de 1819 fue calurosamente y ampliamente recibido por un crítico en la edición de The Revisión mensual: o Revista literaria de abril de 1820; en comparación, un documento técnico de Charles Babbage se descarta brevemente en esta reseña. La secuencia de reseñas en The Monthly Review de septiembre de 1821 concluye que Holdred fue la primera persona en descubrir una solución práctica directa y general de ecuaciones numéricas. Fuller mostró que el método del artículo de Horner de 1819 difiere de lo que luego se conoció como el "método de Horner". y que en consecuencia la prioridad de este método debe ir a Holdred (1820).

A diferencia de sus contemporáneos ingleses, Horner se basó en la literatura continental, especialmente en el trabajo de Arbogast. También se sabe que Horner hizo una lectura detallada del libro de John Bonneycastle sobre álgebra, aunque descuidó el trabajo de Paolo Ruffini.

Aunque a Horner se le atribuye haber hecho el método accesible y práctico, se conocía mucho antes que Horner. En orden cronológico inverso, el método de Horner ya era conocido por:

Paolo Ruffini en 1809 (ver la regla de Ruffini)
Isaac Newton en 1669
el matemático chino Zhu Shijie en el siglo XIV
el matemático chino Qin Jiushao en su Tesoro matemático en nueve secciones en el siglo XIII
el matemático persa Sharaf al-Dîn al-Thūsī en el siglo XII (el primero en utilizar ese método en un caso general de ecuación cúbica)
el matemático chino Jia Xian en el siglo XI (Dinastía del Cantón)
Los nueve capítulos sobre el arte matemático, una obra china de la dinastía Han (202 BC – 220 dC) editada por Liu Hui (siglo III).

Qin Jiushao, en su Shu Shu Jiu Zhang (Tratado matemático en nueve secciones; 1247), presenta una cartera de métodos de tipo Horner para resolver ecuaciones polinómicas, que se basó en trabajos anteriores del matemático Jia Xian de la dinastía Song del siglo XI; por ejemplo, un método se adapta específicamente a las bi-quínticas, de las cuales Qin da un ejemplo, de acuerdo con la costumbre china de entonces de los estudios de casos. Yoshio Mikami en Desarrollo de las Matemáticas en China y Japón (Leipzig 1913) escribió:

"... que puede negar el hecho de que el proceso ilustre de Horner se utilice en China al menos casi seis largos siglos antes que en Europa... Por supuesto, no tenemos la intención de atribuir la invención de Horner a un origen chino, pero el tiempo suficiente hace que no sea totalmente imposible que los europeos pudieran haber sabido del método chino de manera directa o indirecta".

Ulrich Libbrecht concluyó: Es obvio que este procedimiento es un invento chino... el método no se conocía en la India. Dijo que Fibonacci probablemente se enteró por los árabes, quienes quizás lo tomaron prestado de los chinos. Liu Hui ya analiza la extracción de raíces cuadradas y cúbicas de manera similar en relación con los Problemas IV.16 y 22 en Jiu Zhang Suan Shu, mientras que Wang Xiaotong en el siglo VII supone que sus lectores pueden resolver cúbicos por un método de aproximación descrito en su libro Jigu Suanjing.

Contenido relacionado

Más resultados...