Symbolic Integration part 3: Polynomial reduction

By ajb on May 31, 2007 1:45 PM | Permalink | Comments (0) | TrackBacks (0)

This is part of a series. You may like to read part 1 and part 2 first.

In this part, we look at how to extend integration of polynomials to fancier expressions.

In part 1, we integrated a polynomial function by finding its most general form, differentiating, them matching up components.

In part 2, we developed some of the theory of differential fields, showing how fancier functions can be expressed as monomial differential field extensions.

So let's try combining them. Consider the function:

$f = x^2 e^{2x}$

We'd like to integrate this. In fact, this can be done fairly simply using integration by parts, but we'd like to do this systematically.

We'll rewrite this as:

$f = x^2 t^2$

where:

$\begin{align*} Dx & = 1 \\ Dt & = t \end{align*}$

You can think of this as a polynomial with $t$ as the indeterminate, whose coefficients are polynomials with $x$ as the indeterminate, whose coefficients are drawn from $\Q$ .

In other words, this is $\Q$ extended with two differential field extensions. We'll denote this as $\Q[x,t]$ . An element of $\Q[x,t]$ is, in general, a rational polynomial (this is a field, remember) whose coefficients are elements of $\Q[x]$ . An element of $\Q[x]$ , in turn, is a rational polynomial whose coefficients are elements of $\Q$ .

Differentiating a polynomial in $x$ reduces the degree of that polynomial by one. So, for example, the derivative of a cubic polynomial is quadratic. This is related to applying the differential $Dx = 1$ , which also reduces the degree of $x$ by one.

The monomial $t$ , however, obeys the rule $Dt = t$ ; the monomial and its derivative have the same degree. So we might expect the most general form of a quadratic polynomial in $t$ to also be quadratic.

Let's try:

$\begin{align*} \int x^2 t^2 dx & = a_0 + a_1 t + a_2 t^2 \\ \Rightarrow x^2 t^2 & = D(a_0 + a_1 t + a_2 t^2) \\ & = Da_0 + Da_1 t + a_1 t + Da_2 t^2 + 2 a_2 t^2 \\ & = Da_0 + (Da_1 + a_1) t + (Da_2 + 2 a_2) t^2 \end{align*}$

Note that unlike the polynomial that we dealth with in part 1, we can't assume here that $Da_i = 0$ , because $a_i$ might mention $x$ .

Matching up coefficients gives us:

$\begin{align*} Da_0 & = 0 \\ Da_1 + a_1 & = 0 \\ Da_2 + 2 a_2 & = x^2 \end{align*}$

Solving the first equation for $a_0$ is easy, it's just a constant (the constant of integration).

The second two equations are trickier, because they're differential equations. Converting an integral into two differential equations may not seem like much of an improvement, but it actually is, because they only need to be solved in $\Q[x]$ , not $\Q[x,t]$ .

We'll try solving the last equation first. Once again, we'll assume that the most general form for $a_2$ is a polynomial in $x$ . Since taking the derivative of a polynomial in $x$ lowers its degree by one, and the equation mentions $x^2$ at the most, we'll assume that $a_2$ is cubic:

$a_2 = b_0 + b_1 x + b_2 x^2 + b_3 x^3$

Here, we can assume that $Db_i = 0$ . So:

$\begin{align*} x^2 & = D(b_0 + b_1 x + b_2 x^2 + b_3 x^3) \\ & + 2 (b_0 + b_1 x + b_2 x^2 + b_3 x^3) \\ & = (b_1 + 2b_0) + (2 b_2 + 2 b_1) x \\ & + (3 b_3 + 2 b_2) x^2 + 2 b_3 x^3 \end{align*}$

Matching up coefficients:

$\begin{align*} 2 b_3 & = 0 \\ 3 b_3 + 2 b_2 & = 1 \\ 2 b_2 + 2 b_1 & = 0 \\ b_1 + 2 b_0 & = 0 \end{align*}$

These equations are easy to solve:

$\begin{align*} b_3 & = 0 \\ b_2 & = \frac{1}{2} \\ b_1 & = -\frac{1}{2} \\ b_0 & = \frac{1}{4} \end{align*}$

Which gives:

$a_2 = \frac{1}{4} - \frac{1}{2} x + \frac{1}{2} x^2$

We can do a similar procedure to find $a_1$ , but in this case we don't need to bother, because it has an obvious solution: $a_1 = 0$ .

And so, we have a solution:

$\int x^2 t^2 dx = a_0 + (\frac{1}{4} - \frac{1}{2} x + \frac{1}{2} x^2) t^2$

Or:

$\int x^2 e^{2x} dx = a_0 + (\frac{1}{4} - \frac{1}{2} x + \frac{1}{2} x^2) e^{2x}$

where $a_0$ is a constant.

As a check, try differentiating to see that everything is sane.

Let's try another example:

$f = 2\tan^2 x + \tan x + 1$

We can write this as:

$f = 2t^2 + t + 1$

where $Dt = t^2 + 1$

In this case, taking the derivative of $t$ actually increases the degree of a polynomial by one! Since $f$ is quadratic, we expect its integral to be linear. We'll guess:

