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 75^o = 0.9867, SINE X^o = 0.9875, and SINE 76^o = 0. 9899. To find the missing value of SINE X^o, interpolate between the two known values of SINE 75^o and SINE 76^o. 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, 2X² + 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) = A_o + A₁(X – C₁) + A₂(X – C₁) (X – C₂) + ........+ A_n(X – C₁) (X –C₂)... (X – C_n)

Where:

A_o, ...... , A_n are coefficients of the Interpolating polynomial P(x).

C₁, ......, C_n 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 X_o,......, X_n. 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 [X_o, X_n]. Polynomial poly(Y) is constructed using Newtons formula of Interpolation, which is:

Poly(Y) = F[X_o] + F[X_o X₁](Y – X_o) + F[X_o X₁ X₂](Y – X_o)(Y – X₁) + ..... + F[X_o X_n](Y – X_o) (Y – X₁) ..... (Y – X_n-1)

where:
X_o.... X_n = the points along F[X] that have known values.

F[X_o], ..... F[X_o....., X_n] = are the Divided differences that are calculated

From the values X_o,..., X_n along F[X]

Divided differences are calculated using the formula:
F[X₀.....X_n] = ( F[X₁ ...X_n] - F[X₀...X_n-1] )/(X_n- X₀)

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.