Lagrange Interpolation in MATLAB

0
4551

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

  • Lj(x) contains k factors in product and each factor has x
  • Lagrange Interpolation in MATLAB - Lagrange Polynomial

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,

Lagrange Interpolation in MATLAB - Zeroing Process

where, δij is Kronecker’s delta.

So, it can be written that:

Lagrange Interpolation in MATLAB - Polynomial Equation

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

Lagrange Interpolation in MATLAB - Formula

This is the required formula which will also be used in the program code for Lagrange Interpolation in MATLAB.

NOTE:

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

Lagrange Interpolation in MATLAB - Derivation from Divided Difference

Simplifying this equation, we get

Lagrange Interpolation in MATLAB - Derivation from Divided Difference

This can be represented as:

Lagrange Interpolation MATLAB Code - Divided Difference Derivation

Lagrange Interpolation in MATLAB Code:

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:

Lagrange Interpolation in MATLAB - Output

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)

Solution

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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here