Método de Horner

En matemáticas e informática , el método de Horner (o esquema de Horner ) es un algoritmo para la evaluación de polinomios . Recibe su nombre de William George Horner , aunque es mucho más antiguo, atribuido por Horner a Joseph-Louis Lagrange , y fue descubierto cientos de años antes por matemáticos chinos y persas. ^{[ 1 ]} Tras la introducción de las computadoras, este algoritmo se convirtió en fundamental para realizar cálculos eficientes con polinomios.

El algoritmo se basa en la regla de Horner, en la que un polinomio se escribe en forma anidada : ${\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 solo $n$ multiplicaciones y $n$ sumas. Esto es óptimo, ya que es imposible evaluar polinomios de grado $n$ con menos operaciones aritméticas cuando tanto x como los coeficientes a ₀ , ..., a _n se proporcionan como entrada. ^{[ 2 ]}

El método de Horner yEl método de Horner-Ruffini 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, optimizado para el cálculo manual mediante la aplicación de la regla de Horner. Fue ampliamente utilizado hasta la popularización de las computadoras 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},$ dónde $a_{0},\ldots ,a_{n}$ son coeficientes constantes, el problema es evaluar el polinomio en un valor específico. $x_{0}$ de $x.$

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

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

Para ver por qué esto funciona, el polinomio se puede escribir de la forma $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í, mediante la sustitución iterativa del $b_{i}$ en la expresión, ${\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}}$

De manera similar, se puede demostrar que:

Sugerir un procedimiento conveniente para determinar el resultado de la división polinómica. $p(x)/(x-x_{0})$ con $b_{0}$ (que es igual a $p(x_{0})$ ) siendo el resto de la división. Si $x_{0}$ es una raíz de $p(x)$ , entonces $b_{0}=0$ (lo que significa que el resto es $0$ ) y $x-x_{0}$ un factor de $p(x)$ .

Ejemplos

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

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

{\begin{array}{cc}{\begin{array}{r}\\3\\\\\\\end{array}}&{\begin{array}{|rrrr}\ 2&-6&2&-1\\&6&0&6\\\hline 2&0&2&5\end{array}}\end{array}}

Las entradas de la tercera fila son la suma de las de las dos primeras. Cada entrada de la segunda fila es el producto del valor $x$ (3 en este ejemplo) con la entrada de la tercera fila inmediatamente a la izquierda. Las entradas de la primera fila son los coeficientes del polinomio que se va a evaluar. Luego, el resto de $f(x)$ sobre la división por $x-3$ es5 .

Pero por el teorema del resto polinomial , sabemos que el resto es $f(3)$ . De este modo, $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 de la tercera fila. Por lo tanto, la división sintética (que en realidad fue inventada y publicada por Ruffini 10 años antes de la publicación de Horner) es más fácil de usar; se puede demostrar que es equivalente al método de Horner.

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

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

{\begin{array}{cc}{\begin{array}{r}\\2\\\\\\\end{array}}&{\begin{array}{|rrrr}\ 1&-6&11&-6\\&2&-8&6\\\hline 1&-4&3&0\end{array}}\end{array}}

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

Dejar $f_{1}(x)=4x^{4}-6x^{3}+3x-5$ y $f_{2}(x)=2x-1$ . Dividir $f_{1}(x)$ por $f_{2}\,(x)$ utilizando el método de Horner.

${\begin{array}{cc}{\begin{array}{r}\\0.5\\\\\\\end{array}}&{\begin{array}{|rrrrr}\ 4&-6&0&3&-5\\&2&-2&-1&1\\\hline 2&-2&-1&1&-4\end{array}}\end{array}}$

La tercera fila es la suma de las dos primeras filas, dividida por2. Cada entrada en la segunda fila es el producto de1 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

Evaluación utilizando la forma monomial de un grado $n$ El polinomio requiere como máximo $n$ adiciones y $(n^{2}+n)/2$ multiplicaciones, si las potencias se calculan mediante multiplicaciones repetidas y cada monomio se evalúa individualmente. El costo se puede reducir a $n$ adiciones y $2n-1$ multiplicaciones evaluando las potencias de $x$ por iteración.

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^{n}$ y también hay que almacenar $x^{n}$ por sí mismo. Por el contrario, el método de Horner solo requiere $n$ adiciones 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$ multiplicaciones-sumas fusionadas . El método de Horner también se puede extender para evaluar el primero. $k$ derivadas del polinomio con $kn$ sumas y multiplicaciones. ^{[ 3 ]}

