enforce monotonic polynomial fit or at least check it

[souldog]

Can anyone direct me to some resources on generating strictly monotonic polynomial approximations in one dimesion to a given set of data where both the
dependent on independent data sets are monotonically increasing?

Does any one know of a slick way to determine if a polynomial is strictly monotonic over a given interval. (I can do this by hand of course, but need to
do it on a computer :) )

[Yves M]

Well, you could calculate the derivative (easy) and then check whether it's zero in the given interval (not necessarily easy). Depending on the order of the polynomials, you could solve this explicitly (I would not go over order 3 polynomials > order 2 derivate), otherwise you could use newton's method to find a root in the interval and actually instead of trying to find a root, check whether you go from positive to negative, which indicates that there has to be at least one root. You would have to solve the case of a second-order derivate being zero a bit differently though, since the derivative itself may just "touch" zero and actually not change signs.

And just to be clear, any polynomial apart from a straight line can't be wholly monotonic, so you probably restrict yourself to some interval. You should make sure that the interval is bigger than your dataset, because polynomial approximations tend to veer off pretty wildly before and after the last point to fit.

As for the method, you could try Least Squares which is usually fine, but it does of course not guarantee a monotonic polynomial.

[Yves M]

[ moved the thread here, since it seems more appropriate ]

[souldog]

Hi Yves, Thanks for the response, as usual. First let me say that I am very familiar with how to use the first and second deirvative tests to solve this problem.
My problem is not the mathematics invloved, but the fact that I am doing this on
a computer. I also am not free to choose the order, that will be up to the user,
and I was at the moment allowing up to 7th order polynomials. This really is a
"feature" for me.

Some background. What I am doing here is allowing a user to generate a calibration
curve for the command output in a servo system (a system that compares the
desired output, what I am calibrating, to the current feedback, measured with a transducer, a transducer which may be non-linear, although not likely, and uses the difference to drive the system.) As the measured feedback and desired command become equal, the difference becomes zero and the system stops "moving". The problem is that if the command calibration curve, from engineering units, specified by the user, to DAC values, digital to ananlog conversion values, is not stricly monotonic then
the system is not controllable. Therefore, after the user takes a sample set and
produces a calibration curve with a polynoimial fit, I was looking for a way to check if the resulting curve is monotonic over the full range of possible command values (this is a closed bounded interval, as specified by the user and enforced physically).

This seems to me like a, in general, intractable problem, if I need a guarantee that I will not let a non-strictly monotonic curve slip through.

...well as I write this I am convinced? that using laguerre's method or something similar to find the roots, of the derivative is as good as I am going to do...

Thanks Yves.

[Yves M]

I'm not really familiar with Laguerre's method (I've looked it up and it seems pretty reasonable) but I'm just wondering whether you won't have to implement it with complex numbers. Then again, you probably know more about that.

The problem is complex because you have two conflicting goals. First of all have a "best fit" and then the monotonic behaviour over a specific interval. I can't see a mathematical solution to this so trial and checking seems to be the only possibility. Even if you have to find the roots of the derivative, the checking should not be that difficult to do.

[KevinHall]

And just to be clear, any polynomial apart from a straight line can't be wholly monotonic

That's not true. x^3 is monotonic. So is x^5 and x^7 + 5*x^3 +x +9. In fact all polynomials that only contain odd and zero powers of x and whose sign of all odd powers of x are the same are monotonic. Granted, that's a pretty strict condition, but it is nonetheless true.

[Yves M]

True, you're entirely right.

[souldog]

Thanks guys for the responses. I guess I am just going to have to do the grunt
work...

[KevinHall]

Yeah, I would also use numerical methods to find all the zeros of the derivative. Then analyze the derivative between the zeros. That would give you which segments are increasing and which are decreasing. Yves already mentioned ways to find the zeros.

Having experience with servos myself, I have never found it useful to servo off a point whose derivative is zero despite being locally monotonically increasing. I.e. something like x^3 or higher in power. When the position error is small, there's nothing to help pull the equipment into position (unless you have some integrator or something similar to help on this task). In that sense, I would just make sure that there are no zeros in the derivative of the function in the interval of interest. Then all you're left doing is making sure the derivative is positive somewhere in the interval.

Anyway, good luck!

[souldog]

Yah, given that transducers are very linear in their measurement range these days, higher order calibration curves are really not needed. This is just a feature
that we can point to when the customer asks, even though it wont be used.
I guess load cells can exhibit slighlty different slopes in tension and compression
so a piecewise linear cal is probably the most that will be used in practice.

But you always get these request for fudge tables and curve fitting etc... I am really just trying to protect the customers from themselves.