Risch algorithm

Risch algorithm

The Risch algorithm, named after Robert H. 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 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.

Description

The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometry, 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 "ui" and "v" the solution is of the form

: f = sum_{i{u_i} + v^prime ,.

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" e"g", where "f" and "g" are differentiable functions, we have

: (f cdot e^g)' = (f^prime + fcdot 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 cdotln^n g)' = f^prime ln^n{g} + n f frac{g^prime}{g} ln^{n-1}{g}

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

An important consequence of Risch's result is that the Gaussian integral has no elementary antiderivative.

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.

But if you will change 71 to 72, it will not be possible to represent the antiderivative using elementary functions. The reason is that the Galois group of

: x^4 + 10 x^2 - 96 x - 71 ,

is "D"(4), e.g. generated by permutations (1 2 3 4) and (1 3), and contains 8 elements (same as in x^4-2), while the Galois group of

: x^4 + 10 x^2 - 96 x - 72 ,

is "S"(4), e.g. generated by permutations (1 2), (1 3), (1 4), and contains 24 elements.

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 March 2008) is known to implement the full Risch algorithm, although several computer algebra systems have partial implementations. The only software that claims it has implemented in full the negative part is Axiom (e.g. if Axiom says "no" this means that antiderivative cannot be represented using elementary functions, but in a lot of cases Axiom says "error").

For example, all known programs (except Axiom) cannot find the antiderivative forFact|date=April 2008

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

Axiom can solve the above case, the result being:

: F(x) = - ln left( (x^6+15 x^4-80 x^3+27 x^2-528 x+781) sqrt{ x^4+10 x^2-96 x-71} - x^8 - 20 x^6 + 128 x^5 - 54 x^4 + 1408 x^3 - 3124 x^2 - 10001 ight) /8 + C.

Note that a lot of programs (including Maple and Mathematica) can find the antiderivative for the above function using non-elementary functions (which is not the topic for Risch algorithm).

The following is a more complex example, which no software (as of March 2008) is known to find an antiderivative for:

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

While the antiderivative for the above has a short form:

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

Also, the Risch algorithm is not an "algorithm" literally, because it needs as a part to check if some expression is equivalent to zero. And for a common meaning of what an "elementary function" is it's not known whether such an algorithm exists or not (so current computer algebra systems use heuristics); moreover, if one will add abs(x) to the list of elementary functions, it is known that no such algorithm exists, see Richardson's theorem.

ee also

* Lists of integrals
* Liouville's theorem (differential algebra)
* Symbolic integration

References

* [http://www.ams.org/bull/1970-76-03/S0002-9904-1970-12455-7/S0002-9904-1970-12455-7.pdf]
*
*
*
*
*MathWorld|urlname=RischAlgorithm|title=Risch Algorithm|author=Bhatt, Bhuvanesh


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Algorithme de Risch — L’algorithme de Risch, dû à Robert Risch (de), est un algorithme destiné aux systèmes de calcul formel, permettant de calculer des primitives, c est à dire de déterminer une fonction, connaissant sa dérivée. L’algorithme transforme ce… …   Wikipédia en Français

  • Algoritmo de Risch — En matemática el algoritmo de Risch, nombrado en honor a Robert H. Risch, es un algoritmo utilizado para el cálculo de integrales indefinidas (es decir, encontrar la función primitiva de una función dada). El algoritmo transforma el problema de… …   Wikipedia Español

  • Symbolic integration — is the problem of finding a formula for the antiderivative, or indefinite integral, of a given function f ( x ), i.e. to find the differentiable function F ( x ) such that:frac{dF}{dx} = f(x).This is also denoted:F(x) = int f(x)dx.The term… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Axiom (computer algebra system) — Scratchpad redirects here. For scratchpad memory, see Scratchpad RAM. Axiom Developer(s) independent group of people Stable release September 2011 Operating system cross platform …   Wikipedia

  • Computer algebra system — A computer algebra system (CAS) is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form. Contents 1 Symbolic manipulations 2 Additional capabilities …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Integral — This article is about the concept of integrals in calculus. For the set of numbers, see integer. For other uses, see Integral (disambiguation). A definite integral of a function can be represented as the signed area of the region bounded by its… …   Wikipedia

  • Первообразная — Первообразной[1] или примитивной функцией (иногда называют также антипроизводной) данной функции f называют такую F, производная которой (на всей области определения) равна f, то есть F ′ = f. Вычисление первообразной заключается в нахождении… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”