• Loading
    • Polynomial Interpolation And Its Implementation In C

      What is Polynomial Interpolation?


      Interpolation is a method of estimating a missing value that lies between two known values. For example, if you want to find the value of an angle that has the SINE value of 0.9875, assume that the values of SINE 75o = 0.9867, SINE Xo = 0.9875, and SINE 76o = 0. 9899. To find the missing value of SINE Xo, interpolate between the two known values of SINE 75o and SINE 76o. There are two methods of implementing interpolation, Linear and Polynomial:
      • Linear Interpolation: Enables change from one known value to the next known value. It is used for statistical calculations, such as, calculating Variance, Standard Deviations, and Median.
      • Polynomial Interpolation: Enables estimating the missing values of a function F(X) from few known values. It is used for problems that can be expressed in terms of a function F(X).

      Polynomial Interpolation is a numerical method that estimates the missing values of a function F(X) from the known values of F(X). It uses polynomials for estimating the missing values. A polynomial is a mathematical expression containing numbers and positive integer powers associated with an unknown element, X. For example, 2X2 + 10X + 20 is a polynomial of degree 2. The degree of a polynomial is the highest integer power of X. The Polynomial interpolation method is used for problems that can be expressed in terms of a function F(X), such as problems of Differential Calculus and Regression Analysis .

      Working of Polynomial Interpolation

      The working of Polynomial interpolation is the process of constructing a polynomial. The standard form of an Interpolating polynomial is known as the Newton form, the structure of which is:

      P(x) = Ao + A1(X – C1) + A2(X – C1) (X – C2) + ........+ An(X – C1) (X –C2)... (X – Cn)

      Where:

      Ao, ...... , An are coefficients of the Interpolating polynomial P(x).

      C1, ......, Cn are centers of the Interpolating polynomial, when plotted on a graph.

      There are two steps involved in Polynomial interpolation, Constructing and Evaluating an Interpolating polynomial.

      Constructing an Interpolating polynomial involves constructing a polynomial that interpolates a function F(X). To interpolate F(X), a polynomial poly(Y) is constructed using m + 1 points. The points with known values are grouped together and named Xo,......, Xn. These points are known as Interpolation points. Using the polynomial poly(Y) , the value of F(X) at X = Y is estimated, which requires that the point Y lies between the points [Xo, Xn]. Polynomial poly(Y) is constructed using Newtons formula of Interpolation, which is:

      Poly(Y) = F[Xo] + F[Xo X1](Y – Xo) + F[Xo X1 X2](Y – Xo)(Y – X1) + ..... + F[Xo Xn](Y – Xo) (Y – X1) ..... (Y – Xn-1)


      where:
      Xo.... Xn = the points along F[X] that have known values.

      F[Xo], ..... F[Xo....., Xn] = are the Divided differences that are calculated

      From the values Xo,..., Xn along F[X]

      Divided differences are calculated using the formula:
      F[X0.....Xn] = ( F[X1 ...Xn] - F[X0...Xn-1] )/(Xn- X0)

      Evaluating an Interpolating polynomial involves calculating the coefficients of the interpolating polynomial, poly(Y) for the points with unknown values. The known values of the points are substituted in the Newtons formula of Interpolation, for calculating the unknown values. For example, if you want to know the value of Y at F[X]= -2.5, assume the known values are: Xo = -3.0 and F[Xo] = -5.0, X1 = -2.0 and F[X1] = -1.1, X2 = 2.0 and F[X2] = 1.9, and X3 = 3.0 and F[X3] = 4.8. These values are substituted in the Divided difference formula for calculating the coefficients. The values of coefficients calculated through the Divided difference formula are substituted in the Newtons formula of Interpolation to estimate the value of poly(Y) = -2.5.

      Implementing Polynomial Interpolation in C


      Polynomial Interpolation is implemented in C for estimating the unknown values of points along a function F[X] because calculating the unknown values manually may lead to inaccurate and inconsistent results.

      Code:
      /* C program to implement Polynomial Interpolation */
      
      #include <stdlib.h>
      #include <string.h>
      #include<stdio.h>
      #include<conio.h> 
      /* C header files */
      
      /*declaration of variables */
      int poly(const double *y, const double *fx, int m, double *a, double *ps, int l) 
      {
      double value, *tb,*coeff;
      int o, p, q;
      
      /* reserve memory for the divided-difference table and coefficients.*/
       
      if ((tb = (double *)malloc(sizeof(double) * m)) == NULL)
         return -1;
       
      if ((coeff = (double *)malloc(sizeof(double) * m)) == NULL) {
       
         free(tb);
         return -1;
       
      }
       
      /* Initializing the coefficients / 
      memcpy(tb, fx, sizeof(double) * m);
       
      /* calculating the coefficients of the Interpolating Polynomial */ 
      coeff[0] = tb[0];
       
      for (q = 1; q < n; q++) {
       
         for (r = 0; r < m - q; r++) {
       
            p = r + q;
            tb[r] = (tb[r + 1] - tb[r]) / (y[p] - y[r]);
       
         }
       
         coeff[q] = tb[0];
       
      }
       
      free(tb);
       
      /* calculating the unknown values at the specified points */
      for (q = 0; q < l; q++)
       {
         ps[q] = coeff[0];
       
         for (p = 1; p < m; p++) 
         {
            value = coeff[p];
       
            for (r = 0; r < p; r++)
               value = value * (a[q] - y[r]);
       
            ps[q] = ps[q] + value;
          }
       }
       
      free(coeff);
      return 0;
      }
      The above code constructs an Interpolating Polynomial and uses this polynomial to find the unknown values of the function F[X].

      Polynomial Interpolation is used for scientific calculations, such as calculations involved in atomic research and weather forecast.
    • Enter your email address:

      Delivered by FeedBurner

    • Latest Posts

      kate01

      Re: Transfer iPhone SMS and MMS to Android

      You can transfer SMS messages to Android devices manually and freely by following the steps shared in this guide: goo.gl/L6rZNS

      kate01 06-29-2015, 03:51 AM Go to last post
      Moveblelago

      Re: Nuestra historia

      “现在微博、朋友圈往往都是负面消息发酵的很快,但今天这位老人
      而在面对被栽赃成为杀妻凶手悬疑迷雾时,他又必须在悬疑色彩重重

      Moveblelago 06-14-2015, 07:05 PM Go to last post
      Moveblelago

      Re: hi I join Tech Forum

      理改编,将幼儿园段落单拿出来组成一部电影,删去了原作中很多败
      苦难学说”在该剧中逐渐升级,孙家兄弟的平凡生活将再次遭受磨难

      Moveblelago 06-14-2015, 04:46 PM Go to last post
      Moveblelago

      Re: hi I join Tech Forum

      众。梁文道户外走读遭“炮轰” 接受意见反“嘲”高晓松发布会上
      日探班《霍比特人&#50;》片场,采访甘道夫扮演者伊恩&#183;迈凯伦,越来

      Moveblelago 06-14-2015, 04:33 PM Go to last post
      Moveblelago

      Re: hi I join Tech Forum

      局。几乎场场爆满,其中三线城市上座率达到&#56;&#54;&#37;,首周末票房轻
      平凡的世界》的创作态度严谨,从筹备到制作超过七年。剧组除了赶

      Moveblelago 06-14-2015, 04:11 PM Go to last post



    Disclaimer: Users of techforum4u.com are responsible for ensuring that any material they post (article, blog posts, images or other mulitimedia content) does not violate or infringe upon the copyright, patent, trademark, or any personal or proprietary rights of any third party, and is posted with the permission of the owner of such rights.Anyone who violates these rules may have their access privileges removed without warning.