2

I am trying to code an algorithm that does not use the cubic formula in order to determine a cubic function $(ax^{3} + bx^{2} + cx + d)$ roots. I came across an algorithm (https://rosettacode.org/wiki/Roots_of_a_function#Java) where a range is given for where the roots may lie. From then, the algorithm searches inbetween this range. (If anyone knows the name of this algorithm that will also be a massive help!)

However, I would like to improve this somehow by calculating a suitable range for the algorithm to search within so that this does not rely on input and so that many different coefficients can be input and an effective range can be chosen. Is there any way to do this reasonably quickly, looking at coefficients and not actually solving it? I'm not looking for you to write the program for me, just to point me to a way to do this. Thank you :D

Darío A. Gutiérrez
  • 3,863
Karen
  • 21
  • 1
    Here are some general methods: https://en.wikipedia.org/wiki/Properties_of_polynomial_roots#Bounds_on_.28complex.29_polynomial_roots – Jean-Claude Arbaut Sep 19 '16 at 18:49
  • 1
    Related: Range of root of cubic equation. – dxiv Sep 19 '16 at 19:37
  • If you can find f(x) > 0 and f(y) < 0 there is a root between x and y. If $f(x) = ax^3 + bx^2 + cx + d$ then $f'(x) = 3ax^2 + 2bx + c$ which can be solved to find max/min x1 < = x2. (unsolvable the f(x) is strictly increasing or decreasing). If $x1$ and $x2$ are on opposite sides of 0 there is a root between them and one less than x1 and one greater than x2. If they are both same side of 0 or unsolvable there is only one root. – fleablood Sep 19 '16 at 19:43
  • Note that a cubic polynomial with real coefficients will have at least one real root. Perhaps you are asking about finding a real interval that bounds all real roots of a real cubic. Another sensible problem is to find a bound in the complex plane (e.g. a disk centered at the origin) which contains all complex roots (which can be done even for a cubic with complex coefficients). – hardmath Sep 22 '16 at 00:51
  • "From then, the algorithm searches inbetween this range. (If anyone knows the name of this algorithm that will also be a massive help!)" Perhaps you are thinking of the bisection method or related approaches. – hardmath Sep 22 '16 at 00:53

2 Answers2

2

If $|x| > 1$ and $|x| > (|b|+|c|+|d|)/|a|$, then

$|ax^3| > (|b|+|c|+|d|)|x^2| > |bx^2| + |cx| + |d| \ge |bx^2+cx+d|$

and so $|f(x)| \ge |ax^3| - |bx^2+cx+d| > 0$.

This shows that the roots $x$ of $f$ satisy $|x| \le \max \{1, (|b|+|c|+|d|)/|a| \}$

mercio
  • 50,180
0

Well here is something. Maybe not efficient.

$f(x) = ax^3 + bx^2 + cx +d $ will have the same roots as $-ax^2 - bx^2 - cx - d$ so we might as well assume $a > 0$.

Solve for $3ax^2 + 2bx + c = 0$

$x_1,x_2 = -\frac {2b \pm \sqrt{b^2 - 3ac}}{3a}$

if $b^2 \le 3ac$ there is only 1 root. If $f(x_1) > 0$ and $f(x_2) < 0$ (vice versa if $a < 0$). There will be 3 roots: One in $(-\infty, x_1)$, one in $(x_1, x_2)$ and one in $(x_2, \infty)$.

Other wise there is only one root.

So you have three or one ranges which will have exactly one root.

Just guess a bunch of $x$ values within these ranges to fine tune. If $f(x)$ and $f(y)$ are on opposite sides of zero the root will be between them. Otherwise it will not be.

===

fleablood
  • 124,253
  • You missed the case where there are exactly two roots; this can occur when the derivative has a double root. Thus you should have split into $b^2<3ac$ and $b^2=3ac$. Note that there can still be just one root when $b^2=3ac$, if the function is a perfect cube. – Ian Sep 19 '16 at 20:29
  • If that had happened then you would have found the root and you wouldn't need to continue to find the range as you found the root exactly. As the question was to find ranges, I didn't miss that so much as chose not to explore it renders the question of finding ranges unnecessary. – fleablood Sep 19 '16 at 21:32