COMPUTER ALGEBRA AND INTEGRATION

William C. Bauldry Appalachian State University Dept. of Mathematical Sciences Boone, NC 28608

                         wmcb@math.appstate.edu

Abstract Many instructors want students to know “how to do it by hand” before letting them use a CAS. We’ll discuss the algorithms used by CAS to integrate functions and their relation to “doing it by hand.”

1 Introduction

Calculus students everywhere know that differentiation is easy, but integration is hard. The difficulty is apparent when we consider the need for tomes like Abramowitz and Stegun’s Handbook of Mathematical Functions. There are half a dozen or so rules for differentiation that reduce the process to an algorithm. This small collection of rules is why the first symbolic systems developed were for computing derivatives. Since there are very few rules for integration, the first symbolic attempts were done mainly the way hand integration is attempted: simple forms, comparisons, substitutions. These are mostly heuristic techniques. (See Zerwillger’s Handbook of Integration [21] and Hardy’s The Integration of Functions of a Single Variable [6]).

How does computer algebra affect the learning of integration? What techniques are still important? Which others are unnecessary in first-year instruction? We can better answer these questions if we know how computer algebra systems attempt antidifferentiation.

2 The Quest

There is a long, rich history of analysis of integration methods. From Newton’s inclusion of (what are essentially) integral tables in De quadratura to the Mathematica Integrator web page^{1}, there has been a search for a complete answer to the problem of integration.

Define the Problem

We need to state the integration problem precisely. The form presented here is from Akritas ([1], §5.1.1).

The Integration Problem. Given two class of functions, F and G, find an algorithm that, for every f ∈ F, presents a g ∈ G such that g′ = f or proves no such g exists.

1See <http://www.integrals.com/>

Such an algorithm gives a definitive answer to the question “Can f be integrated?” for certain classes. Our main interest is the class of elementary functions over C.

Liouville

One of the first major advances, a decision theory for “integration in finite terms,” was developed by J. Liouville in a set of papers in the 1830’s (see Rosenlicht’s “Integration in finite terms” [16]). Liouville’s theory was the first step in algorithmic integration.

Hermite, Ostrowski, and Onward

In 1872, Hermite [8] considered the case of rational functions using partial fractions as the basic tool. This method requires completely factoring a polynomial that in turn requires algebraic extensions to come to the denominator’s splitting field. In 1946, Ostrowski [12] used square-free factorization to simplify the partial fraction decomposition. Horowitz [9] was able to avoid the full square-free factorization. Rothstein [16] and Trager [18] handled the logarithmic part of the integral efficiently; their methods work for Risch’s algorithm.

Risch and Richardson

The end of the 1960’s brought good news and bad news about the integration problem. In 1969, Risch [15] developed an algorithm that, for certain classes of functions (those in function fields over finitely many algebraic, logarithmic, and exponential extensions of a base field) answered the integration problem. Due to the complexity of working in extension fields, Risch’s algorithm is not yet fully implemented in any computer algebra system.

The bad news came from Richardson [16] in 1968. He provided a simple construction of an elementary function over the constant field F = Q(ı, π, exp, log, abs) that cannot be handled: Let c ∈ F be such that the question whether c = 0 or not cannot be determined. Then consider ∫ c · e^{x^{2}}dx. This integral exists and is 0 if and only if c = 0.

3 Implementation

We will use Maple V to study CAS integration in action since Maple is the only commercial system currently running on desktop computers^{2} that has open code and code tracing. The three basic tools for investigating integration functions in Maple are:

1. infolevel[int] := integer; higher values display more information

   2. print(function name); first requires interface(verboseproc=3)

3. trace(function name); the trace function is readlib defined

The basic flow of integration in Maple is shown in Figure 1.

2Axiom, version 2.1, now runs under Windows 95 or NT.

1. First Stage: polynomial, table lookup

2. Second Stage - heuristics: substitutions, integration by parts, partial fractions special forms involving trig and polynomials

3. Third Stage – Risch Algorithm: Horowitz reduction, Lazard/Rioboo/Trager method

Figure 1: Maple’s Integrator in Outline

Example 1

Follow Maple’s computation of ∫ \frac{1}{x^{3} + x + 1} dx. We set infolevel[int]:=2.

> int(1/(x^3+x+1),x);
int/indef:   first-stage indefinite integration
int/ratpoly:   rational function integration
int/rischnorm:   enter Risch-Norman integrator
int/risch:   enter Risch integration
int/risch:   the field extensions are

[ X ]

unknown:   integrand is

\frac{1}{X^{3} + X + 1}

int/risch/ratpoly:   integrating

\frac{1}{X^{3} + X + 1}

int/risch/ratpoly:   Horowitz' method yields

∫ \frac{1}{X^{3} + X + 1} d X

int/risch/ratpoly:   starting computing subresultants at time   45.000
int/risch/ratpoly:   end of subresultants computation at time   45.000
int/risch/ratpoly:   Rothstein's method - factored resultant is

