World's most popular travel blog for travel bloggers.

[Solved]: Smallest real root of a polynomial in a range

, , No Comments
Problem Detail: 

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

Asked By : user3476782

Answered By : Evil

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56741

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback