Algoritmo de riesgo

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 en honor al matemático estadounidense Robert Henry Risch , especialista en álgebra computacional que lo desarrolló en 1968.

El algoritmo transforma el problema de integración en un problema de álgebra . Se basa en la forma de la función que se está integrando y en métodos para integrar funciones racionales , radicales , logaritmos y funciones exponenciales . Risch lo llamó procedimiento de decisión , porque es un método para decidir si una función tiene una función elemental como integral indefinida y, si la tiene, para determinar esa integral indefinida. Sin embargo, el algoritmo no siempre logra identificar si la antiderivada de una función dada puede o no expresarse en términos de funciones elementales. ^{[ ejemplo necesario ]}

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 trascendental-algebraica mixta. ^[2]

El algoritmo de Risch se utiliza para integrar funciones elementales . Se trata de funciones obtenidas mediante la composición de exponenciales, logaritmos, radicales, funciones trigonométricas y las cuatro operaciones aritméticas ( + − × ÷ ). Laplace resolvió este problema para el caso de funciones racionales , ya que demostró que la integral indefinida de una función racional es una función racional y un número finito de múltiplos constantes de logaritmos de funciones racionales ^{[ cita requerida ]} . El algoritmo sugerido por Laplace suele describirse en los libros de texto de cálculo; como programa informático, finalmente se implementó en la década de 1960. ^{[ cita requerida ]}

Liouville formuló el problema que se resuelve mediante el algoritmo de Risch. Liouville demostró por medios analíticos que si hay 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 sólo un conjunto finito de funciones de la forma de Liouville.

La intuición del 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 debería esperar 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 sólo 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 lo demuestra 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. Esta integral fue resuelta por Chebyshev (y en qué casos es elemental), ^[7] pero la prueba estricta para ella fue realizada finalmente por Zolotarev . ^[6]

El siguiente es un ejemplo más complejo que involucra funciones tanto algebraicas como 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 usando sustitución ( Sympy puede resolverla mientras que FriCAS falla con el error "implementación incompleta (residuos constantes)" en el algoritmo de Risch): ${\displaystyle u=x+{\sqrt {x+\ln x}}}$

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

Algunos "teoremas" de Davenport ^{[ se necesita una definición ]} todavía se están aclarando. Por ejemplo, en 2020 se encontró un contraejemplo de un "teorema" de este tipo, en el que resulta que, después de todo, existe una antiderivada elemental. ^[9]

Transformar el algoritmo teórico de Risch en un algoritmo que pueda ser ejecutado efectivamente por una computadora fue una tarea compleja que llevó mucho tiempo.

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

El caso de funciones puramente algebraicas fue resuelto e implementado en Reduce por James H. Davenport , aunque por simplicidad sólo podía tratar con raíces cuadradas y raíces cuadradas repetidas y no con radicales generales u otras relaciones algebraicas no cuadráticas entre variables. ^[11]

El caso general fue resuelto y casi completamente implementado en Scratchpad, un precursor de Axiom , por Manuel Bronstein, y ahora se está desarrollando en la bifurcación de Axiom, FriCAS. ^[12] Sin embargo, la implementación no incluyó algunas de las ramas para casos especiales por completo. ^[13] Actualmente, no se conoce una implementación completa del algoritmo Risch. ^[14]

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

Obsérvese que 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 desvanecen de forma idéntica. ^[15] 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 , el problema de equivalencia cero es decidible, entonces el algoritmo de Risch es un algoritmo completo. Ejemplos de campos constantes computables son Q y Q ( y ) , es decir, números racionales y funciones racionales en y con coeficientes de números racionales, respectivamente, donde y es un indeterminado que no depende de x .

Este también es un problema en el algoritmo de eliminación de matriz gaussiana (o cualquier algoritmo que pueda calcular el espacio nulo de una matriz), que también 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 ^{[ cita requerida ]} .

• Axioma (sistema de álgebra computacional)
• Expresión de 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 . Apuntes de clase en informática . 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". Revista de computación simbólica . 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). Asociación Matemática de América: 963–972. doi :10.2307/2318066. JSTOR  2318066.

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