Integration, Mathematics

Symbolic integration: Part 1

Posted by Andrew on May 25, 2007 at 3:12 pm.

Well, time to show my true geek­i­ness with a series. We’re going to do sym­bolic integ­ra­tion. You know, anti-derivatives.

Now I know what you’re think­ing. “Andrew,” you say, “I loved integ­ra­tion when I was in high school. I got to mem­or­ise all these cool for­mu­las which I totally still remem­ber. No mat­ter what the prob­lem, I could handle it! And it’s been so use­ful in my later life! Besides, I know everything there is to know about integ­ra­tion. Why spoil things?”

Sure, all this is true. But it seems like there’s some­thing wrong with integ­ra­tion. It seems like it is partly art and partly sci­ence, there seems to be a lot of guess work, and a lot of dead ends.

In fact, this isn’t neces­sary. Once upon a time, they used to teach stu­dents some­thing called “sys­tem­atic integ­ra­tion by parts”. But the key thing is that it was sys­tem­atic. There was a def­in­ite pro­ced­ure to fol­low, and you usu­ally ended up with the right answer.

Now I don’t know about you, but integ­ra­tion as I was taught it was any­thing but sys­tem­atic. It was more like a scat­ter­gun approach: Learn a bunch of tem­plate for­mu­las, and a bunch of tech­niques that may or may not work in any given situation.

Clearly this situ­ation is less than sat­is­fact­ory. And besides, for curiosity’s sake, there are a few things we’d like to know: Given a func­tion, is there an algorithm to com­pute its integ­ral? And is it com­plete? 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 func­tions you allow. It’s well known that, say, the error func­tion doesn’t have a simple closed form, but that’s also true of sin and cos. But sin and cos are more gen­er­ally use­ful and, more to the point, are a bit easier to deal with. We’ll see why later in this series.

There’s also the ques­tion of redund­ancy. For example, \tan x = \sin x / \cos x‚  so we don’t really “need” tan. Sim­il­arly, if we have expo­nen­tials and com­plex num­bers, we don’t actu­ally need sin or cos either, because:

\sin x =\frac{1}{2i} (e^{-ix} - e^{ix})

(where i^2 = -1 ; there’s a sim­ilar for­mula for cos)

The reason for not includ­ing this, though, should be fairly obvi­ous. If the integ­rand only men­tions sin and cos, and doesn’t men­tion expo­nen­tials and i$, then we’d like the answer to be in terms of sin and cos. We want to be con­ser­vat­ive about what we need to com­pute these integ­rals. So we’ll try not to intro­duce any­thing extra.

The prob­lem was essen­tially solved by Robert Risch in his 1969 paper, The Prob­lem of Integ­ra­tion in Finite Terms. Vari­ous refine­ments and improve­ments have, of course, occurred over the years.

First a bit of notation.

I’m going to use D to be the deriv­at­ive oper­ator. (We’ll look at exactly what this means in the next art­icle.) So given a func­tion f , we are try­ing to find a func­tion g such that Dg = f.

The cent­ral idea is a the­orem proved by Liouville, that if this equa­tion has an ele­ment­ary solu­tion, then for for a finite num­ber of con­stants \alpha_i and ele­ment­ary func­tions u_i and v:

f = \sum_{i} \alpha_i \frac{Du_i}{u_i} + Dv

In which case, f has a simple integral:

\int f dx = \sum_{i} \alpha_i \log u_i + v

(Note: In this series, all log­ar­ithms are nat­ural log­ar­ithms unless oth­er­wise spe­cified.  Which they won’t be.)

The tricky part is work­ing out which ele­ment­ary func­tions to try.

One easy way to visu­al­ise this pro­ced­ure is to use the most gen­eral form (MGF) of an integ­ral. Once you’ve determ­ined the MGF, you dif­fer­en­ti­ate it and match up coefficients.

As an example, we’ll try a poly­no­mial, because we under­stand polynomials.

f = x^2 + 3

The deriv­at­ive of a poly­no­mial of order ν is a poly­no­mial of order ν-1.  So it stands to reason that the integ­ral of a poly­no­mial of order ν-1 is a poly­no­mial of order ν.  So we know that the most gen­eral form of the integ­ral of this func­tion is a cubic poly­no­mial with con­stant coefficients.

We con­struct the MGF:

g = a_0 + a_1 x + a_2 x^2 + a_3 x^3

So f must be equal to the deriv­at­ive of g. Since the coef­fi­cients are con­stants, Da_i = 0. Using this:

x^2 + 3 = a_1 + x (2a_2) + x^2 (3a_3)

Match­ing up coef­fi­cients gives us a bunch of equations:

\begin{array}{ccc} a_1 & = & 3\\ 2a_2 & = & 0 \\ 3a_3 & = & 1 \end{array}

Solv­ing these equa­tions and sub­sti­tut­ing them into g gives:

g = a_0 + 3 x + \frac{1}{3} x^3

which is the desired solu­tion. Note that a_0 is uncon­strained; this is the arbit­rary “con­stant of integration”.

Next time, we’ll try to put our intu­ition on a slightly firmer foot­ing, when we look at some of the the­ory that we’re going to need to extend this algorithm to more com­plex expressions.

Leave a Reply