[RESOLVED] Cubic Polynomials

[Sean12345]

From reading the other threads this question appears simple.

Is there any other way to factorise a cubic polynomial than by using the factor theorem?

I ask this because the factor theorem can be quite a tedious method if the number isn't an integer. For example if the cubic polynomial i am trying to solve is P(x) = x³+x²-4x-4 then it wouldn't take long to figure out one of the factors.
P(1) = 1³+1²-(4x1)-4 = -6 ≠ 0
P(-1) = (-1)³+(-1)²-(4x-1)-4 = 0 Therefore (x+1) is a factor.

However if the cubic polynomial i am trying to solve is P(x) = 3x³-8x²-17x+14 it would take a long amount of time to find one of the factors.
P(1) ≠ 0
P(-1) ≠ 0
P(2) ≠ 0
P(-2) ≠ 0
P(7) ≠ 0
P(-7) ≠ 0
After a long period of time you would find that P(3/2) = 0 Therefore (3x-2) is a factor. Surely there is a much quicker way?

[jemidiah]

You could use a numerical method like Newton's Method (http://en.wikipedia.org/wiki/Newton's_method) to find one (or more) of the roots. It requires some familiarity with Calculus to understand and apply, but not too much.

There's also a cubic equation (like the quadratic equation) but it's horrendously long.

Finally, you could search for one negative, and one positive value of P, and search between them for a root.

Hope one of these helps!

[Sean12345]

Thanks,

I'll look at all of the methods suggested even though some of them sound complicated (Calculus ^^) and see which one most suited to me. Nice, quick reply though. Thanks jemidiah.

[jemidiah]

By the way, here's the "cubic equation" (http://en.wikipedia.org/wiki/Cubic_equation#Solution_in_terms_of_a.2C_b.2C_c.2C_and_d) version that would be somewhat familiar to you. You end up substituting a, b, c, and d into dummy variables named q, r, s, and t, which are in turn substituted into your three roots named x1, x2, and x3.

The 3rd method I listed would probably be the most effective "by-hand" method for the equations you look to be dealing with, while the cubic equation one would probably be best for a computer. The Newton's Method one was what first came to mind, and would be effective, but the cubic equation is simply easier (and infinitesimally more accurate in some cases).

The big advantage of the Newton's Method idea is that it works for n-degree polynomials (at least for real roots, without some manipulation), and not just 3rd degree ones.

Good luck! If you'd like an explanation/example on one of them I'd be happy to write one up.

[Sean12345]

The "cubic equation" seems pretty self explanatory from what i have read and i don't really want to divulge into Newton's Method. If you wouldn't mind could you please explain the third method in detail with an example/s as it would be handy to use 2nd to the Factor Theroem on harder polynomials that im doing "by-hand".

Much appreciated.

[jemidiah]

Sure.

I don't know if there's a technical name for this method, but I'm sure it's a pretty standard root finding approach.

The basic idea is that a cubic polynomial will *always* have a point where it goes from positive to negative. Why?

Assume a is positive for the moment. Now let x go to negative infinity. The ax3 term will eventually be much, much larger (in absolute magnitude) than the rest of the terms in the polynomial. a(-infinity)3 goes to -infinity (the cube of a negative number is negative) so that P(-infinity) goes to -infinity.

Now let x go to positive infinity, and the same thing happens: P(infinity) goes to infinity. If a is negative, the opposite happens in both cases, but the polynomial is still positive for some values and negative for others.

By the way, this concept of P("some number") goes to "another number" is basically the concept behind limits, which you'll encounter in your first Calc (and perhaps Pre-Calc) course.

So, for some value the function P is positive, and for some value P is negative. We know P is continuous (that is, it doesn't have any breaks in it, or it's a smooth curve; another Calculus concept), so somewhere it must go through the x-axis--that point is the root we're trying to find.

Note that there can be up to 3 of these points, but in any *cubic* (or odd-degree) polynomial there *must* be at least 1 of these points.


The trick to finding this point is to narrow down the range the point might be in (the example will make this bit more clear). You start with a range of (-inf, inf) [that is, the range from negative infinity to positive infinity, not including the infinities (your argument x is assumed to be real or perhaps imaginary, and infinity is not a real number)]. From there, you choose new beginning and end points, with the goal of always trying to make them have opposite signs in mind. When they have opposite signs, you whittle away at the range until you finally get incredibly close to (or exactly on) the root.


Example 1:
Let P(x) = x³+x²-4x-4
Range: (-inf, inf)
Try P(-100), which is -989604. Note that, when graphed, P(x) starts in the lower left at negative infinity, and goes to the upper right at positive infinity (since a is positive [a=1]). So, the range should make P(lower bound) negative, and P(upper bound) positive.
Try P(100), which is 1009596.