El método de Horner es óptimo, en el sentido de que cualquier algoritmo para evaluar un polinomio arbitrario debe usar al menos la misma cantidad de operaciones. Alexander Ostrowski demostró en 1954 que el número de sumas requeridas es mínimo. ^{[ 4 ]} Victor Pan demostró en 1966 que el número de multiplicaciones es mínimo. ^{[ 5 ]}

Sin embargo, el método de Horner no es óptimo para la evaluación de polinomios matriciales (donde $x$ es una matriz, pero los coeficientes son escalares), cuando contamos las multiplicaciones escalares y las multiplicaciones de matrices por separado, ya que las primeras son más baratas que las segundas.

Esto supone que el polinomio se evalúa en forma monomial y no se permite ningún precondicionamiento de la representación, lo cual tiene sentido si el polinomio se evalúa solo una vez. Sin embargo, si se permite el precondicionamiento y el polinomio se va a evaluar muchas veces, entonces son posibles algoritmos más rápidos . Estos implican una transformación de la representación del polinomio. En general, un grado- $n$ El polinomio se puede evaluar utilizando solo ⌊ n /2 ⌋ +2 multiplicaciones y $n$ adiciones. ^{[ 6 ]}

Evaluación paralela

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

Sin embargo, si se está evaluando un único polinomio de orden muy alto, puede resultar útil dividirlo de la siguiente manera: ${\begin{aligned}p(x)&=\sum _{i=0}^{n}a_{i}x^{i}\\[1ex]&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\[1ex]&=\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)\\[1ex]&=\left(a_{0}+a_{2}x^{2}+a_{4}x^{4}+\cdots \right)+x\left(a_{1}+a_{3}x^{2}+a_{5}x^{4}+\cdots \right)\\[1ex]&=\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i}x^{2i}+x\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i+1}x^{2i}\\[1ex]&=p_{0}(x^{2})+xp_{1}(x^{2}).\end{aligned}}$

En términos más generales, la suma se puede dividir en k partes: $p(x)=\sum _{i=0}^{n}a_{i}x^{i}=\sum _{j=0}^{k-1}x^{j}\sum _{i=0}^{\lfloor n/k\rfloor }a_{ki+j}x^{ki}=\sum _{j=0}^{k-1}x^{j}p_{j}(x^{k})$ donde las sumas internas pueden evaluarse utilizando 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 matemáticas reasociativas (inseguras) . Otro uso de descomponer un polinomio de esta manera es calcular los pasos de las sumas internas de forma alternada para aprovechar el paralelismo a nivel de instrucción .

Aplicación a la multiplicación y división de punto flotante.

El método de 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 van a multiplicar se representa como un polinomio trivial, donde (usando la notación anterior) $a_{i}=1$ , y $x=2$ . Luego, x (o x elevado a alguna potencia) se factoriza repetidamente. En este sistema numérico binario (base 2), $x=2$ , por lo que las potencias de 2 se factorizan repetidamente.

Ejemplo

Por ejemplo, para hallar el producto de dos números (0.15625) y m : ${\begin{aligned}(0.15625)m&=(0.00101_{b})m=\left(2^{-3}+2^{-5}\right)m=\left(2^{-3})m+(2^{-5}\right)m\\&=2^{-3}\left(m+\left(2^{-2}\right)m\right)=2^{-3}\left(m+2^{-2}(m)\right).\end{aligned}}$

Método

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

Un registro que contiene el resultado intermedio se inicializa a d .
Comience con el bit no nulo menos significativo (el de más a la derecha) en m .
1. Cuenta (hacia la izquierda) el número de posiciones de bit hasta el siguiente bit no nulo más significativo. Si no hay bits más significativos, toma el valor de la posición de bit actual.
2. Utilizando ese valor, realice una operación de desplazamiento a la izquierda por esa cantidad de bits en el registro que contiene el resultado intermedio.
Si se contaron todos los bits distintos de cero, el registro de resultado intermedio ahora contiene el resultado final. De lo contrario, se suma d al resultado intermedio y se continúa en el paso 2 con el siguiente bit más significativo en m .

Derivación

