El método de Horner.

Algoritmo de evaluación polinomial.

En matemáticas e informática , el método de Horner (o esquema de Horner ) es un algoritmo para la evaluación polinomial . 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 remonta a muchos cientos de años hasta los matemáticos chinos y persas. ^[1] 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 , en la que un polinomio se escribe en forma anidada :

${\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 solo multiplicaciones y sumas. Esto es óptimo, ya que hay polinomios de grado n que no pueden evaluarse con menos operaciones aritméticas. ^[2] ${\displaystyle n}$ ${\displaystyle n}$

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 que se hace más eficiente para el 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

${\displaystyle 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 son coeficientes constantes, el problema es evaluar el polinomio en un valor específico de ${\displaystyle a_{0},\ldots ,a_{n}}$ ${\displaystyle x_{0}}$ ${\displaystyle x.}$

Para ello, 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 es el valor de . ${\displaystyle b_{0}}$ ${\displaystyle 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 )}\ .}$

Por lo tanto, al sustituir iterativamente the en la expresión, ${\displaystyle b_{i}}$

${\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 bien, se puede comprobar 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 (que es igual a ) el resto de la división, como lo demuestran los ejemplos siguientes. Si es raíz de , entonces (lo que significa que el resto es ), lo que significa que puedes factorizar como . ${\displaystyle b_{0}}$ ${\displaystyle p(x_{0})}$ ${\displaystyle x_{0}}$ ${\displaystyle p(x)}$ ${\displaystyle b_{0}=0}$ ${\displaystyle 0}$ ${\displaystyle p(x)}$ ${\displaystyle x-x_{0}}$

Para encontrar los valores consecutivos, comience determinando , que es simplemente igual a . Luego trabajas recursivamente usando la fórmula; ${\displaystyle b}$ ${\displaystyle b_{n}}$ ${\displaystyle a_{n}}$

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

hasta llegar a . ${\displaystyle b_{0}}$

Ejemplos

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

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

 x 0 │ x 3  x 2  x 1  x 0 3 │ 2 −6 2 −1 │ 6 0 6 └──────────────────────── 2 0 2 5

Las entradas de la tercera fila son la suma de las de las dos primeras. Cada entrada en la segunda fila es el producto del valor de 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 a evaluar. Entonces el resto de la división por es ${\displaystyle f(x)}$ ${\displaystyle x-3}$5 .

Pero por el teorema del resto polinomial , sabemos que el resto es . De este modo, . ${\displaystyle f(3)}$ ${\displaystyle f(3)=5}$

En este ejemplo, si podemos ver eso , las entradas en la tercera fila. Entonces, 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. ${\displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1}$ ${\displaystyle b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5}$

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

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

2 │ 1 −6 11 −6 │ 2 −8 6 └──────────────────────── 1 −4 3 0

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

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

 0,5 │ 4 -6 0 3 -5 │ 2 -2 -1 1 └─────────────────────── 2 -2 -1 1 -4

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

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

Eficiencia

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

Si los datos numéricos se representan en términos de dígitos (o bits), entonces el algoritmo ingenuo también implica almacenar aproximadamente veces el número de bits de : el polinomio evaluado tiene una magnitud aproximada , y también se debe almacenar a sí mismo. Por el contrario, el método de Horner sólo requiere sumas y multiplicaciones, y sus requisitos de almacenamiento son sólo multiplicados por el número de bits de . Alternativamente, el método de Horner se puede calcular con sumas y multiplicaciones fusionadas . El método de Horner también se puede ampliar para evaluar las primeras derivadas del polinomio con sumas y multiplicaciones. ^[3] ${\displaystyle 2n}$ ${\displaystyle x}$ ${\displaystyle x^{n}}$ ${\displaystyle x^{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle kn}$

El método de Horner es óptimo, en el sentido de que cualquier algoritmo para evaluar un polinomio arbitrario debe utilizar al menos la misma cantidad de operaciones. Alexander Ostrowski demostró en 1954 que el número de adiciones necesarias es mínimo. ^[4] Victor Pan demostró en 1966 que el número de multiplicaciones es mínimo. ^[5] Sin embargo, cuando se trata de una matriz, el método de Horner no es óptimo . ${\displaystyle x}$

Esto supone que el polinomio se evalúa en forma monomial y no se permite ningún precondicionamiento de la representación, lo que tiene sentido si el polinomio se evalúa sólo 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 . Implican una transformación de la representación del polinomio. En general, un polinomio de grado se puede evaluar usando solo ⌊ n /2 ⌋ +2 multiplicaciones y sumas. ^[6] ${\displaystyle n}$ ${\displaystyle n}$

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 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, 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 cuadrado de una 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 se evalúa un polinomio único de orden muy alto, puede resultar ú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)+x\left(a_{1}+a_{3}x^{2}+a_{5}x^{4}+\cdots \right)\\&=\sum _{i=0}^{\lfloor n/2\rfloor }a_{2i}x^{2i}+x\sum _{i=0}^{\lfloor n/2\rfloor }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/k\rfloor }a_{ki+j}x^{ki}\\&=\sum _{j=0}^{k-1}x^{j}p_{j}(x^{k})\\\end{aligned}}}$

