Algoritmo rico

El algoritmo de Risch es un algoritmo para el cálculo analítico de integrales indefinidas utilizando los métodos del álgebra diferencial . Se basa en el tipo de función integrable y en métodos para integrar funciones racionales , raíces, logaritmos y funciones exponenciales .

El nombre de Robert Henry Risch . El mismo Risch, quien desarrolló el algoritmo en 1968, lo llamó "procedimiento de resolución" porque el método decide si la antiderivada de una función es una función elemental . El estudio más detallado del algoritmo se presenta en el libro de 100 páginas Computer Algebra Algorithms de Keith Geddes, Stefan Tzapor y George Laban.

Descripción

El algoritmo de Risch integra funciones elementales . Laplace resolvió este problema para funciones racionales mostrando que la integral indefinida de una función racional es en sí misma una función racional con un número finito de constantes multiplicadas por los logaritmos de las funciones racionales. Se implementó en el software a principios de la década de 1960.

Liouville formuló el problema resuelto en el algoritmo de Risch. Demostró analíticamente que si hay una solución elemental g para la ecuación , entonces para constantes y funciones elementales y la solución existe en la forma ${\ estilo de visualización g'=f}$ $\alpha_i$ $tu_{yo}$ $v$

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

Rish creó un método que nos permite considerar solo un conjunto finito de funciones elementales en la forma de Liouville.

El algoritmo de Risch se inspiró en el comportamiento de las funciones exponenciales y logarítmicas durante la diferenciación.

Para una función f e g , donde f y g son derivables , tenemos

(f\cdot e^{g})'=(f'+f\cdot g')\cdot e^{g},

por tanto, si la función e g está contenida como resultado de una integración indefinida, también debe estar incluida en el integrando original. Así mismo, porque

{\big (}f\cdot (\ln g)^{n}{\big )}'=f'(\ln g)^{n}+nf{\frac {g'}{g} }(\lng)^{n-1},

si (ln g ) n está contenido en el resultado de la integración, entonces el integrando original debe contener varias potencias del logaritmo.

Ejemplos de tareas a resolver

Encontrar la antiderivada elemental es muy sensible a cambios menores. Por ejemplo, la siguiente función tiene una antiderivada elemental:

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

a saber:

{\begin{alineado}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){\Grande)}+C.\end{alineado} }

Pero si en la expresión f ( x ) cambiamos 71 a 72, entonces será imposible encontrar una antiderivada elemental. (Algunos sistemas de álgebra computacional pueden, en este caso, devolver la respuesta como una función no elemental , la integral elíptica , que, sin embargo, no está cubierta por el algoritmo de Risch).

Las siguientes funciones son ejemplos más complejos:

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

La antiderivada de esta función tiene una forma abreviada

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

Implementación

La implementación eficiente del software del algoritmo construido teóricamente resultó ser una tarea difícil. En el caso de funciones trascendentales puras (sin raíces ni polinomios), esto fue relativamente fácil de implementar en la mayoría de los sistemas de álgebra computacional. [una]

El caso de las funciones algebraicas puras fue resuelto e implementado en el sistema Reduce por James Davenport [2] [3] . El caso general fue resuelto e implementado por Manuel Bronstein en Scratchpad (predecesor del sistema Axiom ) [4] .

Resolubilidad

El algoritmo de Risch aplicado al caso general de funciones elementales no es un algoritmo en sentido estricto, porque en el curso de su trabajo necesita determinar si algunas expresiones son idénticas a cero ( el problema de las constantes ). Para expresiones cuyas funciones son elementales, no se sabe si existe un algoritmo que haga tal verificación (los sistemas modernos usan heurística ). Además, si se agrega un valor absoluto a la lista de funciones elementales , tal algoritmo no existe ( teorema de Richardson ). Este problema también existe en la división de polinomios por una columna : no será solucionable si es imposible determinar la igualdad de los coeficientes a cero.

Casi todos los algoritmos no triviales que usan polinomios usan un algoritmo de división de polinomios, al igual que el algoritmo de Risch. Si el campo de constantes es computable, entonces el problema de igualdad a cero es solucionable, entonces el algoritmo de Risch está completo. Ejemplos de campos constantes computables son y . $\matemáticas {Q}$ ${\matemáticas {Q}}(y)$

El mismo problema existe en el método de Gauss , que también es necesario para muchas partes del algoritmo de Risch. El método gaussiano dará un resultado incorrecto si es imposible determinar correctamente si la base será idéntica a cero.

Notas

↑ Joel Moses (2012), Macsyma: A personal history , Journal of Symbolic Computation Vol. 47: 123–130 , DOI 10.1016/j.jsc.2010.08.018
↑ No debe confundirse con su padre, Harold Davenport
↑ James H. Davenport. Sobre la integración de funciones algebraicas . — Springer, 1981. - vol. 102.- (Apuntes de clase en informática). - ISBN 0-387-10290-6 , 3-540-10290-6.
↑ Manuel Bronstein (1990), Integración de funciones elementales, Journal of Symbolic Computation Vol. 9 (2): 117–173

Enlaces

R. H. Rish. El problema de la integración en términos finitos // Transacciones de la American Mathematical Society . - Sociedad Matemática Americana, 1969. - vol. 139 . - pág. 167-189 . -doi : 10.2307/ 1995313 . — .
R. H. Rish. La solución del problema de la integración en términos finitos // Boletín de la American Mathematical Society : revista . - 1970. - vol. 76 , núm. 3 . - Pág. 605-608 . -doi : 10.1090 / S0002-9904-1970-12454-5 .
Maxwell Rosenlicht. Integración en términos finitos (inglés) // American Mathematical Monthly : revista. - Asociación Matemática de América, 1972. - vol. 79 , núm. 9 _ - Pág. 963-972 . -doi : 10.2307/ 2318066 . — .
Geddes, Czapor, Labahn. Algoritmos para álgebra computacional . - Editores académicos de Kluwer , 1992. - ISBN 0-7923-9259-0 .
Manuel Bronstein. Integración Simbólica I. - Springer, 2005. - ISBN 3-540-21493-3 .
Manuel Bronstein. Tutorial de Integración Simbólica . — 1998.
Bhatt, Bhuvanesh. Risch Algorithm (inglés) en el sitio web de Wolfram MathWorld .