Rish algorithm

The Rish algorithm is an algorithm for the analytical calculation of indefinite integrals using methods of differential algebra . It is based on the type of integrable function and on the methods of integrating rational functions , roots, logarithms , and exponential functions .

Named after Robert Henry Rich. Rish himself, who developed the algorithm in 1968, called it the "resolving procedure" because the method decides whether the antiderivative of a function is an elementary function. The most detailed study of the algorithm is presented on 100 pages of the book Computer Algebra Algorithms by Keith Geddes, Stefan Zapor and George Laban.

Content

1 Description
2 Examples of tasks
3 Implementation
4 Solvability
5 notes
6 References

Description

The rish algorithm integrates elementary functions . Laplace solved this problem for rational functions by showing that the indefinite integral of a rational function itself is a rational function with a finite number of constants multiplied by the logarithms of rational functions. Software it was implemented in the early 1960s.

Liouville formulated the problem solved in the Rish algorithm. He proved analytically that if there is an elementary solution g for the equation $g'=f$ ${\ displaystyle g '= f}$ then for constants $\alpha _{i}$ ${\ displaystyle \ alpha _ {i}}$ and elementary functions $u_{i}$ ${\ displaystyle u_ {i}}$ and $v$ ${\ displaystyle v}$ the solution exists in the form

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

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

Riesch created a method that allows only a finite set of elementary functions in Liouville form to be considered.

Rish's algorithm was inspired by the behavior of exponential and logarithmic functions during differentiation.

For the function f e ^g , where f and g are differentiable , we have

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

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

so if e ^g were the result of indefinite integration, it would have to be inside the integral. Also in

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

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

if (ln g ) ⁿ were obtained as a result of indefinite integration, then several degrees of the logarithm would be expected in the final expression.

Examples of tasks to be solved

Finding an elementary antiderivative is very sensitive to minor changes. For example, the following function has an elementary antiderivative:

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

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

namely:

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

{\ displaystyle {\ begin {aligned} 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) {\ Big)} + C. \ end {aligned}}}

But if in the expression f ( x ) change 71 to 72, then it will be impossible to find an elementary antiderivative. (Some systems of computer algebra may in this case return the answer as a non-elementary function - an elliptic integral , which, however, is not covered by the Riesz algorithm.)

The following functions are more complex examples:

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

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

The antiderivative of this function is short

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

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

Implementation

Effective software implementation of a theoretically constructed algorithm turned out to be a difficult task. In the case of pure transcendental functions (containing no roots and polynomials), this was relatively easy to implement in most computer algebra systems. ^[one]

The case of pure algebraic functions was solved and implemented in the Reduce system by James Davenport ^[2] ^[3] . The general case was solved and implemented by Manuel Bronstein in Scratchpad (the predecessor of the Axiom system) ^[4] .

Solvability

The Riesch algorithm as applied to the general case of elementary functions is not an algorithm in the strict sense, because in the process it needs to determine if some expressions are identical to zero (the ). For expressions whose functions are elementary, it is not known whether there is an algorithm that does such a check (modern systems use heuristics ). Moreover, if an absolute value is added to the list of elementary functions, such an algorithm does not exist ( ). This problem also exists in the division of polynomials by a column : it will not be solvable if it is impossible to determine the equality of the coefficients to zero.

Almost every non-trivial algorithm that uses polynomials uses their division algorithm, like the Riesch algorithm. If the field of constants is computable, then the problem of equality to zero is solvable, then the Rish algorithm is complete. Examples of computable constant fields are $\mathbb {Q}$ ${\ displaystyle \ mathbb {Q}}$ and $\mathbb {Q} (y)$ ${\ displaystyle \ mathbb {Q} (y)}$ .

The same problem exists in the Gauss method , which is also necessary for many parts of the Riesch algorithm. The Gauss method will give an incorrect result if it is impossible to correctly determine whether the basis is identical to zero.

Notes

↑ Joel Moses (2012), " Macsyma: A personal history ", Journal of Symbolic Computation T. 47: 123–130 , DOI 10.1016 / j.jsc.2010.08.08.018
↑ Not to be confused with his father, Harold Davenport
↑ James H. Davenport. On the integration of algebraic functions. - Springer, 1981. - Vol. 102. - ISBN 0-387-10290-6 , 3-540-10290-6.
↑ Manuel Bronstein (1990), "Integration of elementary functions", Journal of Symbolic Computation T. 9 (2): 117–173

Links

RH Risch. The problem of integration in finite terms // Transactions of the American Mathematical Society . - American Mathematical Society, 1969. - Vol. 139 . - P. 167-189 . - DOI : 10.2307 / 1995313 .
RH Risch. The solution of the problem of integration in finite terms // Bulletin of the American Mathematical Society : journal. - 1970. - Vol. 76 , no. 3 . - P. 605-608 . - DOI : 10.1090 / S0002-9904-1970-12454-5 .
Maxwell Rosenlicht. Integration in finite terms // English Mathematical Monthly : journal. - Mathematical Association of America, 1972. - Vol. 79 , no. 9 . - P. 963–972 . - DOI : 10.2307 / 2318066 .
Geddes, Czapor, Labahn. Algorithms for Computer Algebra. - Kluwer Academic Publishers, 1992 .-- ISBN 0-7923-9259-0 .
Manuel Bronstein. Symbolic Integration I. - Springer, 2005 .-- ISBN 3-540-21493-3 .
Manuel Bronstein. Symbolic Integration Tutorial (unspecified) . - 1998.
Bhatt, Bhuvanesh. Risch Algorithm on the Wolfram MathWorld website.

[1] Joel Moses (2012), " Macsyma: A personal history ", Journal of Symbolic Computation T. 47: 123–130 , DOI 10.1016 / j.jsc.2010.08.08.018

[2] Not to be confused with his father, Harold Davenport

[3] James H. Davenport. On the integration of algebraic functions. - Springer, 1981. - Vol. 102. - ISBN 0-387-10290-6 , 3-540-10290-6.

[4] Manuel Bronstein (1990), "Integration of elementary functions", Journal of Symbolic Computation T. 9 (2): 117–173