Desafío
Dado un polinomio p
con coeficientes reales de orden 1
y grado n
, encontrar otro polinomio q
de grado a lo sumo n
de tal manera que (p∘q)(X) = p(q(X)) ≡ X mod X^(n+1)
, o dicho de otro modo tal que p(q(X)) = X + h(X)
cuando h
es un polinomio arbitrario con ord(h) ≥ n+1
. El polinomio q
está determinado únicamente por p
.
Para un polinomio p(X) = a(n)*X^n + a(n+1)*X^(n+1) + ... + a(m)*X^m
donde n <= m
y a(n) ≠ 0
, a(m) ≠ 0
decimos que n
es el orden de p
y m
es el grado de p
.
Simplificación : puede suponer que p
tiene coeficientes enteros, y a(1)=1
(entonces p(X) = X + [some integral polynomial of order 2]
). En este caso también q
tiene coeficientes integrales.
El propósito de esta simplificación es evitar los problemas con los números de coma flotante. Sin embargo, existe un ejemplo no integral con fines ilustrativos.
Ejemplos
- Considere la serie de Taylor
exp(x)-1 = x + x^2/2 + x^3/6 + x^4/24 + ...
yln(x+1) = x - x^2/2 + x^3/3 - x^4/4 + ...
luego, obviamenteln(exp(x)-1+1)= x
. Si sólo consideramos los polinomios de Taylor de grado 4 de esas dos funciones que obtenemos con la anotación desde abajo (ver casos de prueba)p = [-1/4,1/3,-1/2,1,0]
yq = [1/24, 1/6, 1/2, 1,0]
y(p∘q)(X) ≡ X mod X^5
Considera el polinomio
p(X) = X + X^2 + X^3 + X^4
. Entonces paraq(X) = X - X^2 + X^3 - X^4
obtener(p∘q)(X) = p(q(X)) = X - 2X^5 + 3X^6 - 10X^7 +...+ X^16 ≡ X mod X^5
Casos de prueba
Aquí los polinomios de entrada y salida se escriben como listas de coeficientes (con el coeficiente del monomio de mayor grado primero, el término constante al final):
p = [4,3,2,0]; q=[0.3125,-.375,0.5,0]
Casos de prueba integrales:
p = [1,0]; q = [1,0]
p = [9,8,7,6,5,4,3,2,1,0]; q = [4862,-1430,429,-132,42,-14,5,-2,1,0]
p = [-1,3,-3,1,0]; q = [91,15,3,1,0]
fuente