Algoritmo de Risch

En computación simbólica , el algoritmo de Risch es un método de integración indefinida que se utiliza en algunos sistemas de álgebra computacional para hallar antiderivadas . Recibe su nombre del matemático estadounidense Robert Henry Risch , especialista en álgebra computacional, quien lo desarrolló en 1968.

El algoritmo transforma el problema de la integración en un problema de álgebra . Se basa en la forma de la función que se integra y en métodos para integrar funciones racionales , radicales , logaritmos y funciones exponenciales . Risch lo denominó procedimiento de decisión , ya que es un método para determinar si una función tiene una integral indefinida como función elemental y, en caso afirmativo, para determinar dicha integral. Sin embargo, el algoritmo no siempre logra identificar si la antiderivada de una función dada puede expresarse en términos de funciones elementales. En concreto, el algoritmo no puede resolver el problema de la constante , que resulta indecidible cuando necesita determinar si una expresión de un número complejo arbitrario es igual a cero.

La descripción completa del algoritmo de Risch ocupa más de 100 páginas. ^{[ 1 ]} El algoritmo de Risch-Norman es una variante más simple, más rápida, pero menos potente que fue desarrollada en 1976 por Arthur Norman .

Brian L. Miller ha logrado avances significativos en el cálculo de la parte logarítmica de una integral mixta trascendental-algebraica. ^{[ 2 ]}

El algoritmo de Risch se utiliza para integrar funciones elementales . Estas funciones se obtienen componiendo exponenciales, logaritmos, radicales, funciones trigonométricas y las cuatro operaciones aritméticas ( + − × ÷ ). Laplace resolvió este problema para el caso de las funciones racionales , al demostrar que la integral indefinida de una función racional es la suma de dicha función y un número finito de múltiplos constantes de logaritmos de funciones racionales. El algoritmo propuesto por Laplace se describe habitualmente en los libros de texto de cálculo; finalmente, se implementó como programa informático en la década de 1960.

Liouville formuló el problema que resuelve el algoritmo de Risch. Liouville demostró por medios analíticos que si existe una solución elemental g para la ecuación g ′ = f, entonces existen constantes α _i y funciones u _i y v en el campo generado por f tales que la solución es de la forma

${\displaystyle g=v+\sum _{i<n}\alpha _{i}\ln(u_{i})}$

Risch desarrolló un método que permite considerar únicamente un conjunto finito de funciones de la forma de Liouville.

La intuición para el algoritmo de Risch proviene del comportamiento de las funciones exponencial y logarítmica bajo diferenciación. Para la función f e ^g , donde f y g son funciones diferenciables , tenemos

${\displaystyle \left(f\cdot e^{g}\right)^{\prime }=\left(f^{\prime }+f\cdot g^{\prime }\right)\cdot e^{g},\,}$

por lo tanto, si e ^g estuviera en el resultado de una integración indefinida, se esperaría que estuviera dentro de la integral. Además, como

${\displaystyle \left(f\cdot (\ln g)^{n}\right)^{\prime }=f^{\prime }\left(\ln g\right)^{n}+nf{\frac {g^{\prime }}{g}}\left(\ln g\right)^{n-1}}$

entonces, si (ln g ) ⁿ estuviera en el resultado de una integración, entonces solo se deberían esperar unas pocas potencias del logaritmo.

Encontrar una antiderivada elemental es muy sensible a los detalles. Por ejemplo, la siguiente función algebraica (publicada en sci.math.symbolic por Henri Cohen en 1993 ^{[ 3 ]} ) tiene una antiderivada elemental, como muestra Wolfram Mathematica desde la versión 13 (sin embargo, Mathematica no utiliza el algoritmo de Risch para calcular esta integral): ^{[ 4 ] [ 5 ]}

${\displaystyle f(x)={\frac {x}{\sqrt {x^{4}+10x^{2}-96x-71}}},}$

a saber:

${\displaystyle {\begin{aligned}F(x)=-{\frac {1}{8}}\ln &\,{\Big (}(x^{6}+15x^{4}-80x^{3}+27x^{2}-528x+781){\sqrt {x^{4}+10x^{2}-96x-71}}{\Big .}\\&{}-{\Big .}(x^{8}+20x^{6}-128x^{5}+54x^{4}-1408x^{3}+3124x^{2}+10001){\Big )}+C.\end{aligned}}}$

Pero si el término constante 71 se cambia a 72, no es posible representar la antiderivada en términos de funciones elementales, ^{[ 6 ]} como también muestra FriCAS . Algunos sistemas de álgebra computacional pueden devolver aquí una antiderivada en términos de funciones no elementales (es decir, integrales elípticas ), que están fuera del alcance del algoritmo de Risch. Por ejemplo, Mathematica devuelve un resultado con las funciones EllipticPi y EllipticF. Integrales en la forma${\displaystyle \int {\frac {x+A}{\sqrt {x^{4}+ax^{3}+bx^{2}+cx+d}}}\,dx}$fueron resueltos por Chebyshev (y en qué casos es elemental), ^{[ 7 ]} pero la prueba estricta para ello fue finalmente realizada por Zolotarev . ^{[ 6 ]}

El siguiente es un ejemplo más complejo que involucra funciones algebraicas y trascendentales : ^{[ 8 ]}

${\displaystyle f(x)={\frac {x^{2}+2x+1+(3x+1){\sqrt {x+\ln x}}}{x\,{\sqrt {x+\ln x}}\left(x+{\sqrt {x+\ln x}}\right)}}.}$

De hecho, la antiderivada de esta función tiene una forma bastante corta que se puede encontrar mediante sustitución. ${\displaystyle u=x+{\sqrt {x+\ln x}}}$( SymPy puede resolverlo, mientras que FriCAS falla con el error "implementación incompleta (residuos constantes)" en el algoritmo de Risch):

