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;
	printf("Please enter function's point count:\n");
	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");
	}
	printf("Please enter point to calculate:\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

Lagrange Interpolation C Code Result