Newton Backward Interpolation Program 

What is Newton’s Forward and Backward Interpolation ?


Given the set of (n+1) values of x and y, it is required to find y n (x), a polynomial of the nth degree such that y and y n (x) agree at the tabulated points. The values of x be equidistant i.e. xi = x0 + ih, i=0, 1, 2…..n.

Since y n(x) is a polynomial of the nth degree                                                                                                                                                                                                                                       
y n(x) =a0 +a1(x-x0) +a2(x-x0)(x-x1)………….+an(x-x0)………….(x-x n-1)
Imposing now the condition that y and yn(x) should agree at the set of tabulated points and applying x=x0+ph we get Newton’s Forward difference interpolation formula which is given by.
y n(x) = y0 + pDy0 + p (p-1) / 2! D2y0+ p (p-1) (p-2) / 3! D3y0 + ……… + p (p-1) (p-2)…. (p-n+1) / n! Dn y0

It is useful for interpolation near the beginning of a set of tabular values.
Similarly if yn (x) chosen in the form
y n(x) = a0+a1 (x-x n) + a2 (x-x n) (x-x n-1) +……..an(x-x n) (x-x n-1)……(x-x1) then we have
y n (x) = y n + pÑy n + p(p+1) / 2 Ñ2 y n + ………+ p(p+1)…..(p+n-1) / n! Ñ n y n           where p= x-x n / h
This is Newton’s Backward difference interpolation formula and it uses tabular values to the left of y n. It is useful for interpolation near the end of the tabular values.

#Invoke stdio.h, conio.h and math.h header file here
void main()
{
  float x[10],y[10][10],sum,p,u,temp;
  int i,n,j,k=0,f,m;
  float fact(int);
  clrscr();
  printf("\nhow many record you will be enter: ");
  scanf("%d",&n);
  for(i=0; i  {
   printf("\n\nenter the value of x%d: ",i);
   scanf("%f",&x[i]);
   printf("\n\nenter the value of f(x%d): ",i);
   scanf("%f",&y[k][i]);
  }
  printf("\n\nEnter X for finding f(x): ");
  scanf("%f",&p);

  for(i=1;i  {
    for(j=i;j    {
     y[i][j]=y[i-1][j]-y[i-1][j-1];
    }
  }
  printf("\n_____________________________________________________\n");
  printf("\n  x(i)\t   y(i)\t    y1(i)    y2(i)    y3(i)    y4(i)");
  printf("\n_____________________________________________________\n");
  for(i=0;i  {
    printf("\n %.3f",x[i]);
    for(j=0;j<=i;j++)
    {
     printf("   ");
     printf(" %.3f",y[j][i]);
    }
   printf("\n");
  }

  i=0;
  do
  {
   if(x[i]
    k=1;
   else
    i++;
  }while(k != 1);
  f=i+1;
  u=(p-x[f])/(x[f]-x[f-1]);
  printf("\n\n u = %.3f ",u);

   n=n-i+1;
  sum=0;
  for(i=0;i  {
   temp=1;
   for(j=0;j   {
    temp = temp * (u + j);
   }
    m=fact(i);
    sum = sum + temp*(y[i][f]/m);
  }
  printf("\n\n f(%.2f) = %f ",p,sum);
  getch();
}

float fact(int a)
{
  float fac = 1;

  if (a == 0)
   return (1);
  else
   fac = a * fact(a-1);

  return(fac);
}



Output