## The Lagrange Interpolation

The polynomial that fits a set of node points can also be obtained by the Lagrange interpolation:

 (15)

where are the Lagrange basis polynomials of degree that span the space of all nth degree polynomials:

 (16)

Note that when , we get

 (17)

This polynomial passes through all points:

 (18)

but it is only an approximation of at any other point .

Specially, when , i.e., , we get an important property of the Lagrange basis polynomials:

 (19)

Due to the uniqueness of the polynomial interpolation, , and they have the same error function as in Eq. (12):

 (20)

The computational complexity for calculating one of the basis polynomials is and the complexity for is for each . If there are samples for , then the total complexity is .

To reduce the computational complexity, we express the numerator of based on the (n+1)th degree polynomial defined in Eq. (7) as

 (21)

Then the denominator of can be found by evaluating at :

 (22)

Here the second to the last expression is an indeterminate form which leads to the last equality due to L'Hôpital's rule. Now the Lagrange basis polynomial can be expressed as

 (23)

where is the barycentric weight, and the Lagrange interpolation can be written as:

 (24)

We see that the complexity for calculating for each of the samples of is (both for and the summation), and the total complexity for all samples is .

Example: Approximate function by a polynomial of degree , based on the following points:

Based on these points, we construct the Lagrange polynomials as the basis functions of the polynomial space (instead of the power functions in the previous example):

Note that indeed . The interpolating polynomial can be obtained as a weighted sum of these basis functions:

which is the same as previously found based on the power basis functions, with the same error .

The Matlab code that implements the Lagrange interpolation (both methods) is listed below:

function [v L]=LI(u,x,y)  % Lagrange Interpolation
% vectors x and y contain n+1 points and the corresponding function values
% vector u contains all discrete samples of the continuous argument of f(x)
n=length(x);     % number of interpolating points
k=length(u);     % number of discrete sample points
v=zeros(1,k);    % Lagrange interpolation
L=ones(n,k);     % Lagrange basis polynomials
for i=1:n
for j=1:n
if j~=i
L(i,:)=L(i,:).*(u-x(j))/(x(i)-x(j));
end
end
v=v+y(i)*L(i,:);
end
end


function [v L]=LInew(u,x,y)  % Lagrange interpolation
% u: data points; (x,y) sample points
n=length(x);     % number of sample points
m=length(u);     % number of data points
L=ones(n,m);     % Lagrange basis polynomials
v=zeros(1,m);    % interpolation results
w=ones(1,m);     % omega(x)
dw=ones(1,n);    % omega'(x_i)
for i=1:n
w=w.*(u-x(i));
for j=1:n
if j~=i
dw(i)=dw(i)*(x(i)-x(j));
end
end
end
for i=1:n
L(i,:)=w./(u-x(i))/dw(i);
v=v+y(i)*L(i,:);
end
end