0

Given the cubic function: y = -3 + 10x - 7x^2 + 1x^3, how can I find a value of x when y = 0.5?

WolframAlpha shows 3 possible solutions when y = 0.5: 0.535, 1.256 and 5.209.

How did WolframAlpha calculate this?

Approximations are fine.

Ultimately I need to calculate this step by step in code, so showing your work is a huge help.

I'll be solving for x thousands of these with different coefficients and y values. In my particular case, y will always be between 0 and 1 and the only x I care about will also be between 0 and 1.

Plot

Xoque55
  • 4,384
Ryan
  • 163
  • 1
    What sort of polynomial equations do you need to be able to solve? degree $3$ max? do you know that they always have a solution? – Asinomás Dec 18 '15 at 23:01
  • 1
    If approximations are good enough, try Newton's method. – rogerl Dec 18 '15 at 23:02
  • Yes, they will always have a solution between 0 and 1. Yes, always 3 max. – Ryan Dec 18 '15 at 23:02
  • 1
    Well, you can use cardano's formula to obtain in explicitly or (much easier, use newton's method or binary search to aproximate it) – Asinomás Dec 18 '15 at 23:03
  • Going to need some help with this. Can anyone go step by step through a possible solution? – Ryan Dec 18 '15 at 23:04
  • 1
    what programming language do you need it in? – Asinomás Dec 18 '15 at 23:07
  • Step by step math would be fine. Any pseudo-code, even better. I'll port it to PHP eventually. I just need approximations for specific points on a regression for a ton of datasets. Thanks for your help. – Ryan Dec 18 '15 at 23:09
  • The challenge is that, in general, polynomials even in one variable cannot be solved explicitly for degree $5$ of higher. If you are always dealing with a cubic, then it's easier (there are explicit formulas). If you are always dealing with this cubic, then you could write the formula in terms of these constants. If you need an algebraic solution or a numerical solution, that also makes a difference. – Michael Burr Dec 18 '15 at 23:19
  • The equation will always match the above exactly (cubic). The coefficients will change and the y value. I'll always be solving for the lowest value of x > 0. And the lowest values of x > 0 will be < 1. – Ryan Dec 18 '15 at 23:21

3 Answers3

1

Instead of finding $x$ such that $-3 + 10x - 7x^2 + 1x^3 = 0.5$, it's more conventional to move the $0.5$ over and equivalently look for $x$ that satisfies $ -3.5 + 10x - 7x^2 + 1x^3 = 0$. This task is called finding the roots of a polynomial.

The only bulletproof way I know of is to use Sturm's theorem and use binary search to zoom in on the roots. But you can usually get away with binary search (if you know two bounds of the root with opposite sign under the polynomial) or Newton's method (if you know a point close to the root and the polynomial is well-behaved nearby.).

NovaDenizen
  • 4,216
  • 15
  • 23
  • Thanks for taking a look at this. Could you walk roughly through how you actually reach something close to 0.535 for the above? If it's a binary search, can you show a few steps for me? – Ryan Dec 18 '15 at 23:31
  • Let $p(x)$ be the adjusted polynomial. $p(0) = -3.5$ and $p(1) = 0.5$, so there must be a root $r$ where $0 < r < 1$. $p(0.5) = -0.125 < 0$, so $0.5 < r < 1$. $p(0.75)= 0.484375$ so $0.5 < r < 0.75$. Now the midpoint of the range is $0.625$. $p(0.625) = 0.259\dots > 0$ so $0.5 < r < 0.625$. – NovaDenizen Dec 21 '15 at 16:43
1

For sure, Cardano method is the general way to get the solutions (real or complex).

In the case where the equation has three real roots, you can also use the trigonometric method. In the case you posted, the solutions will then be given by $$x_1=\frac{7}{3}+\frac{2}{3} \sqrt{19} \cos \left(\theta\right)$$ $$x_2=\frac{7}{3}+\sqrt{\frac{19}{3}} \sin \left(\theta\right)-\frac{1}{3} \sqrt{19} \cos \left(\theta\right)$$ $$x_3=\frac{7}{3}-\sqrt{\frac{19}{3}} \sin \left(\theta\right)-\frac{1}{3} \sqrt{19} \cos \left(\theta\right)$$ using $$\theta=\frac{1}{3} \tan ^{-1}\left(\frac{3 \sqrt{2127}}{301}\right) $$which numerically are $$x_1\approx 5.20935\quad \,\quad x_2\approx1.25552\quad \,\quad x_3\approx0.535132$$

If only one real root exists, then it can be obtained using hyperbolic functions.

For the ordering of the roots when all are real, you could look at the comments to this question of mine.

Community
  • 1
Claude Leibovici
  • 260,315
0

User Izumi Kawashima at StackOverflow pointed me to EasyCalculation.com's JavaScript algorithm (below). This made my job super easy.

His question is to find an even faster algorithm, so if you can think of one, I'm sure he'd appreciate it.

Posted here for posterity.

function positiveCube(s){
  var d3 = 1 / 3.0;
  return (s < 0) ? -Math.pow(-s, d3) : Math.pow(s, d3);
}

var p = [2,3,4,5]; // f(x) = 2 + 3x + 4x^2 + 5x^3
var roots = [];    // found real roots will be pushed

var a = p[3];
var b = p[2] / a;
var c = p[1] / a;
var d = p[0] / a;
var b2 = b * b;
var q = (3.0 * c - b2) / 9.0;
var r = (-27.0 * d + b * (9.0 * c - 2.0 * b2)) / 54.0;
var q3 = q * q * q;
var discrim = q3 + r * r;
var term1 = b / 3.0;

if (discrim > 0) {
  // One real, two complex roots
  var s, t;
  var discrimsq = Math.sqrt(discrim);
  s = r + discrimsq;
  t = r - discrimsq;
  s = positiveCube(s);
  t = positiveCube(t);
  roots.push(-term1 + s + t);
}else if (discrim === 0) {
  // Three real, two of them equal
  var r13 = positiveCube(r);
  roots.push(-term1 + r13 * 2.0);
  roots.push(-r13 - term1);
  roots.sort();
}else {
  q = -q;
  q3 = -q3;
  var dum1 = Math.acos(r / Math.sqrt(q3));
  var r13 = 2.0 * Math.sqrt(q);
  roots.push(-term1 + r13 * Math.cos(dum1 / 3));
  roots.push(-term1 + r13 * Math.cos((dum1 + 2 * Math.PI) / 3));
  roots.push(-term1 + r13 * Math.cos((dum1 + 4 * Math.PI) / 3));
  roots.sort();
}
Community
  • 1
Ryan
  • 163