Interpolation: Lagrange and Newton Polynomials

In engineering, you often encounter discrete data points from sensors, simulations, or experiments, and need to estimate values between them. Interpolation is the process of constructing a function that passes exactly through a set of known points, providing a continuous model for approximation. Mastering polynomial interpolation methods like Lagrange and Newton forms is essential for tasks ranging from digital signal processing to computer-aided design, as they offer powerful tools for curve fitting and function approximation.

Foundations of Polynomial Interpolation

When you have a set of $n+1$ data points $(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$ with distinct $x$-values, polynomial interpolation seeks a single polynomial that passes through all points. A fundamental result guarantees that there exists a unique polynomial $P(x)$ of degree at most $n$ that satisfies $P(x_i)=y_i$ for all $i$. This interpolating polynomial serves as an approximation to the underlying function that generated the data, assuming it is smooth. For engineers, this means you can reconstruct continuous signals from sampled data or create simplified models for complex phenomena. The challenge lies not in existence, but in efficiently computing and representing this polynomial, which leads to the two primary forms you will implement.

The Lagrange Interpolation Method

Lagrange interpolation constructs the unique polynomial by building it as a linear combination of basis polynomials. For each data point $i$, a Lagrange basis polynomial $L_i(x)$ is defined. This polynomial has the property that it equals 1 at $x_i$ and 0 at all other given $x_j$ points. The formula for each basis polynomial is:

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

The full interpolating polynomial $P(x)$ is then the weighted sum of these basis polynomials, with the weights being the corresponding $y$-values:

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

Consider a concrete example where you need a polynomial through points $(1,2)$, $(2,3)$, and $(4,5)$. First, construct the three basis polynomials:

• $L_0(x)=\frac{(x-2)(x-4)}{(1-2)(1-4)}=\frac{(x-2)(x-4)}{3}$
• $L_1(x)=\frac{(x-1)(x-4)}{(2-1)(2-4)}=\frac{(x-1)(x-4)}{-2}$
• $L_2(x)=\frac{(x-1)(x-2)}{(4-1)(4-2)}=\frac{(x-1)(x-2)}{6}$

Then, $P(x)=2\cdot L_0(x)+3\cdot L_1(x)+5\cdot L_2(x)$. After simplification, you obtain the quadratic polynomial that passes through all three points. The Lagrange form is conceptually clear and directly reveals the interpolation property, but it has a computational drawback: adding a new data point requires recalculating all basis polynomials from scratch.

The Newton Interpolation Method

Newton's divided difference form addresses the inefficiency of Lagrange when points are added dynamically. This method expresses the interpolating polynomial using a nested multiplication scheme based on divided differences, which are computed recursively from the data. The Newton polynomial is written as:

$$P(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\cdots +f[x_0,\dots ,x_n]\prod _{i=0}^{n-1}(x-x_i)$$

Here, $f[x_i]$ is simply $y_i$, and higher-order divided differences are defined. For instance, $f[x_i,x_j]=\frac{f[x_j]-f[x_i]}{x_j-x_i}$ and $f[x_i,x_j,x_k]=\frac{f[x_j,x_k]-f[x_i,x_j]}{x_k-x_i}$. Using the same points $(1,2)$, $(2,3)$, $(4,5)$, compute the divided difference table:

• Zeroth order: $f[1]=2$, $f[2]=3$, $f[4]=5$
• First order: $f[1,2]=\frac{3-2}{2-1}=1$, $f[2,4]=\frac{5-3}{4-2}=1$
• Second order: $f[1,2,4]=\frac{f[2,4]-f[1,2]}{4-1}=\frac{1-1}{3}=0$

Thus, the Newton polynomial is $P(x)=2+1(x-1)+0(x-1)(x-2)=x+1$, which matches the result from Lagrange. The key advantage is that if you add a new point $(5,7)$, you only need to compute one new divided difference and append a term to the polynomial, making it more efficient for sequential data.

Analysis and Implementation Considerations

When you implement both methods, you'll analyze their numerical behavior and limitations. Computationally, Lagrange interpolation is straightforward to code but can suffer from numerical instability for large $n$ due to many multiplications and subtractions. Newton's method, with its divided differences, is generally more stable and efficient, especially when using Horner's method to evaluate the nested form. However, both methods produce the same mathematical polynomial; the difference lies in representation and computation. This leads to a critical issue: as the degree $n$ increases, polynomial interpolation can exhibit Runge's phenomenon, where the polynomial oscillates wildly between points, particularly near the endpoints of the interval when points are equally spaced. This oscillation makes high-degree polynomial interpolation unsuitable for many engineering applications, such as approximating smooth functions from noisy data.

When to Choose Splines Over Polynomials

Runge's phenomenon underscores that polynomial interpolation is not always the best tool. For a large number of data points or when smoothness is crucial, spline interpolation becomes preferable. A spline constructs a piecewise polynomial, typically of low degree (like cubic), that passes through all points and ensures continuity of derivatives at the junctions, called knots. This avoids the large oscillations of high-degree global polynomials. You should choose spline interpolation when:

• You have many data points (e.g., more than 10).
• The underlying function is expected to be smooth but not necessarily polynomial.
• You need to avoid excessive curvature between points, as in computer graphics or geographic mapping.
• The data has regions with different behaviors, as splines can adapt locally.

Polynomial interpolation remains ideal for few points, theoretical analysis, or when an analytic form is needed, but in practical engineering, splines often provide more reliable and stable approximations.

Common Pitfalls

1. Using High-Degree Polynomials Blindly: Attempting to interpolate many points with a single high-degree polynomial often leads to Runge's phenomenon, causing poor approximation between points. Correction: Use spline interpolation or approximate with lower-degree polynomials via regression when data is noisy.

1. Ignoring Numerical Stability: Implementing Lagrange interpolation directly for many points can result in significant rounding errors due to repeated subtractions. Correction: Use Newton's form with careful divided difference computations or employ barycentric Lagrange formulations for better stability.

1. Confusing Interpolation with Extrapolation: Polynomials that fit data well inside the interval may diverge rapidly outside it. Correction: Never use interpolating polynomials for extrapolation without rigorous error analysis; consider alternative models for prediction beyond the data range.

1. Overlooking Computational Efficiency: Recalculating the entire Lagrange polynomial for each new point is inefficient. Correction: Use Newton's method if data points are added sequentially, as it allows incremental updates.

Summary

• Lagrange interpolation builds the unique polynomial through $n+1$ points using basis polynomials that are 1 at their node and 0 at others, offering conceptual clarity but computational inefficiency when adding points.
• Newton interpolation uses divided differences to express the same polynomial in a nested form, enabling efficient point addition and better numerical stability through recursive computation.
• Runge's phenomenon demonstrates that high-degree polynomial interpolation on equally spaced points can lead to severe oscillations, making it unreliable for many points.
• Spline interpolation is preferable when dealing with numerous data points, as it uses piecewise low-degree polynomials to ensure smoothness without global oscillations.
• In practice, choose polynomial interpolation for small, well-behaved datasets, and splines for larger sets or when local smoothness is critical.