Open Educational Resources

Polynomial Interpolation: Newton Interpolating Polynomials

7.2.1 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 n through n+1 data points (x_i,y_i) with 1\leq i\leq n+1:

    \[ f_n(x)=b_1+b_2(x-x_1)+b_3(x-x_1)(x-x_2)+\cdots+b_{n+1}(x-x_1)(x-x_2)\cdots(x-x_n) \]

where the coefficients b_i are defined recursively using the divided differences as follows:

    \[\begin{split} b_1&=y_1\\ b_2&=[y_1,y_2]=\frac{y_2-y_1}{x_2-x_1}\\ b_3&=[y_1,y_2,y_3]=\frac{[y_2,y_3]-[y_1,y_2]}{x_3-x_1}=\frac{\frac{y_3-y_2}{x_3-x_2}-\frac{y_2-y_1}{x_2-x_1}}{x_3-x_1}\\ \vdots &\\ b_{n+1}&=[y_1,y_2,y_3,\cdots,y_{n+1}]=\frac{[y_2,y_3,\cdots,y_{n+1}]-[y_1,y_2,y_3,\cdots,y_{n}]}{x_{n+1}-x_1} \end{split} \]

This recursive divided differences are illustrated in the following table:
Interpolation5

The following Mathematica code implements a recursive function “f” that produces the coefficients b_i.

View Mathematica Code View Python Code

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 b_i 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:

    \[ b_1=y_1=1\qquad b_2=\frac{5-1}{2-1}=4 \]

Therefore, the interpolating polynomial has the form:

    \[ y=1+4(x-1)=1+4x-4=-3+4x \]

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:

    \[ b_1=y_1=1\qquad b_2=\frac{5-1}{2-1}=4 \qquad b_3=\frac{\frac{2-5}{3-2}-\frac{5-1}{2-1}}{3-1}=-3.5 \]

Therefore, the interpolating polynomial has the form:

    \[ y=1+4(x-1)-3.5(x-1)(x-2)=-3.5x^2+14.5x-10 \]

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:

    \[\begin{split} y=&1+4(x-1)-3.5(x-1)(x-2)+12.19697(x-1)(x-2)(x-3)\\ &-14.346144(x-1)(x-2)(x-3)(x-3.2)\\ =&-14.3461x^4+144.181x^3-509.935x^2+739.728x-358.628 \end{split} \]

MATLAB file for the above examples: Download
MATLAB file for the ddiff Matlab function called by the Matlab code: Download

7.2.2 Lecture Video


Page Comments

  1. Renee Penetrante says:

    Hi! I just want to let you know that the matlab code attached doesn’t seem to work for me as matlab keeps on saying that ddiff function is not found and suggests me to use diff instead. However, using diff results in “Unable to perform assignment because the indices on the
    left side are not compatible with the size of the right side.”

    1. Samer Adeeb says:

      I have added a link to download the ddif function.

Leave a Reply

Your email address will not be published.