C program of Newton Backward Interpolation Formula

Mr Coder August 25, 2012 12

C program of Newton Backward Interpolation formula : Newton has proposed several methods of estimating the values of any number at certain point by learning the behavior of previous values. Newton’s Backward interpolation formula is one of them. Newton’s backward interpolation is based on interpolating the newton’s polynomial which is sometimes also referred as Newton’s divided differences interpolation polynomial because the coefficients of the polynomial are calculated using divided differences.

(From Wikipedia) :Given a set of k + 1 data points

                                                               (x_0, y_0),\ldots,(x_k, y_k)

where no two xj are the same, the interpolation polynomial in the Newton form 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 n_0(x) \equiv 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}).

Now

If the nodes are reordered as {x}_{k},{x}_{k-1},\dots,{x}_{0}, 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,\;\dots,\;k ,then,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}]

N(x)=\sum_{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots,{y}_{k-i}]

is called the Newton Backward Divided Difference Formula.

Now Let us see how to implement above logic using C program. Below C program of Newton Backward Interpolation formula which takes number of values of x as input from user and then takes values of x and corresponding values of y. Then it asks user at which point he wish to estimate the value and the displays the output value of N(x) at that point.

C program of Newton Backward Interpolation Formula :

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<process.h>
#include<conio.h>
#include<stdlib.h>

int main()
{
int n;            
int i,j,k; 
float mx[10],my[10];           
float x,h,x0=0,fun=0,p;                                          
float y0,sum=0,diff[20][20];                            
float y1,y2,y3,y4;           

printf("----------------------------------------------------------------------\n");
printf("-------------------made by C code champ ------------------------------\n");
printf("----------------------------------------------------------------------\n");
printf("\n\n\t!! NEWTON'S BACKWARD INTERPOLATION FORMULA !! ");
printf("\n\n Enter the values of x you want to enter -> ");
scanf("%d",&n);

printf("\n\n Enter the value in the form of x : ");
for(i=0;i<n;i++)
   {
   printf("\n Enter the value of x[%d] : ",i+1);
   scanf("%f",&mx[i]);
   }

printf("\n\n Enter the value in the form of y : ");
for(i=0;i<n;i++)
   {
   printf("\n Enter the value of y[%d] : ",i+1);
   scanf("%f",&my[i]);
   }

printf("\n\n Enter the value of x for which u want the value of y : ");
scanf("%f",&x);

// Calculation and processing section.
h=mx[1]-mx[0];
for(i=0;i<n-1;i++)
   diff[i][1]=my[i+1]-my[i];

for(j=2;j<=4;j++)
   for(i=0;i<n-j;i++)
      diff[i][j]=diff[i+1][j-1]-diff[i][j-1];
i=0;

while(!mx[i]>x)
     i++;

x0=mx[i];
sum=0;

y0=my[i];
fun=1;

p=(x-x0)/h;
sum=y0;

for(k=1;k<=4;k++)
   {
   fun=(fun*(p-(k-1)))/k;
   sum=sum+fun*diff[i][k];
   }

// Output
printf("\n When x = %6.4f , y = %6.8f\n\n",x,sum);
getch();
system("pause");
}

We hope you all have enjoyed the C program of Newton Backward Interpolation formula i.e. backward divided difference. If you have any issues with above code, ask us in form of comments.

12 Comments »

  1. Tester August 25, 2012 at 9:04 am - Reply

    testing…

  2. online tv software September 17, 2012 at 2:56 am - Reply

    i read your article and loave it so much ,thank you so much.

  3. Nichole Semenick September 18, 2012 at 7:20 pm - Reply

    hey buddy, this is a quite intriguing post

    • Morrie October 19, 2012 at 11:14 pm - Reply

      Touchdown! That’s a raelly cool way of putting it!

  4. ugg outlet store October 6, 2012 at 8:50 am - Reply

    Thanks ! Supper Post !!

  5. turcioshumb October 9, 2012 at 6:41 pm - Reply

    wow its great post..

  6. guild wars 2 gold October 10, 2012 at 6:38 am - Reply

    Wow! Thank you! I permanently wanted to write on my site something like that. Can I include a part of your post to my blog?

    • Mr Coder October 10, 2012 at 7:29 pm - Reply

      Yes! you can include.

      • Della October 20, 2012 at 12:57 am - Reply

        You’ve got it in one. Couldn’t have put it beettr.

  7. Jacoby October 19, 2012 at 9:23 pm - Reply

    If my probelm was a Death Star, this article is a photon torpedo.

  8. chanel handbag November 3, 2012 at 10:05 pm - Reply

    Thank you a lot for providing individuals with a very splendid opportunity to read from this website. It really is so terrific and as well , stuffed with fun for me and my office colleagues to visit the blog particularly three times in 7 days to read through the new guides you have got. And lastly, I am just always fulfilled with your perfect solutions you serve. Some 2 facts in this post are completely the simplest we’ve ever had.

  9. Gagan Koda November 23, 2012 at 3:35 am - Reply

    I have found a simpler code than this. Not sure which one is good.

    C/C++ program for divide difference interpolation formula.
    http://ashishrevar.com/2011/11/divide-difference-interpolation-formula/#comment-488

Leave A Response »