Risch algorithm

From Wikipedia, the free encyclopedia

The Risch algorithm is an algorithm for the calculus operation of indefinite integration (i.e. finding antiderivatives). The algorithm transforms the problem of integration into a problem in algebra. It is based on the form of the function being integrated and on methods for integrating rational functions, radicals, logarithms, and exponential functions. Robert Risch, who developed the algorithm in 1968, called it a decision procedure, because it is a method for deciding if a function has a simple-looking function as an indefinite integral; and also, if it does, determining it. The Risch-Norman algorithm, a faster but less powerful technique, was developed in 1976.

The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, and the four operations (+ − × ÷). Laplace solved this problem for the case of rational functions, as he showed that the indefinite integral of a rational function is a rational function and a finite number of constant multiples of logarithms of rational functions. The algorithm suggested by Laplace is usually described in calculus textbooks but was only implemented in the 1960s.

Liouville formulated the problem solved by the Risch algorithm. Liouville proved by analytical means that if there is an elementary solution g to the equation g ′ = f then for constants α_i and elementary functions u_i and v the solution is of the form

$f = \sum_{i<n} \alpha_i \frac{u_i^{\prime}}{u_i} + v^\prime \,.$

Risch developed a method for finding a finite set of elementary functions to consider.

The intuition for the Risch algorithm comes from the behavior of the exponential and logarithm functions under differentiation. If there is a function f e^g where f and g are functions of x, then

$(f \cdot e^g)' = (f^\prime + f\cdot g^\prime)\cdot e^g$

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

$(f \cdot\ln^n g)' = f^\prime \ln^n{g} + n f \frac{g^\prime}{g} \ln^{n-1}{g}$

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

Transforming the Risch decision procedure into an algorithm that can be executed by a computer is a complex task that requires the use of heuristics and many refinements.

[edit] References

R. H. Risch (1969). "The Problem of Integration in Finite Terms". Transactions of the American Mathematical Society 139: 167-189.
Maxwell Rosenlicht (1972). "Integration in finite terms". American Mathematical Monthly 79: 963-972.
Geddes, Czapor, Labahn (1992). Algorithms for Computer Algebra. Kluwer Academic Publishers. ISBN 0-7923-9259-0.
Manuel Bronstein (2005). Symbolic Integration I. Springer. ISBN 3-540-21493-3.
Manuel Bronstein (1998). "Symbolic Integration Tutorial".
MathWorld entry on the Risch Algorithm