Existe-t-il une implémentation complète de l'algorithme de Risch?

Oct 15 2020

Existe-t-il une implémentation complète (commerciale ou non) généralement disponible de l'algorithme de Risch pour déterminer si une fonction élémentaire a une primitive élémentaire?

L' article de Wikipedia sur l'intégration symbolique affirme que le cas général de l'algorithme de Risch a été résolu et implémenté dans Axiom par Manuel Bronstein, et une réponse à une autre question MO dit la même chose. Cependant, j'ai quelques doutes, sur la base du commentaire suivant de Manuel Bronstein lui-même sur le groupe sci.math.symbolicde discussion USENET le 5 septembre 2003:

Si Axiom renvoie une intégrale non évaluée, alors il a prouvé qu'aucune primitive élémentaire n'existe. Il existe cependant des cas où Axiom peut renvoyer un message d'erreur indiquant que vous avez atteint une branche non implémentée de l'algorithme, auquel cas il ne peut pas conclure. Richard avait donc raison de souligner que l'algorithme de Risch n'y est pas non plus pleinement implémenté. Axiom est unique pour faire la différence entre les branches non implémentées et les preuves de non-intégrabilité, et aussi pour prouver réellement l'indépendance algébrique des blocs de construction de l'intégrande avant de conclure à la non intégrabilité (d'autres supposent généralement cette indépendance après avoir effectué une vérification de dépendance heuristique).

Bronstein est malheureusement décédé le 6 juin 2005 . Il est possible qu'il ait terminé la mise en œuvre avant de mourir, mais je n'ai pas été en mesure de le confirmer. Je sais que Bronstein n'a jamais réussi à terminer son livre sur l'intégration des fonctions algébriques. [ EDIT: Comme vérification supplémentaire, j'ai envoyé un courriel à Barry Trager. Il a confirmé que la mise en œuvre sur laquelle lui et Bronstein avaient travaillé n'était pas complète. Il ne savait pas grand-chose des autres implémentations mais n’était pas au courant d’implémentations complètes.]

J'ai accès à Maple 2018, et il ne semble pas non plus avoir une implémentation complète. Un cas de test utile est l'intégrale suivante, tirée de l' algorithme de Trager (apparemment non publié) pour l'intégration de fonctions algébriques revisité par Daniel Schultz:$$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz fournit explicitement une primitive élémentaire dans son article, mais Maple 2018 renvoie l'intégrale non évaluée.

Réponses

20 SamBlake Oct 15 2020 at 08:43

Aucun système d'algèbre informatique ne met en œuvre un processus de décision complet pour l'intégration de fonctions mixtes transcendantales et algébriques.

L'intégrale de l'excellent article de Schultz peut être résolue par Maple si vous convertissez l'intégrale en notation RootOf (pourquoi cela n'est pas fait en interne dans Maple est une question intéressante?)

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);

Mes expériences suggèrent que Maple a la meilleure implémentation de l'algorithme Risch-Trager-Bronstein pour l'intégration d'intégrales purement algébriques en termes de fonctions élémentaires (ref: tableau 1, section 3 de Sam Blake, A Simple Method for Computing Some Pseudo-Elliptic Integrals en termes de fonctions élémentaires , arXiv: 2004.04910 ). Cependant, l'implémentation de Maple n'intègre pas d'expressions contenant des paramètres ou des radicaux imbriqués (qui ont tous deux un certain support dans AXIOM et FriCAS).

Il semblerait que des progrès significatifs aient été réalisés dans le calcul de la partie logarithmique d'une intégrale mixte transcendantale-algébrique par Miller [1]. Cependant, pour autant que je sache, aucun système d'algèbre informatique n'a implémenté son algorithme. On ne sait pas non plus si l'algorithme de Miller peut traiter des paramètres, par exemple, l'algorithme de Risch-Trager-Bronstein a des difficultés avec l'intégrale pseudo-elliptique suivante

$$\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),$$ où $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. Mon heuristique dans l'article précédemment lié calcule cette intégrale rapidement avec la substitution$u=\frac{px^2+q}{p x}$.

En ce qui concerne le cas mixte algébrique-transcendantal de l'algorithme Risch-Trager-Bronstein, une intégrale qui ne peut pas être résolue avec Maple, Mathematica, AXIOM ou FriCAS (et éventuellement d'autres CAS) est

$$\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.$$

Cette intégrale est intéressante car elle renvoie deux messages distincts d'AXIOM et de FriCAS suggérant que leurs implémentations respectives sont incomplètes. Retours FriCAS

(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)

Alors que AXIOM revient

(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). « Sur l'intégration des fonctions élémentaires: calcul de la partie logarithmique ». Thèse (Ph.D.) Texas Tech University, Département de mathématiques et de statistique.