Description

MA202 Numerical Techniques LAB#8 Interpolation
Interpolation is to connect discrete data points in a plausible way so that one can get reasonable estimates of data points among the given points. The interpolation curve passes through all the data points.
For a given set of N + 1 data points (x0,y0),(x1,y1),…,(xN,yN), we want to find the coefficients of an Nth degree polynomial function to match them:
PN(x) = a0 + a1x + a2x2 + … + aNxN (1)
Interpolation by Newton polynomial The Nth-degree Newton polynomial matching the N + 1 data points (x0,y0),(x1,y1),…,(xN,yN) can be recursively obtained as the sum of the (N − 1)th degree Newton polynomial matching the N data points (x0,y0),(x1,y1),…,(xN,yN) and one additional term.
nN(x) = a0+a1(x−x0)+a2(x−x0)(x−x1)+… = nN−1(x)+aN(x−x0)(x−x1)…(x−xN−1) (2)
with n0(x) = a0
In order to derive a formula to find the successive coefficients a0,a1,…,aN that make this equation accommodate the data points, we will determine a0 and a1 so that
n1(x) = n0(x) + a1(x − x0) (3)
matches the first two data points (x0,y0) and (x1,y1). We need to solve the two following equations
and n1(x0) = a0 + a1(x0 − x0) = y0 (4)
to get n1(x1) = a0 + a1(x1 − x0) = y1 (5)
(6)
Starting from this first-degree Newton polynomial, we can proceed to the second degree
Newton polynomial n2(x) = n1(x) + a2(x − x0)(x − x1) = a0 + a1(x − x0) + a2(x − x0)(x − x1) (7)
which, with the same coefficients a0 and a1 as (6), still matches the first two data points (x0,y0) and (x1,y1), since the additional (third) term is zero at (x0,y0) and (x1,y1). This is to say that the additional polynomial term does not disturb the matching of previously existing data. Therefore, given the additional matching condition for the third data point (x2,y2), we only have to solve
n2(x2) = a0 + a1(x2 − x0) + a2(x2 − x0)(x2 − x1) ≡ y2 (8)
for only one more coefficient a2 to get
(9)
Generalizing these results (6) and (9) yields the formula to get the Nth coefficient aN of the Newton polynomial function (2) as
(10)
This is the divided difference, which can be obtained successively from the second row of Table 1.
Table 1: Divided Difference Table
xk yk Dfk D2fk D3fk –
x0 y0 Df0 = y1−y0 x1−x0 D2f0 = Df1−Df0 x2−x0 –
x1 y1 Df1 = y2−y1 x2−x1 D2f1 = Df2−Df1 x3−x1 –
x2 y2 Df2 = y3−y2 x3−x2 –
x3 y3 –
Q. 1: Find and draw a Newton polynomial matching the following data points (2, 6), (1, 0), (1, 0), (2, 6), (4, 60)
Q. 2: Given the following data:
x: [0.8 1.4 2.7 3.8 4.8 4.9] y: [0.69 1.00 2.00 2.39 2.34 2.83]
Find a Newton polynomial curve passing through the data.
Q. 3: Explore the MATLAB commands related to all interpolation techniques like interp1, spline, pchip, makima, ppval. Use at least two different MATLAB fuctions to interpolate the data in Q.1 and Q.2
Divided difference algorithm
A pseudocode for computing divided difference is real array (aij)0:n×0:n integer i,j,n
for i = 0 to n do
(ai0) ←f(xi) = y0 end for
for j = 1 to n do for i = 0 to n-j do
(aij) ← ((ai+1,j−1) − ai,j−1)/(xi+j − xi) end for end for
This algorithm computes and stores all components of the divided difference. The coefficients of the Newton interpolating polynomial are stored in the first row of the array (aij)0:n×0:n i.e., in a(0 : n,0).
From the given data points, construct the divided difference table as Table 1 using the pseudocode mentioned above. Then use the Table together with equation (2) to get the Newton polynomial. Plot the polynomial over the given points. This process should be casted as a MATLAB function. Note that the Newton polynomial does not depend on the order of the data points; that is, changing the order of the data points does not make any difference.