${\displaystyle F(x)=2\left({\sqrt {x+\ln x}}+\ln \left(x+{\sqrt {x+\ln x}}\right)\right)+C.}$

Algunos "teoremas" de Davenport aún se están aclarando. Por ejemplo, en 2020 se encontró un contraejemplo a uno de estos "teoremas", donde se demostró que, después de todo, existe una antiderivada elemental. ^{[ 9 ]}

Transformar el algoritmo teórico de Risch en un algoritmo que pudiera ser ejecutado eficazmente por un ordenador fue una tarea compleja que llevó mucho tiempo.

El caso de las funciones puramente trascendentales (que no involucran raíces de polinomios) es relativamente sencillo y se implementó tempranamente en la mayoría de los sistemas de álgebra computacional . La primera implementación la realizó Joel Moses en Macsyma poco después de la publicación del artículo de Risch. ^{[ 10 ]}

El caso de las funciones puramente algebraicas fue parcialmente resuelto e implementado en Reduce por James H. Davenport ; por simplicidad, solo podía manejar raíces cuadradas y raíces cuadradas repetidas, y no radicales generales u otras relaciones algebraicas no cuadráticas entre variables. ^{[ 11 ]}

El caso general fue resuelto e implementado casi por completo en Scratchpad, un precursor de Axiom , por Manuel Bronstein; existe una bifurcación de Axiom, FriCAS, con desarrollo activo de Risch y otros algoritmos en GitHub. ^{[ 12 ] [ 13 ]} Sin embargo, la implementación no incluyó completamente algunas de las ramas para casos especiales. ^{[ 14 ] [ 15 ]} A partir de 2025, no existe una implementación completa del algoritmo de Risch. ^{[ 16 ]}

El algoritmo de Risch aplicado a funciones elementales generales no es un algoritmo propiamente dicho, sino un semialgoritmo, ya que requiere comprobar, como parte de su funcionamiento, si ciertas expresiones son equivalentes a cero ( problema de la constante ), en particular en el cuerpo de las constantes. Para expresiones que involucran únicamente funciones comúnmente consideradas elementales , se desconoce si existe un algoritmo que realice dicha comprobación ( los sistemas actuales de álgebra computacional utilizan heurísticas); además, si se añade la función valor absoluto a la lista de funciones elementales, se sabe que no existe tal algoritmo; véase el teorema de Richardson .

Este problema también surge en el algoritmo de división de polinomios ; este algoritmo fallará si no puede determinar correctamente si los coeficientes se anulan idénticamente. ^{[ 17 ]} Prácticamente todos los algoritmos no triviales relacionados con polinomios utilizan el algoritmo de división de polinomios, incluido el algoritmo de Risch. Si el campo constante es computable , es decir, para elementos que no dependen de x , entonces el problema de la equivalencia cero es decidible, por lo que el algoritmo de Risch es un algoritmo completo. Ejemplos de campos constantes computables son ℚ y ℚ ( y ) , es decir, números racionales y funciones racionales en y con coeficientes de números racionales, respectivamente, donde y es una indeterminada que no depende de x .

Esto también representa un problema en el algoritmo de eliminación gaussiana de matrices (o en cualquier algoritmo que pueda calcular el espacio nulo de una matriz), el cual es necesario para muchas partes del algoritmo de Risch. La eliminación gaussiana producirá resultados incorrectos si no puede determinar correctamente si un pivote es idénticamente cero.

• Axioma (sistema de álgebra computacional)
• Expresión en forma cerrada
• Función gamma incompleta
• Listas de integrales
• Teorema de Liouville (álgebra diferencial)
• Integral no elemental
• Integración simbólica

• Bronstein, Manuel (1990). "Integración de funciones elementales". Journal of Symbolic Computation . 9 (2): 117– 173. doi : 10.1016/s0747-7171(08)80027-2 .

• Bronstein, Manuel (1998). "Tutorial de integración simbólica" (PDF) . ISSAC'98, Rostock (agosto de 1998) y Taller de álgebra diferencial, Rutgers .

• Bronstein, Manuel (2005). Integración simbólica I. Springer. ISBN 3-540-21493-3.

• Davenport, James H. (1981). Sobre la integración de funciones algebraicas . Lecture Notes in Computer Science . Vol.  102. Springer. ISBN 978-3-540-10290-8.

• Geddes, Keith O .; Czapor, Stephen R.; Labahn, George (1992). Algoritmos para álgebra computacional . Boston, MA: Kluwer Academic Publishers. pp.  xxii+585. Bibcode : 1992afca.book.....G . doi : 10.1007/b102438 . ISBN 0-7923-9259-0.

• Moses, Joel (2012). "Macsyma: Una historia personal". Journal of Symbolic Computation . 47 (2): 123– 130. doi : 10.1016/j.jsc.2010.08.018 .

• Risch, RH (1969). "El problema de la integración en términos finitos" . Transactions of the American Mathematical Society . 139. American Mathematical Society: 167–189 . doi : 10.2307/1995313 . JSTOR 1995313 . 

• Risch, RH (1970). "La solución del problema de la integración en términos finitos" . Boletín de la Sociedad Matemática Americana . 76 (3): 605– 608. doi : 10.1090/S0002-9904-1970-12454-5 .

• Rosenlicht, Maxwell (1972). "Integración en términos finitos". American Mathematical Monthly . 79 (9). Mathematical Association of America: 963– 972. doi : 10.2307/2318066 . JSTOR 2318066 . 

• Bhatt, Bhuvanesh. "Algoritmo de riesgo" . MundoMatemático .