Lokal ein Polynom invertieren

20

Herausforderung

Bei einem Polynom pmit reellen Koeffizienten der Ordnung 1und der Grad n, finden ein anderes Polynom qvom Grad höchstens nso dass (p∘q)(X) = p(q(X)) ≡ X mod X^(n+1), oder mit anderen Worten, dass , p(q(X)) = X + h(X)wo hein beliebiges Polynom mit ord(h) ≥ n+1. Das Polynom qwird eindeutig bestimmt durch p.

Für ein Polynom , p(X) = a(n)*X^n + a(n+1)*X^(n+1) + ... + a(m)*X^mwo n <= mund a(n) ≠ 0, a(m) ≠ 0sagen wir, nist die Reihenfolge der pund mist der Grad der p.

Vereinfachung : Sie können davon ausgehen, dass pes ganzzahlige Koeffizienten gibt, und a(1)=1(so p(X) = X + [some integral polynomial of order 2]). In diesem Fall qhat auch Integralkoeffizienten.

Der Zweck dieser Vereinfachung besteht darin, die Probleme mit Gleitkommazahlen zu vermeiden. Es gibt jedoch ein nicht einstückiges Beispiel zu Illustrationszwecken.

Beispiele

  • Betrachten Sie die Taylor-Reihe von exp(x)-1 = x + x^2/2 + x^3/6 + x^4/24 + ...und ln(x+1) = x - x^2/2 + x^3/3 - x^4/4 + ...dann offensichtlich ln(exp(x)-1+1)= x. Betrachtet man nur die Taylor-Polynome vom Grad 4 dieser beiden Funktionen, so erhält man die Notation von unten (siehe Testfälle) p = [-1/4,1/3,-1/2,1,0]und q = [1/24, 1/6, 1/2, 1,0]und(p∘q)(X) ≡ X mod X^5

  • Betrachten Sie das Polynom p(X) = X + X^2 + X^3 + X^4. Dann q(X) = X - X^2 + X^3 - X^4bekommen wir

    (p∘q)(X) = p(q(X)) = X - 2X^5 + 3X^6 - 10X^7 +...+ X^16 ≡ X mod X^5

Testfälle

Hier werden die Eingangs- und Ausgangspolynome als Koeffizientenlisten geschrieben (wobei der Koeffizient des Monoms höchsten Grades zuerst und der konstante Term zuletzt):

p = [4,3,2,0];  q=[0.3125,-.375,0.5,0]

Integrale Testfälle:

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]
code-golf math polynomials fehlerhaft
quelle

Antworten:

5

Python 2 + Sympy, 128 Bytes

Wir invertieren das Polynom lokal, indem wir q (x) = x annehmen, es mit p zusammensetzen, den Koeffizienten für x 2 prüfen und es von q subtrahieren. Angenommen, der Koeffizient war 4, dann wird das neue Polynom zu q (x) = x - 4x 2 . Wir setzen dies dann wieder mit p zusammen, aber suchen den Koeffizienten für x 3 . Etc...

from sympy import*
i=input()
p=Poly(i,var('x'));q=p*0+x
n=2
for _ in i[2:]:q-=compose(p,q).nth(n)*x**n;n+=1
print q.all_coeffs()
orlp
quelle
2

Mathematica, 45 Bytes

Normal@InverseSeries[#+O@x^(#~Exponent~x+1)]&

Ja, Mathematica hat eine eingebaute dafür ....

Unbenannte Funktion, die als Eingabe ein Polynom in der Variablen verwendet x, z. B. -x^4+3x^3-3x^2+xfür den letzten Testfall, und ein Polynom mit ähnlicher Syntax zurückgibt, z. B. x+3x^2+15x^3+91x^4für den letzten Testfall.

#+O@x^(#~Exponent~x+1)verwandelt die Eingabe #in ein Potenzreihenobjekt, abgeschnitten auf den Grad von #; InverseSeriestut was es sagt; und Normalverwandelt die resultierende abgeschnittene Potenzreihe wieder in ein Polynom. (Wir könnten diese anfänglichen 7 Bytes speichern, wenn eine Antwort in der Form x+3x^2+15x^3+91x^4+O[x]^5akzeptabel wäre. Wäre dies ein akzeptables Format sowohl für die Eingabe als auch für die Ausgabe, InverseSerieswäre dies allein eine 13-Byte-Lösung.)

Greg Martin
quelle
2

JavaScript (ES6), 138 Byte

a=>a.reduce((r,_,i)=>[...r,i<2?i:a.map(l=>c=p.map((m,j)=>(r.map((n,k)=>p[k+=j]=m*n+(p[k]||0)),m*l+(c[j]||0)),p=[]),c=[],p=[1])&&-c[i]],[])

Port von @orlps Antwort. E / A erfolgt in Form von Koeffizienten-Arrays in umgekehrter Reihenfolge, dh die ersten beiden Koeffizienten sind immer 0 und 1.

Neil
quelle