En general, para un número binario con valores de bits ( $d_{3}d_{2}d_{1}d_{0}$ ) el producto es $(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, es necesario que se eliminen los términos con coeficientes iguales a cero, 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 esta implicación en la ecuación factorizada: $=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 de forma 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áticas binarias (base 2), la multiplicación por una potencia de 2 es simplemente una operación de desplazamiento de registro . Por lo tanto, la multiplicación por 2 se calcula en base 2 mediante un desplazamiento aritmético . El factor (2 ⁻¹ ) es un desplazamiento aritmético a la derecha , a (0) no produce ninguna operación (ya que 2 ⁰ = 1 es el elemento neutro multiplicativo ), y a (2 ¹ ) produce un desplazamiento aritmético a la izquierda. El producto de la multiplicación ahora se puede calcular rápidamente utilizando solo operaciones de desplazamiento aritmético, suma y resta .

El método es particularmente rápido en procesadores que admiten una instrucción única de desplazamiento, suma y acumulación. En comparación con una biblioteca de punto flotante de C, el método de Horner sacrifica algo de precisión; sin embargo, es nominalmente 13 veces más rápido (16 veces más rápido cuando se utiliza la forma de " dígito con signo canónico " (CSD)) y utiliza solo el 20 % del espacio de código. ^{[ 7 ]}

Otras aplicaciones

El método de Horner puede utilizarse para convertir entre diferentes sistemas de numeración posicional —en cuyo caso x es la base del sistema numérico y los coeficientes a _i son los dígitos de la representación en base x de un número dado— y también puede utilizarse si x es una matriz , en cuyo caso la mejora en la eficiencia computacional es aún mayor. Sin embargo, para estos casos se conocen métodos más rápidos . ^{[ 8 ]}

Hallazgo de raíces polinómicas

Utilizando 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 de la siguiente manera. Dado un polinomio $p_{n}(x)$ de grado $n$ con ceros $z_{n}<z_{n-1}<\cdots <z_{1},$ hacer alguna suposición inicial $x_{0}$ de tal manera que $z_{1}<x_{0}$ Ahora repita los dos pasos siguientes:

Utilizando el método de Newton , encuentre el cero más grande. $z_{1}$ de $p_{n}(x)$ usando la suposición $x_{0}$ .
Utilizando el método de Horner, divida $(x-z_{1})$ para obtener $p_{n-1}$ . Regrese al paso 1 pero use el polinomio $p_{n-1}$ y la suposición inicial $z_{1}$ .

Estos dos pasos se repiten hasta encontrar todos los ceros reales del polinomio. Si los ceros aproximados no son lo suficientemente precisos, los valores obtenidos pueden usarse como estimaciones iniciales para el método de Newton, pero utilizando el polinomio completo en lugar de los polinomios reducidos. ^{[ 9 ]}

Ejemplo

Hallazgo de raíces polinómicas mediante el método de Horner

Consideremos el polinomio $p_{6}(x)=(x+8)(x+5)(x+3)(x-2)(x-3)(x-7)$ que se puede ampliar a $p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040.$

De lo anterior sabemos que la raíz más grande de este polinomio es 7, por lo que podemos hacer una estimación inicial de 8. Usando el método de Newton, se encuentra el primer cero de 7, como se muestra en negro en la figura de la derecha. A continuación $p(x)$ está dividido por $(x-7)$ para obtener $p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720$ que se muestra en rojo en la figura de la derecha. Se utiliza el método de Newton para encontrar la raíz más grande de este polinomio con una estimación inicial de 7. La raíz más grande de este polinomio, que corresponde a la segunda raíz más grande del polinomio original, se encuentra en 3 y está marcada con un círculo rojo. El polinomio de grado 5 ahora se divide por $(x-3)$ para obtener $p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240$ que se muestra en amarillo. El cero de este polinomio se encuentra en 2 nuevamente usando el método de Newton y está rodeado en amarillo. Ahora se utiliza el método de Horner para obtener $p_{3}(x)=x^{3}+16x^{2}+79x+120$ que se muestra en verde y se encuentra que tiene un cero en − 3. Este polinomio se reduce aún más a $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 estimación inicial para el método de Newton, o reduciendo $p_{2}(x)$ y resolviendo la ecuación lineal . Como se puede observar, se encontraron las raíces esperadas de −8 , −5 , −3 , 2, 3 y 7.

Diferencia dividida de un polinomio

El método de Horner se puede modificar para calcular la diferencia dividida. $(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 ^{[ 10 ]} ${\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 ${\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}}$ Este cálculo de la diferencia dividida está sujeto a un menor error de redondeo que la evaluación $p(x)$ y $p(y)$ por separado, particularmente cuando $x\approx y$ .

Derivada de un polinomio

Sustituyendo $y=x$ en este método da ${\textstyle d_{1}=p'(x)=\sum _{i=1}^{n}ia_{i}x^{i-1}}$ , el derivado de $p(x)$ Evaluar un polinomio y su derivada en un punto es útil para encontrar raíces mediante el método de Newton .

Historia

El algoritmo de Qin Jiushao para resolver la ecuación polinómica cuadrática $-x^{4}+763200x^{2}-40642560000=0$ resultado: x =840 ^{[ 11 ]}

{\displaystyle -x^{4}+763200x^{2}-40642560000=0} — El algoritmo de Qin Jiushao para resolver la ecuación polinómica cuadrática $-x^{4}+763200x^{2}-40642560000=0$ resultado: x =840 ^{[ 11 ]}

El artículo de Horner, titulado "Un nuevo método para resolver ecuaciones numéricas de todos los órdenes, mediante aproximación continua", ^{[ 12 ]} fue leído ante la Royal Society de Londres, en su reunión del 1 de julio de 1819, con una continuación en 1823. ^{[ 12 ]} El artículo de Horner en la Parte II de Philosophical Transactions of the Royal Society of London de 1819 fue recibido con entusiasmo y amplitud por un crítico en el número de The Monthly Review: or, Literary Journal de abril de 1820; en comparación, un artículo técnico de Charles Babbage es descartado bruscamente 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 ^[¹³^] demostró que el método del artículo de Horner de 1819 difiere de lo que posteriormente se conoció como "método de Horner" y que, en consecuencia, la prioridad de este método debería recaer en Holdred (1820).

A diferencia de sus contemporáneos ingleses, Horner se basó en la literatura continental, en particular en la obra de Arbogast . También se sabe que Horner realizó una lectura minuciosa del libro de álgebra de John Bonneycastle, aunque descuidó la obra de Paolo Ruffini .

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

Paolo Ruffini en 1809 (ver regla de Ruffini ) ^{[ 14 ]}^{[ 15 ]}
Isaac Newton en 1669 ^{[ 16 ]}^{[ 17 ]}
el matemático chino Zhu Shijie en el siglo XIV ^{[ 15 ]}
El matemático chino Qin Jiushao en su Tratado matemático en nueve secciones en el siglo XIII.
el matemático persa Sharaf al-Dīn al-Ṭū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 Song ).
Los Nueve Capítulos sobre el Arte Matemático , una obra china de la dinastía Han (202 a. C. – 220 d. C.) editada por Liu Hui (activo en el siglo III).^{[ 19 ]}

Qin Jiushao , en su Shùshū Jiǔzhāng ( Tratado matemático en nueve secciones ; 1247), presenta un conjunto de métodos de tipo Horner para resolver ecuaciones polinómicas, basados en trabajos anteriores del matemático Jia Xian , de la dinastía Song del siglo XI ; por ejemplo, un método es especialmente adecuado para ecuaciones biquínticas, de las cuales Qin ofrece un ejemplo, en consonancia con la costumbre china de la época de realizar estudios de caso. Yoshio Mikami , en El desarrollo de las matemáticas en China y Japón (Leipzig, 1913), escribió:

«... ¿ quién puede negar que el ilustre proceso de Horner se utilizó en China al menos seis largos siglos antes que en Europa ?... Por supuesto, no pretendemos en absoluto atribuir la invención de Horner a un origen chino, pero el transcurso del tiempo hace que no sea del todo imposible que los europeos pudieran haber conocido el método chino de forma directa o indirecta.» ^{[ 20 ]}

Ulrich Libbrecht concluyó: Es obvio que este procedimiento es una invención china ... el método no era conocido en la India . Dijo que Fibonacci probablemente lo aprendió de los árabes, quienes tal vez lo tomaron prestado de los chinos. ^{[ 21 ]} La extracción de raíces cuadradas y cúbicas siguiendo líneas similares ya es discutida por Liu Hui 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 ecuaciones cúbicas mediante un método de aproximación descrito en su libro Jigu Suanjing .

Véase también

Algoritmo de Clenshaw para evaluar polinomios en forma de Chebyshev.
Algoritmo de De Boor para evaluar splines en forma de B-spline .
Algoritmo de De Casteljau para evaluar polinomios en forma de Bézier
El plan de Estrin para facilitar la paralelización en arquitecturas informáticas modernas.
Método de Lill para aproximar gráficamente las raíces
Regla de Ruffini y división sintética para dividir un polinomio por un binomio de la forma x − r

Notas

↑ 600 años antes, por el matemático chino Qin Jiushao y 700 años antes, por el matemático persa Sharaf al-Dīn al-Ṭūsī
↑ Pan 1966
↑ Pankiewicz 1968 .
↑ Ostrowski 1954 .
↑ Pan 1966 .
↑ Knuth 1997 .
↑ Kripasagar 2008 , pág. 62 .
↑ Higham 2002 , Sección 5.4 .
↑ Kress 1991 , pág. 112 .
↑ Fateman y Kahan 2000
↑ Libbrecht 2005 , págs. 181-191 .
1 2 Horner 1819 .
↑ Fuller 1999 , págs. 29–51 .
↑ Cajori 1911 .
1 2 O'Connor, John J.; Robertson, Edmund F. , "El método de Horner " , Archivo de Historia de las Matemáticas de MacTutor , Universidad de St Andrews
^ Análisis por serie Quantitatum, Fluctiones ac Differentias : Cum Enumeratione Linearum Tertii Ordinis, Londini. Ex Officina Pearsoniana. Año MDCCXI, pág. 10, 4º párrafo.
↑ Obras completas de Newton, edición de 1779, en una nota a pie de página, vol. I, págs. 270-271
^ Berggren 1990 , págs. 304–309 .
↑ Temple 1986 , pág. 142 .
↑ Mikami 1913 , pág. 77
↑ Libbrecht 2005 , pág. 208 .

Referencias

Berggren, JL (1990). "Innovación y tradición en el Muadalat de Sharaf al-Din al-Tusi". Journal of the American Oriental Society . 110 (2): 304– 309. doi : 10.2307/604533 . JSTOR 604533 .
Cajori, Florian (1911). "El método de aproximación de Horner anticipado por Ruffini" . Boletín de la Sociedad Matemática Americana . 17 (8): 409– 414. doi : 10.1090/s0002-9904-1911-02072-9 . Archivado del original el 4 de septiembre de 2017. Consultado el 4 de marzo de 2012 .Leído ante la Sección Sudoccidental de la Sociedad Matemática Americana el 26 de noviembre de 1910.
Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). "Introducción a los Algoritmos" . Historia Matemática . 8 (3) (3ª ed.). Prensa del MIT: 277– 318. doi : 10.1016/0315-0860(81)90069-0 .
Fateman, RJ ; Kahan, W. (2000). Mejora de integrales exactas a partir de sistemas de álgebra simbólica (PDF) (Informe). PAM. Universidad de California, Berkeley: Centro de Matemáticas Puras y Aplicadas. Archivado del original (PDF) el 14 de agosto de 2017. Consultado el 17 de mayo de 2018 .
Fuller, AT (1999). "Horner contra Holdred: Un episodio en la historia del cálculo de raíces" . Historia Mathematica . 26 : 29–51 . doi : 10.1006/hmat.1998.2214 .
Higham, Nicholas (2002). Precisión y estabilidad de los algoritmos numéricos . SIAM. ISBN 978-0-89871-521-7.
Holdred, T. (1820). Un nuevo método para resolver ecuaciones con facilidad y rapidez; mediante el cual se halla el valor verdadero de la cantidad desconocida sin reducción previa. Con un suplemento que contiene otros dos métodos para resolver ecuaciones, derivados del mismo principio (PDF) . Richard Watts. Archivado del original (PDF) el 6 de enero de 2014. Consultado el 10 de diciembre de 2012 .
El método de Holdred se encuentra en el suplemento que aparece después de la página número 45 (que es la página 52 de la versión en PDF).
Horner, William George (julio de 1819). "Un nuevo método para resolver ecuaciones numéricas de todos los órdenes mediante aproximación continua". Philosophical Transactions . 109. Royal Society of London: 308–335 . doi : 10.1098/rstl.1819.0023 . JSTOR 107508. S2CID 186210512 .
Disponible directamente en línea a través del enlace, pero también reimpreso con análisis en DE Smith: A Source Book in Mathematics , McGraw-Hill, 1929; reimpresión de Dover, 2 vols., 1959.
Knuth, Donald (1997). El arte de la programación informática . Vol. 2: Algoritmos seminuméricos (3.ª ed.). Addison-Wesley. págs. 486-488 en la sección 4.6.4. ISBN 978-0-201-89684-8.
Kress, Rainer (1991). Análisis numérico . Springer.
Kripasagar, Venkat (marzo de 2008). "Micromatemáticas eficientes : técnicas de multiplicación y división para MCU". Revista Circuit Cellar (212).
Libbrecht, Ulrich (2005). «Capítulo 13» . Matemáticas chinas en el siglo XIII (2.ª ed.). Dover. ISBN 978-0-486-44619-6Archivado del original el 6 de junio de 2017. Consultado el 23 de agosto de 2016 .
Mikami, Yoshio (1913). «Capítulo 11. Ch'in Chiu-Shao» . El desarrollo de las matemáticas en China y Japón (1.ª ed.). Reimpresión de Chelsea Publishing Co., págs. 74-77 .
Ostrowski, Alexander M. (1954). «Sobre dos problemas de álgebra abstracta relacionados con la regla de Horner» . Estudios de matemáticas y mecánica presentados a Richard von Mises . Academic Press. pp. 40–48 . ISBN 978-1-4832-3272-0Archivado del original el 15 de abril de 2019. Consultado el 23 de agosto de 2016 .{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
Pan, Y. Ja (1966). "Sobre los medios para calcular los valores de los polinomios". Russian Math. Surveys . 21 : 105– 136. doi : 10.1070/rm1966v021n01abeh004147 . S2CID 250869179 .
Pankiewicz, W. (1968). "Algoritmo 337: cálculo de un polinomio y sus valores derivados mediante el esquema de Horner" . Communications of the ACM . 11 (9). ACM: 633. doi : 10.1145/364063.364089 . S2CID 52859619 .
Spiegel, Murray R. (1956). Schaum's Outline of Theory and Problems of College Algebra . McGraw-Hill. ISBN 9780070602267.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
Temple, Robert (1986). El genio de China: 3000 años de ciencia, descubrimiento e invención . Simon and Schuster. ISBN 978-0-671-62028-8.
Whittaker, ET ; Robinson, G. (1924). El cálculo de las observaciones . Londres: Blackie.
Wylie, Alexander (1897). "Apuntes sobre la ciencia de la aritmética china" . Investigaciones chinas . Shanghái. págs. 159–194 . {{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
Reimpreso de ejemplares de The North China Herald (1852).

Enlaces externos

"Esquema de Horner" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
Qiu, Jin-Shao. "Método Horner" (PDF) . turing.une.edu.au (en chino). Archivado del original (PDF) el 6 de enero de 2014. Consultado el 17 de enero de 2026 .
Weisstein, Eric W. (28 de septiembre de 2018). "Método de Horner" . mathworld.wolfram.com . Consultado el 17 de enero de 2026 .Más información sobre la aplicación para encontrar raíces

[1] 600 años antes, por el matemático chino Qin Jiushao y 700 años antes, por el matemático persa Sharaf al-Dīn al-Ṭūsī

[2] Pan 1966

[3] Pankiewicz 1968 .

[4] Ostrowski 1954 .

[5] Pan 1966 .

[6] Knuth 1997 .

[7] Kripasagar 2008 , pág. 62 .

[8] Higham 2002 , Sección 5.4 .

[9] Kress 1991 , pág. 112 .

[Fateman_&_Kahan-10] Fateman y Kahan 2000

[11] Libbrecht 2005 , págs. 181-191 .

[Horner-12] 1 2 Horner 1819 .

[13] Fuller 1999 , págs. 29–51 .

[Cajori-14] Cajori 1911 .

[St_Andrews-15] 1 2 O'Connor, John J.; Robertson, Edmund F. , "El método de Horner " , Archivo de Historia de las Matemáticas de MacTutor , Universidad de St Andrews

[16] Análisis por serie Quantitatum, Fluctiones ac Differentias : Cum Enumeratione Linearum Tertii Ordinis, Londini. Ex Officina Pearsoniana. Año MDCCXI, pág. 10, 4º párrafo.

[17] Obras completas de Newton, edición de 1779, en una nota a pie de página, vol. I, págs. 270-271

[18] Berggren 1990 , págs. 304–309 .

[19] Temple 1986 , pág. 142 .

[20] Mikami 1913 , pág. 77

[21] Libbrecht 2005 , pág. 208 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[

[ 19 ]

[ 20 ]

[ 21 ]