donde las sumatorias 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 son ventajosos, aunque para cálculos de punto flotante esto requiere habilitar matemáticas reasociativas (inseguras) ^{[ cita necesaria ]} .

Aplicación a la multiplicación y división en 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) y . Luego, x (o x elevado a alguna potencia) se factoriza repetidamente. En este sistema numérico binario (base 2), , las potencias de 2 se factorizan repetidamente. ${\displaystyle a_{i}=1}$ ${\displaystyle x=2}$ ${\displaystyle x=2}$

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=\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 encontrar el producto de dos números binarios d y m :

1. Un registro que contiene el resultado intermedio se inicializa en d .

2. Comience con el bit distinto de cero menos significativo (el más a la derecha) en m .

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

2c. Usando ese valor, realice una operación de desplazamiento a la izquierda con esa cantidad de bits en el registro que contiene el resultado intermedio.

3. Si se contaron todos los bits distintos de cero, entonces el registro de resultados intermedio ahora contiene el resultado final. De lo contrario, agregue d al resultado intermedio y continúe 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 ( ), el producto es ${\displaystyle d_{3}d_{2}d_{1}d_{0}}$

${\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 esta implicación en el 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

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

o de manera equivalente (según sea consistente con el "método" descrito anteriormente)

${\displaystyle =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 cambio de registro . Así, multiplicar por 2 se calcula en base 2 mediante un desplazamiento aritmético . El factor (2 ⁻¹ ) es un desplazamiento aritmético hacia la derecha , un (0) no produce ninguna operación (ya que 2 ⁰ = 1 es el elemento identidad multiplicativo ) y un (2 ¹ ) da como resultado un desplazamiento aritmético hacia la izquierda. El producto de la multiplicación ahora se puede calcular rápidamente utilizando únicamente operaciones aritméticas de desplazamiento, suma y resta.

El método es particularmente rápido en procesadores que admiten una acumulación de desplazamiento y suma de una sola instrucción. En comparación con una biblioteca de punto flotante 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 canónico con signo " (CSD)) y utiliza sólo el 20% del espacio de código. ^[7]

Otras aplicaciones

El método de Horner se puede utilizar para convertir entre diferentes 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 en base x de un número determinado, y también se puede utilizar 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 . ^[8]

Hallazgo de raíz polinómica

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 de grado con ceros, haga una suposición inicial tal que . Ahora repita los siguientes dos pasos: ${\displaystyle p_{n}(x)}$ ${\displaystyle n}$ ${\displaystyle z_{n}<z_{n-1}<\cdots <z_{1},}$ ${\displaystyle x_{0}}$ ${\displaystyle z_{1}<x_{0}}$

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

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

Ejemplo

Búsqueda de raíces polinómicas mediante el método de Horner

Considere el polinomio

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

que se puede ampliar a

${\displaystyle 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, el primer cero de 7 se encuentra como se muestra en negro en la figura de la derecha. A continuación se divide por para obtener ${\displaystyle p(x)}$ ${\displaystyle (x-7)}$

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

que está dibujado en rojo en la figura de la derecha. El método de Newton se utiliza para encontrar el cero más grande de este polinomio con una estimación inicial de 7. El cero más grande de este polinomio que corresponde al segundo cero más grande del polinomio original se encuentra en 3 y está rodeado por un círculo rojo. El polinomio de grado 5 ahora se divide por para obtener ${\displaystyle (x-3)}$

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

que se muestra en amarillo. El cero de este polinomio se encuentra nuevamente en 2 usando el método de Newton y está rodeado por un círculo amarillo. Actualmente 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 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 usando el cero final como estimación inicial para el método de Newton o reduciendo y resolviendo la ecuación lineal . Como puede verse, se encontraron las raíces esperadas de −8, −5, −3, 2, 3 y 7. ${\displaystyle p_{2}(x)}$

Diferencia dividida de un polinomio

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

${\displaystyle 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},}$

proceder de la siguiente manera ^[10]

${\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}}}$

