In numerical analysis, Lagrange polynomials are used for polynomial interpolation. For a given set of distinct points $x_j$ and numbers $y_j$, the Lagrange polynomial is the polynomial of the least degree that at each point $x_j$ assumes the corresponding value $y_j$ (i.e. the functions coincide at each point). The interpolating polynomial of the least degree is unique, however, and it is therefore more appropriate to speak of “the Lagrange form” of that unique polynomial rather than “the Lagrange interpolation polynomial”, since the same polynomial can be arrived at through multiple methods.

Given a set of k + 1 data points

$(x_0, y_0),\ldots,(x_j, y_j),\ldots,(x_k, y_k)$

where no two $x_j$ are the same, the Lagrange Interpolation form is a linear combination

$L(x) := \sum_{j=0}^{k} y_j \ell_j(x)$

of Lagrange basis polynomials

$\ell_j(x) := \prod_{\begin{smallmatrix}0\le m\le k\\ m\neq j\end{smallmatrix}} \frac{x-x_m}{x_j-x_m} = \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots \frac{(x-x_k)}{(x_j-x_k)},$

where $0\le j\le k$. Note how, given the initial assumption that no two $x_i$ are the same, $x_j - x_m \neq 0$, so this expression is always well-defined. The reason pairs $x_i = x_j$ with $y_i\neq y_j$ are not allowed is that no interpolation function $L$ such that $y_i = L(x_i)$ would exist; a function can only get one value for each argument $x_i$. On the other hand, if also $y_i = y_j$, then those two points would actually be one single point.

For all $i\neq j$, $\ell_j(x)$ includes the term $(x-x_i)$ in the numerator, so the whole product will be zero at $x=x_i$:

$\ell_{j\ne i}(x_i) = \prod_{m\neq j} \frac{x_i-x_m}{x_j-x_m} = \frac{(x_i-x_0)}{(x_j-x_0)} \cdots \frac{(x_i-x_i)}{(x_j-x_i)} \cdots \frac{(x_i-x_k)}{(x_j-x_k)} = 0.$

On the other hand,

$\ell_i(x_i) := \prod_{m\neq i} \frac{x_i-x_m}{x_i-x_m} = 1$

In other words, all basis polynomials are zero at $x=x_i$, except $\ell_i(x)$, for which it holds that $\ell_i(x_i)=1$, because it lacks the $(x-x_i)$ term.

It follows that $y_i \ell_i(x_i)=y_i$, so at each point $x_i$, $L(x_i)=y_i+0+0+\dots +0=y_i$, showing that $L$ interpolates the function exactly. ( Definition Source : Wikipedia )

The Lagrange Interpolation C Code is written below.

#include <stdio.h>
#include <stdlib.h>

double Lagrange(int n, int k,double value);
double* fx;
double* x;
double Calculate(int n, double x);
void main() {
int size;
double question;
scanf("%d", &size);

fx = (double*)malloc(sizeof(double)*size);
x = (double*)malloc(sizeof(double)*size);
for (int i = 0; i < size; i++)
{
printf("Enter  x(%d):", i);
scanf("%lf", &x[i]);
printf("Enter fx(%d):", i);
scanf("%lf", &fx[i]);
printf("------\n");
}
scanf("%lf", &question);
printf("\n");
printf("Result =====> f(%4.2lf) = %5.4lf\n",question, Calculate(size, question));
printf("\n");
system("PAUSE");
}

double Lagrange(int n, int k, double val)
{
double result = 1;
for (int i = 0; i < n; i++)
{
if (i!=k)
result = result * (double)((val - x[i]) / (x[k] - x[i]));
}
return result;
}

double Calculate(int n,double x)
{
double intPolasyon = 0;
double *L = (double*)malloc(sizeof(double)*n);
double *F = (double*)malloc(sizeof(double)*n);
for (int i = 0; i < n; i++)
{
L[i] = Lagrange(n, i, x);
intPolasyon += fx[i] * L[i];
printf("L(%d) = %5.3lf\n", i, L[i]);
}

printf("\n");
return intPolasyon;
}

Lagrange Interpolation C Code Result