Last modified: December 01, 2022

This article is written in: 🇺🇸

Lagrange Polynomial Interpolation

Lagrange Polynomial Interpolation is a widely used technique for determining a polynomial that passes exactly through a given set of data points. Suppose we have a set of $(n+1)$ data points $(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$ where all $x_i$ are distinct. The aim is to find a polynomial $L\left(x\right)$ of degree at most $n$ such that:

$$L\left(x_i\right)=y_i,\text{for}i=0,1,\dots ,n.$$

Instead of solving a system of linear equations (as would be required if we used a general polynomial form), Lagrange interpolation provides a direct formula for the interpolating polynomial in terms of Lagrange basis polynomials. This approach is conceptually straightforward and does not require forming and solving large linear systems.

Conceptual Illustration:

Imagine that you have three points $(x_0,y_0),(x_1,y_1),(x_2,y_2)$. The Lagrange form builds a polynomial that goes exactly through these points. Each Lagrange basis polynomial $P_i\left(x\right)$ is constructed to be zero at all $x_j$ except $x_i$. By taking a suitable linear combination of these basis polynomials with weights given by $y_i$, we get an interpolating polynomial $L\left(x\right)$.

The Lagrange polynomial passing through all these points is unique and matches every given data point exactly.

Mathematical Formulation

Given $(n+1)$ distinct points $(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$, the Lagrange interpolation polynomial is constructed as follows:

I. Lagrange Basis Polynomials:

For each $i$ in $0,1,\dots ,n$, define the $i$-th Lagrange basis polynomial $P_i\left(x\right)$ by:

$$P_i\left(x\right)=\prod _{\begin{array}{c}j=0j\ne i\end{array}}^n\frac{x-x_j}{x_i-x_j}.$$

Notice that $P_i\left(x_k\right)={\delta }_{ik}$, where ${\delta }_{ik}$ is the Kronecker delta. In other words:

$$P_i\left(x_k\right)=\{\begin{array}{cc}1& \text{if}i=k,\\ 0& \text{if}i\ne k.\end{array}$$

II. Lagrange Interpolating Polynomial:

Once we have the $P_i\left(x\right)$, the interpolating polynomial $L\left(x\right)$ is given by:

$$L\left(x\right)=\sum _{i=0}^n{y}_i{P}_i\left(x\right).$$

By construction, $L\left(x_j\right)=y_j$ for all $j$. The degree of $L\left(x\right)$ is at most $n$.

Derivation

Starting from the requirement that $L\left(x\right)$ matches all data points:

$$L\left(x_i\right)=y_i\text{for}i=0,1,\dots ,n.$$

Consider polynomials $P_i\left(x\right)$ defined as:

$$P_i\left(x\right)=\prod _{\begin{array}{c}j=0j\ne i\end{array}}^n\frac{x-x_j}{x_i-x_j}.$$

This construction ensures that for each fixed $i$:

• When $x=x_i$, the numerator in $P_i\left(x\right)$ contains all factors $(x_i-x_j)$ for $j\ne i$, which exactly cancel with the denominator $(x_i-x_j)$. Thus, $P_i\left(x_i\right)=1$.
• For $x=x_k$ with $k\ne i$, the factor $(x_k-x_k)$ in the numerator makes $P_i\left(x_k\right)=0$.

Hence $P_i\left(x\right)$ acts like a "selector" polynomial that equals 1 at $x_i$ and 0 at every other $x_j$.

To construct $L\left(x\right)$ that passes through all points, we form:

$$L\left(x\right)=\sum _{i=0}^n{y}_i{P}_i\left(x\right).$$

Evaluating at $x=x_k$:

$$L\left(x_k\right)=\sum _{i=0}^n{y}_i{P}_i\left(x_k\right)=y_k,$$

since $P_k\left(x_k\right)=1$ and $P_i\left(x_k\right)=0$ for $i\ne k$.

Algorithm Steps

I. Input:

A set of $(n+1)$ points $(x_i,y_i)$ with all $x_i$ distinct.

II. Initialization:

Set $L\left(x\right)=0$.

III. Compute Lagrange Basis Polynomials:

For each $i=0,1,\dots ,n$:

• Initialize $P_i\left(x\right)=1$.
• For each $j=0,1,\dots ,n$ with $j\ne i$:

$$P_i\left(x\right)=P_i\left(x\right)\cdot \frac{x-x_j}{x_i-x_j}.$$

IV. Form the Interpolating Polynomial:

Compute:

$$L\left(x\right)=\sum _{i=0}^n{y}_i{P}_i\left(x\right).$$

Result:

The polynomial $L\left(x\right)$ is the desired Lagrange interpolating polynomial. To interpolate at any $x$, just evaluate $L\left(x\right)$.

Example

Given Points:

Let’s consider three points:

$$A(-1,1),B(2,3),C(3,5).$$

We have $n=2$ (since there are 3 points), and thus the polynomial $L\left(x\right)$ will be of degree at most 2.

Compute $P_0\left(x\right)$ for the point $A(-1,1)$:

$$P_0\left(x\right)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}=\frac{(x-2)(x-3)}{(-1-2)(-1-3)}=\frac{(x-2)(x-3)}{(-3)(-4)}=\frac{(x-2)(x-3)}{12}.$$

Compute $P_1\left(x\right)$ for the point $B(2,3)$:

$$P_1\left(x\right)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}=\frac{(x+1)(x-3)}{(2+1)(2-3)}=\frac{(x+1)(x-3)}{3\cdot (-1)}=-\frac{(x+1)(x-3)}{3}.$$

Compute $P_2\left(x\right)$ for the point $C(3,5)$:

$$P_2\left(x\right)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}=\frac{(x+1)(x-2)}{(3+1)(3-2)}=\frac{(x+1)(x-2)}{4}.$$

Now, plug these into $L\left(x\right)$:

$$L\left(x\right)=y_0{P}_0\left(x\right)+y_1{P}_1\left(x\right)+y_2{P}_2\left(x\right)$$

Substitute $(y_0,y_1,y_2)=(1,3,5)$:

$$L\left(x\right)=1\cdot \frac{(x-2)(x-3)}{12}+3\cdot (-\frac{(x+1)(x-3)}{3})+5\cdot \frac{(x+1)(x-2)}{4}.$$

This polynomial will exactly fit the three given points.

Advantages

I. Exact Fit:

The Lagrange interpolation polynomial passes through all given data points exactly. There is no approximation error at these nodes.

II. No Linear System Needed:

Unlike other polynomial interpolation techniques that require solving a system of equations, Lagrange interpolation provides a direct formula.

III. Simplicity of Form:

The formula for the interpolating polynomial is explicit and easy to implement.

IV. Flexibility:

Works for any set of points with distinct $x_i$.

Limitations

I. Runge’s Phenomenon:

For a large number of interpolation points, Lagrange interpolation may cause oscillations between the points, especially if the points are unevenly spaced.

II. Recalculation for Added Points:

If a new point is added, the entire polynomial must be recomputed from scratch, unlike some other forms (e.g., Newton’s divided differences) that allow incremental updates more easily.

III. Computational Cost:

Evaluating Lagrange polynomials directly can be computationally intensive for large $n$ due to the product terms, though this can be mitigated with more efficient evaluation strategies.