Este cálculo de la diferencia dividida está sujeto a menos error de redondeo que evaluar y por separado, particularmente cuando . Al sustituir en este método se obtiene la derivada de . ${\displaystyle p(x)}$ ${\displaystyle p(y)}$ ${\displaystyle x\approx y}$ ${\displaystyle y=x}$ ${\displaystyle d_{1}=p'(x)}$ ${\displaystyle p(x)}$

Historia

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

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 secuela 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 calurosamente y ampliamente por un crítico ^{[ enlace muerto permanente ]} en la edición de The Monthly Review: or, Literary Journal de abril de 1820; en comparación, en esta revisión se descarta tajantemente un artículo técnico de Charles Babbage . 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 ^[13] demostró que el método del artículo de Horner de 1819 difiere de lo que más tarde se conoció como "método de Horner" y que, en consecuencia, la prioridad para 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 la obra de Arbogast . También se sabe que Horner leyó atentamente el libro de álgebra de John Bonneycastle, aunque descuidó el trabajo de Paolo Ruffini .

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

• 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) ^[18]
• el matemático chino Jia Xian en el siglo XI ( dinastía Song )
• Los Nueve Capítulos sobre el Arte Matemático , obra china de la dinastía Han (202 a. C. – 220 d. C.) editada por Liu Hui (fl. siglo III). ^[19]

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 de la dinastía Song del siglo XI, Jia Xian ; por ejemplo, un método es específicamente adecuado para biquínticos, del cual Qin da un ejemplo, de acuerdo con la costumbre china de entonces de estudiar casos de caso. Yoshio Mikami en Development of Mathematics in China and Japan (Leipzig 1913) escribió:

"... ¿quién puede negar el hecho de que el ilustre proceso de Horner se utilizó en China al menos casi seis largos siglos antes que en Europa... Por supuesto, no pretendemos de ninguna manera atribuir el invento de Horner a un origen chino, pero el lapso de tiempo hace que no sea del todo imposible que los europeos pudieran haber conocido el método chino de manera 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 se enteró de esto de los árabes, quienes tal vez tomaron prestado de los chinos. ^[21] 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úbicas mediante una aproximación. método descrito en su libro Jigu Suanjing .

Ver también

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

Notas

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, pag. 62.
8. Higham 2002, sección 5.4.
9. Kress 1991, pag. 112.
10. Fateman y Kahan 2000
11. Libbrecht 2005, págs. 181-191.
12. Horner 1819.
13. Fuller 1999, págs. 29–51.
14. Cajori 1911.
15. O'Connor, John J.; Robertson, Edmund F. , "Método de Horner", Archivo MacTutor de Historia de las Matemáticas , 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. Artículos recopilados de Newton, edición de 1779, en una nota a pie de página, vol. Yo, pág. 270-271
18. Berggren 1990, págs. 304–309.
19. Templo 1986, pag. 142.
20. Mikami 1913, pag. 77
21. Libbrecht 2005, pag. 208.

