View Question
Q: Need general solution to cubic equation ( Answered ,   6 Comments )
 Question
 Subject: Need general solution to cubic equation Category: Science > Math Asked by: donkan-ga List Price: \$5.00 Posted: 25 Nov 2004 04:23 PST Expires: 25 Dec 2004 04:23 PST Question ID: 433886
 ```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```
 Answer
 Subject: Re: Need general solution to cubic equation Answered By: mathtalk-ga on 02 Dec 2004 06:07 PST Rated:
 ```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```
 donkan-ga rated this answer: and gave an additional tip of: \$10.00 ```mathtalk, now I think I can write that program. You've really gone above and beyond. Thank you! donkan```

 Comments
 Subject: Re: Need general solution to cubic equation From: mathtalk-ga on 25 Nov 2004 20:46 PST
 ```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```
 Subject: Re: Need general solution to cubic equation From: donkan-ga on 30 Nov 2004 13:31 PST
 ```Thanks for your insightful suggestion, mathtalk. BTW have you given up on my question? donkan```
 Subject: Re: Need general solution to cubic equation From: mathtalk-ga on 30 Nov 2004 16:46 PST
 ```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```
 Subject: Re: Need general solution to cubic equation From: donkan-ga on 30 Nov 2004 22:36 PST
 ```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```
 Subject: Re: Need general solution to cubic equation From: mathtalk-ga on 01 Dec 2004 10:32 PST
 ```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```
 Subject: Re: Need general solution to cubic equation From: donkan-ga on 01 Dec 2004 12:21 PST
 ```"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```
 Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service. If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for

 Google Home - Answers FAQ - Terms of Service - Privacy Policy