Pular para o conteúdo

Conheça Walt Disney World

Risch algorithm

The Risch algorithm, named after Robert Henry Risch, 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. Risch, who developed the algorithm in 1968, called it a decision procedure, because it is a method for deciding if a function has an elementary function as an indefinite integral; and also, if it does, determining it. The Risch algorithm is summarized (in more than 100 pages) in Algorithms for Computer Algebra by Keith O. Geddes, Stephen R. Czapor and George Labahn. The Risch–Norman algorithm (after A. C. Norman), a faster but less powerful technique, was developed in 1976.

Contents

Description

The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometry, and the four arithmetic 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; as a computer program it was finally 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 ui and v the solution is of the form

g = v + \sum_{i<n} \alpha_i \,\ln (u_i)

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

The intuition for the Risch algorithm comes from the behavior of the exponential and logarithm functions under differentiation. For the function f eg, where f and g are differentiable functions, we have

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

so if eg 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 lnng were in the result of an integration, then only a few powers of the logarithm should be expected.

Problem examples

Finding an elementary antiderivative is very sensitive to details. For instance, the following function has an elementary antiderivative:

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

namely:

\begin{align} F(x) = - \frac{1}{8}\ln &\,\Big( (x^6+15 x^4-80 x^3+27 x^2-528 x+781) \sqrt{ x^4+10 x^2-96 x-71} \Big. \\ & {} - \Big .(x^8 + 20 x^6 - 128 x^5 + 54 x^4 - 1408 x^3 + 3124 x^2 + 10001) \Big) + C. \end{align}

(Some computer algebra systems may here return an antiderivative in terms of non-elementary functions (i.e. elliptic integrals), which however are outside the scope of the Risch algorithm.) But if 71 is changed to 72, it is not possible to represent the antiderivative using elementary functions.

The following function[1] is a more complex example:

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

In fact, the antiderivative of this function has a fairly short form:

F(x) = 2 (\sqrt{x+\ln x} + \ln(x+\sqrt{x+\ln x})) + C.

Implementation

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. No software (as of February 2011) is known to implement the full Risch algorithm, although several computer algebra systems have partial implementations.

Decidability

The Risch algorithm applied to general elementary functions is not an algorithm but a semi-algorithm because it needs to check, as a part of its operation, if certain expressions are equivalent to zero (constant problem), in particular in the constant field. For expressions that involve only functions commonly taken to be elementary it is not known whether an algorithm performing such a check exists or not (current computer algebra systems use heuristics); moreover, if one adds the absolute value function to the list of elementary functions, it is known that no such algorithm exists; see Richardson's theorem.

Note that this issue also arises in the polynomial division algorithm; this algorithm will fail if it cannot correctly determine whether coefficients vanish identically.[2] Therefore, the Risch algorithm too requires that the constant field be computable, i.e., that for elements not dependent on x, the problem of zero-equivalence is decidable.

See also

References

Notes

  1. ^ This example comes from Manuel Bronstein's "Symbolic Integration Tutorial". See the references.
  2. ^ "Mathematica 7 Documentation: PolynomialQuotient". Section: Possible Issues. http://reference.wolfram.com/mathematica/ref/PolynomialQuotient.html. Retrieved 17 July 2010. 
fonte: https://web.archive.org/web/20120719135824/https://en.wikipedia.org/wiki/Risch_algorithm
Personal tools
  • Log in / create account
Namespaces
Variants
Actions
Navigation
Toolbox
Print/export
Marcações: