Finding root of a polynomial

Let's say I've got $ax^3 + bx^2 + cx + d = 0$

I want to find x for a general-case.

Mathematica gave me a very long solution, and even longer for one which has $kx^4$.

Can you please help me reproduce the algorithm used by Mathematica to generate formula of: $$P(x) = a_0x^0 + a_1x^1 + a_2x^2 + a_3x^3 + \cdots+ a_nx^n$$ i.e., general case of a polynomial.

-
The solutions are indeed messy for solving third and fourth degree polynomial equations. $5th$ degree polynomials (called quintic polynomials) are in general unsolvable. Most likely (though I do not know explicitly how it is programmed), Mathematica estimates the values of roots using, for example Newton-Raphson approximation. See here for more info. –  JavaMan Feb 23 '12 at 17:02
The formulas for degree 3 and degree 4 are known as the Cardano formulas (for degree 3) and the Ferrari formulas (for degree 4). You can find their derivation in Wikipedia. However, there do not exist any such formulas for general polynomials of degree 5 or higher. Note well: it's not that no such formulas are known, it's been proven that no such formulas exist. –  Arturo Magidin Feb 23 '12 at 17:02
The Abel-Ruffini Theorem says that there is no general solution in radicals to polynomials of degree greater than 4. Here's a short implementation note on the factorization algorithm used by Mathematica: reference.wolfram.com/mathematica/tutorial/… –  dls Feb 23 '12 at 17:03
Thank you very much for clarifying this. –  Quantic Programming Feb 23 '12 at 19:03

Here's a (standard) method to treat the cubic case, though it hides some of what is going on, which is basically Galois Theory. You might as well suppose that $a \neq 0$ (otherwise you would be dealing with a quadratic at worse). Hence you can divide through and assume that $a = 1.$ So let's work instead with the cubic $x^3 + ax^2 + bx + c.$ Now set $y = x + \frac{a}{3}.$ Then $x^3 + ax^2 + bx + c$ has the form $y^3 + ey + f,$ and if we can solve for $y,$ we can easily recover $x$ (the constants $e$ and $f$ can be calculated routinely in terms of $a,b$ and $c,$ but we omit the rather tedious details. Hence if we can solve equations of the form $x^3 + ax + b =0,$ we can deal with the general cubic, and we may as well suppose that $b \neq 0,$ for the case $b =0$ is easy. To solve the equation $x^3 + ax + b = 0$ when $b \neq 0$, set $x = u+v.$ The equation may then be written as $(u^3 + v^3) + b + (u+v)(3uv+a) = 0.$ We can try to solve separately, but simultaneously, $(u+v)(3uv+a) = 0$ and $u^3 +v^3 = -b.$ Note that $u +v \neq 0$ since $b \neq 0,$ so we need $uv = -\frac{a}{3}$ and $u^3 + v^3 = -b.$ Hence $(t -u^3)(t-v^3) = t^2 +bt -\frac{a^3}{27}$, and two solutions do have a simultaneous solution, with $u^3$ and $v^3$ being the roots of a quadratic.

-

The trick is transforming the general cubic equation into a new cubic equation with missing $x^2$ term is due to Nicolo Fontana Tartaglia.

Apply the substitution

$$x = y - \frac{b}{3a}$$

then we get

$$a\left(y-\frac{b}{3a} \right)^3 + b\left(y-\frac{b}{3a} \right)^2+c\left(y-\frac{b}{3a} \right)+d = 0$$

which simplifies to

$$ay^3 + \left( c-\frac{b^2}{3a}\right)y+ \left(d + \frac{2b^3}{27a^2} - \frac{bc}{3a} \right) = 0$$

This is called a depressed cubic equation, because the square term is eliminated. It is much easier to use this and then find the roots. (back substitute to get the roots in terms of $x$)

For example $$2x^3-18x^2+46x-30=0$$

Substitute $x=y+3$ and simplify this cubic equation to

$2y^3-8y=0 \Rightarrow y=0,2,-2$ which then gives the roots as $x=1,3,$ and $5$.

-
Presumably, this is the "very long solution" given by Mathematica to which the OP refers. How does this answer the question? –  JavaMan Feb 23 '12 at 17:25
Nitpicking is good, there is room for progress! –  Kirthi Raman Feb 23 '12 at 22:48
:-) Nitpicking is indeed good! –  JavaMan Feb 23 '12 at 23:34