Newton’s backward interpolation

Newton’s backward interpolation

Suppose $$y=f( x )$$is tabulated for equally spaced valued
$$x=x_0,x_0+h,x_0+2h,\ldots ,x_0+nh$$
given by
$$y=y_0,y_1,y_2,\ldots ,y_n$$
Here,
$$x_i=x_0+ih$$ for $$i=0,1,2,\ldots ,n$$
Now, assuming $$y=f( x )$$ as a polynomial of degree n in x, we write
$$y=a_n+a_{n-1}( x-x_n )+a_{n-2}( x-x_n )( x-x_{n-1} )+\ldots +a_0( x-x_n )\ldots ( x-x_1 )$$

Putting, $$x=x_n$$, we get
$$y=a_n+a_{n-1}( x-x_n )+a_{n-2}( x-x_n )( x-x_{n-1} )+\ldots +a_0( x-x_n )\ldots ( x-x_1 )$$
or $$y_n=a_n+a_{n-1}($$ $$x_n$$ $$-x_n )+a_{n-2}($$ $$x_n$$ $$-x_n )($$ $$x_n$$ $$-x_{n-1} )+\ldots +a_0($$ $$x_n$$ $$-x_n )\ldots ($$ $$x_n$$ $$-x_1 )$$
or $$y_n=a_n+0+...$$
or $$y_n=a_n$$

Putting, $$x=x_{n-1}$$, we get
$$y=a_n+a_{n-1}( x-x_n )+a_{n-2}( x-x_n )( x-x_{n-1} )+\ldots +a_0( x-x_n )\ldots ( x-x_1 )$$
or $$y_{n-1}=a_n+a_{n-1}($$ $$x_{n-1}$$ $$-x_n )+a_{n-2}($$ $$x_{n-1}$$ $$-x_n )($$ $$x_{n-1}$$ $$-x_{n-1} )+\ldots$$
$$+a_0($$ $$x_{n-1}$$ $$-x_n ) ($$ $$x_{n-1}$$ $$-x_{n-1} )$$

or $$y_{n-1}=a_n+a_{n-1}( x_{n-1}-x_n )+0+...$$
or $$y_{n-1}=a_n+a_{n-1}( -h)$$
or $$y_{n-1}=y_n-a_{n-1}h$$
or $$a_{n-1}=\frac{y_n-y_{n-1}}{h}$$
or $$a_{n-1}=\frac{\nabla {y_n}}{h}$$

Putting, $$x=x_{n-2}$$, we get
$$y=a_n+a_{n-1}( x-x_n )+a_{n-2}( x-x_n )( x-x_{n-1} )+\ldots +a_0( x-x_n )\ldots ( x-x_1 )$$
or $$y_{n-2}=a_n+a_{n-1}($$ $$x_{n-2}$$ $$-x_n )+a_{n-2}($$ $$x_{n-2}$$ $$-x_n )($$ $$x_{n-2}$$ $$-x_{n-1} )$$
$$+a_{n-3}($$ $$x_{n-2}$$ $$-x_n ) ($$ $$x_{n-2}$$ $$-x_{n-1} )($$
$$x_{n-2}$$ $$- x_{n-2})+...$$
or $$y_{n-2}=a_n+a_{n-1}( x_{n-2}-x_n )+ a_{n-2}( x_{n-2}-x_n )( x_{n-2}-x_{n-1} )+0+...$$
or $$y_{n-2}=a_n+a_{n-1}( x_{n-2}-x_n )+ a_{n-2}( x_{n-2}-x_n )( x_{n-2}-x_{n-1} )$$
or $$y_{n-2}=a_n+a_{n-1}( 2h )+ a_{n-2}(2h)(h)$$
or $$y_{n-2}=2a_n+a_{n-1}( h )+2 a_{n-2}(h^2)$$
or $$a_{n-2}=\frac{\nabla ^2y_n}{2!h^2}$$

Similarly, we get
$$a_{n-i}=\frac{\nabla^i y_n}{i!h^i}$$ for $$i=0,1,2,\ldots ,n$$

Setting , $$x={x_n}+ph$$ and substituting, $$a_i$$ for $$i=0,1,2,\ldots ,n$$ we get
$$y=a_n+a_{n-1}( x-x_n )+a_{n-2}( x-x_n )( x-x_{n-1} )+\ldots +a_0( x-x_n )\ldots ( x-x_1 )$$
or $$y=y_n+\frac{\nabla y_n}{h}[ ph ]+ \frac{\nabla ^2y_n}{2!h^2} [ p( p+1 )h^2 ]+...$$
or $$y=y_n+\nabla y_n[ p ]+ \frac{\nabla ^2y_n}{2!} [ p( p+1 )]+...$$

