Given a(x-cubed) + b(x-squared) + cx + d = 0, what is the forumula for
solving for the roots?

I've found http://mathworld.wolfram.com/CubicFormula.html, but don't understand it.

---

Request for Question Clarification by mathtalk-ga on 25 Nov 2004 07:54 PST

Hi, donkan-ga:

It would probably be expeditious for you to say how far you can follow
the explanation given there.

The first step is to divide through by a.  Of course, if a = 0, then
the equation is not actually a cubic equation (because the
third-degree term would be missing).

So is it clear that you only need to solve a "monic" (leading
coefficient = 1) cubic equation?

regards, mathtalk-ga

---

Clarification of Question by donkan-ga on 25 Nov 2004 08:10 PST

Yes.

---

Clarification of Question by donkan-ga on 25 Nov 2004 08:13 PST

I don't really care about following the MathWord explanation. I'm
assuming that there is a formula for these equations such as there is
for solving quadratic equations. Am I wrong?

donkan

---

Request for Question Clarification by mathtalk-ga on 25 Nov 2004 12:18 PST

Hi, donkan-ga:

In principle, yes, one could write a "formula" involving square roots
and cube roots, based on the coefficients of a cubic polynomial, which
yields one or more of its roots.  I don't recall ever seeing it
written out this way.  In practice memorizing such a formula would be
significantly harder than remembering the procedure (recipe) for
solving the general cubic.

To get a feel for what the difference is, it is like the procedure for
completing the square for solving a quadratic, instead of plugging
into the quadratic formula.  However since the procedure for solving
the general cubic has an intermediate step to solve a quadratic
equation, this "extra" step in the procedure translates into a big
jump in complexity if we require the quadratic formula (for this
intermediate solution) to be substituted in place of all the
consequent references to it.

You will find a brief explanation of Cardano's "formula" for solving
cubic equations (mixed in with much else, unfortunately) in roughly
the last quarter of my Answer to this earlier Question:

[Google Answers: Integral Equation]
http://answers.google.com/answers/threadview?id=374299

For the list price you have currently offered, I'd be willing to
reprise that method of solution here.

regards, mathtalk-ga

---

Clarification of Question by donkan-ga on 25 Nov 2004 13:36 PST

Now, that's WAY over my head. But since you are "of an algorithmic
turn of mind", I should tell you why I've asked my question. I'm
learning Python, and have a simple script to solve quadratic
equations:

======================================================
# solveQuadraticEquations.py
# i.e., equations of form a*x**2 + b*x + c

from cmath import sqrt

#y,m,d = raw_input("Enter a date(YYYY-MM-DD): ").split("-")
a,b,c = raw_input("Enter the coefficients a,b,c: ").split(",")
a,b,c = int(a), int(b), int(c)

print "equation is (%d*x**2) + (%d*x) + (%d) = 0" % (a,b,c)
a,b,c = float(a), float(b), float(c)
print "b**2 - 4*a*c =", b**2 - 4*a*c, 
if b**2 - 4*a*c < 0:
    print "It's negative, and therefore the roots are imaginary."
else:
    print "It's non-negative, and therefore the roots are real."

root1 = (-b + sqrt(b**2 - 4*a*c))/(2*a)
root2 = (-b - sqrt(b**2 - 4*a*c))/(2*a)

#print "roots are %f and %f" % (root1, root2)

print "They are", root1, "and", root2
===================================================

I was looking for something harder but practical (however I just
realized that my Casio calculator easily solves cubic equations).

So I'd like to give it a try with what you can do for me.

donkan

---

Request for Question Clarification by elmarto-ga on 25 Nov 2004 16:37 PST

Hi donkan,
There certainly is a formula that solves for the roots of a cubic
equation, which is given in the Mathworld page, although a few
substitutions need to be done in order to have the solution in terms
of the coefficients of the equation. Would you like me to post that
solution? Are you interested in understanding the proof that it really
is the solution?

Note also that there can be imaginary roots. How does your program handle them?

