Interpolation Extrapolation and Curve-Fitting using higher order polynomial


There are numerous cases that you want to transfer data from one location (source grid) onto another locations (destination grid). Let’s say you have measured the concentration of some pollutants along the river every 1km from the river mouth. Now if you want to know what is the concentration at a certain location lets say 3.5km from the river mouth, there is no measured data. and of course you need to interpolate your data to the location that you want to know. Likewise, extrapolation serves the same purpose with this exception that the new location that you want to know about is located outside the region you made measurements or you have data.

Interpolation reproduces the [measured] data at the known location exactly. This means that the interpolant will generate the same data at the source grid. This is used for data driven approach. However, sometimes you want to use a model driven approach. In this case, you won’t reproduce the exact data at the known location; however, you are fitting a curve (model) to your known data set on source grid and estimating the value based on the fitted curve at the destination grid.

There are many methods to perform the above task. Most of them can be shown simply as:

f_{destination}=P \times f_{source}

I like to think of P as a projector or a transformation that interpolates/extrapolates/transforms/projects data from a source grid onto a destination grid. What is interesting is that for most of the methods the entries in P depends only on how the points on source and destination grid are located relative to each other. Therefore, as long as the points in source and destination grid have not moved relative to each other, the matrix P is not going to be changed.

This property can be used to perform a more efficient data transfer from one grid onto another. In those cases that your source grid and destination grid is not changing but the data on the source grid is constantly changing and it needs to be projected onto the destination grid, the matrix P can be generated once and after that it is only a matrix multiplication. This happens in many cases, particularly in the solution of Partial Differential Equations (PDEs). Some software packages such as NCL, ESMF, and SCRIP call this matrix, i.e. P, as interpolation weights.

I have recently developed another package in MATLAB which constructs the matrix P based on the chosen degree polynomial in 2D, i.e.:

f(x_d,y_d)=\sum_{i=0}^{n}{\sum_{j=0}^{n}{a_{i,j}x_d^iy_d^j}}

n is the degree of the polynomial. If you choose n=1, it would be bilinear interpolation. If you choose n=3 it would be cubic interpolation, if you choose n=4 it would be fourth order Lagrange interpolation. Although you can choose n to be anything that you like, but remember that large n suffers from Runge-Phenomenon.

The command in MATLAB has the following form

 P=ConstructInterpolator(xs,ys,xd,yd,nPoly,nInterp) 

where nPoly is the degree of the polynomial, and nInterp tells the program how many point to use to determine the coefficients. Let’s say you have chosen nPoly=4, therefore there would be (nPoly+1)^2=25 coefficients, i.e. a_{i,j}. If nInterp is set to be 25, then the program looks for the 25 closest points and uses that to determine the coefficients. Depending how the points are distributed you may end up with ill-conditioned or even singular matrices. Therefore, sometimes it is better to use more points than the minimum requirements. Therefore, if you set nInterp to something bigger than 25, in this case, the coefficients are going to be determined using a least-squeare approach. In this case you are actually curve-fitting.

This code can be used to interpolate/extrapolate/curve-fitting on 2D structured grids, unstructured grids, or even scattered data/grids/points. The source and destination grid does not need to be of the same type.

You can download the code from Mathworks file exchange (here). The code is accompanied by some Test_*.m functions. I suggest start running those codes first to get acquainted with the program.

Should you have any questions, feel free to send me an e-mail or ask it here on the blog. I do my best to answer them as quickly as possible. But sometimes I might be late.

Advertisements
This entry was posted in Program. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s