7
$\begingroup$

I'm trying to numerically find the smallest real root of a polynomial in a given range. My initial plan was to shift the polynomial so that the bottom of the range was 0, expand the resulting expressions to find the new coefficients, then use the Jenkins-Traub algorithm until it finds the first (smallest) root or increases out of the range. However, the Wiki page says that it only generally finds the roots in increasing order, so it sounds like that's not guaranteed. Is there a way to guarantee finding the first root? If not, what is the most efficient way to solve the problem?

Finding all the roots then sorting is possible, but is inefficient as the degree of the polynomial gets larger, and, I hope, unnecessary. The bisection method is another common algorithm, but consider the polynomial: $-5x^2+5x-1$ with a range of (0,2), which would cause the angle bisection to fail. The best answer is one that guarantees success with the fastest time for a reasonable degree polynomial (less than say 10).

Improve this question
$\endgroup$
10
  • $\begingroup$ What properties do you want your algorithm to have? Do you just any algorithm for the task? If so, there are algorithms: e.g., find all the roots, then sort. (There are multiple ways to find all roots: factor the polynomial; find one root $r$ and divide $p(x)$ by $x-r$; use binary search.) Another algorithm is to use the bisection method appropriately. So, it seems like there are many possible answers, and I'm not sure exactly what you're looking for. Can you edit the question to clarify how you will evaluate answers? $\endgroup$
    – D.W. ♦
    Commented Apr 29, 2016 at 2:43
  • $\begingroup$ @D.W. Corrected the question. Speed is the key; it'll be happening a lot. $\endgroup$
    – 1I1III1
    Commented Apr 29, 2016 at 3:20
  • $\begingroup$ @D.W. degree. Fixed. Sorry about the confusion. I think I might have come up with an acceptable solution, but I'm not convinced it always works, or is the fastest option. Do I post an answer and accept it, then accept another if a better one comes along, or post it as part of the question because I'm not sure, or as a comment? If I do accept a solution will the question still be seen by people that might have a better solution? $\endgroup$
    – 1I1III1
    Commented Apr 29, 2016 at 7:14
  • 1
    $\begingroup$ Great! Post an answer - you're welcome to answer your own question! You might wait a day or two before accepting, to give a chance for a better answer. (You can certainly accept one answer and then change which one you accept later, but it's often better to wait a few days before accepting an answer, if you think there's a chance a better answer might be possible. Accepting an answer might be viewed as a signal that "I am satisfied with this answer".) $\endgroup$
    – D.W. ♦
    Commented Apr 29, 2016 at 7:23
  • 2
    $\begingroup$ Have you tried mix like Strum algorithm (to split range into ranges to know how many roots are there) and the run Newton method, which converges very fast with good initial guess? Of course for Strum - only up to first root range found. Housholder is very tempting, but please check the runtime first to tweak the degree (and there is chance that it will in fact be Newton after all). $\endgroup$
    – Evil
    Commented Apr 29, 2016 at 14:46

1 Answer 1

Reset to default
1
$\begingroup$

I would like to propose mix of Sturm algorithm (to split range into ranges to know how many roots are there) and then run Newton method, which converges very fast with good initial guess.

Of course for Sturm - only up to first root range found.

Housholder is very tempting, but please check the runtime first to tweak the degree (and there is chance that it will in fact be Newton after all, when degree is equal one).

The main idea behind that is local root finding methods are faster than global ones, but they might diverge to some other place, but you are interested in the first one, so providing good initial guess will put Newton method in the radius of convergence.

The things to add: there might be many roots in small distance, so the main idea was to "pick one" range and start finding it, your idea of finding the slope is very neat, and if you merge the slope finding with initial range picking it seems like boosted Newton for very small cost.
The idea is to also show Newton method which root you are after (otherwise it might go after surrounding one).

About binary search, if you want to apply it until there is one root - yes, indeed, but if the idea is to check more ranges - I would cut it for resources savings.

Improve this answer
$\endgroup$

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.