What is Lagrange Interpolation?

Lagrange interpolation is a powerful and widely used method in numerical analysis for finding a unique polynomial that passes through a given set of distinct data points. When you have a collection of (x, y) coordinates, this method allows you to construct a polynomial function that perfectly fits all those points. This is particularly useful when you need to estimate values between known data points or approximate a complex function with a simpler polynomial.

Key Formula: The Lagrange Interpolating Polynomial

The Lagrange interpolating polynomial, denoted as P(x), is constructed as a sum of terms, where each term is a product of a y-value and a special polynomial called a Lagrange basis polynomial.

P(x) = Σ yᵢ * Lᵢ(x)

where Lᵢ(x) = Π (x - xⱼ)/(xᵢ - xⱼ) for j ≠ i

P(x): This is the resulting Lagrange interpolating polynomial. It's the function that will pass through all your given data points.
Σ (Sigma): This symbol means "summation." You add up all the terms for each data point.
yᵢ: This represents the y-coordinate (output value) of the i-th data point (xᵢ, yᵢ).
Lᵢ(x): This is the i-th Lagrange basis polynomial. It's a special polynomial designed to be equal to 1 at x = xᵢ and 0 at all other x-coordinates (xⱼ where j ≠ i) of your given data points.
Π (Pi): This symbol means "product." You multiply together all the terms for each j that is not equal to i.
(x - xⱼ): This is a factor in the numerator. It ensures that the basis polynomial Lᵢ(x) becomes zero when x is equal to any other x-coordinate (xⱼ) in your dataset, except for xᵢ.
(xᵢ - xⱼ): This is a factor in the denominator. It normalizes the term so that Lᵢ(x) equals 1 when x is equal to xᵢ. This ensures that each yᵢ contributes only its value at its corresponding xᵢ.

By summing these specially constructed terms, the Lagrange polynomial P(x) is guaranteed to pass exactly through every given data point.

Properties and Characteristics

Lagrange interpolation possesses several important properties that make it a valuable tool in numerical analysis, but also some limitations that practitioners should be aware of.

Uniqueness of the Polynomial

Unique polynomial of degree ≤ n-1: For any set of 'n' distinct data points (x₁, y₁), (x₂, y₂), ..., (xₙ, yₙ), there exists one and only one polynomial of degree at most 'n-1' that passes through all these points. Lagrange interpolation constructs this unique polynomial. This means if you have 3 points, the resulting polynomial will be at most degree 2 (a parabola).
Exact interpolation at nodes: The Lagrange polynomial P(x) will exactly match the given y-values at each of the input x-coordinates (nodes). That is, P(xᵢ) = yᵢ for all i. This is a fundamental characteristic of interpolation methods.
Minimal degree polynomial: The Lagrange polynomial is the polynomial of the lowest possible degree that passes through all the given points. This is often desirable for simplicity and computational efficiency.

Error Bounds and Limitations

Runge phenomenon: A significant limitation of high-degree polynomial interpolation, including Lagrange interpolation, is the Runge phenomenon. This occurs when interpolating a function with equally spaced nodes over a large interval. The interpolating polynomial can oscillate wildly between the nodes, especially near the edges of the interval, leading to large errors even if the function itself is smooth.
Error term formula: The error in Lagrange interpolation can be expressed by a formula that depends on the (n+1)-th derivative of the original function and the product of (x - xᵢ) terms. This formula helps in understanding how the error behaves and where it might be largest.
Convergence properties: While Lagrange interpolation provides an exact fit at the given nodes, it does not guarantee good approximation or convergence for points *between* the nodes, especially as the number of points increases or if the points are not optimally chosen.

Key Applications

Numerical integration: Lagrange interpolation is a foundational concept for developing numerical integration techniques (quadrature rules), such as Newton-Cotes formulas (e.g., Trapezoidal Rule, Simpson's Rule). It allows us to approximate the area under a curve by integrating the interpolating polynomial instead of the original function.
Data fitting: When you have a set of experimental data points and you want to find a continuous function that best represents the trend in that data, Lagrange interpolation can be used to fit a polynomial curve through those points. This is common in engineering, physics, and economics.
Function approximation: If a complex function is difficult to evaluate directly, or if you only have its values at certain points, Lagrange interpolation can be used to create a simpler polynomial approximation that can be easily evaluated at any point within the range of the given data.
Solving differential equations: In some numerical methods for solving differential equations, the solution is approximated by a polynomial, and Lagrange interpolation can be used to construct this polynomial based on known values.

Advanced Topics and Extensions

While the basic Lagrange interpolation is powerful, there are more advanced considerations and extensions that address its limitations or broaden its applicability.

Numerical Stability and Efficiency

Condition number: The condition number of the interpolation problem relates to how sensitive the interpolating polynomial is to small changes in the input data points. A high condition number indicates that small errors in the input can lead to large errors in the output polynomial, signaling numerical instability.
Barycentric form: The standard Lagrange formula can be computationally expensive for many points. The barycentric form of Lagrange interpolation is a more numerically stable and efficient way to evaluate the polynomial, especially when adding or removing data points.
Node distribution: The choice of interpolation nodes significantly impacts the accuracy and stability of the interpolation. Non-equally spaced nodes, such as Chebyshev nodes, are often preferred over equally spaced nodes to mitigate the Runge phenomenon and improve the overall approximation quality.

Related Interpolation Methods

Hermite interpolation: This is an extension of Lagrange interpolation that not only matches the function values at the nodes but also matches the derivative values at those nodes. This results in a smoother interpolating polynomial that better captures the local behavior of the original function.
Multivariate interpolation: While Lagrange interpolation typically deals with functions of a single variable, multivariate interpolation extends the concept to functions of multiple variables (e.g., f(x, y)). This is crucial for interpolating data in higher dimensions, such as in image processing or geographic information systems.
Rational interpolation: Instead of using polynomials, rational interpolation uses ratios of polynomials (rational functions) to interpolate data. This can sometimes provide better approximations for functions with singularities or asymptotic behavior, where polynomials might perform poorly.
Spline interpolation: Unlike a single high-degree polynomial, spline interpolation uses a series of lower-degree polynomials (splines) connected smoothly at the nodes. This approach avoids the Runge phenomenon and provides a more flexible and locally controlled approximation, widely used in computer graphics and CAD.

Lagrange Interpolation Calculator

Understanding Lagrange Interpolation