Extrapolation for Two Dimensional Lookup Table

[jegues]

Hello,

I am writing a program for a two dimensional look up table. The idea is that the user will enter values for x and y and the program will look up the corresponding output value from the table.

For example, consider the table shown below.

For this table, if the user enters x = 2 and y = 1 then the program will output 6.

If the user enters values between two entries of the table then the program will interpolate. For example, using the same table shown in the attached *.pdf, if the user enters x = 1 and y = 1.5 then the program will output 1.5.

Furthermore, if the user enters x = 1.25 and y = 1.25 the program will use bilinear interpolation and output 2.5.

With this I am able to handle every x and y input that is within the x and y ranges provided in the table.

However, if the user enters input values that are outside the range of the table, how should the program determine its output?

If we think our 2d table as a 2d mesh, where every point on the mesh corresponds to an entry in the table, then we can see that I have 9 different regions that I must deal with depending on the users input of x and y.

In each of these regions, I must select 4 points so that I can formulate a surface, $$f(x,y) = a_0 + a_1 x + a_2 y + a_3 x y$$ and solve the for the coefficients $$a_0, a_1, a_2, a_3$$.

Whenever the input point (x,y) is within the boundaries of the 2d mesh (i.e. marked region 9 in the *.pdf) then selecting the 4 points to use is easy, I just select the 4 surrounding points on the mesh.

However, whenever the input point (x,y) is outside the boundaries of the mesh, I don't know how to intelligently select which 4 points to use to define my surface.

Any ideas/comments/suggestions?

 

[Dr. Courtney]

Extrapolation can never be done with as much confidence as interpolation.

If you think a linear approach is reasonable outside of the table bounds, I would fit the data to a plane f(x, y) = ax + by +c and use that plane to estimate values beyond the boundaries.

 

[jegues]

Extrapolation can never be done with as much confidence as interpolation.

If you think a linear approach is reasonable outside of the table bounds, I would fit the data to a plane f(x, y) = ax + by +c and use that plane to estimate values beyond the boundaries.

Hi Dr. Courtney,

Thanks for your reply.

If I'm going to use a plane, then I need some mechanism to decide which three points I am going to use to define that plane. Also, for there to be a solution, the three points I select cannot lie on the same line either.

Do you have any ideas as to how I should select which three points should be used to define my plane? I imagine this will depend on which particular region the users input lands in?

Thanks!

 

[Dr. Courtney]

Do a least squares fit to all the points. It minimizes the sum of the squared errors from the points to the best fit plane.

 

[gmax137]

... However, if the user enters input values that are outside the range of the table, how should the program determine its output? ... However, whenever the input point (x,y) is outside the boundaries of the mesh, I don't know how to intelligently select which 4 points to use to define my surface.

Is there a meaningful expectation about how the function behaves outside the boundaries of the table? For instance, based on the physical meaning of the data / function? If not, then the best approach may be to have your program check the user input values first, and print to output "Input values are out of bounds" or something similar. Otherwise, the user is going to get results based on Your interpretation of how the function behaves.

 

[Dr. Courtney]

Is there a meaningful expectation about how the function behaves outside the boundaries of the table? For instance, based on the physical meaning of the data / function? If not, then the best approach may be to have your program check the user input values first, and print to output "Input values are out of bounds" or something similar. Otherwise, the user is going to get results based on Your interpretation of how the function behaves.

Ordinarily, I would agree. But if you look at the table of data in this case, it is very close to a linear function:

f(x, y) = 5(x - 1) + y

In such cases where the agreement is so good within the range, it is unlikely that the extrapolation does not remain reasonable for at least a small amount outside the domain of the table. Therefore, I would recommend at least giving a linearly extrapolated value with a warning that it is an extrapolated value and that accuracy may degrade quickly for numbers well outside of the domain of the data on which it is based.

 

[gmax137]

I was under the impression that the specific table given was just an example and the OP was trying to write a generic algorithm for double interpolation. I see now that was just my assumption.

 

[Dr. Courtney]

I was under the impression that the specific table given was just an example and the OP was trying to write a generic algorithm for double interpolation. I see now that was just my assumption.

You might be right. Of course, the reasonableness of extrapolation with a linear function (plane) depends on how linear the data is.