Symbolic integration part 1

Now I know what you're thinking. "Andrew," you say, "I loved integration when I was in high school. I got to memorise all these cool formulas which I totally still remember. No matter what the problem, I could handle it! And it's been so useful in my later life! Besides, I know everything there is to know about integration. Why spoil things?"

Sure, all this is true. But it seems like there's something wrong with integration. It seems like it is partly art and partly science, there seems to be a lot of guess work, and a lot of dead ends.

In fact, this isn't necessary. Once upon a time, they used to teach students something called "systematic integration by parts". But the key thing is that it was systematic. There was a definite procedure to follow, and you usually ended up with the right answer.

Now I don't know about you, but integration as I was taught it was anything but systematic. It was more like a scattergun approach: Learn a bunch of template formulas, and a bunch of techniques that may or may not work in any given situation.

Clearly this situation is less than satisfactory. And besides, for curiosity's sake, there are a few things we'd like to know: Given a function, is there an algorithm to compute its integral? And is it complete? That is, will it answer "yes, there is one and here it is", or "no, there isn't"?

The answer, of course, is going to depend on what functions you allow. It's well known that, say, the error function doesn't have a simple closed form, but that's also true of sin and cos. But sin and cos are more generally useful and, more to the point, are a bit easier to deal with. We'll see why later in this series.

There's also the question of redundancy. For example, tan x = sin x / cos x, so we don't really "need" tan. Similarly, if we have exponentials and complex numbers, we don't actually need sin or cos either, because:

(where ; there's a similar formula for cos)

The reason for not including this, though, should be fairly obvious. If the integrand only mentions sin and cos, and doesn't mention exponentials and i, then we'd like the answer to be in terms of sin and cos. We want to be conservative about what we need to compute these integrals. So we'll try not to introduce anything extra.

The problem was essentially solved by Robert Risch in his 1969 paper, The Problem of Integration in Finite Terms. Various refinements and improvements have, of course, occurred over the years.

First a bit of notation.

I'm going to use to be the derivative operator. (We'll look at exactly what this means in the next article.) So given a function , we are trying to find a function such that .

The central idea is a theorem proved by Liouville, that if this equation has an elementary solution, then for for a finite number of constants and elementary functions and :

In which case, has a simple integral:

(Note: In this series, all logarithms are natural logarithms unless otherwise specified.)

The tricky part is working out which elementary functions to try.

One easy way to visualise this procedure is to use the most general form (MGF) of an integral. Once you've determined the MGF, you differentiate it and match up coefficients.

As an example, we'll try a polynomial, because we understand polynomials.

We know that the most general form of the integral of this function is a cubic polynomial with constant coefficients. So we construct the MGF:

So must be equal to the derivative of . Since the coefficients are constants, . Using this:

Matching up coefficients gives us a bunch of equations:

Solving these equations and substituting them into g gives:

which is the desired solution. Note that is unconstrained; this is the arbitrary "constant of integration".

In general, if is a polynomial in with degree ν, then its integral will be a polynomial in with degree ν+1. In this way, we can integrate arbitrary polynomials.

Next time, we'll try to put our intuition on a slightly firmer footing, when we look at some of the theory that we're going to need to extend this algorithm to more complex expressions.

On to part 2...