Interpolation recommendations (linear, cubic?)

Question

I need to find a good approximation of the points where the undefined function crosses the threshold value. I cross my space and whenever I find that the next two steps are on opposite sides of the threshold, I add a point somewhere in the middle:

_{(source: ning.com )}

My first approach was simply to choose the middle, but this is obviously a terrible decision:

_{(source: ning.com )}

Now I use linear interpolation, which gives a reasonable result, but the main function will almost never be linear. Thus, this only works if my step size is small enough:

_{(source: ning.com )}

Fetching a basic function can be quite expensive, but I'd like to try adding one or two additional samples to get a much better approximation. Can cubic interpolation be used here? Like this:

_{(source: ning.com )}

Or are there better ways?

Very grateful David Rutten

ps. I write in C #, but it does not depend on the language.

Answer 1

In the last image, only three points are displayed, which are enough to determine a quadratic polynomial, not a cubic one. For cubic interpolation, you will need four points. The cubic polynomial can be set in different ways; here are two.

The easiest way is to simply allow the (single) polynomial to go through all four points.

Another way is to use tangents. Again, we need four points. Let the left two points define the slope. Ask the polynomial to go through the second point (in general, it does not go through the first point) and corresponds to the calculated slope at that point. And the same on the right side for the fourth and third points.

By the way, any higher-order polynomial is probably a bad idea, because they tend to become very unstable when there is even a small amount of input noise.

If you give more detailed information about your problem area, I can give a more specific answer. For example, where does your data come from, what curve can you usually expect, and can you go back and try more if necessary? I can also provide equations and pseudo-code if necessary.

Update: stupid, I left the sentence, citing two paths without typing them. Allocated them now.

Answer 2

The magic word is “root solver”; the mathematical root is the value in which the function is zero. By adding / subtracting a threshold, you can use root crawlers.

If you have a hint about what function you are performing, you can set up a very quick root search. If you don’t have the prompt suggested by your post ("undefined"), the best method is the Brent method, the combination of the secant method and the bisection method or the secant method. Wikipedia has an entry for this method.

Contrary to your opinion, you should not use more complex functions. The main performance constraint is function evaluations, which increase with increasing number of points / derivation or more complex interpolation functions.

The Newton-Raphson method is VERY BAD if you are near the maximum / minimum / inflection point, because the almost zero derivative sends you far from the point, and other problems arise with it. Do not use it until you know what you are doing.

Answer 3

My math is incredibly rusty, but you can find the Newton Raphson method gives good results. In the general case, it converges very quickly on the exact solution, assuming that the iteration starts "close enough" to the desired root.