Calcular los coeficientes de la serie de potencia

24

Dado un polinomio p(x)con coeficientes integrales y un término constante de p(0) = 1 or -1, y un entero no negativo N, devuelve el Ncoeficiente enésimo del seris de potencia (a veces llamado "serie de Taylor") de f(x) = 1/p(x)desarrollado en x0 = 0, es decir, el coeficiente del monomio de grado N.

Las condiciones dadas aseguran que la serie de potencias exista y que sus coeficientes sean enteros.

Detalles

Como siempre, el polinomio puede aceptarse en cualquier formato conveniente, por ejemplo, una lista de coeficientes, por ejemplo, p(x) = x^3-2x+5podría representarse como [1,0,-2,5].

La serie de poderes de una función fdesarrollada en 0está dada por

y el Nenésimo coeficiente (el coeficiente de x^N) viene dado por

donde denota la nenésima derivada def

Ejemplos

  • El polinomio p(x) = 1-xda como resultado la serie geométrica, f(x) = 1 + x + x^2 + ...por lo que la salida debería ser 1para todos N.

  • p(x) = (1-x)^2 = x^2 - 2x + 1da como resultado la derivada de la serie geométrica f(x) = 1 + 2x + 3x^2 + 4x^3 + ..., por lo que la salida para Nes N+1.

  • p(x) = 1 - x - x^2 da como resultado la función generadora de la secuencia de Fibonacci f(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...

  • p(x) = 1 - x^2da como resultado la función generadora de 1,0,1,0,...ief(x) = 1 + x^2 + x^4 + x^6 + ...

  • p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3da como resultado la función generadora de los números triangulares f(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ...que significa que el Nenésimo coeficiente es el coeficiente binomial(N+2, N)

  • p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3 resultados en f(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + ...

falla
fuente
¿Sería aceptable tomar un polinomio como una lista infinita de coeficientes de series de potencia como [1,-1,0,0,0,0,...]?
xnor
Sí, creo que este es un formato aceptable.
flawr 01 de
Buenos ejemplos elegidos!
Greg Martin
Me alegro de que lo
aprecies

Respuestas:

9

Mathematica, 24 23 bytes

Guardado 1 byte gracias a Greg Martin

D[1/#2,{x,#}]/#!/.x->0&

Función pura con dos argumentos #y #2. Asume que el polinomio #2satisface PolynomialQ[#2,x]. Por supuesto, hay una función incorporada para esto:

SeriesCoefficient[1/#2,{x,0,#}]&
ngenisis
fuente
1
¡Bien hecho, superando al incorporado! Supongo que puede guardar un byte suponiendo que #es el entero Ny #2el polinomio.
Greg Martin
6

Matlab, 81 79 75 bytes

A diferencia de las dos respuestas anteriores, esto no hace uso de cálculos simbólicos. La idea es que puede calcular iterativamente los coeficientes:

function C=f(p,N);s=p(end);for k=1:N;q=conv(p,s);s=[-q(end-k),s];end;C=s(1)

Pruébalo en línea!

Explicación

function C=f(p,N);
s=p(end);            % get the first (constant coefficient)
for k=1:N;           
    q=conv(p,s);     % multiply the known coefficients with the polynomial
    s=[-q(end-k),s]; % determine the new coefficient to make the the product get "closer" 
end;
C=s(1)           % output the N-th coefficient
falla
fuente
4

GeoGebra , 28 bytes

Derivative[1/A1,B1]/B1!
f(0)

La entrada se toma de las celdas A1 y B1 de la hoja de cálculo de un polinomio y un número entero respectivamente, y cada línea se ingresa por separado en la barra de entrada. La salida es por asignación a la variable a.

Aquí hay un gif que muestra la ejecución:

Coeficientes de Taylor

Usar builtins es mucho más largo, a 48 bytes:

First[Coefficients[TaylorPolynomial[1/A1,0,B1]]]
TheBikingViking
fuente
4

Haskell, 44 bytes

p%n=(0^n-sum[p!!i*p%(n-i)|i<-[1..n]])/head p

Un cálculo directo sin incorporaciones algebraicas. Toma de entrada como una lista infinita de coeficientes de series de potencias, como p = [1,-2,3,0,0,0,0...](es decir p = [1,-2,3] ++ repeat 0) para 1-2*x+x^2. Llámalo como p%3, que da -4.0.

La idea es que si p es un polinomio y q = 1 / p es inverso, entonces podemos expresar la igualdad p · q = 1 término por término. El coeficiente de x n en p · q es dada por la convolución de los coeficientes de p y q :

p 0 · q n + p 1 · q n-1 + ... + p n · q 0

Para que p · q = 1 se mantenga, lo anterior debe ser igual a cero para todo n> 0 . Por aquí, podemos expresar q n recursivamente en términos de q 0 , ..., q n-1 y los coeficientes de p .

q n = - 1 / p 0 · (p 1 · q n-1 + ... + p n · q 0 )

Esto es exactamente lo que se calcula en la expresión sum[p!!i*p%(n-i)|i<-[1..n]]/head p, con head pel coeficiente principal p 0 . El coeficiente inicial q 0 = 1 / p 0 se maneja aritméticamente en la misma expresión usando 0^ncomo indicador para n==0.

xnor
fuente
3

J, 12 bytes

1 :'(1%u)t.'

Utiliza el adverbio t.que toma un polinomio pen forma de verbo en el LHS y un entero no negativo ken el RHS y calcula el coeficiente kth de la serie Taylor de pat x = 0. Para obtener la serie de potencia, pse toma el recíproco de antes de aplicarlo.

Pruébalo en línea!

millas
fuente
2

Arce, 58 26 bytes

Esta es una función sin nombre que acepta un polinomio xy un entero N.

EDITAR: acabo de notar que hay un incorporado:

(p,N)->coeftayl(1/p,x=0,N)
falla
fuente
1

MATL , 19 bytes

0)i:"1GY+@_)_8Mh]1)

Traducción de la gran respuesta de Matlab de @flawr .

Pruébalo en línea!

Cómo funciona

0)      % Implicitly input vector of polynomial coefficients and get last entry
i       % Input N
:"      % For k in [1 2 ... N]
  1G    %   Push vector of polynomial coefficients
  Y+    %   Convolution, full size
  @     %   Push k
  _     %   Negate
  )     %   Index. This produces the end-k coefficient
  _     %   Negate
  8M    %   Push first input of the latest convolution
  h     %   Concatenate horizontally
]       % End
1)      % Get first entry. Implicitly display
Luis Mendo
fuente
1

JavaScript (ES6), 57 bytes

(a,n)=>a.reduce((s,p,i)=>!i|i>n?s:s-p*f(a,n-i),!n)/a[0]

La respuesta del puerto de Haskell de @xnor. Originalmente probé una versión iterativa, pero resultó ser de 98 bytes, sin embargo, será mucho más rápido para N grande, ya que estoy recordando efectivamente las llamadas recursivas:

(a,n)=>[...Array(n+1)].fill(0).map((_,i,r)=>r[i]=r.reduce((s,p,j)=>s-p*(a[i-j]||0),!i)/a[0]).pop()

n+1se requieren términos, que se guardan en la matriz r. Inicialmente, son ceros lo que permite reducir toda la matriz rde una vez, ya que los ceros no afectarán el resultado. El último coeficiente calculado es el resultado final.

Neil
fuente
1

PARI / GP, 31 27 bytes

f->n->Pol(Ser(1/f,,n+1))\x^n
alephalpha
fuente