2
$\begingroup$

I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed.

I can use general Newton's method for all degrees, or only for 5th+, and for 2,3 and 4 I can use algebraic formulas that solve quadratic, cubic and quartic equations. Since algebraic formulas need to use sqrt, acos and similar functions - does it make sense at all to use algebraic formulas - or is it better to use Newton's method for all degrees? I guess the latter will actually be faster?

This is my equation:

$$\frac{1}{(b_1x + 1)} + \frac{1}{(b_2x + 1)} + ... + \frac{1}{(b_nx + 1)} -k = 0$$

and constraints:

$$1 \leq k<n \\ b_n>0 $$

e.g. for $n=3$:

$$b_1 b_2 b_3 (-k)x^3 +\left(b_1 b_2+b_3 b_2+b_1 b_3- b_1 b_2 k-b_3 b_2 k-b_1 b_3 k\right)x^2 + \left(2 b_1+2 b_2+2 b_3-b_1 k-b_2 k-b_3 k\right)x + 3-k =0$$

which can be written as

$$\sum_{i=0}^n(n-i-k)\binom{\{b_1,...,b_n\}}{i}x^i=0.$$

$\endgroup$
  • 1
    $\begingroup$ Is the question how to find the roots of a polynomial the fastest? $\endgroup$ – Solomonoff's Secret Jul 23 at 18:40
  • $\begingroup$ Yes - is it faster to use Newton's method for 2nd, 3rd and 4th degree polynomial or is it faster to use quadratic, cubic and quartic equations? $\endgroup$ – Bojan Vukasovic Jul 23 at 18:42
  • $\begingroup$ @Apass.Jack I updated equation to be equal to 0 $\endgroup$ – Bojan Vukasovic Jul 24 at 12:44
  • $\begingroup$ These are all integral polynomials, might be counting something, it possible you have rational roots in which case use the rational roots theorem and be done precisely and quickly. $\endgroup$ – Algeboy Jul 24 at 12:44
  • $\begingroup$ @Algeboy I need only one positive real solution. I will update question. $\endgroup$ – Bojan Vukasovic Jul 24 at 12:45
1
$\begingroup$

The sum goes to infinity at x = -1 / $b_i$. Between $b_i$ and $b_{I+1}$ it is continuous. So each of these intervals contains a point wher the sum of fractions equals k. Go from there.

$\endgroup$
  • $\begingroup$ Thanks. I guess this is initial guess for newtons method? I just updated constraints for variables in equations - does it change anything? Also, do you recommend Newton's method for all or only n>=5 ? $\endgroup$ – Bojan Vukasovic Jul 25 at 22:02

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.