Lecture 4 min.
The Risch algorithm is an algorithm for the analytic computation of indefinite integrals that uses methods of differential algebra. It is based on the type of the integrand and on methods for integrating rational functions, roots, logarithms, and exponential functions.
It is named after Robert Henry Risch . Risch himself, who developed the algorithm in 1968, called it a "decision procedure," because the method decides whether the antiderivative of a function is an elementary function. The most detailed study of the algorithm is presented in 100 pages of the book "Algorithms for Computer Algebra" by Keith Geddes, Stephen Czapor and George Labahn.
The Risch algorithm integrates elementary functions. Laplace solved this problem for rational functions, showing that the indefinite integral of a rational function is itself a rational function plus a finite number of constants multiplied by logarithms of rational functions. It was implemented in software in the early 1960s.
Liouville formulated the problem solved by the Risch algorithm. He proved analytically that if there is an elementary solution g to the equation 
, then for constants αi
and elementary functions ui
and v
the solution exists in the form
Risch created a method that allows one to consider only a finite set of elementary functions in Liouville's form.
The Risch algorithm was inspired by the behavior of exponential and logarithmic functions under differentiation.
For a function f eg, where f and g are differentiable, we have
so if the function eg appears in the result of indefinite integration, it must also be part of the original integrand. Similarly, since
if (ln g)n appears in the result of integration, then several powers of the logarithm must be present in the original integrand.
Finding an elementary antiderivative is very sensitive to slight changes. For example, the following function has an elementary antiderivative:
namely:
But if in the expression f(x) one changes 71 to 72, it becomes impossible to find an elementary antiderivative. (Some computer algebra systems may in this case return the answer as a non-elementary function — an elliptic integral, which, however, is not covered by the Risch algorithm.)
The following functions are more complicated examples:
The antiderivative of this function has a short form
An efficient software implementation of the theoretically constructed algorithm turned out to be a difficult task. In the case of purely transcendental functions (containing no roots or polynomials) it was implemented relatively easily in most computer algebra systems
The case of purely algebraic functions was solved and implemented in the Reduce system by James Davenport . The general case was solved and implemented by Manuel Bronstein in Scratchpad (the predecessor of the Axiom system) .
The Risch algorithm, applied to the general case of elementary functions, is not an algorithm in the strict sense, because in the course of its work it needs to determine whether certain expressions are identically zero (the constant problem). For expressions whose functions are elementary, it is unknown whether an algorithm exists that performs such a check (modern systems use heuristics). Moreover, if the absolute value function is added to the list of elementary functions, no such algorithm exists (Richardson's theorem ). This problem also arises in polynomial long division: it is not decidable if one cannot determine whether coefficients are equal to zero.
Almost every nontrivial algorithm that uses polynomials uses a division algorithm for them, as does the Risch algorithm. If the field of constants is computable, then the zero-equivalence problem is decidable, and the Risch algorithm is complete. Examples of computable fields of constants are 
and 
.
The same problem exists in Gaussian elimination, which is also necessary for many parts of the Risch algorithm. Gaussian elimination will give an incorrect result if it is impossible to correctly determine whether a basis is identically zero.
Comments