¿Existe una implementación completa del algoritmo de Risch?

Oct 15 2020

¿Existe una implementación completa generalmente disponible (comercial o no) del algoritmo de Risch para determinar si una función elemental tiene una antiderivada elemental?

El artículo de Wikipedia sobre integración simbólica afirma que el caso general del algoritmo de Risch fue resuelto e implementado en Axiom por Manuel Bronstein, y una respuesta a otra pregunta de MO dice lo mismo. Sin embargo, tengo algunas dudas, basadas en el siguiente comentario del propio Manuel Bronstein en el grupo de noticias USENET sci.math.symbolicel 5 de septiembre de 2003:

Si Axiom devuelve una integral no evaluada, entonces se ha demostrado que no existe una antiderivada elemental. Sin embargo, hay algunos casos en los que Axiom puede devolver un mensaje de error que indica que ha llegado a una rama no implementada del algoritmo, en cuyo caso no puede concluir. Así que Richard tenía razón al señalar que el algoritmo de Risch tampoco está completamente implementado allí. Axiom es único en hacer la diferencia entre ramas no implementadas y pruebas de no integrabilidad, y también en probar realmente la independencia algebraica de los bloques de construcción del integrando antes de concluir la no integrabilidad (otros típicamente asumen esta independencia después de realizar alguna verificación de dependencia heurística).

Bronstein lamentablemente falleció el 6 de junio de 2005 . Es posible que haya completado la implementación antes de morir, pero no he podido confirmarlo. Sé que Bronstein nunca logró terminar su libro sobre la integración de funciones algebraicas. [ EDITAR: Como verificación adicional, le envié un correo electrónico a Barry Trager. Confirmó que la implementación en la que él y Bronstein trabajaron no estaba completa. No sabía mucho sobre otras implementaciones, pero no conocía ninguna implementación completa.]

Tengo acceso a Maple 2018 y tampoco parece tener una implementación completa. Un caso de prueba útil es la siguiente integral, tomada del artículo (aparentemente inédito) del algoritmo de Trager para la integración de funciones algebraicas revisado por Daniel Schultz:$$\int \frac{29x^2+18x-3}{\sqrt{x^6+4x^5+6x^4-12x^3+33x^2-16x}}\,dx$$ Schultz proporciona explícitamente una antiderivada elemental en su artículo, pero Maple 2018 devuelve la integral sin evaluar.

Respuestas

20 SamBlake Oct 15 2020 at 08:43

Ningún sistema de álgebra por computadora implementa un proceso de decisión completo para la integración de funciones trascendentales y algebraicas mixtas.

La integral del excelente artículo de Schultz puede ser resuelta por Maple si convierte el integrando a la notación RootOf (¿Por qué esto no se hace internamente en Maple es una pregunta interesante?)

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

Mis experimentos sugieren que Maple tiene la mejor implementación del algoritmo de Risch-Trager-Bronstein para la integración de integrales puramente algebraicas en términos de funciones elementales (ref: tabla 1, sección 3 de Sam Blake, A Simple Method for Computing Some Pseudo-Elliptic Integrals en términos de funciones elementales , arXiv: 2004.04910 ). Sin embargo, la implementación de Maple no integra expresiones que contengan parámetros o radicales anidados (ambos tienen algún soporte en AXIOM y FriCAS).

Parecería que se ha logrado algún progreso significativo en el cálculo de la parte logarítmica de una integral mixta trascendental-algebraica por Miller [1]. Aunque, hasta donde yo sé, ningún sistema de álgebra computacional ha implementado su algoritmo. Tampoco está claro si el algoritmo de Miller puede manejar parámetros, por ejemplo, el algoritmo de Risch-Trager-Bronstein tiene dificultades con la siguiente integral pseudoelíptica

$$\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),$$ dónde $y=\sqrt{2 p^2 x^4+2 p x^3+(4 pq+1)x^2+2 q x+2 q^2}$. Mi heurística en el artículo vinculado anteriormente calcula esta integral rápidamente con la sustitución$u=\frac{px^2+q}{p x}$.

En lo que respecta al caso mixto algebraico-trascendental del algoritmo de Risch-Trager-Bronstein, una integral que no se puede resolver con Maple, Mathematica, AXIOM o FriCAS (y posiblemente otro CAS) es

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

Esta integral es interesante ya que devuelve dos mensajes distintos de AXIOM y FriCAS sugiriendo que sus respectivas implementaciones están incompletas. Vuelve 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)

Mientras AXIOM regresa

(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). “ Sobre la integración de funciones elementales: cálculo de la parte logarítmica ”. Tesis (Ph.D.) Texas Tech University, Departamento de Matemáticas y Estadística.

12 DimaPasechnik Oct 15 2020 at 20:11

Fricas , un clon de código abierto de Axiom, implementa una parte considerable de Risch, verhttp://fricas-wiki.math.uni.wroc.pl/RischImplementationStatus