1

I have a series of points representing values of a function, an example is below:

chart

The values for X and Y can be real (non-integers). The function is monotonic, non-decreasing.

I want to be able to interpolate / assess the value of the function for any X (e.g. 1.5), so that a continuous function line would look like the following:

chart 2

This is a standard interpolation problem, so I used Lagrange interpolation so far. It's quite simple and gives good enough results.

The problem with interpolation is that it also interpolates the values that are given as input, so the end results are for the input data will be different (e.g x=1, x=2)

Is there an algorithm that can guarantee that all the input values will have the same value after the interpolation? Linear interpolation is one solution, but it's linear the distances between X's don't have to be even (the graph is ugly then).

Please forgive my english / math language, I am not a native speaker.

Khashayar
  • 2,014
  • 3
  • 22
  • 31
Naariom Met
  • 231
  • 1
  • 9
  • 3
    Errr... Just a note. I think you are confusing interpolation with fitting. Interpolation always perserves accuracy at the data points. It estimates the values between data points. Fitting tries to figure out a function that describes the data set the best. I don't think there is a method that will produce a smooth function and pass every given point. Well, technically I think high order polynomial would, but it would look uglier. But I am not sure, this would be better asked at math stack, or statistics. – luk32 May 21 '14 at 09:11
  • @luk32 I was not sure what to call it exactly. Let me relax the requirements: I need the first and last point to be the same (in the example for x=1 and x=10), all the intermediate can be approximates, but the function must remain monotonic. In fact this is what I drew.. I guess I couldn't describe it as good. Is this possible? – Naariom Met May 21 '14 at 09:58
  • I don't believe that there is a fit that can guarantee that all values are identical to the input, the best you can do is use a measure to see how good the fit in like MSE. If you are writing a program, then maybe your solution isn't in the math, but in the implementation. use the input as the values up to the values that you need to interpolate.... – NiRR May 21 '14 at 10:26
  • @NiRR please read my previous comment: is it possible if I want the only first and last points to be the same? – Naariom Met May 21 '14 at 11:07
  • 1.your image is not interpolation!!! 2.you can use 4 point cubic patches like here http://stackoverflow.com/a/23627081/2521214 just convert it to 2D and use some parameter t for both axises (similar to SPLINEs or BEZIER cubics patches). if you need better continuity then C1 then just increase number of control points. High order polynomials tend to oscilate and the result will be ugly – Spektre May 22 '14 at 05:11

1 Answers1

2

The Lagrange interpolating polynomial in fact passes through all the n points, http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html. Although, for the 1d problem, cubic splines is a preferred interpolator.

If you rather want to fit a model, e.g., a linear, quadratic, or a cubic polynomial, or another function, to your data than I think you could still put the constraints on the coefficients to ensure the approximating function passes through some selected points. Begin by choosing the model, and then solve the Least Squares fitting problem.

rych
  • 682
  • 3
  • 10
  • 22