El polinomio de cambio

Question

Supongamos que existe un polinomio:

$p(x) = a_0x^n + a_1x^{n-1} + ... + a_{n-1}x + a_{n}$

Me gustaría "shift" (no estoy seguro de cuál es el término correcto), sustituyendo $x$ para alguna otra función de $x$.

Lo que quiero decir es que me gustaría para "transformar" el polinomio mediante la sustitución de la $x$$x+1$, por ejemplo:

$p(x) = a_0(x+1)^n + a_1(x+1)^{n-1} + ... + a_{n-1}(x+1) + a_{n}$

Yo podría hacerlo mediante la expansión de cada término y, a continuación, la suma de los términos de la misma orden. Por ejemplo:

$x^2 - 1$ ---> $(x+1)^2 - 1$ ---> $(x^2 + 2x + 1) - 1$ ---> $x^2 + 2x$

Mi pregunta es, es posible hacer dicha transformación "rápidamente"? Actualmente tengo a ampliar cada término, agregar a cada uno de sus elementos al elemento anterior del mismo grado y así sucesivamente. No hay un truco que a su vez, el coeficientes de $[1, 0, -1]$ a $[1, 2, 0]$ en una sola vez?

Si había un truco para que el anterior $x+1$ de sustitución, hay trucos similares para otros, demasiado? Por ejemplo,$1/x$? Hay un método general de construcción de algún tipo de sustitución que convierte a un conjunto de coeficientes en uno de otro?

Answer 1

Esto es comúnmente referido como un "Taylor shift", por la razón ya citado. Por desgracia, una búsqueda en la web normalmente revela manera más resultados para "Taylor Swift"...
[editar]curiosamente, este se mantiene incluso después de que usted haga clic en "Buscar lugar para taylor shift" en Google. Por otro lado, por ahora esta respuesta muy anotó #1 para la consulta "taylor shift polinomio". Sin embargo, "taylor swift polinomio" te lleva a la "Polinomio de Taylor de la Serie de la fórmula" en la Uncyclopedia, que se describe como "Un País Occidental de la fórmula musical inventado por Taylor Swift", así como los Polinomios de la Canción, una parodia de Taylor Swift "Todo ha Cambiado". Bueno, plus ça change, plus c'est la même chose...[/edit]

Hay un breve estudio de la complejidad de los resultados para Taylor cambios en el capítulo 4 de Jürgen Gerhard del Modular de los Algoritmos en la Simbólica Suma y la Integración Simbólica (Springer, Lecture Notes in Computer Science, Vol. 3218, 2004; DOI: 10.1007/b104035), con enlaces a los artículos originales de investigación. También, busque en los libros de texto de Álgebra computacional; buenas palabras de moda son "Taylor shift", "rápido polinomio de división con resto y aplicaciones", y "basado en FFT polinomio multipunto de evaluación y de interpolación".

Línea de base: el Uso de, por ejemplo, un divide y vencerás enfoque, usted puede ahorrar aproximadamente un orden de magnitud (es decir, $n$). Que trae el costo a $\tilde O(n)$ aritmética de las operaciones en el coeficiente de anillo, donde polylogarithmic factores son ignorados. Tenga en cuenta que estas son las operaciones aritméticas; el bit de complejidad será mayor por un factor de $n$ y, obviamente, también dependerá del tamaño (magnitud y/o de precisión) de la entrada.

El rápido algoritmos son, conceptualmente, no demasiado. Pero requieren de un buen número de asintóticamente rápido subrutinas para el polinomio aritmético, así que no es para los débiles de corazón. Y cuando se trata de una aplicación real: que bien podría ser una forma totalmente diferente de la bestia. El ingenuo algoritmo funciona bastante bien para los bajos grados; el rendimiento de la rápida algoritmos depende de manera crucial de la implementación subyacente de rápido polinomio aritmético. Es decir, no hacerlo por su cuenta, pero mira por las bibliotecas como Víctor Shoup del NTL, William Hart FLINT, Fredrik Johansson Arb, Andreas Engel del MPFRCX, o de un adulto sistema de álgebra computacional.
También, si usted está interesado sólo en los cambios por 1 ($x \mapsto x+1$), el esquema de Horner-como el de Taylor cambio debe ser de multiplicación -, que se eleva significativamente el umbral cuando asintóticamente métodos rápidos tomar la iniciativa.

[editar] se me olvidó mencionar: si sustituye $1/x$$x$, usted termina con una función racional. Pero es posible que desee obtener $q(x) = x^n p(1/x)$, y esto es simplemente el polinomio con coeficientes en orden inverso, es decir,$q_i = p_{n-i}$. También, de una escala ($x \mapsto s\cdot x$) es bastante fácil de lograr: sólo la escala de la $i$-ésimo coeficiente por $s^i$. Esto es especialmente barato si $s$ es una potencia de dos (y, por lo tanto, la multiplicación es sólo un bitshift). Para una combinación lineal arbitraria $x \mapsto a\cdot x+b$ o Mobius transformar $x \mapsto \frac{a\cdot x +b}{c\cdot x + d}$, descompone en pasos más simples. Para un mayor orden de la composición (es decir, calcular los $(f \circ g)(x) = g(f(x))$, donde ambos se $f$ $g$ son no-lineal de polinomios), probablemente debería mirar a multipunto de evaluación - y la interpolación basada en algoritmos.

Answer 2

Sí, los hay. El truco está en expansión de Taylor. Si quieres cambio $p(x)=x^2-1$$p(x+1)$, luego tomar la expansión de Taylor en el punto de $x-1$$\Delta x=x-(x-1)=1$. $$\begin{align}p(x)&=p(x-1)+p'(x-1)\Delta x+\frac12p''(x-1)\Delta x^2\\&=(x-1)^2-1+2(x-1)+1\\&=(x-1)^2+2(x-1)\end{align}$$ No se expanden. Sólo reemplace$x$$x+1$, tenemos $$p(x+1)=x^2+2x$$

Nota: este truco solo es válido para funciones analíticas (tal vez no?). Pero creo que ser más rápido que la sustitución sólo para polinomios, ya que su expansión de Taylor ha finito de orden y de la manera más fácil de calcular la derivada.

Answer 3

Por supuesto, la expansión de Taylor, por ejemplo mediante la aplicación repetida de la Horner esquema, es casi tan rápido como de forma iterativa la expansión de los binomios y la adición de ellos con los coeficientes, que se requiere de $O(n^2)$ operaciones.

Schönhage propuesto un método más rápido el uso de la FFT métodos (entero o punto flotante), basadas en el binomio de expansión

$$\sum a_k(x+h)^k=\sum_j\left(\sum_k (k!\,a_k)\frac{h^{k-j}}{(k-j)!}\right)\frac{x^{j}}{j!}$$

donde el interior de la suma puede ser interpretado como parte de un producto de convolución de las secuencias de $(n!\,a_n,(n-1)!\,a_{n-1},...3!\,a_3,2!\,a_2, a_1, a_0)$$(1,h,\frac{h^2}{2!},\frac{h^3}{3!},...,\frac{h^n}{n!})$.