This is Newton’s backward difference interpolation formula and it is useful for interpolation near the end of a set of tabular values.

Example 1

The population of a town was as given below. Estimate the population for the year 1925.

 x 1891 1901 1911 1921 1931 y 46 66 81 93 101

Solution
According to given set of data values, we form difference table as below

 X Y 1st diff 2nd diff 3rd diff 4th diff 1891 46 66-46=20 1901 66 15-20=-5 81-66=15 (-3)-(-5)=2 1911 81 12-15=-3 (-1)-(2)=-3 93-81=12 (-4)-(-3)=-1 1921 93 8-12=-4 101-93=8 1931 101

Here,
$$h=10$$ and $$x_n=1931$$
Thus, we have
$$x=x_n+ph$$
or $$1925=1931+p\times 10$$
or $$p=-0.6$$
Using formula, we get
$$y=y_n+\nabla y_n[ p ]+ \frac{\nabla ^2y_n}{2!} [ p( p+1 )]+...$$
or $$y_{1925}= 101+ 8 [ -0.6 ]+ \frac{(-4)}{2!} [ (-0.6)( 0.4 )]+\frac{(-1)}{3!} [ (-0.6)( 0.4 )(1.4)]+\frac{(-3)}{4!} [ (-0.6)( 0.4 )(1.4)(2.4)]$$

or $$y_{1925}=101-4.8+0.48+0.056+0.1008$$

or $$y_{1925}=96.83$$
This completes.

Example 2

In the table below, values of y are consecutive terms of a series are given. Find tenth term of the series.

 3 4 5 6 7 8 9 2.7 6.4 12.5 21.6 34.3 51.2 72.9

Solution
According to given set of data values, the difference table is

 X Y 1st diff 2nd diff 3rd diff 3 2.7 3.7 4 6.4 2.4 6.1 0.6 5 12.5 3 9.1 0.6 6 21.6 3.6 12.7 0.6 7 34.3 4.2 16.9 0.6 8 51.2 4.8 21.7 9 72.9

Here,
$$h=1$$ and $${x_n}=9$$
Thus, we have
$$x={x_n}+ph$$
or $$10=9+p$$
or $$p=1$$
Now, tenth term of the series is
$$y=y_n+p\nabla y_n+\frac{p( p+1 )}{2!}\nabla ^2y_n+\ldots$$
or $$y=72.9+21.7+4.8\frac2{2!}+0.6\frac{2\times 3}{3!}$$
or $$y=100$$

Example 3

Find cubic polynomial which takes the following values.
$$y( 0 )=1,y( 1 )=0,y( 2 )=1$$ and $$y( 3 )=10$$

Solution
According to given set of data values, we form difference table as below

 X Y 1st diff 2nd diff 3rd diff 0 1 -1 1 0 2 1 6 2 1 8 9 3 10

Here,
$$h=1$$ and $$x_n=3$$
Thus, we have
$$x=x_n+ph$$
or $$p=(x-3)$$
Now, cubic polynomial for given data value is
$$y=y_n+p\nabla y_n+\frac{p( p+1 )}{2!}\nabla ^2y_n+\ldots$$
or $$y=10+(x-3)(9 )+\frac{(x-3)(x-2)}{2!}(8)+\frac{(x-3)(x-2)(x-1)}{3!}(6)$$
or $$y=10+9x-27+4(x^2-5x+6)+(x-1)(x^2-5x+6)$$
or $$y=10+9x-27+(4x^2-20x+24)+(x^3-6x^2+11x-6)$$
or $$y=x^3-2x^2+1$$
This completes.

Exercise

Use Newton's Backward difference formula to compute followings.
1. Find the value when x=4 from the following table [Answer: 33]
 x 0 1 2 3 y 1 0 1 10
2. Find solution of f(11) of an equation $$x^2-x+1$$ using a = 2 and b= 10, step value h = 1.
3. Estimate the number of students who obtained marks between 75 and 80
 Marks 30-40 40-50 50-60 60-70 70-80 Number 31 42 51 35 31
4. Find cubic polynomial which takes the following values: y( 0 )=1,y( 1 )=2, y( 2 )=1 and y( 3 )=10