# ## Polynomial Interpolation: Newton Interpolating Polynomials

### Newton Interpolating Polynomials

As stated in the introduction, the matrix formed in Equation 1 can be ill-conditioned and difficult to find an inverse for. A simpler method can be used to find the interpolating polynomial using Newton’s Interpolating Polynomials formula for fitting a polynomial of degree through data points with : where the coefficients are defined recursively using the divided differences as follows: This recursive divided differences are illustrated in the following table: The following Mathematica code implements a recursive function “f” that produces the coefficients .

View Mathematica Code
Data = {{1, 3}, {4, 5}, {5, 6}, {6, 8}, {7, 8}};
f[anydata_] := If[Length[anydata] == 1, anydata[[1, 2]], If[Length[anydata] ==2, (anydata[[2, 2]] - anydata[[1, 2]])/(anydata[[2, 1]] -anydata[[1, 1]]), (f[Drop[anydata, 1]] - f[Drop[anydata, -1]])/(anydata[[Length[anydata], 1]] - anydata[[1, 1]])]]
NP[anydata_] := Sum[f[anydata[[1 ;; i]]]*Product[(x - anydata[[j, 1]]), {j, 1, i - 1}], {i, 1, Length[anydata]}]
(*Using the Newton polynomial function*)
y = Expand[NP[Data]]
(*Using the interpolating polynomial built-in function*)
y2 = Expand[InterpolatingPolynomial[Data, x]]

View Python Code
import numpy as np
import sympy as sp
sp.init_printing(use_latex=True)

Data = [(1, 3), (4, 5), (5, 6), (6, 8), (7, 8)]
x = sp.symbols('x')
def f(anydata):
if len(anydata) == 1:
return anydata
elif len(anydata) == 2:
return (anydata - anydata)/(anydata -anydata)
else:
return (f(anydata[1:]) - f(anydata[:-1]))/(anydata[len(anydata)-1] - anydata)
def NP(anydata):
return sum([f(anydata[0:i+1])*np.prod([(x - anydata[j]) for j in range(i)]) for i in range(len(anydata))])
# Using the Newton polynomial function
display("y: ",sp.expand(NP(Data)))
# Using the interpolating polynomial built-in function
display("y2: ",sp.interpolate(Data, x))


Newton’s formula for generating an interpolating polynomial adopts a form similar to that of a Taylor’s polynomial but is based on finite differences rather than the derivatives. I.e., the coefficients are calculated using finite difference. One advantage to this form is that the degree of a Newton’s interpolating polynomial can be increased (or decreased) automatically by adding (or removing) more terms corresponding to new points without discarding existing terms.

#### Example 1

Using Newton’s interpolating polynomials, find the interpolating polynomial to the data: (1,1),(2,5).

##### Solution

We have two data points, so, we will create a polynomial of the first degree. Therefore: Therefore, the interpolating polynomial has the form: #### Example 2

Using Newton’s interpolating polynomials, find the interpolating polynomial to the data: (1,1),(2,5),(3,2).

##### Solution

We have three data points, so, we will create a polynomial of the second degree. Therefore: Therefore, the interpolating polynomial has the form: #### Example 3

Using Newton’s interpolating polynomials, find the interpolating polynomial to the data: (1,1),(2,5),(3,2),(3.2,7),(3.9,4).

##### Solution

The divided difference table for these data points were created in excel as follows: Therefore, the Newton’s Interpolating Polynomial has the form: MATLAB file for the above examples:
MATLAB file for the ddiff Matlab function called by the Matlab code:

### Lecture Video

1. Renee Penetrante says:
1. Samer Adeeb says: