1
$\begingroup$

I would like to find the first positive solution(if there is one) to this equation:

$$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$

The simplest way I fond would be to do the following: $$ax^2+bx+c = (dx^2+ex+f) * (gx+h)$$ $$(=)$$ $$ax^2+bx+c - (dx^2+ex+f) * (gx+h) = 0$$ $$(=)$$ $$Ax^3+Bx^2+Cx+D = 0$$ and find the roots of the cubic. But, finding the roots of a cubic is computationally expensive. As it requierers the use of sqrt, cos and sin.

(I am only looking for the smallest positive if there is any, if you know some algorithm that does that even for cubics, I would like to know more about it).

So my question is: "is there another way to find the solutions of this equation?" Like IF the equation was: $$(ax^2+bx+c) * (dx+e) = 0$$ it could be solved by solving the quadratic and the linear separately instead of calculating the resulting cubic and solve it afterward. Any help is appriciated! Thanks in advance.

$\endgroup$
2
  • 1
    $\begingroup$ Don't use Cardano's formulas to find the roots of the cubic. As you said, they are slow and also are numerically unstable. Use Newton's method instead. You can target the smallest positive root directly by choosing appropriately the initial point. The selection is done based on cases depending on the coefficients and the stationary points. The stationary points are the roots of a quadraitc (the derivative). These you can find using the "citardauq formula". $\endgroup$ – plop Mar 29 at 20:19
  • 1
    $\begingroup$ Unless you have additional information that you are not saying, note that your equation can give raise to any cubic equation. So, your problem, as stated, is equivalent to the problem of finding the smallest positive root of an arbitrary cubic. $\endgroup$ – plop Mar 29 at 20:24
2
$\begingroup$

It depends on what kind of answer you want. Finding closed-form algebraic solutions is different from finding numeric solutions.

Having said that, I agree with plop here. Your best bet is to get bounds on the roots, and then use an iterative algorithm. The good news is that for a cubic, it's not difficult to find bounds.

First off, I assume that you know to compute the roots of a quadratic using the Citardauq formula when appropriate. If $b\ge 0$ then:

$$x_1 = \frac{-b - \sqrt{b^2 - 4ac}}{2a}$$

$$x_2 = \frac{2c}{-b - \sqrt{b^2 - 4ac}}$$

Otherwise:

$$x_1 = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$$

$$x_2 = \frac{2c}{-b + \sqrt{b^2 - 4ac}}$$

Using this method, the addition/subtraction of $b$ and the square root of the discriminant have the same sign, so there is no cancellation there.

To find all roots of a cubic $p(x) = a x^3 + b x^2 + cx + d$ numerically, first find the roots of the derivative $x_1$ and $x_2$, and evaluate the cubic at those two points. Assuming that $x_1 \le x_2$, you have four cases to consider.

  1. If $x_1 = x_2$, then the cubic is of the form $a(x - x_1)^3 + d - ax_1^3$. This means it has one real root at $\sqrt[3]{x_1^3 - \frac{d}{a}} + x_1$. If $ax_1^3=d$ then it's a triply-repeated root.
  2. If $p(x_1)$ and $p(x_2)$ have opposite sign, then the cubic has three distinct real roots. Specifically, there is a real root in each of the following ranges: $\left(-\infty,x_1\right)$, $\left(x_1,x_2\right)$, $\left(x_2,\infty\right)$. Use this to get an initial estimate and use a numeric root finder.
  3. If $x_1 \ne x_2$ but $p(x_1)$ and $p(x_2)$ have the same sign, then the cubic has only one real root. It is either in the range $\left(-\infty,x_1\right)$ or $\left(x_2,\infty\right)$, depending on the sign of $a$.
  4. If one of $p(x_1)$ or $p(x_2)$ are zero, then there is a repeated real root at that point and a third real root elsewhere. Again, it is either in the range $\left(-\infty,x_1\right)$ or $\left(x_2,\infty\right)$, depending on the sign of $a$.

Because you need the smallest positive root, you can eliminate ranges from consideration. For example, suppose you find yourself in case 2. If $x_2 \le 0$, you only need to check the range $\left(x_2,\infty\right)$ for a positive root, as the other two roots are guaranteed to be negative. You never have to perform the iterative algorithm on all three ranges in case 2.

Doing this kind of exhaustive case analysis becomes unwieldy for higher-degree polynomials, which is why we tend to prefer different methods there. This is beyond the scope of the question, but as a general guide:

  • It's usually worth performing squarefree factorisation if possible, because numeric methods tend to converge more slowly around repeated roots.
  • You can bound the roots using Vincent's theorem (or Sturm's theorem, which is slower but a bit easier to understand) and then use numerical root finding if you only need the real roots.
  • You can use something like Aberth's method if you need complex roots.
$\endgroup$
2
  • 1
    $\begingroup$ $x^3-1$ has both its stationary points at $x=0$, but its only real root at $x=1$. Case (1) needs to be split in more cases, depending on the value of $P(x_1)$ and on the signs of $x_1$ and of $a$. $\endgroup$ – plop Mar 30 at 14:00
  • $\begingroup$ Oh, yes. Let me fix that. $\endgroup$ – Pseudonym Mar 31 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.