We now know the root we're looking for is in the range (-100, 100) [the -100, and 100 can't be the root, since P(them) <> 0].

To whittle away at this range efficiently, let's use a modified binary search. Basically, you look at the point in the middle of the range every time and proceed accordingly.

The point in the middle of the range is 0, and P(0) = -4. So, our root is definitely in the range (0, 100), since P(0) is negative and P(100) is positive.

Do this again to find P(50) = 127296, giving the range (0, 50).
P(25) = 16146, giving (0, 25).
P(12.5) = 2055.375, giving (0, 12.5).
P(6) = 224, giving (0, 6) [you don't always have to take the middle point, it's just when the search algorithm is at its fastest, at least for a computer. To avoid fractions as much as possible, you can round]
P(3) = 20, giving (0, 3)
P(1) = -6, giving (1, 3)
P(2) = 0. We found the root!


Example 2:
Let P(x) = 3x³-8x²-17x+14

Try start range of (-1, 10)
P(-1) = 20, P(10) = 2044. Oops, the point isn't in this range; let's expand the lower bound since it's too close to 0.

Try (-10, 10)
P(-10) = -3616, giving (-10, 10) as a range where the root must be. But, we also know P(-1), giving (-10, -1).
P(-5) = -476, giving (-5, -1)
P(-3) = -88, giving (-3, -1)
P(-2) = -8, giving (-2, -1)
P(-1.5) = 11.375, giving (-2, -1.5)
P(-1.75) = 3.171875, giving (-2, -1.75)
P(-1.875) = -1.875, giving (-1.875, -1.75)
...
P(-1.828427) ~ 0, giving a root at about -1.828427.

I checked a couple times, and 3/2 doesn't look like it's a root of this polynomial. Maybe a number was typed wrong, which is probably why this root is so weird. Edit: 2/3 is a root, just noticed. This algorithm gave one of the weirder roots, which is one of its pitfalls. To work wonderfully in every case, the roots *all* have to be simple rational numbers (in this case, two of the roots are weird numbers, and the algorithm happened to find one of them)

In any case, you'll either get incredibly close to the root, or be close enough to guess it yourself. Sometimes you'll only be able to find a range like in the second example--but, if you know there's another root out there, you can simply mess with the ranges until you find it (in this case, that would mean picking (2, 10) or so at first).

Hope this helps some.

[jemidiah]

Sorry for the double post, but the other one seemed long enough....

Note: to be honest, this'll probably confuse you, but I got started and wanted to finish my thoughts. Please ignore it if it seems too convoluted.


There's an interesting (if cryptic) addition one can make to the above algorithm, so that you can find (or restrict to an arbitrary margin) any root you wish. However, it's probably too complicated to be done by hand most of the time.

Assume a is positive. If a is negative, multiply the function by negative 1--P(x) and -P(x) have the same roots anyway, since P(a) = 0 = -P(a), satisfying the Factor Theorem.

Case I: 1 real root, 2 imaginary roots. The algorithm will find the 1 real root--thus finding all real roots.

Case II: 3 real roots. The algorithm can find any of these three roots. It must have some knowledge of the location of the rest of the roots. How can it gain this knowledge? It can figure out (using a simple derivative, again from Calculus) where the polynomial changes direction.

Given P(x) = ax3 + bx2 + cx + d, we know that P changes direction when P'(x) = 0, where P'(x) is the derivative (or slope function) of P(x). P'(x) = [from Calc.] 3ax2 + 2bx + c. This is a quadratic, and the roots may be found with standard methods, which will yield points at which the function will change direction, namely x1 and x2. If x1 and x2 are different, let's call the smaller of the two roots x1 and the larger x2, so that [if x1 <> x2] x1 < x2.

Subcase I: x1 = x2. In this case, P changes directions twice instantaneously at the point x1, meaning it does not actually switch directions--it merely pauses at x1 [this is a bit mystical now, but derivatives makes it much clearer]. That is, the function doesn't "go back down" for a while after it comes up from negative infinity; it continues on to positive infinity after briefly pausing. So, it never has a chance to get to the x-axis more than once, meaning the point you found is the one and only root anyway--meaning this isn't even a proper subcase in the first place.

Subcase II: x1, x2, and root1 are not all distinct. That is, x1 = root1 or x2 = root1 [x1 = x2 has already been covered, which further implies that x1 = x2 = root1, so for this subcase it is safe to assume x1 <> x2]. In this case, x1 or x2 (respectively) is a double root. Why? Because the function must lightly touch the axis at a root and turn back the way it came--leaving room for only 1 more real root when it turns the 2nd time [remember, x1 <> x2, so the function must turn twice] as it crosses the x-axis again. Where is the final root?

