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.$$

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Is the question how to find the roots of a polynomial the fastest? $\endgroup$
    – Reinstate Monica
    Commented Jul 23, 2019 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
    Commented Jul 23, 2019 at 18:42
  • $\begingroup$ @Apass.Jack I updated equation to be equal to 0 $\endgroup$
    – Bojan Vukasovic
    Commented Jul 24, 2019 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
    Commented Jul 24, 2019 at 12:44
  • $\begingroup$ @Algeboy I need only one positive real solution. I will update question. $\endgroup$
    – Bojan Vukasovic
    Commented Jul 24, 2019 at 12:45

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jul 25, 2019 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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