Lema (matemáticas)
En matemáticas, un lema es un teorema o proposición plenamente demostrado, que se usa para probar teoremas más complejos. El lema generalmente constituye... (leer más)
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:
Esto permite la evaluación de un polinomio de grado n con sólo n{displaystyle n} multiplicaciones y n{displaystyle 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.
Dado el polinomio
Donde a0,...... ,an{displaystyle a_{0},ldotsa_{n} son coeficientes constantes, el problema es evaluar el polinomio a un valor específico x0{displaystyle x_{0} de x.{displaystyle x.}
Para esto, se define recursivamente una nueva secuencia de constantes de la siguiente manera:
Entonces... b0{displaystyle B_{0} es el valor de p()x0){displaystyle p(x_{0}}.
Para ver por qué esto funciona, el polinomio se puede escribir en la forma
Así, sustituyendo iterativamente al bi{displaystyle B_{i} en la expresión,
Ahora, se puede probar que;
Esta expresión constituye la aplicación práctica de Horner, ya que ofrece una forma muy rápida de determinar el resultado de;
siendo b0 (que es igual a p(x0)) el resto de la división, como se demuestra en los siguientes ejemplos. si x0 es una raíz de p(x), entonces b0 = 0 (lo que significa que el resto es 0), lo que significa que puedes factorizar p(x) con (x-x0).
Para encontrar los valores b consecutivos, comienza determinando bn, que es simplemente igual a an. Luego, avanza hasta los otros b & 39; s, usando la fórmula;
hasta llegar a b0.
Evaluate f()x)=2x3− − 6x2+2x− − 1{displaystyle f(x)=2x^{3}-6x^{2}+2x-1} para x=3.{displaystyle x=3.}
Usamos la división sintética de la siguiente manera:
x0. x3 x2 x1 x03 −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){displaystyle f(x)} on division by x− − 3{displaystyle x-3} 5.
Pero por el teorema del resto polinomio, sabemos que el resto es f()3){displaystyle f(3)}. Así f()3)=5{displaystyle f(3)=5}
En este ejemplo, si a3=2,a2=− − 6,a1=2,a0=− − 1{displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1} podemos ver que b3=2,b2=0,b1=2,b0=5{displaystyle 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){displaystyle f(x)} on division by x− − 3{displaystyle x-3}. El resto es 5. Esto hace que el método de Horner sea útil para la división polinomio larga.
Divide x3− − 6x2+11x− − 6{displaystyle x^{3}-6x^{2}+11x-6} por x− − 2{displaystyle x-2}:
2 −6 11 −6 2 - 8 6 - No. 1 −4 3 0
El cociente es x2− − 4x+3{displaystyle x^{2}-4x+3}.
Vamos f1()x)=4x4− − 6x3+3x− − 5{displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5} y f2()x)=2x− − 1{displaystyle f_{2}(x)=2x-1}. Divide f1()x){displaystyle f_{1}(x)} por f2()x){displaystyle 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
La evaluación usando la forma monomio de un polinomio de grado n requiere como máximo n adiciones y (n2 + 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 n, y también se debe almacenar xn). 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.
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:
De manera más general, la suma se puede dividir en k partes:
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).
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) ai=1{displaystyle A_{i}=1}, y x=2{displaystyle x=2}. Entonces, x (o x a algún poder) se factora repetidamente. En este sistema de numeral binario (base 2), x=2{displaystyle x=2}, por lo que los poderes de 2 se factoran repetidamente.
Por ejemplo, para encontrar el producto de dos números (0.15625) y m:
Para encontrar el producto de dos números binarios d y m:
En general, para un número binario con valores bits (d3d2d1d0{displaystyle D_{3}d_{2}d_{0}) el producto es
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:
Todos los denominadores son iguales a uno (o el término está ausente), por lo que esto se reduce a
o equivalente (de acuerdo con el "método" descrito anteriormente)
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−1) es un cambio aritmético a la derecha, un (0) no da como resultado ninguna operación (ya que 20 = 1 es el elemento de identidad multiplicativo), y un (21) 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.
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.
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 pn()x){displaystyle p_{n}(x)} grado n{displaystyle 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 x0{displaystyle 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:
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.
Considere el polinomio
que se puede expandir a
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){displaystyle p(x)} se divide por ()x− − 7){displaystyle (x-7)} para obtener
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){displaystyle (x-3)} para obtener
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
que se muestra en verde y se encontró que tiene un cero en −3. Este polinomio se reduce aún más a
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 p2()x){displaystyle 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.
El método de Horner puede ser modificado para calcular la diferencia dividida ()p()Sí.)− − p()x))/()Sí.− − x).{displaystyle (p(y)-p(x))/(y-x). } Dado el polinomio (como antes)
proceda de la siguiente manera
Al finalizar, tenemos
Esta computación de la diferencia dividida está sujeta a menos error redondeado que evaluación p()x){displaystyle p(x)} y p()Sí.){displaystyle p(y)} por separado, en particular cuando x.. Sí.{displaystyle xapprox y}. Sustitución Sí.=x{displaystyle y=x} en este método da d1=p.()x){displaystyle d_{1}=p'(x)}, el derivado de p()x){displaystyle p(x)}.
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:
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.
En matemáticas, un lema es un teorema o proposición plenamente demostrado, que se usa para probar teoremas más complejos. El lema generalmente constituye... (leer más)
En matemáticas, la identidad de Euler es la... (leer más)
En física matemática y matemáticas, las matrices de Pauli son un conjunto de tres 2 × 2 matrices complejas que son hermitianas, involutivas y unitarias.... (leer más)