6.4. 6.4 Symbolic integration

The problem of indefinite integration is the following: given a function , find a function the derivative of which is , that is, ; for this relationship the notation is also used. In introductory calculus courses, one tries to solve indefinite integration problems by different methods, among which one tries to choose in a heuristic way: substitution, trigonometric substitution, integration by parts, etc. Only the integration of rational functions is usually solved by an algorithmic method.

It can be shown that indefinite integration in the general case is algorithmically unsolvable. So we only have the possibility to look for a reasonably large part that can be solved using algorithms.

The first step is the algebraisation of the problem: we discard every analytical concept and consider differentiation as a new (unary) algebraic operation connected to addition and multiplication in a given way, and we try to find the “inverse” of this operation. This approach leads to the introduction of the concept of differential algebra.

The integration routines of computer algebra systems (e.g. MAPLE ), similarly to us, first try a few heuristic methods. Integrals of polynomials (or a bit more generally, finite Laurent-series) are easy to determine. This is followed by a simple table lookup process (e.g. in case of MAPLE 35 basic integrals are used). One can, of course, use integral tables entered from books as well. Next we may look for special cases where appropriate methods are known. For example, for integrands of the form

where is a polynomial, the integral can be determined using integration by parts. When the above methods fail, a form of substitution called the “derivative-divides” method is tried: if the integrand is a composite expression, then for every sub-expression , we divide by the derivative of , and check if vanishes from the result after the substitution . Using these simple methods we can determine a surprisingly large number of integrals. To their great advantage, they can solve simple problems very quickly. If they do not succeed, we try algorithmic methods. The first one is for the integration of rational functions. As we will see, there is a significant difference between the version used in computer algebra systems and the version used in hand computations, since the aims are short running times even in complicated cases, and the simplest possible form of the result. The Risch algorithm for integrating elementary functions is based on the algorithm for the integration of rational functions. We describe the Risch algorithm, but not in full detail. In most cases, we only outline the proofs.

6.4.1. 6.4.1 Integration of rational functions

In this subsection, we introduce the notion of differential field and differential extension field, then we describe Hermite's method.

6.4.1.1.  Differential fields.

Let be a field of characteristic 0, with a mapping of into itself satisfying:

(1) (additivity);

(2) (Leibniz-rule).

The mapping is called a differential operator, differentiation or derivation, and is called a differential field. The set is the field of constants or constant subfield in . If , we also write . Obviously, for any constant , we have . The logarithmic derivative of an element is defined as (the “derivative of ”).

Theorem 6.21 With the notations of the previous definition, the usual rules of derivation hold:

(1) ;

(2) derivation is -linear: for , ;

(3) if , is arbitrary, then ;

(4) for and ;

(5) for (integration by parts).

Example 6.17 (1) With the notations of the previous definition, the mapping on is the trivial derivation, for this we have .

(2) Let . There exists a single differential operator on with , it is the usual differentiation. For this the constants are the elements of . Indeed, for by induction, so the elements of and are also constants. We have by induction that the derivative of power functions is the usual one, thus, by linearity, this is true for polynomials, and by the differentiation rule of quotients, we get the statement. It is not difficult to calculate that for the usual differentiation, the constants are the elements of .

(3) If , where is an arbitrary field of characteristic 0, then there exists a single differential operator on with constant subfield and : it is the usual differentiation. This statement is obtained similarly to the previous one.

If is an arbitrary field of characteristic 0, and with the usual differentiation, then is not the derivative of anything. (The proof of the statement is very much like the proof of the irrationality of , but we have to work with divisibility by rather than by 2.)

The example shows that for the integration of and other similar functions, we have to extend the differential field. In order to integrate rational functions, an extension by logarithms will be sufficient.

6.4.1.2.  Extensions of differential fields.

Let be a differential field and a subfield of . If differentiation doesn't lead out of , then we say that is a differential subfield of , and is a differential extension field of . If for some we have , that is, the derivative of is the logarithmic derivative of , then we write . (We note that , just like is a relation rather than a function. In other words, is an abstract concept here and not a logarithm function to a given base.) If we can choose , we say that is logarithmic over .

Example 6.18 (1) Let , , where is a new indeterminate, and let , that is, . Then .

(2) Analogically,

is in the differential field .

(3) Since

the integral can be considered as an element of

or an element of

as well. Obviously, it is more reasonable to choose the first possibility, because in this case there is no need to extend the base field.

6.4.1.3.  Hermite's method

Let be a field of characteristic 0, non-zero relatively prime polynomials. To compute the integral using Hermite's method, we can find polynomials with