Subsubcase I: x1 = root1. Going from negative infinity all the way up near (slightly before) x1, the function stays negative but nears the x axis. At x1, the function touches the x axis, and then turns back, going down until it reaches x2, at which point it turns again, this time heading back up to positive infinity. So, the function goes from negative at x2 to positive at some later point. So, search the range (x2, infinity) to find the final root.

Subsubcase II: x2 = root2. Going from positive infinity (heading right to left instead of the usual left to right) all the way up near (slightly before) x2, the function stays positive but nears the x axis. At x2, the function touches the x axis and then turns back, going up until it reaches x1, at which point it turns again, this time heading back down to negative infinity. So, the function goes from positive at x1 to negative at some earlier point. So, search the range (-infinity, x1).

Subcase III: x1, x2, and root1 are all distinct. That is, none of x1, x2, and root1 are equal.

Subsubcase I: P(x1) < 0 and P(x2) < 0. Both turning points occur when the function is negative, meaning the function only goes from negative to positive once [draw it out if this seems incorrect]. So, there was only one root anyway--and this isn't really a proper subsubcase.

Subsubcase II: P(x1) < 0 and P(x2) > 0. This cannot occur since the function decreases as it goes from x1 to x2, while it appears to have increased. So, this can never occur--and this isn't really a proper subsubcase.

Subsubcase III: P(x1) > 0 and P(x2) > 0. The same thing as subsubcase I applies here; simply invert the graph.

Subsubcase IV: P(x1) > 0 and P(x2) < 0. The function is negative near negative infinity and positive near positive infinity. So, (-inf, x1), (x1, x2), and (x2, inf) are all valid ranges, since there is a sign change between the endpoints of each range. Check each range in turn (though of course not the one that contains root1).


Done! This algorithm can find to an arbitrary precision all real roots of a cubic polynomial, in very short order.

[Sean12345]

Great posts. I fully understood the first method, the second im still trying to get my head around. Yesterday i read up on the other methods you talked about in your first post on this thread (i.e. "Newton's Method" and the "cubic equation") just out of interest ^^. It turns out both these methods are on my course so ill look at them when my time comes. The method explained in detail is perfectly explained and im sure to use it in the future. The addition seems good so ill try and get my head round it.

Thanks Jemidiah.

[jemidiah]

Here's a much more elegant explanation of my previous post (<--- is a perfectionist).

Succinctly: Let x1 and x2 be the point(s) where P'(x) = 0, and let x1 <= x2 by choice. Check the three ranges (-inf, x1), (x1, x2), and (x2, inf) for roots using the above algorithm, as well as the points x1 and x2. You will always find all real roots in this manner.

Verbosely: from Calculus, we can calculate when the function changes direction [see previous post for details if interested]. A cubic polynomial does so exactly 2 times--perhaps, both of them are at the same point. Call these turning points x1, and x2, where x1 <= x2 by choice.

We know that roots have to occur in a range where the function goes from positive to negative (or negative to positive). The function can only cross the x-axis to make a root when it is negative and going positive, or when it's positive and going negative--that is, during times when the function is going in one direction already and happens to be on the wrong side of the axis.

Each cubic polynomial has (up to) three ranges, during which time it is moving in one particular direction: (-inf, x1), (x1, x2), and (x2, inf). Perhaps during part of this range, the function will be negative while increasing or positive while decreasing--who knows. The point is, the potential exists for a root to exist in one of those ranges--and only one root would exist. So, search those three ranges, and you'll come up with (up to) three roots.

More formally,
Case 1: There is a root in all three ranges (-inf, x1), (x1, x2), and (x2, inf). There must be only one root in all three ranges, since any more would violate the fact that a cubic polynomial can have at most 3 real roots. As such, the root finding algorithm will find all 3 roots*.

Case 2: There is a root in 1 of the above ranges. The algorithm will find the 1 root in the range that contains the root. The range containing the root can be determined by checking which range changes sign*.

Case 3: There is no root in the above ranges. Then, the root(s) must be at x1 or x2. So, check these values as roots, and you will determine all real roots by default. Note that x1 or x2 could be a double (or triple, in the case of x1=x2) root.

*The function never changes direction in a given range. So, given a range (r1, r2) from above...
-if P(r1) < P(r2), the function increases from r1 to r2, and any point r1 < r < r2 satisfies P(r1) < P(r) < P(r2)
-if P(r1) > P(r2), similarly P(r1) > P(r) > P(r2)
In either case, the function will only be positive or negative in a given range if it is positive or negative at the endpoints of the range. So, there is only a root in the range if there is a sign change at the endpoint of the range (this only applies for these specific ranges, which were chosen carefully for this purpose).