Lagrange Interpolating Polynomial

Interpolation is a method to estimate unknown values of a function based on its known values. For a given set of data points (x₀, y₀), (x₁, y₁), (x₂, y₂),…,(x_n, y_n) interpolation helps us to predict the function value y at a new point x within the range of known x_i values.

The Lagrange interpolation technique does the same. It uses a set of known data points to construct a polynomial that passes through each of them, thus defining the behavior of the function.

It has wide applications in image scaling, AI modeling, and NLPs, among others.

The n^th-order Lagrange polynomial is expressed as:

${P\left( x\right) =\sum ^{n-1}_{i=0}y_{i}\cdot L_{i}\left( x\right)}$

Here,

• n is the degree of the polynomial
• y_i is the given function values corresponding to x_i, for all i = 0, 1, …, n
• L_i(x) are the Lagrange basis polynomials defined as: ${L_{i}\left( x\right) =\prod ^{n-1}_{j=0,j\neq i}\dfrac{x-x_{j}}{x_{i}-x_{j}}}$

For First Order (Degree 1)

The 1^st-order Lagrange interpolation polynomial approximates a function using two data points (x₀, y₀) and (x₁, y₁).

These polynomials are expressed as

P₁(x) = y₀L₀(x) + y₁L₁(x)

⇒ ${P_{1}\left( x\right) =\dfrac{\left( x-x_{1}\right) }{\left( x_{0}-x_{1}\right) }y_{0}+\dfrac{\left( x-x_{0}\right) }{\left( x_{1}-x_{0}\right) }y_{1}}$

For Second Order (Degree 2)

The 2^nd-order Lagrange interpolation polynomial approximates a function using three data points (x₀, y₀), (x₁, y₁), and (x₂, y₂).

Lagrange Interpolation Formula for 2^nd order polynomials is:

P₂(x) = y₀L₀(x) + y₁L₁(x) + y₂L₂(x)

⇒ ${P_{2}\left( x\right) =\dfrac{\left( x-x_{1}\right) \left( x-x_{2}\right) }{\left( x_{0}-x_{1}\right) \left( x_{0}-x_{2}\right) }y_{0}+\dfrac{\left( x-x_{0}\right) \left( x-x_{2}\right) }{\left( x_{1}-x_{0}\right) \left( x_{1}-x_{2}\right) }y_{1}+\dfrac{\left( x-x_{0}\right) \left( x-x_{1}\right) }{\left( x_{2}-x_{0}\right) \left( x_{2}-x_{1}\right) }y_{2}}$

For Third Order (Degree 3)

Similarly, the 3^rd-order interpolation polynomial is given by:

P₃(x) = y₀L₀(x) + y₁L₁(x) + y₂L₂(x) + y₃L₃(x)

⇒ ${P_{3}\left( x\right) =\dfrac{\left( x-x_{1}\right) \left( x-x_{2}\right) \left( x-x_{3}\right) }{\left( x_{0}-x_{1}\right) \left( x_{0}-x_{2}\right) \left( x_{0}-x_{3}\right) }y_{0}+\dfrac{\left( x-x_{0}\right) \left( x-x_{2}\right) \left( x-x_{3}\right) }{\left( x_{1}-x_{0}\right) \left( x_{1}-x_{2}\right) \left( x_{1}-x_{3}\right) }y_{1}+\dfrac{\left( x-x_{0}\right) \left( x-x_{1}\right) \left( x-x_{3}\right) }{\left( x_{2}-x_{0}\right) \left( x_{2}-x_{1}\right) \left( x_{2}-x_{3}\right) }y_{2}+\dfrac{\left( x-x_{0}\right) \left( x-x_{1}\right) \left( x-x_{2}\right) }{\left( x_{3}-x_{0}\right) \left( x_{3}-x_{1}\right) \left( x_{3}-x_{2}\right) }y_{3}}$

Proof

Now, let us verify whether Lagrange interpolating polynomial P(x) satisfies the interpolation property. 

Constructing the Lagrange Basis Polynomials L_i(x)

Each basis polynomial L_i(x) is: 

${L_{i}\left( x\right) =\prod ^{n-1}_{j=0,j\neq i}\dfrac{x-x_{j}}{x_{i}-x_{j}}}$

This means

• At x = x_i (j = i), L_i(x_i) = 1
• At all other points x = x_j (j ≠ i), L_i(x_j) = 0

Verifying the Interpolation Condition

Let us substitute x = x_k into P(x). We have:

${P\left( x_{k}\right) =\sum ^{n-1}_{i=0}y_{i}\cdot L_{i}\left( x_{k}\right)}$

• If k = i, L_i(x_k) = 1
• If k ≠ i, L_i(x_k) = 0

Thus, only when i = k, P(x) becomes

${P\left( x_{k}\right) =\sum ^{n-1}_{i=0}y_{i}\cdot L_{i}\left( x_{k}\right)}$ = y_k ⋅ 1 = y_k 

⇒ P(x_k) = y_k, showing that the Lagrange polynomial interpolates the given data points.

from the fact 

Verifying the Uniqueness of the Polynomial

The interpolation polynomial P(x) is unique. Now, let us suppose there exists another polynomial Q(x) of degree n – 1 that also interpolates the same data points.

Then, R(x) = P(x) – Q(x), a polynomial of degree ≥ n – 1 with n roots at x₀, x₁, …, x_{n – 1}  

Since a polynomial of degree n – 1 can have at most n – 1 roots, R(x) must be identically zero.

Thus, P(x) = Q(x), proving that any two polynomials interpolating the same data points must be identical.

The uniqueness of the polynomials is followed.

Properties

The Lagrange polynomial follows the following properties:

Degree 

The Lagrange Polynomial, P(x), is of degree n – 1, where n is the number of data points. It is mathematically expressed as:

P(x_i) = y_i, for all i = 0, 1, …, n – 1

Here,

(x₀, y₀), (x₁, y₁), …, (x_{n – 1}, y_{n – 1}) represent the given set of n  data points

Uniqueness

For a given set of n+ distinct data points, the Lagrange interpolating polynomial is unique. Also, the polynomial passes exactly through the given data points.

Solved Examples