$\begin{align*} 2t^2 + t + 1& = D(a_0 + a_1 t) \\ & = Da_0 + Da_1 t + a_1 (1 + t^2) \\ & = (Da_0 + a_1) + (Da_1) t + a_1 t^2 \end{align*}$

Matching up coefficients:

$\begin{align*} a_1 & = 2 \\ Da_1 & = 1 \\ Da_0 + a_1 & = 1 \end{align*}$

Unfortunately, these equations don't have a solution, because the first two equations are not able to be satisfied.

This is always a problem with derivations which increase the degree of a polynomial. A quadratic polynomial has three coefficients, but a linear polynomial has only two. So in this case, we have a problem where we have three equations, but only two unknowns. Something has to give.

We can fix this by adding another unknown to take up the slack, outside the derivation:

$\begin{align*} 2t^2 + t + 1& = D(a_0 + a_1 t) + b_1 t \\ & = Da_0 + Da_1 t + a_1 (1 + t^2) + b_1 t \\ & = (Da_0 + a_1) + (Da_1 + b_1) t + a_1 t^2 \end{align*}$

(Why did we multiply $b_1$ by $t$ ? Because making it a factor of $t^2$ or a constant doesn't work. Try it and see. And as an exercise, try to think of a good reason why, in retrospect, they shouldn't work.)

We now have a system of equations we can solve, and we find:

$2t^2 + t + 1 = D(2t - x) + t$

Or:

$\int 2 \tan^2 x + \tan x + 1 dx = 2 \tan x - x + \int \tan x dx$

This isn't entirely satisfactory, since we haven't solved the whole integral, but we have reduced the "unknown" part to a smaller polynomial. And it's a polynomial with a special property: its degree is smaller than the degree of $Dt$ .

This is a theme that will come up later: Some integration techniques only work on functions which take a certain form. Techniques like this (which is called the polynomial reduction) can be used to reduce the functions to those forms, so that the fancier algorithms can be made to work.

Another example is dealing with rational polynomials. Recall that the elements of $\Q[x]$ are rational polynomials; each element is of the form $f/g$ where $f$ and $g$ are polynomials in $x$ with coefficients from $\Q$ . It's well-known that polynomials support division with remainder, much like integers. If $q$ is the quotient and $r$ is the remainder, then:

$\frac{f}{g} = q + \frac{r}{g}$

where $q$ , $r$ and $g$ are polynomials. This operation splits the rational polynomial into two parts which can be integrated separately. One part is a polynomial (which we can attack with the polynomial reduction), and the other part is a rational polynomial $r/g$ with the useful property that the degree of $r$ is less than that of $g$ . It will turn out that the algorithms for integrating rational functions like this do require this property.

I think that the above approach is the easiest way to apply the polynomial reduction with a pencil and paper, but if you're implementing it by computer, there's a slightly more efficient way.

Consider this example:

$f = t^3 + t^2 + 2t + 1$

where $Dt = t^2 + 1$ (i.e. $t = \tan x$ ). We know that taking the derivative a polynomial in $t$ increases the degree of the polynomial by 1, so the integral of $f$ , if it's a polynomial in $t$ , will be quadratic.

What will the leading coefficient of this polynomial be? Take an arbitrary $t^2$ term and differentiate it:

$\begin{align*} D(a_2 t^2) & = Da_2 + 2 a_2 t (t^2 + 1) \\ & = 2 a_2 t^3 + O(t) \end{align*}$

Since the $t^3$ term of $f$ has a coefficient of $1$ , we have:

$\begin{align*} 2 a_2 & = 1 \\ a_2 & = \frac{1}{2} \end{align*}$

We can use this to remove the $t^3$ term from the integral:

$\begin{align*} & \int t^3 + t^2 + 2t + 1 dx \\ = & \int t^3 + t^2 + 2t + 1 - D(\frac{1}{2}t^2) dx + \int D(\frac{1}{2}t^2) dx \\ = & \frac{1}{2} t^2 + \int t^3 + t^2 +2 t + 1 - D(\frac{1}{2}t^2) dx \\ = & \frac{1}{2} t^2 + \int t^3 + t^2 + 2t + 1 - t(1+t^2) dx \\ = & \frac{1}{2} t^2 + \int t^2 + t + 1 dx \end{align*}$

We can repeat the process until the degree of the polynomial of the "unknown" part is less than 2 (which is the degree of $Dt$ ).

Start playing with this! Think up some polynomial-esque functions, and start integrating them. As an exercise, think about how you might extend this technique to handle sin and cos. Try some examples. Maybe use the Mathematica integrator to check your working.

Anyway, enough pencil-on-paper algebra for the moment. The techniques that we're developing here are systematic enough that they can be implemented in source code. So next time, that's what we'll start doing.

0 TrackBacks

Listed below are links to blogs that reference this entry: Symbolic Integration part 3: Polynomial reduction.

TrackBack URL for this entry: http://andrew.bromage.org/mt/mt-tb.cgi/71

Symbolic Integration part 3: Polynomial reduction

Categories

Tags

0 TrackBacks

Leave a comment

Search

About this Entry