En matemáticas e informática , la evaluación de polinomios se refiere al cálculo del valor de un polinomio cuando sus valores indeterminados se sustituyen por algunos valores. En otras palabras, evaluar el polinomio a consiste en computación Ver también Anillo polinomial § Evaluación polinomial
Para evaluar el polinomio univariado el método más ingenuo usaría multiplicaciones para calcular , usar multiplicaciones para calcular y así sucesivamente para un total de multiplicaciones y adiciones. Usando mejores métodos, como la regla de Horner , esto se puede reducir a multiplicaciones y adiciones. Si se permite algún procesamiento previo, es posible ahorrar aún más.
Fondo
Este problema surge con frecuencia en la práctica. En geometría computacional , los polinomios se usan para calcular aproximaciones de funciones usando polinomios de Taylor . En criptografía y tablas hash , los polinomios se utilizan para calcular el hash independiente de k .
En el primer caso, los polinomios se evalúan utilizando aritmética de punto flotante , que no es exacta. Por lo tanto, diferentes esquemas de evaluación darán, en general, respuestas ligeramente diferentes. En este último caso, los polinomios suelen evaluarse en un campo finito , en cuyo caso las respuestas siempre son exactas.
Métodos generales
Regla de Horner
El método de Horner evalúa un polinomio usando corchetes repetidos:
Este método reduce el número de multiplicaciones y adiciones a solo
El método de Horner es tan común que se ha agregado una instrucción de computadora, operación Multiplicar-acumular , a muchos procesadores de computadora, que permiten hacer las operaciones de suma y multiplicación en un solo paso combinado.
Multivariante
Si el polinomio es multivariado, la regla de Horner se puede aplicar de forma recursiva sobre algún orden de las variables. P.ej
Se puede escribir como
Carnicer y Gasca describieron una versión eficiente de este enfoque. [1]
Evaluación con preprocesamiento
Los polinomios arbitrarios se pueden evaluar con menos operaciones de las que requiere la regla de Horner si primero "preprocesamos" los coeficientes. .
Motzkin [2] dio un ejemplo por primera vez , quien señaló que
Se puede escribir como
donde los valores se calculan de antemano sobre la base de . El método de Motzkin usa solo 3 multiplicaciones en comparación con el 4 de Horner.
Los valores de cada se puede calcular fácilmente expandiendo e igualando los coeficientes:
Ejemplo
Para calcular la expansión de Taylor , podemos aumentar la escala en un factor de 24, aplicar los pasos anteriores y reducir la escala. Eso nos da el cálculo de tres multiplicaciones
Mejorando sobre la forma equivalente de Horner (es decir ) por 1 multiplicación.
Evaluación multipunto
Evaluar de un polinomio de grado en múltiples puntos se puede hacer con multiplicaciones usando el método de Horner veces. Usando el enfoque de preprocesamiento anterior, esto se puede reducir en un factor de dos, es decir, amultiplicaciones. Sin embargo, usando la Transformada Rápida de Fourier es posible reducir el requerimiento de tiempo a solo. [3]
En el caso de que los puntos en los que deseamos evaluar los polinomios tengan alguna estructura, existen métodos más simples. Por ejemplo, Knuth [4] proporciona un método para tabular valores polinomiales del tipo
- .
Evaluación dinámica
En el caso donde no se conocen de antemano, Kedlaya y Umans [5] proporcionaron una estructura de datos para evaluar polinomios en un campo finito de tamaño a tiempo por evaluación después de un preprocesamiento inicial. Larsen [6] demostró que esto es esencialmente óptimo.
La idea es transformar de grado en un polinomio multivariado , tal que y los grados individuales de es como máximo . Ya que esto terminó, el mayor valor puede tomar ) es . Utilizando el teorema del resto chino es suficiente para evaluar modulo diferentes primos con un producto al menos . Cada primo puede tomarse como aproximadamente y el número de primos necesarios, , es más o menos lo mismo. Haciendo este proceso de forma recursiva podemos obtener los números primos tan pequeños como. Eso significa que podemos calcular y almacenar en todos los valores posibles en tiempo y espacio. Si tomamos obtenemos , por lo que el requisito de tiempo / espacio es solo
Kedlaya y Umans muestran además cómo combinar este preprocesamiento con la evaluación multipunto rápida (FFT). Esto permite algoritmos óptimos para muchos problemas algebraicos importantes, como la composición modular polinomial .
Polinomios específicos
Mientras que los polinomios generales requieren operaciones para evaluar, algunos polinomios se pueden calcular mucho más rápido. Por ejemplo, el polinomio se puede calcular usando solo una multiplicación y una suma, ya que
Evaluación de poderes
Un tipo de polinomio particularmente interesante son las potencias como . Tales polinomios siempre se pueden calcular enoperaciones. Supongamos, por ejemplo, que necesitamos calcular; simplemente podríamos empezar con y multiplicar por Llegar . Luego podemos multiplicar eso por sí mismo para obtener y así sucesivamente para conseguir y en solo cuatro multiplicaciones. Otros poderes como se puede calcular de manera similar de manera eficiente mediante el primer cálculo por 2 multiplicaciones y luego multiplicar por .
La forma más eficiente de calcular una potencia determinada es proporcionada por la exponenciación de la cadena de adición. Sin embargo, esto requiere diseñar un algoritmo específico para cada exponente, y el cálculo necesario para diseñar estos algoritmos es difícil ( NP-completo ). Por lo tanto, generalmente se prefiere la exponenciación mediante el cuadrado para cálculos efectivos.
Familias polinomiales
A menudo, los polinomios aparecen en una forma diferente a la conocida . Para polinomios en forma de Chebyshev , podemos usar el algoritmo de Clenshaw . Para polinomios en forma Bézier podemos usar el algoritmo de De Casteljau , y para B-splines existe el algoritmo de De Boor .
Polinomios duros
El hecho de que algunos polinomios se puedan calcular significativamente más rápido que los "polinomios generales" sugiere la pregunta: ¿Podemos dar un ejemplo de un polinomio simple que no se puede calcular en un tiempo mucho menor que su grado? Strassen [7] ha demostrado que el polinomio
no puede ser evaluado por con menos de multiplicaciones y adiciones. Al menos este límite se mantiene si solo se permiten operaciones de esos tipos, dando lugar a la llamada "cadena polinomial de longitud".
El polinomio dado por Strassen tiene coeficientes muy grandes, pero por métodos probabilísticos, se puede demostrar que deben existir incluso polinomios con coeficientes de solo 0 y 1 de modo que la evaluación requiera al menos multiplicaciones. [8]
Para otros polinomios simples, se desconoce la complejidad. El polinomio se conjetura que no es computable en el tiempo para cualquier . Esto está respaldado por el hecho de que si se puede calcular rápidamente, la factorización de enteros se puede calcular en tiempo polinomial, rompiendo el criptosistema RSA . [9]
Polinomios matriciales
A veces, el costo computacional de las multiplicaciones escalares (como ) es menor que el costo computacional de las multiplicaciones "no escalares" (como ). El ejemplo típico de esto son las matrices. Si es un matriz, una multiplicación escalar toma sobre operaciones aritméticas, mientras se calcula toma sobre (o utilizando la multiplicación de matrices rápida ).
Los polinomios matriciales son importantes, por ejemplo, para calcular la matriz exponencial .
Paterson y Stockmeyer [10] mostraron cómo calcular un grado polinomio usando solo multiplicaciones no escalares y multiplicaciones escalares. Por tanto, un polinomio matricial de grado n puede evaluarse enhora. Si esto es menos que es decir, más rápido que una única multiplicación de matrices con el algoritmo estándar.
Este método funciona de la siguiente manera: para un polinomio
sea k el menor número entero no menor que Los poderes se calculan con multiplicaciones de matrices, y luego se calculan mediante multiplicación repetida por Ahora,
- ,
dónde para i ≥ n . Esto requiere solo más multiplicaciones no escalares.
Podemos escribir esto sucintamente usando el producto Kronecker :
- .
Ver también
- El esquema de Estrin para facilitar la paralelización en arquitecturas informáticas modernas
- La teoría de la complejidad de los circuitos aritméticos estudia la complejidad computacional de evaluar diferentes polinomios.
Referencias
- ^ Carnicer, J .; Gasca, M. (1990). "Evaluación de polinomios multivariados y sus derivadas" . Matemáticas de la Computación . 54 (189): 231–243. doi : 10.2307 / 2008692 .
- ^ Motzkin, TS (1955). "Evaluación de polinomios y evaluación de funciones racionales". Boletín de la American Mathematical Society . 61 (163): 10.
- ^ Von Zur Gathen, Joachim ; Jürgen, Gerhard (2013). Álgebra informática moderna . Prensa de la Universidad de Cambridge . Capítulo 10. ISBN 9781139856065.
- ^ Knuth, Donald (2005). Arte de la programación informática . Volumen 2: Algoritmos seminuméricos. Addison-Wesley . ISBN 9780201853926.
|volume=
tiene texto extra ( ayuda ) - ^ Kedlaya, Kiran S .; Umans, Christopher (2011). "Factorización rápida de polinomios y composición modular". Revista SIAM de Computación . 40 (6): 1767–1802. doi : 10.1137 / 08073408x . hdl : 1721,1 / 71792 .
- ^ Larsen, KG (2012). "Límites inferiores de sonda de celda superior para evaluar polinomios". Simposio sobre Fundamentos de la Informática . IEEE . 53 : 293-301. doi : 10.1109 / FOCS.2012.21 .
- ^ Strassen, Volker (1974). "Polinomios con coeficientes racionales que son difíciles de calcular". Revista SIAM de Computación . 3 (2): 128-149. doi : 10.1137 / 0203010 .
- ^ Schnorr, CP (1979), "Sobre la complejidad aditiva de los polinomios y algunos nuevos límites inferiores", Theoretical Computer Science , Springer , 67 , pp. 286-297, doi : 10.1007 / 3-540-09118-1_30
- ^ Chen, Xi, Neeraj Kayal y Avi Wigderson. Derivadas parciales en complejidad aritmética y más. Now Publishers Inc, 2011.
- ^ Paterson, Michael S .; Stockmeyer, Larry J. (1973). "Sobre el número de multiplicaciones no escalares necesarias para evaluar polinomios". Revista SIAM de Computación . 2 (1): 60–66. doi : 10.1137 / 0202007 .