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

(15) |

(16) |

(17) |

(18) |

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) |

(22) |

(23) |

(24) |

**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:

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