Interpolation: Lagrange's Method

Introduction to Interpolation

Interpolation is the process of estimating unknown values that fall within a range of known values. For example, if you're monitoring the growth of a plant by measuring its height every Sunday, you may want to estimate its height on a Wednesday, which is not a measurement day. Interpolation allows you to fill in these gaps using the known measurements.

In mathematical terms, if we have a set of known points represented as (x, y), interpolation helps us find a corresponding y for an x that lies between the known points. This is crucial in various fields, including data analysis, computer graphics, and scientific computing.

What is Lagrange Interpolation?

Lagrange interpolation is a method named after the mathematician Joseph-Louis Lagrange. It provides a systematic way to estimate unknown values by constructing a polynomial that passes through all known data points. This method is particularly useful when dealing with a small number of data points.

Lagrange Interpolation Formula

The Lagrange interpolation formula is given by:

In this formula:

• $P(x)$ is the polynomial we want to determine.
• $y_i$ represents the known y-values corresponding to each x-value.
• $L_i(x)$ are the Lagrange basis polynomials defined as:
  $$L_i(x) = \prod_{\substack{0 \leq j \leq n \\ j \neq i}} \frac{x - x_j}{x_i - x_j}$$

Each basis polynomial $L_i(x)$ contributes to the final polynomial $P(x)$ based on how close x is to each known point. The basis polynomial is constructed to be equal to 1 at the x-value corresponding to its known point and 0 at all other known points.

Estimating a Missing Value

Let’s say we have the following points representing the height of a plant over a few days:

Now, we want to estimate the height of the plant on Day 3 (x = 3). Here’s how we can do that using Lagrange interpolation:

1. First, we identify our known points:$(1, 3), (2, 5), (4, 7)$.
2. We will calculate the Lagrange basis polynomials:

   For $L_0(x)$:

   $$L_0(x) = \frac{(x-2)(x-4)}{(1-2)(1-4)} = \frac{(x-2)(x-4)}{(-1)(-3)} = \frac{(x-2)(x-4)}{3}$$

   For $L_1(x)$:

   $$L_1(x) = \frac{(x-1)(x-4)}{(2-1)(2-4)} = \frac{(x-1)(x-4)}{(1)(-2)} = -\frac{(x-1)(x-4)}{2}$$

   For $L_2(x)$:

   $$L_2(x) = \frac{(x-1)(x-2)}{(4-1)(4-2)} = \frac{(x-1)(x-2)}{(3)(2)} = \frac{(x-1)(x-2)}{6}$$
3. We can now write the polynomial using our known y-values:
   $$P(x) = 3 \cdot L_0(x) + 5 \cdot L_1(x) + 7 \cdot L_2(x)$$
4. Finally, we substitute $x = 3$ into $P(x)$:
   $$P(3) = 3 \cdot L_0(3) + 5 \cdot L_1(3) + 7 \cdot L_2(3)$$
5. Now we compute each term:
   1. Calculating $L_0(3)$:
      $$L_0(3) = \frac{(3-2)(3-4)}{3} = \frac{(1)(-1)}{3} = -\frac{1}{3}$$
   2. Calculating $L_1(3)$:
      $$L_1(3) = -\frac{(3-1)(3-4)}{2} = -\frac{(2)(-1)}{2} = 1$$
   3. Calculating $L_2(3)$:
      $$L_2(3) = \frac{(3-1)(3-2)}{6} = \frac{(2)(1)}{6} = \frac{1}{3}$$
6. Substituting these values back into the polynomial gives us:
   $$P(3) = 3 \cdot \left(-\frac{1}{3}\right) + 5 \cdot 1 + 7 \cdot \left(\frac{1}{3}\right)$$
7. Simplifying this results in:
   $$P(3) = -1 + 5 + \frac{7}{3} = 4 + \frac{7}{3} = \frac{12}{3} + \frac{7}{3} = \frac{19}{3} \approx 6.33$$
8. Therefore, the estimated height of the plant on Day 3 is approximately 6.33 cm. This example demonstrates how the Lagrange interpolation formula can be effectively used to estimate unknown values between known data points.

More Complex Example: Sales Data

Suppose we have the following quarterly sales data for a company:

We want to estimate the sales for Q1.5 (midway through Q2):

1. Identify the points: Q1 (0, 10), Q2 (1, 15), Q3 (2, 25), Q4 (3, 20).
2. Calculate the Lagrange basis polynomials:
   $$L_0(x) = \frac{(x-1)(x-2)(x-3)}{(0-1)(0-2)(0-3)} = -\frac{(x-1)(x-2)(x-3)}{6}$$
   $$L_1(x) = \frac{(x-0)(x-2)(x-3)}{(1-0)(1-2)(1-3)} = \frac{(x-0)(x-2)(x-3)}{2}$$
   $$L_2(x) = \frac{(x-0)(x-1)(x-3)}{(2-0)(2-1)(2-3)} = -\frac{(x-0)(x-1)(x-3)}{2}$$
   $$L_3(x) = \frac{(x-0)(x-1)(x-2)}{(3-0)(3-1)(3-2)} = \frac{(x-0)(x-1)(x-2)}{6}$$
3. Formulate the polynomial:
   $$P(x) = 10 \cdot L_0(x) + 15 \cdot L_1(x) + 25 \cdot L_2(x) + 20 \cdot L_3(x)$$
4. Evaluate for Q1.5 (x = 1.5) to estimate sales.

This method allows for estimating values even in situations where only a few data points are available, enhancing predictive modeling capabilities.

When to Use Lagrange Interpolation

Lagrange interpolation is particularly effective in scenarios such as:

• You have a limited number of data points.
• Your data points are evenly distributed across the range.
• You require an exact polynomial that passes through all your known points.

Applications include but are not limited to:

• Predicting stock prices based on historical data.
• Estimating environmental data such as temperature or rainfall.
• Creating smooth curves in computer graphics and animation.
• Interpolating values in numerical simulations and modeling.

Limitations of Lagrange Interpolation

Despite its strengths, Lagrange interpolation has several limitations:

• As the number of points increases, the polynomial degree increases, which can lead to large oscillations between points (known as Runge's phenomenon).
• The computational complexity grows with the number of data points, making it inefficient for large datasets.
• Outliers can heavily influence the result, leading to inaccurate estimates.

In such cases, alternative methods like spline interpolation or piecewise polynomial interpolation may be more suitable.

Conclusion

Lagrange interpolation serves as a powerful mathematical tool for estimating unknown values between known data points. While it is subject to certain limitations, its ability to construct precise polynomials makes it invaluable in various applications across different fields. Understanding Lagrange interpolation not only enhances our interpolation techniques but also lays the groundwork for exploring more advanced numerical methods in mathematics and computational sciences.