How to make sure if a polynomial curve is monotonic under interval [a,b]?

Question

Hi, guys,

If I got a polynomial curve, and I want to find all monotonic curve segments and corresponding intervals by programming.
What's the best way to do this...
I want to avoid solving equation like f'(x) = 0;
Using some nice numerical ways to do this,like bi-section, is preferred.
f'(x) expression is available.

Thanks.

Add additional details. For example, I get a curve in 2d space, and its polynomial is

x: f(t) y: g(t)

t is [0,1]

So, if I want to get its monotonic curve segment, I must know the position of t where its tangent vector is (1,0).

One direct way to resolve this is to setup an equation "f'(x) = 0".

But I want to use the most efficient way to do this.

For example, I try to use recursive ways to find this. Divide the range [0,1] to four parts, and check whether the four tangents projection on vector (1,0) are in same direction, and two points are close enough. If not, continue to divide the range into 4 parts, until they are in same direction in (1,0) and (0,1), and close enough.

Answer 1

I think you will have to find the roots of f'(x) using a numerical method (feel free to implement any root-seeking algorithm you want, Wikipedia has a list). The roots will be those points where the gradient reaches zero; say x1, x2, x3.

You then have a set of intervals (-inf, x1) (x1, x2) etc, continuity of a polynomial ensures that the gradient will be always positive or always negative between a particular pair of points.

So evaluating the gradient sign at a point within each interval will tell you whether that interval is monotically increasing or not. If you don't care for a "strictly" increasing section, you could patch together adjacent intervals which have positive gradient (as a point of inflection will show up as one of the f'(x)=0 roots).

Answer 2

The monotic curve segments are delimited by the roots of f'(x). You can find the roots by using an iterative algorithm like Newton's method.

Answer 3

As an alternative to computing the roots of f', you can also use Sturm Sequences.

They allow counting the number of roots (here, the roots of f') in an interval.