Best regards,
elmarto

---

Clarification of Question by donkan-ga on 25 Nov 2004 18:08 PST

I'm most interested in the formula, in an algorithmic form. If you can
help me understand it's proof, that would be a bonus.

Python has a module, cmath, for complex numbers, so the imaginary
roots would not be a problem, I'm thinking.

donkan

Hi, donkan-ga:

As we discussed in an early Clarification, the leading coefficient of
the cubic polynomial may as well be 1:

x^3 + a x^2 + b x + c = 0

because one can always divide both sides by the nonzero "leading" coefficient.

Note: If c = 0 in this equation, then simply factoring out x = 0 as
one root will reduce the remaining equation to a quadratic one.

Reduction to  z³ + Mz = N
=========================

Let x = z - a/3, and substitute:

(z - a/3)^3 + a (z - a/3)^2 + b (z - a/3) + c = 0

z^3 - 3(a/3)z^2 + 3(a^2/9)z - (a^3/27)
    +     a z^2 - 2(a^2/3)z + (a^3/9)
                +       b z - (ab/3)
                            +   c     = 0

When like terms are collected, the coefficients of z^2 will cancel out:

z^3 + (b - a^2/3)z + (2a^3/27 - ab/3 + c) = 0

So, if we define:

  M  =  b - a^2/3

  N  =  -(2(a^3)/27 - ab/3 + c)

then:

  x is a root of x^3 + a x^2 + b x + c = 0
  
  if and only if
  
  x = z - a/3 and z is a root of z^3 + Mz = N

Note:  Once again we observe that if N = 0, then z = 0 is one of the
roots and by factoring out z, we can reduce the problem to solving a
quadratic equation.

On the other hand, if M = 0, then our equation is simply z^3 = N.  So
we can find the three roots z by taking the three complex cube roots
of N.

In the next section we will want to assume M is not zero.

Auxiliary Quadratic
===================

Let z = w - M/(3w), and substitute:

(w - M/(3w))^3 + M(w - M/(3w)) = N

w^3 - 3(M/(3w))*w^2 + 3(M/(3w))^2*w - (M/(3w))^3 + Mw - (M^2)/(3w) = N

w^3 - Mw            +  (M^2)/(3w)   - (M/(3w))^3 + Mw - (M^2)/(3w) = N

Thus after cancellations:

w^3 - ((M^3)/27)/w^3 = N

But this can be treated as a quadratic equation in w^3:

(w^3)^2 - N(w^3) - (M^3)/27 = 0

Applying the quadratic formula will give two solutions for w^3.

Taking three cube roots of each (counting complex values) gives six solutions!

However these are actually three pairs of duplicate roots.

You only need to work with one of the two quadratic roots.

So:

  z is a root of z^3 + Mz = N
  
  if and only if
  
  z = w - M/(3w) and w^3 is a root of (w^3)^2 - N(w^3) - (M^3)/27 = 0

Note:  If M is nonzero, then the roots of the auxiliary quadratic in
w^3 will also be nonzero.  Since we use division by w to define the
substitution for z, it makes sense to have eliminated cases where M =
0 in the "reduction" step.

A note about complex arithmetic
===============================

A program based on the outline above would need to perform complex arithmetic.

This is so, even if all the roots of the cubic polynomial turn out to be real.

There are some more complicated procedures that can work around this.

[A cubic polynomial with real coefficients must have at least one real root.]


regards, mathtalk-ga

mathtalk, now I think I can write that program. You've really gone
above and beyond. Thank you!

donkan

Let me suggest a simple improvement to your routine for solving the
quadratic equation.  One can sometimes encounter a set of coefficients
for which b and sqrt(b^2 - 4ac) are nearly equal in absolute value, so
that exactly one of the expressions:

  -b + sqrt(b^2 - 4ac)

  -b - sqrt(b^2 - 4ac)

will involve a substantial amount of subtractive cancellation.

The suggestion is to find one of the roots using the alternative in
which the same sign is chosen for sqrt(b^2 - 4ac) as will agree with
-b (thus avoiding any subtractive cancellation in computing that
root).  Then compute the other root from the first by using the fact
that the product of both roots is c/a:

  2nd root = (c/a)/(1st root)

This precaution guarantees that you will obtain the best precision for both roots.

regards, mathtalk-ga

Thanks for your insightful suggestion, mathtalk.

BTW have you given up on my question?

donkan

Hi, donkan-ga:

Note that it was elmarto-ga who offered to make "a few substitutions"
in the MathWorld page results "in order to have the solution in terms
of the coefficients of the equation."  I did not give up on your
Question so much as I was standing aside waiting to see what
elmarto-ga would provide.

If you are mainly interested in programming variations on solving
polynomial equations in Python, I'll be happy to offer some
suggestions.  It's not quite clear to me how general you want the code
to be.  Judging just by your existing code for the quadratic formula
might not lead to the correct generalization, esp. as you mentioned
the possibility of using complex numbers.

A general quadratic would have complex coefficients, and applying the
quadratic formula would require extracting square roots of complex
numbers.  This might be a good place for you to start.

Basically the solution of the general cubic polynomial (complex
coefficients) would require as subroutine the solution of the general
quadratic, so that's another reason to begin with problems of low
degree but general coefficients.

A robust general solver for polynomials poses all sorts of interesting
numerical issues, e.g. when you are working with floating point
computation, how do you tell the difference between a double root and
two distinct roots that are very close?

But I'll let you lead the way.

regards, mathtalk-ga

Thanks for getting back to me, math-talk.

"A general quadratic would have complex coefficients, and applying the
quadratic formula would require extracting square roots of complex
numbers.  This might be a good place for you to start."

I just tried adjusting my program for solving quadratic equations to
the most general case. It has no problem with complex (and
non-integer) coefficients. And no problem computing square roots of
complex numbers.

"A robust general solver for polynomials poses all sorts of interesting
numerical issues, e.g. when you are working with floating point
computation, how do you tell the difference between a double root and
two distinct roots that are very close?"

Yes, I see what you mean, but I wouldn't mind if a double root shows
up as two distinct roots that are very close. Also, the new version of
Python, 2.4, which I downloaded today, has a decimal module that can
easily compute accurately to 100 digits; I haven't figured out how to
use it yet, however.

So I'd like to see your robust general solver.

Thanks,

donkan

Hi, donkan-ga:

Just to clarify my suggestion, if you have a question you'd like
answered, and I think I can do a good job in the amount of time
commensurate with the price you've offered, I'll be happy to do my
best.

By offering a low price for a very open-ended discussion, you invite
interested Researchers and Commenters to post a variety of remarks
that you may find helpful.  There's no harm in that.

I'm sure you can appreciate that there's a big gap between attempting
to explain some specific point on that MathWorld page that you find
obscure, and writing a practical root-finding program for you.  I
think that if you make a skillful use of subroutines, you will find
the discussion on the MathWorld page does give a workable approach to
computing the roots of a cubic polynomial.

The essence of the algorithm is to reduce such a problem to finding
roots of a cubic polynomial in the special form:

  z³ + Mz = N

It turns out that these roots can be found by solving an "auxiliary
quadratic" polynomial, and I'd be happy for the price you've offered
to explain why this is so.

My earlier Comment on an implementation detail for the quadratic
formula was meant to illustrate that there are programming issues not
addressed by a single mathematical expression for the roots.  I
applaud your selection of root-finding problems to sharpen your Python
programming skills; Python is a neat language, and root-finding
illustrates many of the important topics in numerical analysis.

regards, mathtalk-ga

"The essence of the algorithm is to reduce such a problem to finding
roots of a cubic polynomial in the special form:

  z³ + Mz = N

It turns out that these roots can be found by solving an "auxiliary
quadratic" polynomial, and I'd be happy for the price you've offered
to explain why this is so."

Please do so.

Thanks,

donkan