Referencias

• Berggren, JL (1990). "Innovación y tradición en Muadalat de Sharaf al-Din al-Tusi". Revista de la Sociedad Oriental Americana . 110 (2): 304–309. doi :10.2307/604533. JSTOR  604533.
• Cajori, Florián (1911). "El método de aproximación de Horner anticipado por Ruffini". Boletín de la Sociedad Matemática Estadounidense . 17 (8): 409–414. doi : 10.1090/s0002-9904-1911-02072-9 .Leído ante la Sección Sudoeste de la Sociedad Matemática Estadounidense el 26 de noviembre de 1910.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein10.1016/0315-0860(81)90069-0, 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 .{{cite journal}}: CS1 maint: numeric names: authors list (link)
• Fateman, RJ ; Kahan, W. (2000). Mejora de integrales exactas a partir de sistemas de álgebra simbólica (PDF) (Reporte). PAM. Universidad de California, Berkeley: Centro de Matemáticas Puras y Aplicadas. Archivado desde el original (PDF) el 14 de agosto de 2017 . Consultado el 17 de mayo de 2018 .
• Más completo, AT (1999). "Horner versus Holdred: un episodio en la historia de la computación raíz". Historia Matemática . 26 : 29–51. doi : 10.1006/hmat.1998.2214 .
• Higham, Nicolás (2002). Precisión y estabilidad de algoritmos numéricos . SIAM. ISBN 978-0-89871-521-7.
• Holdred, T. (1820). Un nuevo método para resolver ecuaciones con facilidad y rapidez; por el cual se encuentra 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 desde el 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 siguiente a la página número 45 (que es la página 52 de la versión pdf).

• Horner, William George (julio de 1819). "Un nuevo método de resolución de ecuaciones numéricas de todos los órdenes, mediante aproximación continua". Transacciones filosóficas . 109 . Real Sociedad de Londres: 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 evaluación en DE Smith: A Source Book in Mathematics , McGraw-Hill, 1929; Reimpresión de Dover, 2 volúmenes, 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 . Saltador.
• 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-6. Archivado desde el 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 en Matemáticas y Mecánica presentados a Richard von Mises . Prensa académica. págs. 40–48. ISBN 978-1-4832-3272-0.
• Pan, Y. Ja (1966). "Sobre los medios para calcular valores de polinomios". Matemáticas rusas. Encuestas . 21 : 105-136. doi :10.1070/rm1966v021n01abeh004147. S2CID  250869179.
• Pankiewicz, W. (1968). "Algoritmo 337: cálculo de un polinomio y sus valores derivados mediante esquema de Horner". Comunicaciones de la ACM . 11 (9). ACM: 633.doi : 10.1145 /364063.364089 . S2CID  52859619.
• Spiegel, Murray R. (1956). Esquema de la teoría y los problemas del álgebra universitaria de Schaum . McGraw-Hill. ISBN 9780070602267.
• Templo, Robert (1986). El genio de China: 3.000 años de ciencia, descubrimiento e invención . Simón y Schuster. ISBN 978-0-671-62028-8.
• Whittaker, et al ; Robinson, G. (1924). El cálculo de las observaciones. Londres: Blackie.
• Wylie, Alejandro (1897). "Apuntes sobre la ciencia de la aritmética china". Investigaciones chinas . Llevar a la fuerza. págs. 159-194.{{cite book}}: CS1 maint: location missing publisher (link)

  Reimpreso de números de The North China Herald (1852).

enlaces externos

• "Esquema de Horner", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Qiu Jin-Shao, Shu Shu Jiu Zhang (Cong Shu Ji Cheng ed.)
• Para obtener más información sobre la aplicación de búsqueda de raíces, consulte [1]