Algoritmo de riesgo

En computación simbólica, el algoritmo de Risch es un método de integración indefinida utilizado en algunos sistemas de álgebra computacional para encontrar antiderivadas. Lleva el nombre del matemático estadounidense Robert Henry Risch, especialista en álgebra informática 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 integra 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.

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

Brian L. Miller ha logrado algunos avances significativos en el cálculo de la parte logarítmica de una integral mixta trascendental-algebraica.

Descripción

El algoritmo de Risch se utiliza para integrar funciones elementales. Estas son funciones que se obtienen al componer exponenciales, logaritmos, radicales, funciones trigonométricas y las cuatro operaciones aritméticas (+ − × ÷). Laplace resolvió este problema para el caso de las 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. El algoritmo sugerido por Laplace generalmente se describe en los libros de texto de cálculo; como programa informático, finalmente se implementó en la década de 1960.

Liouville formuló el problema que se resuelve con el algoritmo de Risch. Liouville probó por medios analíticos que si hay una solución elemental g a la ecuación g′ = f entonces existen constantes α_i y funciones u_i y v en el campo generado por f tal que la solución es de la forma

<math alttext="{displaystyle g=v+sum _{ig=v+.. i.nα α iIn⁡ ⁡ ()ui){displaystyle g=v+sum _{i obtenidos}alpha _{i}ln(u_{i}}<img alt="{displaystyle g=v+sum _{i

Risch developed a method that allows one to consider only a finite set of functions of Liouville 's form.

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

()f⋅ ⋅ eg).. =()f.. +f⋅ ⋅ g.. )⋅ ⋅ eg,{displaystyle left(fcdot e^{g}right)}=left(f^{prime }+fcdot g^{prime }right)cdot e^{g},}

so if <in^g were in the result of an indefinite integration, it should be expected to be inside the integral. Also, as

()f⋅ ⋅ ()In⁡ ⁡ g)n).. =f.. ()In⁡ ⁡ g)n+nfg.. g()In⁡ ⁡ g)n− − 1{displaystyle left(fcdot (ln g)^{n}right)^{prime }=f^{prime }left(ln gright)^{n}+nf{frac {g^{prime }{g}}}left(ln gright)}{n-1}}}}

then if (in g)ⁿ were in the result of an integration, then only a few powers of the logarithm should be expected.

Ejemplos de problemas

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) tiene una antiderivada elemental, como muestra Wolfram Mathematica desde la versión 13 (sin embargo, Mathematica no usa el algoritmo de Risch para calcular esta integral):

f()x)=xx4+10x2− − 96x− − 71,{displaystyle f(x)={frac {x}{sqrt {x^{4}+10x^{2}-96x-71}}}

a saber:

F()x)=− − 18In()()x6+15x4− − 80x3+27x2− − 528x+781)x4+10x2− − 96x− − 71− − ()x8+20x6− − 128x5+54x4− − 1408x3+3124x2+10001))+C.{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}{4} Grande.

Pero si el término constante 71 se cambia a 72, no es posible representar la antiderivada en términos de funciones elementales, 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. Esta integral fue resuelta por Chebyshev (y en qué casos es elemental), pero Zolotarev finalmente hizo la demostración estricta.

El siguiente es un ejemplo más complejo que involucra tanto funciones algebraicas como trascendentales:

f()x)=x2+2x+1+()3x+1)x+In⁡ ⁡ xxx+In⁡ ⁡ x()x+x+In⁡ ⁡ x).{displaystyle f(x)={2}+2x+1+(3x+1){sqrt {x+ln x}}{x,{sqrt {x+ln x}}left(x+{sqrt {x+ln x}right)}}}}}}}}}}}}}}

De hecho, el antiderivativo de esta función tiene una forma bastante corta que se puede encontrar utilizando sustitución u=x+x+In⁡ ⁡ x{displaystyle u=x+{sqrt {x+ln x}}} (SimPy puede resolverlo mientras que FriCAS falla con el error "implementation incomplete (constant residuos)" en el algoritmo Risch:

F()x)=2()x+In⁡ ⁡ x+In⁡ ⁡ ()x+x+In⁡ ⁡ x))+C.{cH00FF}+lnlnlnlncH00}+lnlnleft(x+{sqrt {x+ln x}right)right)+ C.}

Algunos "teoremas" de Davenport aún se están aclarando. Por ejemplo, en 2020, un contraejemplo de tal "teorema" se encontró, donde resulta que existe una antiderivada elemental después de todo.

Implementación

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

El caso de las funciones puramente trascendentales (que no involucran raíces de polinomios) es relativamente fácil y se implementó temprano 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.

El caso de funciones puramente algebraicas fue resuelto e implementado en Reduce por James H. Davenport, aunque por simplicidad solo 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.

El caso general se resolvió e implementó casi por completo en Scratchpad, un precursor de Axiom, de Manuel Bronstein, y ahora se está desarrollando en la bifurcación de Axiom, FriCAS. Sin embargo, la implementación no incluyó completamente algunas de las ramas para casos especiales. Actualmente, no se conoce una implementación completa del algoritmo Risch.

Decidibilidad

El algoritmo de Risch aplicado a funciones elementales generales no es un algoritmo sino un semi-algoritmo porque necesita verificar, como parte de su operación, si ciertas expresiones son equivalentes a cero (problema constante), en particular en la constante campo. Para las expresiones que involucran solo funciones que comúnmente se consideran elementales, no se sabe si existe o no un algoritmo que realice tal verificación (los sistemas de álgebra computacional actuales usan heurística); además, si uno agrega la función de valor absoluto a la lista de funciones elementales, se sabe que tal algoritmo no existe; ver el teorema de Richardson.

Tenga en cuenta 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. 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 número racional coeficientes, respectivamente, donde y es un indeterminado que no depende de x.

Este también es un problema en el algoritmo de matriz de eliminación de Gauss (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.