[[z^{3} − \frac{3}{31} z − \frac{1}{31}, 1]]

int/risch/ratpoly:   result is

∑_{R=%1} R ln( X − \frac{62}{9} R^{2} + \frac{31}{9} R + \frac{4}{9})

%1 := RootOf(31 Z^{3} − 3 Z − 1)

 int/risch:   exit Risch integration

∑_{R=%1} R ln(x − \frac{62}{9} R^{2} + \frac{31}{9} R + \frac{4}{9})

%1 := RootOf(31 Z^{3} − 3 Z − 1)

Example 2

Compare the results of different CAS for ∫ \frac{1}{(1 + 3 sin^{2}(x))} dx shown in Figure 2. It is

System  Integral  Discont. ; in [0, 2π]
TI-92+  \frac{tan^{−1}(2·tan(x))}{2} − \frac{mod(2·x−π,2·π)−2·x}{4}  none
Derive for Windows  \frac{x}{2} − \frac{ATAN[\frac{SIN(2x)}{COS(2x)−3}]}{2}  none
Maple V Rel. 5 (beta) \frac{1}{2} arctan (\frac{tan(\frac{x}{2})}{2+\sqrt{3}}) − \frac{1}{2} arctan (\frac{tan(\frac{x}{2})}{\sqrt{3}−2})  π
Mathematica 3.0  ^{\frac{ArcTan[\sqrt{2} Tan[x]]}{2}}  \frac{π}{2} and \frac{3π}{2}

Figure 2: Integration Choices

interesting to note the different number of discontinuities introduced by the different systems. This is most easily seen by graphing. The Maple output is shown after a combine. All of the systems compute the correct definite integral over [0, 2π] — which demonstrates that they do not apply the Fundamental Theorem, since then both Maple and Mathematica

would return 0 instead of π for the value of ∫_{0}^{2π} \frac{1}{(1 + 3 sin^{2}(x))} dx. (Axiom’s integrator

complains of a pole at π.)

4 Conclusion

The techniques that are useful in conjunction with a CAS are: substitution (including basic trigonometric substitutions), integration by parts, and partial fractions. The pitfalls in the casual application of the Fundamental Theorem that ae illustrated by using it with the integrals in Figure 2 can be studied. The old lists of special substitutions, (for example, tan(x/2)), and the special forms, (such as sec^{m}(θ) · tan^{n}(θ)), that were standard fare in first-year Calculus can be been replaced by an emphasis on analysis.

References

[1] A. Akritas, Elements of Computer Algebra with Applications, Wiley, New York, 1989.

[2] M. Bronstein, “The transcendental Risch differential equation,” J. Symbolic Comp, 9, 1990, 49–60.

[3] J. Calmet, Computer Algebra; EUROCAM ’82, Springer-Verlag, New York, 1982.

[4] B. Char et al, Maple V Library Reference Manual, Springer-Verlag, New York, 1992.

[5] K. Geddes, S. Czapor, and G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Pub., 1992.

[6] G. Hardy, The Integration of Functions of a Single Variable, Hafner, New York, 1971.

[7] A. Heck, Introduction to Maple, 2nd ed., Springer, New York, 1996.

[8] E. Hermite, “Sur l’integration des fractions rationelles,” N. Ann. de Math., 1872, 145–148.

[9] E. Horowitz, “Algorithms for partial fraction decomposition and rational function integration,” in Proc. Second Symp. Sym. and Alg. Manip., ACM Press, 1971, 441–457.

[10] R. Jenks and R. Sutor, AXIOM: The Scientific Computation System, Springer-Verlag, New York, 1992.

[11] —, Macsyma User’s Guide, 2nd ed., Macsyma Inc., 1996.

[12] A. Ostrowski, “Sur l’intégrabitité élémentaire de quelques classes d’expressions,” Comm. Math. Helvetica 18, 1946, 283–308.

[13] A. Rich and D. Stoutmeyer, Derive User Manual, SoftWarehouse, 1996.

[14] D. Richardson, “Some unsolvable problems involving elementary functions of a real variable,” J. Symbolic Logic 33, 1968, 511–520.

[15] H. Risch, “The problem of integration in finite terms,” Trans. AMS 139, 167–189.

[16] M. Rothstein, Aspects of Symbolic Integration and Simplification of Exponential amd Primitive Functions, Ph.D. Thesis, U of Wisc., Madison, 1976.

[17] M. Rosenlicht, “Integration in finite terms,” Am. Math. Monthly 79, 1972, 963–971.

[18] B. Trager, “Algebraic Factoring and Rational Function Integration,” in Proc. SYMSAC ’76, ACM Press, 1976, 219–226.

[19] S. Wolfram, The Mathematica Book, 3rd ed., Wolfram Media, 1996.

[20] —, TI-92 Guidebook, Texas Instruments, 1995.

[21] D. Zerwilleger, Handbook of Integration, Jones and Bartlett Pub., Boston, 1992.