Newtons Interpolating Polynomials Method

This code conduct an Interpolation for a given set of data using Newton’s Interpolating Polynomials method, where the coefficients of the polynomial are calculated using Newton’s divided differences method.

Code Outputs:

Printed Table of Interpolated Values
Chart Compare of Interpolated Values with Given Points.

Xi F(Xi)
3.0000 0.2274
11.0000 0.0003
31.0000 0.5464
53.0000 0.5287
71.0000 0.3455
93.0000 0.3624
111.0000 0.7551

Input Requirements:

X Axis Points
Y Axis Points

About the Method:

Newton polynomial, named after its inventor Isaac Newton, is an interpolation polynomial for a given set of data points. The Newton polynomial is sometimes called Newton’s divided differences interpolation polynomial because the coefficients of the polynomial are calculated using Newton’s divided differences method.

Definition:

Given a set of k + 1 data points

(x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})

where no two x_j are the same, the Newton interpolation polynomial is a linear combination of Newton basis polynomials

N(x):=\sum _{{j=0}}^{{k}}a_{{j}}n_{{j}}(x)

with the Newton basis polynomials defined as

n_{j}(x):=\prod _{{i=0}}^{{j-1}}(x-x_{i})

for j > 0 and n0(x) = 1.

The coefficients are defined as

a_{j}:=[y_{0},\ldots ,y_{j}]

where

[y_{0},\ldots ,y_{j}]

is the notation for divided differences.

Thus the Newton polynomial can be written as

N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\cdots +[y_{0},\ldots ,y_{k}](x-x_{0})(x-x_{1})\cdots (x-x_{{k-1}}).

Newton Forward Divided Difference Formula:

The Newton polynomial can be expressed in a simplified form when x0, x1, …, xk are arranged consecutively with equal spacing. Introducing the notation h = xi+1 – xi for each i = 0,1,…, k-1 $and x = x0 + s.h$ $,$ the difference x – xi can be written as (s – i).h. So the Newton polynomial becomes

{\begin{aligned}N(x)&=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}\\&=\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]\\&=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}].\end{aligned}}

This is called the Newton forward divided difference formula

Newton Backward Divided Difference Formula:

If the nodes are reordered as xk, xk-1, …, x0, the Newton polynomial becomes

N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1}).

If ${x}_{{k}},\;{x}_{{k-1}},\;\dots ,\;{x}_{{0}}$ are equally spaced with $x={x}_{k}+sh$ and ${x}_{{i}}={x}_{{k}}-(k-i)h$ for i = 0, 1, …, k, then,

{\begin{aligned}N(x)&=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}\\&=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}].\end{aligned}}

is called the Newton backward divided difference formula.

Examples:

The divided differences can be written in the form of a table. For example, for a function f is to be interpolated on points x0, …, xn. Write

{\begin{matrix}x_{0}&f(x_{0})&&\\&&{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}}&\\x_{1}&f(x_{1})&&{{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}-{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}&\\x_{2}&f(x_{2})&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&f(x_{n})&&\\\end{matrix}}

Then the interpolating polynomial is formed as above using the topmost entries in each column as coefficients. For example, suppose we are to construct the interpolating polynomial to f(x) = tan(x) using divided differences, at the points:

$x_{0}=-{\tfrac {3}{2}}$	$x_{1}=-{\tfrac {3}{4}}$	$x_{2}=0$	$x_{3}={\tfrac {3}{4}}$	$x_{4}={\tfrac {3}{2}}$
$f(x_{0})=-14.1014$	$f(x_{1})=-0.931596$	$f(x_{2})=0$	$f(x_{3})=0.931596$	$f(x_{4})=14.1014$

Using six digits of accuracy, we construct the table:

{\begin{matrix}-{\tfrac {3}{2}}&-14.1014&&&&\\&&17.5597&&&\\-{\tfrac {3}{4}}&-0.931596&&-10.8784&&\\&&1.24213&&4.83484&\\0&0&&0&&0\\&&1.24213&&4.83484&\\{\tfrac {3}{4}}&0.931596&&10.8784&&\\&&17.5597&&&\\{\tfrac {3}{2}}&14.1014&&&&\\\end{matrix}}

Thus, the interpolating polynomial is

-14.1014+17.5597(x+{\tfrac {3}{2}})-10.8784(x+{\tfrac {3}{2}})(x+{\tfrac {3}{4}})+4.83484(x+{\tfrac {3}{2}})(x+{\tfrac {3}{4}})(x)+0(x+{\tfrac {3}{2}})(x+{\tfrac {3}{4}})(x)(x-{\tfrac {3}{4}})=

=-0.00005-1.4775x-0.00001x^{2}+4.83484x^{3}

Given more digits of accuracy in the table, the first and third coefficients will be found to be zero.

Another example:

The sequence f0 such that f0(1) = 6, f0(2) = 9, f0(3) = 2 and f0(4) =5, i.e., they are 6, 9, 2, 5 from x0 = 1 to x3 = 4.

You obtain the slope of order 1 in the following way:

$f_{1}(x_{0},x_{1})={\frac {f_{0}(x_{1})-f_{0}(x_{0})}{x_{1}-x_{0}}}={\frac {9-6}{2-1}}=3$
$f_{1}(x_{1},x_{2})={\frac {f_{0}(x_{2})-f_{0}(x_{1})}{x_{2}-x_{1}}}={\frac {2-9}{3-2}}=-7$
$f_{1}(x_{2},x_{3})={\frac {f_{0}(x_{3})-f_{0}(x_{2})}{x_{3}-x_{2}}}={\frac {5-2}{4-3}}=3$

As we have the slopes of order 1, it’s possible to obtain the next order:

$f_{2}(x_{0},x_{1},x_{2})={\frac {f_{1}(x_{1},x_{2})-f_{1}(x_{0},x_{1})}{x_{2}-x_{0}}}={\frac {-7-3}{3-1}}=-5$
$f_{2}(x_{1},x_{2},x_{3})={\frac {f_{1}(x_{2},x_{3})-f_{1}(x_{1},x_{2})}{x_{3}-x_{1}}}={\frac {3-(-7)}{4-2}}=5$