next up previous
Next: Example Up: HermiteHorowitz, Rothstein, Previous: Hermite's method

Rothstein-Trager Method

We have now reduced the problem to the integration of , where degree degree , and is square-free (has only simple roots). We know by the classical algorithm that this rational function can be expressed as

where the are the k distinct roots of , and the are the residues of at the roots of . This gives , which has possibly complex coefficients. Can we avoid the use of complex numbers?

The answer is yes, and depends on the following observation. We know that the are the residues of , and indeed we know an explicit formula for them: , because the roots of are simple (this is easy to prove: first note that , and that since and that is the Laurent expansion of ). Rearranging this formula for the residues we get

 

The key to the Rothstein-Trager method is to observe that this means the are the roots of the following resultant:

 

where means take the resultant in terms of x, leaving a polynomial in z.

This resultant formula looks strange, and indeed it's hard to think how it was recognized in the first place, but it's not hard to verify. What it is saying is that the common roots of and are the roots of the resultant---and that's easy, because one of the polynomials doesn't contain z in the first place. So this formula is easy to understand with hindsight.

The next main observation of the Rothstein-Trager method is that it is the distinct residues that give rise to uncombineable log terms: can be combined to . So the only way we can avoid using complex numbers, or algebraic extensions in general, is if there are multiple roots of the resultant.

This is true in general, and we have the following theorem, which is theorem 11.7 in Geddes et al.

Theorem If , b is monic and square-free, and , then

 

where the are the distinct roots of , and further the .

For a proof of this theorem see Geddes et al.. For now, note that it solves the problem completely. We compute a resultant, find its distinct roots, compute some GCD's, and then we write down the integral. All the calculations are rational. (Except of course for the factorization of the resultant, but even there we can do as well as is possible with another square-free factorization).

Remark. I have not stressed the fact that this method introduces only those algebraic extensions that are necessary. For a discussion of this, see Geddes et al., but note that this idea goes beyond the simple rational function integration performed here and will prove useful in identifying functions which have no elementary antiderivative in the Risch algorithm, which we will see next week.



next up previous
Next: Example Up: HermiteHorowitz, Rothstein, Previous: Hermite's method



Rob Corless
Thu Nov 16 13:46:20 PST 1995