Named after Joseph Louis Lagrange, Lagrange Interpolation is a popular technique of numerical analysis for interpolation of polynomials. In a set of distinct point and numbers xj and yj respectively, this method is the polynomial of the least degree at each xj by assuming corresponding value at yj. Lagrange Polynomial Interpolation is useful in Newton-Cotes Method of numerical integration and in Shamir’s secret sharing scheme in Cryptography.
In this tutorial, we’re going to write a program for Lagrange Interpolation in MATLAB, and go through its mathematical derivation along with a numerical example. You can also check out our earlier tutorial where we discussed a C program for this interpolation technique.
Derivation of Lagrange Interpolation:
Consider a given set of k+1 points, (x0, y0) , (x1, y1), ( x2, y2)….. (xk, yk) where each points are distinct.
Let’s assume a function L(xj) such that L(xj) = yj , j = 0, 1 , 3 , 3 . .. k
Observing the following points
Now, consider what happens when this product is expanded.
Since the product skips m = j, when i = j then all terms are [xj – xm ] / [xj – xm] =1
Also, when i ≠ j, m ≠ j does not produce it and one term in the product will be for m = I, that is, [xi – xi]/[xj – xi] = 0
Zeroing the entire product,
where, δij is Kronecker’s delta.
So, it can be written that:
Therefore, the considered function L(x) is a polynomial with degree at most k and where L(xj) = yj
So, for all i ≠ j, lj(x) includes the term ( x – xi ) in the numerator, therefore the entire product will be found to be zero at x = xj
This is the required formula which will also be used in the program code for Lagrange Interpolation in MATLAB.
The Lagrange Interpolation formula can also be derived from Newton’s divided difference formula.
When a polynomial function f(x) is be approximated with an nth degree polynomial, nth divided difference of f(x) is constant and the (n+1)th divided difference is zero.
Mathematically, f[x0, x1, x2, x3, . . . . . .. . xn] = 0
By using the second property of divided difference, it can be written that
Simplifying this equation, we get
This can be represented as:
Lagrange Interpolation in MATLAB Code:
% Lagrange Interpolation MATLAB Program
function [P,R,S] = lagrangepoly(X,Y,XX)
X = [1 2 3 4 5 6 7 8]; % inputting the values of given x
Y = [0 1 0 1 0 1 0 1]; % inputting the values of given y
%[P,R,S] = lagrangepoly(X,Y);
xx = 0.5 : 0.01 : 8.5;
%axis([0.5 8.5 -5 5])
if size(X,1) > 1; X = X'; end % checking for parameters
if size(Y,1) > 1; Y = Y'; end
if size(X,1) > 1 || size(Y,1) > 1 || size(X,2) ~= size(Y,2)
error('both inputs must be equal-length vectors') % displaying error
end % end of scope of if
N = length(X);
pvals = zeros(N,N);
% for evaluating the polynomial weights for each order
for i = 1:N
% the polynomial with roots may be values of X other than this one
pp = poly(X( (1:N) ~= i));
pvals(i,:) = pp ./ polyval(pp, X(i));
P = Y*pvals;
YY = polyval(P,XX); % output is YY with given XX
P = YY; % assigning to output
% end of scope of if
if nargout > 1 % checking for conndtions
R = roots( ((N-1):-1:1) .* P(1:(N-1)) );
if nargout > 2
% the evalustion of acual value at the poins of zero derivative
S = polyval(P,R);
The above Matlab code for Lagrange method is written for interpolation of polynomials fitting a set of points. The program uses a user-defined function named LAGRANGE(X, Y) with two input parameters which are required to be row vectors.
The row vectors X and Y define a set of n points which are used in Lagrange method for the determination of (n-1)th order polynomial in X which passes through these points. The function of P in the program is to return the n coefficients which define the polynomial in the same order as used by POLY and POLYVAL.
Similarly, R and S are defined to return x-coordinates and y-values at n-1 extreme of the resulting polynomial. YY returns the value of the polynomial sampled at the points which are specified in XX.
All the inputs which are required to give to the program are embedded in the source code. The values of X and Y initially set in the program are:
X = [1 2 3 4 5 6 7 8] and Y = [0 1 0 1 0 1 0 1]
A sample output of this MATLAB program is given below:
Numerical Example in Lagrange Interpolation:
Now, let’s analyze Lagrange Interpolation and its Matlab code mathematically using a different set of parameters. The question here is:
From the following sets of data, find the value of x corresponding to y=15 by using Lagrange Interpolation.
(5,12), (6,13), (9,14), 11,16)
Given value of x and y are:
X: 5 6 9 11
Y: 12 13 14 16
By using the Lagrange Interpolation Formula:
x(y)=(y-13)(y-14)(y-16)*5/(12-13)(12-14)(12-16) + (y-12)(y-14)(y-16)*6/(13-12)(13-14)(13-16) + (y-12)(y-13)(y-16)*9/(14-12)(14-13)(14-16) + (y-12)(y-13)(y-14)*11/(16-12)(16-13)(16-14)
By substituting y= 15, we get x = 11.5; which is the required answer.
If you have any questions regarding Lagrange interpolation, its MATLAB code, or its derivation, bring them up to us from the comments section. You can find more Numerical methods tutorial using Matlab here.