Peeking at different interpolation algorithms

[Namir]

I have been looking at various difference and divided-difference interpolation algorithms. In addition to the well-known Newton Forward-Difference, Backward-Difference, Forward-Divided-Difference, and Backward-Divide-Difference methods, little else, of difference methods, is covered in most numerical analysis books. The difference methods rely on equally spaced x values and are able to simplify the equations used and calculation schemes. The divided-difference methods handle non-equidistant values of x. In either case of difference and divided difference, you build a table of derivative estimates. The table entries look like a triangle laying on its side with a rectangular base (comprising of the (x, y) values). The triangle is made up of columns. The first column approximate the first derivatives, the second column approximate the second derivatives, and so on. Each column has one less row than the column to its left. The estimate of these derivative use the difference (in the case of equidistant x values) or divided difference (in the case of non-equidistant x values).

The Newton forward difference and divided difference schemes use the top table values of the derivatives in the interpolation polynomial. Conversely, the Newton backward difference and divided difference schemes use the bottom table values of the derivatives in the interpolation polynomial.

I stumbled on a numerical analysis book sitting on my bookshelf (Elements of Numerical Analysis by Radhey S. Gupta) and it covered several difference methods for interpolation. They are the Gauss forward, Gauss backward, Stirling, Bessel, Everett, and Steffensen methods. Without going into details (you can read about Gauss and Stirling methods on the Internet), all of these methods tap into the various derivative estimates along and around the central axis of the difference table (remember the table is a triangle leaning on its side). Each of these methods suggests a special scheme to pick the values of the derivatives in the difference table.

Using Excel, I was able to build a Gauss forward divided difference (by studying its simpler difference counterpart) to interpolate values for data with non-equidistant x values. I tested data for both equidistant and non-equidistant values of x. The results are interesting:

1. The errors are smaller when we interpolate for x near the mid table values. The errors increase the more the interpolated x deviates from the mid table values.

2. The above is true for both equidistant and non-equidistant values of x. In the case of equidistant values of x, the error increases as the difference between neighboring x’s increases. In the case of non-equidistant values of x, the error increases with the average spacing of the x value.

So should we ditch Newton’s difference and divided-difference methods in favor of these new found little darling interpolation algorithms? The answer is no, not necessarily. Why? These algorithms use mid-table values and may not do well if you are interpolating x values that are not so close to the mid-table x values. This is their Achilles heal!

Consider a large table of x and y values at non-equidistant values of x. If you want to interpolate for xi, then lookup in the table and locate the first two values of x that make up an interval that contains the value of xi. Then select a few more x values (along with their associated y values) down in the table, build the Newton Forward Divided-Difference table, and finally perform the interpolation. You should get good results based on the number of points you have selected and the information represented by the (x, y) values (i.e. the true function that is sampled by the table’s data).

If the xi value is near or at the end of the table, then use the Backward Divided-Difference. Select two values of x that that make up an interval that contains the value of xi. Select a few values of (x, y) up in the table, build the backward divided-difference table, and perform the interpolation.

So, armed with the Newton Forward and Backward Difference and Divided-Difference, as well as Lagrange (my favorite!) methods, you are good for most of your Interpolation needs. There are other new algorithms like Neville and Thiele interpolation that can explore and use.

[Albert Chan]

With divided difference, there is no requirement that the table be sorted.
Just do Forward Divided Difference, with the entries closest to interested region up on top.

Example, from https://jp.mathworks.com/matlabcentral/f...on-formula
(note: the link had the entries entered wrong, below is corrected points)

Points: (-2, 18.4708), (-1, 17.8144), (0, 17.107), (1, 16.3432), (2, 15.5154), find y(0.25):

Assume calculations with 6 sig. digits, and we want best interpolated values in the middle:

Code:

p   y(p)      Divided Difference Table
+0  17.107
+1  16.3432  -0.763800
-1  17.8144  -0.735600  -0.0282000
+2  15.5154  -0.766333  -0.0307330  -0.00126650
-2  18.4708  -0.738850  -0.0274830  -0.00108333  -0.0000915850

y(p) = 17.107 + (p-0)*(-0.7638 + (p-1)*(-0.0282 + (p+1)*(-0.0012665 + (p-2)*(-0.000091585))))

→ y(0.25) ≈ 16.9216

Above formula is same (except slight rounding errors) as Gauss Forward Formula:

Code:

p   y(p)      Difference Table
-2  18.4708  
-1  17.8144  -0.6564
+0  17.107   -0.7074  -0.0510
+1  16.3432  -0.7638  -0.0564  -0.0054
+2  15.5154  -0.8278  -0.0640  -0.0076  -0.0022

y(p) = \(17.107 + \binom{p}{1}(-0.7638) + \binom{p}{2}(-0.0564)
+ \binom{p+1}{3}(-0.0076) + \binom{p+1}{4}(-0.0022) \)

[Albert Chan]

Perhaps an easier way to produce Forward Divided Difference polynomial:

New Formulas and Methods for Interpolation, Numerical Differentiation and Numerical Integration

Redoing post #2 with the New Divided Difference Table, again assume 6 sig. digits calculations

Code:

p   y(p)      New Divided Difference Table
+0  17.107
+1  16.3432  -0.7638
-1  17.8144  -0.7074  -0.0282
+2  15.5154  -0.7958  -0.032   -0.00126667
-2  18.4708  -0.6819  -0.0273  -0.0009     -0.0000916675

Top entries are "locked", and use to compute the slope (divided difference).

1st column = [ (y-17.107) / (x-0) for (x,y) in [[1,16.3432],[-1,17.8144],[2,15.5154],[-2,18.4708]]]
2nd colume = [ (y+0.7638)/(x-1) for (x,y) in [[-1,-0.7074],[2,-0.7958],[-2,-0.6819]]]
...

y(p) = 17.107 + (p-0)*(-0.7638 + (p-1)*(-0.0282 + (p+1)*(-0.00126667 + (p-2)*(-0.0000916675))))

This interpolation scheme were used by Acton Forman's Numerical Method that Work.
The book were originally published in 1970, so perhaps above is not that "New"

https://www.hpmuseum.org/forum/thread-11...#pid102623

[Albert Chan]

(08-02-2019 09:27 PM)Albert Chan Wrote:  

Code:

p   y(p)      Difference Table
-2  18.4708  
-1  17.8144  -0.6564
+0  17.107   -0.7074  -0.0510
+1  16.3432  -0.7638  -0.0564  -0.0054
+2  15.5154  -0.8278  -0.0640  -0.0076  -0.0022

y(p) = \(17.107 + \binom{p}{1}(-0.7638) + \binom{p}{2}(-0.0564)
+ \binom{p+1}{3}(-0.0076) + \binom{p+1}{4}(-0.0022) \)

We can build interpolation formula on the fly, for any path, without looking up.
Just think of what the interpolation X values sequence.
Then assume the list were originally sorted the same way, with numbers on the diagonal.

For Above Gauss Forward Formula, X's = 0, 1, -1, 2, -2

y(p) = 17.107 + (p-0)/1*(-0.7638 + (p-1)/2*(-0.0564 + (p+1)/3*(-0.0076 + (p-2)/4*(-.0022)))))

Had we wanted Gauss Backward Formula, X's = 0, -1, 1, -2, 2

y(p) = 17.107 + (p-0)/1*(-0.7074 + (p+1)/2*(-0.0564 + (p-1)/3*(-0.0054 + (p+2)/4*(-.0022)))))