Gibt es eine vollständige Implementierung des Risch-Algorithmus?

Oct 15 2020

Gibt es eine allgemein verfügbare (kommerzielle oder nicht) vollständige Implementierung des Risch-Algorithmus, um festzustellen, ob eine Elementarfunktion ein Elementarantiderivativ hat?

Der Wikipedia-Artikel über symbolische Integration behauptet, dass der allgemeine Fall des Risch-Algorithmus von Manuel Bronstein in Axiom gelöst und implementiert wurde, und eine Antwort auf eine andere MO-Frage sagt dasselbe. Ich habe jedoch einige Zweifel, basierend auf dem folgenden Kommentar von Manuel Bronstein selbst in der USENET-Newsgroup sci.math.symbolicam 5. September 2003:

Wenn Axiom ein nicht bewertetes Integral zurückgibt, hat es bewiesen, dass kein elementares Antiderivativ existiert. Es gibt jedoch einige Fälle, in denen Axiom eine Fehlermeldung zurückgeben kann, die besagt, dass Sie einen nicht implementierten Zweig des Algorithmus getroffen haben. In diesem Fall kann er nicht abgeschlossen werden. Richard hat also zu Recht darauf hingewiesen, dass der Risch-Algorithmus auch dort nicht vollständig implementiert ist. Axiom ist einzigartig darin, den Unterschied zwischen nicht implementierten Zweigen und Beweisen der Nichtintegrierbarkeit zu machen und auch die algebraische Unabhängigkeit der Bausteine des Integranden vor dem Abschluss der Nichtintegrierbarkeit tatsächlich zu beweisen (andere nehmen diese Unabhängigkeit normalerweise nach Durchführung einer heuristischen Abhängigkeitsprüfung an).

Bronstein ist leider am 6. Juni 2005 verstorben . Es ist möglich, dass er die Implementierung abgeschlossen hat, bevor er starb, aber ich konnte das nicht bestätigen. Ich weiß, dass Bronstein es nie geschafft hat, sein beabsichtigtes Buch über die Integration algebraischer Funktionen fertigzustellen. [ EDIT: Als weitere Überprüfung habe ich Barry Trager eine E-Mail geschickt. Er bestätigte, dass die Implementierung, an der er und Bronstein arbeiteten, nicht vollständig war. Er wusste nicht viel über andere Implementierungen, kannte jedoch keine vollständigen Implementierungen.]

Ich habe Zugriff auf Maple 2018 und es scheint auch keine vollständige Implementierung zu haben. Ein nützlicher Testfall ist das folgende Integral, das aus dem (anscheinend unveröffentlichten) Trager-Algorithmus für die Integration algebraischer Funktionen von Daniel Schultz stammt:$$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz liefert in seiner Arbeit ausdrücklich ein elementares Antiderivativ, aber Maple 2018 gibt das Integral unbewertet zurück.

Antworten

20 SamBlake Oct 15 2020 at 08:43

Kein Computeralgebrasystem implementiert einen vollständigen Entscheidungsprozess für die Integration gemischter transzendentaler und algebraischer Funktionen.

Das Integral aus dem hervorragenden Papier von Schultz kann von Maple gelöst werden, wenn Sie den Integranden in die RootOf-Notation konvertieren (Warum dies in Maple nicht intern erfolgt, ist eine interessante Frage?)

int(convert((29*x^2+18*x-3)/(x^6+4*x^5+6*x^4-12*x^3+33*x^2-16*x)^(1/2),RootOf),x);

Meine Experimente legen nahe, dass Maple die beste Implementierung des Risch-Trager-Bronstein-Algorithmus für die Integration rein algebraischer Integrale in Bezug auf Elementarfunktionen hat (siehe Tabelle 1, Abschnitt 3 von Sam Blake, Eine einfache Methode zur Berechnung einiger pseudoelliptischer Integrale in Bezug auf elementare Funktionen , arXiv: 2004.04910 ). Die Implementierung von Maple integriert jedoch keine Ausdrücke, die Parameter oder verschachtelte Radikale enthalten (beide werden in AXIOM und FriCAS unterstützt).

Es scheint, dass Miller bei der Berechnung des logarithmischen Teils eines gemischten transzendental-algebraischen Integrals einige bedeutende Fortschritte erzielt hat [1]. Soweit ich weiß, hat jedoch kein Computeralgebrasystem seinen Algorithmus implementiert. Es ist auch nicht klar, ob Millers Algorithmus mit Parametern umgehen kann, zum Beispiel hat der Risch-Trager-Bronstein-Algorithmus Schwierigkeiten mit dem folgenden pseudoelliptischen Integral

$$\int\frac{\left(p x^2-q\right) \left(p x^2-x+q\right)dx}{x \left(p x^2+2 x+q\right) \sqrt{2 p^2x^4+2 p x^3+(4 p q+1) x^2+2 q x+2 q^2}} = - \frac{1}{\sqrt{2}}\log (x) + \frac{1}{\sqrt{2}}\log \left(\sqrt{2} y +2 p x^2+x+2q\right) - \frac{3}{\sqrt{5}}\tanh ^{-1}\left(\frac{\sqrt{5} y}{3 p x^2+3 q+x}\right),$$ wo $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. Meine Heuristik in dem zuvor verknüpften Artikel berechnet dieses Integral schnell mit der Substitution$u=\frac{px^2+q}{p x}$.

In Bezug auf den gemischten algebraisch-transzendentalen Fall des Risch-Trager-Bronstein-Algorithmus ist ein Integral, das mit Maple, Mathematica, AXIOM oder FriCAS (und möglicherweise anderem CAS) nicht gelöst werden kann

$$\int \frac{\left(\sqrt{x}+1\right) \left(e^{2x \sqrt{x}} -a\right) \sqrt{a^2+2 a x e^{2 \sqrt{x}} +cx e^{2 \sqrt{x}} +x^2 e^{4 \sqrt{x}}}}{x \sqrt{x}e^{\sqrt{x}} \left(a+x e^{2 \sqrt{x}} \right)} dx.$$

Dieses Integral ist interessant, da es zwei unterschiedliche Nachrichten von AXIOM und FriCAS zurückgibt, die darauf hinweisen, dass ihre jeweiligen Implementierungen unvollständig sind. FriCAS kehrt zurück

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:                                                               
   integrate: implementation incomplete (has polynomial part)

Während AXIOM zurückkehrt

(1) -> integrate(((-a+exp(2*x^(1/2))*x)*x^(-3/2)*(1+x^(1/2))*(a^2+2*a*exp(2*x^(1/2))*x+c*exp(2*x^(1/2))*x+exp(4*x^(1/2))*x^2)^(1/2))/(exp(x^(1/2))*(a+exp(2*x^(1/2))*x)),x)
                                                                                                        
   >> Error detected within library code:
   integrate: implementation incomplete (constant residues)

[1] Miller, B. (2012). " Zur Integration elementarer Funktionen: Berechnung des logarithmischen Teils ". Diplomarbeit (Ph.D.) Texas Tech University, Fakultät für Mathematik und Statistik.

12 DimaPasechnik Oct 15 2020 at 20:11

Fricas , ein Open-Source-Klon von Axiom, implementiert einen beträchtlichen Teil von Rischhttp://fricas-wiki.math.uni.wroc.pl/RischImplementationStatus