How to carry out partial fraction decomposition

[viki]

hi , I am trying for partial fraction deomposition of polynomials.
I have problems in solving the denominator and in applying different
conditions for special cases . Is there any stright forward method for this.

[Lerner]

You could try looking for a math library that already does this. There is no straightforward way of doing this yourself.

[~s.o.s~]

The first step in solving the problem is to identify the problem domain properly. Dig out some information on partial fraction decomposition, try to formulate a basic algorithm (the sequence of steps you would follow in achieving the objective).

To start off with, just post a basic algorithm on achieving the desired task and we will definately guide you through the rest of the process.

Maybe the below link will help you in formulating a basic algorithm,

http://www.mathematicshelpcentral.com/lecture_notes/precalculus_algebra_folder/partial_fraction_decomposition.htm

Hope it helped, bye.

[Rashakil Fol]

Yeah, there's a simple and straightforward algorithm for this.

The first step is to understand how to represent a linear system of equations with matrices and how to solve that with a computer program.

Once you understand that, you'll need some way to be able to find all the roots of a polynomial (so that it can be factored). You can't do this exactly -- some solutions will need to be approximate, i.e. 'numerical'. And of course you'll need to use complex numbers.

Then, you'll need to understand how to implement polynomial division (and then implement that on a computer).

Once you've done that, it's a simple matter of taking a rational expression and using polynomial division to turn that into the sum of a polynomial and a remainder, a remainder that looks like [tex]\frac{A_0 + A_1 x + A_2 x^2 + \cdots + A_{n-1} x^{n-1}}{B_0 + B_1 x + B_2 x^2 + \cdots + B_{n} x^n}[/tex] and then find the roots of the bottom polynomial to factor the bottom into [tex]\alpha (x - z_1)(x - z_2)\cdots (x - z_n)[/tex], at which point you can conclude that we're looking for an expansion of the form [tex]\frac{C_1}{x - z_1} + \frac{C_2}{x - z_2} + \cdots \frac{C_N}{x - z_n}[/tex] At this point, just add the fractions together (symbolically), and then you'll get expressions in C_1, C_2, etc in a system of equations with teh A_n's on the right side, which you know how to solve since it's just a system of linear equations, and that was the first step.

Okay?

It's a good programming exercise.

[Lerner]

Any ten year old should be able do it!

HaHaHa!

[~s.o.s~]

What are u exactly trying to prove Mr. Lerner. First you say there is no straightforward way to do it and ask the OP to use an external library. And when the solution is posted you say that even a ten year old kid could do it ???

[Rashakil Fol]

Well, I was kind of joking when I said straightforward :)

But anybody with a good understanding of basic algebra could be taught how to do this and understand how it works.

Also, anybody capable of following instructions can be taught how to do this by hand.

And if you can do this by hand, you better be able to write a computer program that can do it, too, if you call yourself a programmer.

There are still a few important subtle issues, though. One is that of double roots. If you have a double root, then one of your partial fractions must contain a squared denominator. (And with a triple root, you'll also have a cubed denominator, etc.) For example,
[tex]\frac{3x+4}{x^2+10x+25}[/tex]
expands into
[tex]\frac{3}{x+5}-\frac{11}{(x+5)^2}[/tex]
This is arguably not really a partial fraction expansion; you might say the problem has no solution.

Not only does that issue add some complexity to the program, it raises the question: how do you detect a double root? Well that's an annoying problem, if you're finding solutions numerically. So I would recommend finding some magical polynomial root finder algorithm, at least, that recognizes multiple roots (somehow), and use that. But don't even trust that.

So finding partial fraction expansions is a very tricky problem, and it's sensitive to numerical inaccuracy. The good news is, if you do have multiplicated roots but can't recognize them because of numerical inaccuracies, you'll notice when your numerators blow up.

But if you, say, restrict the problem to cubic or quadratic denominators, it's relatively straightforward.

[WolfPack]

What are u exactly trying to prove Mr. Lerner. First you say there is no straightforward way to do it and ask the OP to use an external library. And when the solution is posted you say that even a ten year old kid could do it ???

I think you missed a hint of sarcasm in Lerner's reply. :)

[Lerner]

The comment about a ten year old being able to implement this type of process was meant to be funny, which is why I wrote HaHaHa afterword. It would be a rare ten year old indeed who could use the algorhythm posted by Rashakil Fol to factor polynomials, let alone convert the necessary mathematical expressions into code. I'm glad you weren't in any of my classes during shool if you think the algorhythm posted is straightforward! Correct it may be (and probably is!), straightforward (I don't think so!). In fact finding an appropriate library and finding the appropriate functions/classes/etc to use within the library, etc., probably won't be straight forward either, though it will (probably) be easier than doing it from scratch.

[~s.o.s~]

I think you missed a hint of sarcasm in Lerner's reply. :)

Yeah kind of, these people dont even tell me when they are serious and when they are not. Sudden swings from serious thoughts about how to solve the equation to quoting sarcasm are a bit err... hard to determine.

Anyways like Mr. Rashakil Fol said, the problem stmt is simple or complicated depeding on the feat the original poster is trying to achieve. But assuming that its a college exercise, double root detection wont be necessary i think.

And btw good scarcasm Mr. Lerner, you almost got me there. :mrgreen:

[Lerner]

A well developed sense of humor is not one of my strengths!

I wish the OP good luck and my hat goes off with a respectful bow to all of you who can factor polynomials, by whatever mechanism you use!

[DavidB]

Do you know some conditions ahead of time? For example, will the denominator always be a linear term, such as (x- a)? If so, it would make the program a lot simpler.

You might find something by doing a search on the term "synthetic division".

It is often used for solving the roots of polynomials (deflating them).
Say you have the polynomial P(x) = 0 and you know one root is x = a. You then know P(x) = (x-a)*Q(x) = 0. Q(x) is found by synthetic division, removing the root you already know so that the remaining equation, Q(x), is simpler to solve.

For example, check out sub-routine quadsd on the following page:

http://www.crbond.com/download/misc/rpoly.cpp

You may not be solving for the roots of polynomials, but the synthetic division procedure, itself, might be applicable to your problem. "Numerical Recipes" also provides some code.

Hope this gives you some ideas.

David