where and is monic and square-free. The rational function is called the rational part, the expression is called the logarithmic part of the integral. The method avoids the factorisation of into linear factors (in a factor field or some larger field), and even its decomposition into irreducible factors over .

Trivially, we may assume that is monic. By Euclidean division we have , where , thus, . The integration of the polynomial part is trivial. Let us determine the square-free factorisation of , that is, find monic and pairwise relatively prime polynomials such that and . Let us construct the partial fraction decomposition (this can be achieved by the Euclidean algorithm):

where every has smaller degree than .

The Hermite-reduction is the iteration of the following step: if , then the integral is reduced to the sum of a rational function and an integral similar to the original one, with reduced by 1. Using that is square-free, we get , thus, we can obtain polynomials by the application of the extended Euclidean algorithm such that and . Hence, using integration by parts,

It can be shown that using fast algorithms, if , then the procedure requires operations in the field , where is a bound on the number of operations needed to multiply to polynomials of degree at most .

Hermite's method has a variant that avoids the partial fraction decomposition of . If , then is square-free. If , then let

Since , there exist polynomials such that

Dividing both sides by and integrating by parts,

thus, is reduced by one.

Note that and can be determined by the method of undetermined coefficients (Horowitz's method). After division, we may assume . As it can be seen from the algorithm, we can choose and . Differentiating (6.15), we get a system of linear equations on coefficients of and coefficients of , altogether coefficients. This method in general is not as fast as Hermite's method.

The algorithm below performs the Hermite-reduction for a rational function of variable .

Hermite-Reduction( )

  1     2     3   
                        
                           Square-Free 
                           
                           4  construct the partial fraction decomposition of , compute numerators          belonging to   5     6     7  
                           FOR
                         
                         
                        
                           TO
                         
                            8    
                           DO
                         
                           9    
                           FOR
                         
                         
                        
                           TO
                         
                          10       
                           DO
                         
                          11       
                           WHILE
                         
                          12          
                           DO
                         determine  and  from the equation   13               14               15               16         17    18  
                           RETURN
                         
                         
                     

If for some field of characteristic 0, we want to compute the integral , where are non-zero relatively prime polynomials with , square-free and monic, we can proceed by decomposing polynomial into linear factors, , in its splitting field , then constructing the partial fraction decomposition, , over , finally integrating we get

The disadvantage of this method, as we have seen in the example of the function , is that the degree of the extension field can be too large. An extension degree as large as can occur, which leads to totally unmanageable cases. On the other hand, it is not clear either if a field extension is needed at all: for example, in case of the function , can we not compute the integral without extending the base field? The following theorem enables us to choose the degree of the field extension as small as possible.

Theorem 6.22 (Rothstein-Trager integration algorithm) Let be a field of characteristic 0, non-zero relatively prime polynomials, , square-free and monic. If is an algebraic extension of , are square-free and pairwise relatively prime monic polynomials, then the following statements are equivalent:

(1) ,

(2) The polynomial can be decomposed into linear factors over , are exactly the distinct roots of , and if . Here, is the resultant taken in the indeterminate .

Example 6.19 Let us consider again the problem of computing the integral . In this case,

the roots of which are and Thus,

The algorithm, which can be easily given based on the previous theorem, can be slightly improved: instead of computing (by calculations over the field ), can also be computed over , applying the Extended-Euclidean-Normalised algorithm. This was discovered by Trager, and independently by Lazard and Rioboo. It is not difficult to show that the running time of the complete integration algorithm obtained this way is if .

Theorem 6.23 (Lazard-Rioboo-Trager-formula) Using the notations of the previous theorem, let denote the multiplicity of as a root of the polynomial . Then

(1) ;

(2) if denotes the remainder of degree in the Extended-Euclidean-Normalised algorithm performed in on and , then .

The algorithm below is the improved Lazard-Rioboo-Trager version of the Rothstein-Trager method. We compute for the rational function of indeterminate , where is square-free and monic, and .

Integrate-Logarithmic-Part( )

  1  Let  by the subresultant algorithm, furthermore   2  let  be the remainder of degree  during the computation   3   
                        
                           Square-free 
                           
                           4     5  
                           FOR
                         
                         
                        
                           TO
                         
                           6    
                           DO
                         
                        
                           IF
                         
                           7       
                           THEN
                         
                         the gcd of the coefficients of    8          
                        
                           Extended-Euclidean-Normalised 
                           
                           9          
                        
                           Primitive-Part 
                           
                          10          
                        
                           Factors 
                           
                          11          
                           FOR
                         
                         
                        
                           TO
                         
                          12             
                           DO
                         
                          13                
                        
                           Solve 
                           
                          14                
                           IF
                         
                          15                   
                           THEN
                         
                          16                   
                           ELSE
                         
                        
                           FOR
                         
                         
                        
                           TO
                         
                          17                      
                           DO
                         
                          18  
                           RETURN
                         
                          
                     

Example 6.20 Let us consider again the problem of computing the integral . In this case,

The polynomial is irreducible in , thus, we cannot avoid the extension of . The roots of are . From the Extended-Euclidean-Normalised -algorithm over , , thus, the integral is

6.4.2. 6.4.2 The Risch integration algorithm

Surprisingly, the methods found for the integration of rational functions can be generalised for the integration of expressions containing basic functions (, etc.) and their inverse. Computer algebra systems can compute the integral of remarkably complicated functions, but sometimes they fail in seemingly very simple cases, for example the expression is returned unevaluated, or the result contains a special non-elementary function, for example the logarithmic integral. This is due to the fact that in such cases, the integral cannot be given in “closed form”.

Although the basic results for integration in “closed form” had been discovered by Liouville in 1833, the corresponding algorithmic methods were only developed by Risch in 1968.

6.4.2.1.  Elementary functions.

The functions usually referred to as functions in “closed form” are the ones composed of rational functions, exponential functions, logarithmic functions, trigonometric and hyperbolic functions, their inverses and -th roots (or more generally “inverses” of polynomial functions, that is, solutions of polynomial equations); that is, any nesting of the above functions is also a function in “closed form”.

One might note that while is usually given in the form , the algorithm for the integration of rational functions returns

as solution. Since trigonometric and hyperbolic functions and their inverses over can be expressed in terms of exponentials and logarithms, we can restrict our attention to exponentials and logarithms. Surprisingly, it also turns out that the only extensions needed are logarithms (besides algebraic numbers) in the general case.

6.4.2.2.  Exponential elements.

Let be a differential extension field of the differential field . If for a , there exists a such that , that is, the logarithmic derivative of equals the derivative of an element of , then we say that is exponential over and we write . If only the following is true: for an element , there is a such that , that is, the logarithmic derivative of is an element of , then is called hyperexponential over .

Logarithmic, exponential or hyperexponential elements may be algebraic or transcendent over .

6.4.2.3.  Elementary extensions.

Let be a differential extension field of the differential field . If

where for , is logarithmic, exponential or algebraic over the field

(), then is called an elementary extension of . If for , is either transcendental and logarithmic, or transcendental and exponential over , then is a transcendental elementary extension of .

Let be the differential field of rational functions with the usual differentiation and constant subfield . An elementary extension of is called a field of elementary functions, a transcendental elementary extension of is called a field of transcendental elementary functions.

Example 6.21 The function can be written in the form , where , , . Trivially, is exponential over , is exponential over and is exponential over . Since and , can be written in the simpler form . The function is not only exponential but also algebraic over , since , that is, . So . But can be put in an even simpler form:

Example 6.22 The function

can be written in form , where , , , and satisfies the algebraic equation . But can also be given in the much simpler form .

Example 6.23 The function can be written in the form , where and , so is logarithmic over , and is exponential over . But , so is algebraic over , and .

6.4.2.4.  The integration of elementary functions.

The integral of an element of a field of elementary functions will be completely characterised by Liouville's Principle in case it is an elementary function. Algebraic extensions, however, cause great difficulty if not only the constant field is extended.

Here we only deal with the integration of elements of fields of transcendental elementary functions by the Risch integration algorithm.

In practice, this means an element of the field of transcendental elementary functions , where are algebraic over and the integral is an element of the field

of elementary functions. In principle, it would be simpler to choose as constant subfield but, as we have seen in the case of rational functions, this is impossible, for we can only compute in an exact way in special fields like algebraic number fields; and we even have to keep the number and degrees of as small as possible. Nevertheless, we will deal with algebraic extensions of the constant subfield dynamically: we can imagine that the necessary extensions have already been made, while in practice, we only perform extensions when they become necessary.

After the conversion of trigonometric and hyperbolic functions (and their inverses) to exponentials (and logarithms, respectively), the integrand becomes an element of a field of elementary functions. Examples 6.21 and 6.22 show that there are functions that do not seem to be elements of a transcendental elementary extension “at first sight”, and yet they are; while Example 6.23 shows that there are functions that seem to be elements of such an extension “at first sight”, and yet they are not. The first step is to represent the integrand as an element of a field of transcendental elementary functions using the algebraic relationships between the different exponential and logarithmic functions. We will not consider how this can be done. It can be verified whether we succeeded by the following structure theorem by Risch. We omit the proof of the theorem. We will need a definition.

An element is monomial over a differential field if and have the same constant field, is transcendental over and it is either exponential or logarithmic over .

Theorem 6.24 (Structure theorem) Let be the field of constants and a differential extension field of , which has constant field . Let us assume that for all , either is algebraic over , or , with and , or , with and . Then

1. , where , is monomial over if and only if there is no product

which is an element of ;

2. , where , is monomial over if and only if there is no linear combination

which is an element of .

Product and summation is only taken for logarithmic and exponential steps.

The most important classic result of the entire theory is the following theorem.

Theorem 6.25 (Liouville's Principle) Let be a differential field with constant field . Let be a differential extension field of with the same constant field. Let us assume that . Then there exist constants and elements such that

that is,

Note that the situation is similar to the case of rational functions.

We will not prove this theorem. Although the proof is lengthy, the idea of the proof is easy to describe. First we show that a transcendental exponential extension cannot be “eliminated”, that is differentiating a rational function of it, the new element does not vanish. This is due to the fact that differentiating a polynomial of an element of the transcendental exponential extension, we get a polynomial of the same degree, and the original polynomial does not divide the derivative, except for the case when the original polynomial is monomial. Next we show that no algebraic extension is needed to express the integral. This is essentially due to the fact that substituting an element of an algebraic extension into its minimal polynomial, we get zero, and differentiating this equation, we get the derivative of the extending element as a rational function of the element. Finally, we have to examine extensions by transcendental logarithmic elements. We show that such an extending element can be eliminated by differentiation if and only if it appears in a linear polynomial with constant leading coefficient. This is due to the fact that differentiating a polynomial of such an extending element, we get a polynomial the degree of which is either the same or is reduced by one, the latter case only being possible when the leading coefficient is constant.

6.4.2.5.  The Risch algorithm.

Let be an algebraic number field over , and a field of transcendental elementary functions. The algorithm is recursive in : using the notation , we will integrate a function , where . (The case is the integration of rational functions.) We may assume that and are relatively prime and is monic. Besides differentiation with respect to , we will also use differentiation with respect to , which we denote by . In the following, we will only present the algorithms.

6.4.2.6.  Risch algorithm: logarithmic case.

Using the notations of the previous paragraph, we first presume that is transcendental and logarithmic, , . By Euclidean division, , hence

Unlike the integration of rational functions, here the integration of the polynomial part is more difficult. Therefore, we begin with the integration of the rational part.

6.4.2.7.  Logarithmic case, rational part.

Let be the square-free factorisation of . Then

is obvious. It can be shown that the much stronger condition is also fulfilled. By partial fraction decomposition,

We use Hermite-reduction: using the extended Euclidean algorithm we get polynomials that satisfy and . Using integration by parts,

Continuing this procedure while , we get

where , and is a square-free and monic polynomial.

It can be shown that the Rothstein-Trager method can be applied to compute the integral . Let us calculate the resultant

It can be shown that the integral is elementary if and only if is of the form , where and . If we compute the primitive part of , choose it as and any coefficient of is not a constant, then there is no elementary integral. Otherwise, let be the distinct roots of in its factor field and le

for . It can be shown that

Let us consider a few examples.

Example 6.24 The integrand of the integral is , where . Since

is a primitive polynomial and it has a coefficient that is, not constant, the integral is not elementary.

Example 6.25 The integrand of the integral is , where . Here,

which has primitive part . Every coefficient of this is constant, so the integral is elementary, , , so

6.4.2.8.  Logarithmic case, polynomial part.

The remaining problem is the integration of the polynomial part

According to Liouville's Principle is elementary if and only if

where and for , is an extension of and . We will show that can be an algebraic extension of . A similar reasoning to the proof of Liouville's Principle shows that and (that is, independent of ) for . Thus,

We also get, by the reasoning used in the proof of Liouville's Principle, that the degree of is at most . So if , then

Hence, we get the following system of equations:

where in the last equation. The solution of the first equation is simply a constant . Substituting this into the next equation and integrating both sides, we get

Applying the integration procedure recursively, the integral of can be computed, but this equation can only be solved if the integral is elementary, it uses at most one logarithmic extension, and it is exactly . If this is not fulfilled, then cannot be elementary. If it is fulfilled, then for some and , hence, and with an arbitrary integration constant . Substituting for into the next equation and rearranging, we get

so we have

after integration. The integrand on the right hand side is in , so we can call the integration procedure in a recursive way. Just like above, the equation can only be solved when the integral is elementary, it uses at most one logarithmic extension and it is exactly . Let us assume that this is the case and

where and . Then the solution is and , where is an arbitrary integration constant. Continuing the procedure, the solution of the penultimate equation is and with an integration constant . Substituting for into the last equation, after rearrangement and integration, we get

This time the only condition is that the integral should be an elementary function. If it is elementary, say

then is the coefficient of in , , and the result is

Let us consider a few examples.

Example 6.26 The integrand of the integral is , where . If the integral is elementary, then

and , , . With the unknown constant from the second equation, . Since , we get , . From the third equation . Since , after integration and , we get , , hence, .

Example 6.27 The integrand of the integral is , where and . If the integral is elementary, then

and , , . With the unknown constant from the second equation, . Since , we get , . From the third equation . Since , the equation

must hold but we know from Example 6.24 that the integral on the left hand side is not elementary.

6.4.2.9.  Risch algorithm: exponential case.

Now we assume that is transcendental and exponential, , . By Euclidean division, , hence

We plan using Hermite's method for the rational part. But we have to face an unpleasant surprise: although for the square-free factors

is obviously satisfied, the much stronger condition is not. For example, if , then

It can be shown, however, that this unpleasant phenomenon does not appear if , in which case . Thus, it will be sufficient to eliminate from the denominator. Let , where , and let us look for polynomials with , and . Dividing both sides by , we get

Using the notation , is a finite Laurent-series the integration of which will be no harder than the integration of a polynomial. This is not surprising if we note . Even so, the integration of the “polynomial part” is more difficult here, too. We start with the other one.

6.4.2.10.  Exponential case, rational part.

Let be the square-free factorisation of . Then, since , . Using partial fraction decomposition

Hermite-reduction goes the same way as in the logarithmic case. We get

where , and is a square-free and monic polynomial, .

It can be shown that the Rothstein-Trager method can be applied to compute the integral . Let us calculate the resultant

It can be shown that the integral is elementary if and only if is of form , where and . If we compute the primitive part of , choose it as and any coefficient of is not a constant, then there is no elementary integral. Otherwise, let be the distinct roots of in its factor field and let

for . It can be shown that

Let us consider a few examples.

Example 6.28 The integrand of the integral is , where . Since

is a primitive polynomial which only has constant coefficients, the integral is elementary, , , thus,

Example 6.29 The integrand of the integral is , where . Since

is a primitive polynomial that has a non-constant coefficient, the integral is not elementary.

6.4.2.11.  Exponential case, polynomial part.

The remaining problem is the integration of the “polynomial part”

According to Liouville's Principle is elementary if and only if

where and for , is an extension of and . It can be shown that can be an algebraic extension of . A similar reasoning to the proof of Liouville's Principle shows that we may assume without breaking generality that is either an element of (that is, independent of ), or it is monic and irreducible in for . Furthermore, it can be shown that there can be no non-monomial factor in the denominator of , since such a factor would also be present in the derivative. Similarly, the denominator of can have no non-monomial factor either. So we get that either , or , since this is the only irreducible monic monomial. But if , then the corresponding term of the sum is , which can be incorporated into . Hence, we get that if has an elementary integral, then

where and . The summation should be taken over the same range as in since

Comparing the coefficients, we get the system

where . The solution of the equation is simply ; if this integral is not elementary, then cannot be elementary either, but if it is, then we have determined . In the case , we have to solve a differential equation called Risch differential equation to determine . The differential equation is of the form , where the given functions and are elements of , and we are looking for solutions in . At first sight it looks as if we had replaced the problem of integration with a more difficult problem, but the linearity of the equations and that the solution has to be in means a great facility. If any Risch differential equation fails to have a solution in , then is not elementary, otherwise

The Risch differential equation can be solved algorithmically, but we will not go into details.

Let us consider a few examples.

Example 6.30 The integrand of the integral is , where . If the integral is elementary, then , where . It is not difficult to show that the differential equation has no rational solutions, so is not elementary.

Example 6.31 The integrand of the integral is , where and . If the integral is elementary, then , where . Differentiating both sides, , thus, . Since is transcendental over , by comparing the coefficients and , which has no solutions. Therefore, is not elementary.

Example 6.32 The integrand of the integral

is

where . If the integral is elementary, then it is of the form , where

The second equation can be integrated and is elementary. The solution of the first equation is . Hence,

Exercises

6.4-1 Apply Hermite-reduction to the following function :

6.4-2 Compute the integral , where

6.4-3 Apply the Risch integration algorithm to compute the following integral: