Interpolation and Approximation Theory

In a world driven by data, we often know a function only at a finite set of points—from sensor readings and financial data to digital images and scientific measurements. The fundamental challenge is reconstructing a reliable, continuous model from these discrete samples to predict, analyze, and visualize. Interpolation and Approximation Theory provides the rigorous mathematical toolkit for this exact purpose, governing how we build functions that pass through or closely follow our data, with profound applications in curve fitting, computer graphics, and data analysis. Mastering this field means understanding the trade-offs between exactness, stability, and computational cost.

Polynomial Interpolation: Lagrange and Newton Forms

The most intuitive approach is polynomial interpolation, which constructs a polynomial of minimal degree that passes exactly through a given set of $n+1$ distinct data points. Two classic, mathematically equivalent formulations are the Lagrange and Newton forms. The Lagrange interpolating polynomial is built directly from a set of cardinal basis polynomials. For data points $(x_0,y_0),...,(x_n,y_n)$, the Lagrange form is:

$$P_n(x)=\sum _{k=0}^n{y}_k{L}_k(x)\text{where}{L}_k(x)=\prod _{\begin{array}{c}j=0\\ j\ne k\end{array}}^n\frac{x-x_j}{x_k-x_j}.$$

Each basis polynomial $L_k(x)$ is designed to be 1 at $x_k$ and 0 at all other $x_j$, making the construction elegant and theoretically insightful. In contrast, the Newton interpolating polynomial uses a recursive, nested structure based on divided differences:

$$P_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+...+f[x_0,x_1,...,x_n](x-x_0)...(x-x_{n-1}).$$

The notation $f[x_i,...,x_j]$ represents a divided difference, a recursive calculation of slope-like quantities. The Newton form's primary advantage is its computational efficiency when adding new data points; you can simply append a new term without recalculating the entire polynomial, unlike the Lagrange form.

The Runge Phenomenon and the Need for Splines

A critical pitfall when using high-degree polynomial interpolation on equally spaced points is the Runge phenomenon. This is the tendency for the interpolating polynomial to oscillate wildly, with extreme error, near the endpoints of the interval. It demonstrates that increasing the polynomial degree (and thus the number of data points) does not guarantee a better approximation and can, in fact, lead to catastrophic divergence from the underlying function you hope to represent.

This instability leads to the powerful concept of spline interpolation. Instead of using a single high-degree polynomial across the entire data set, you piece together multiple low-degree polynomials (typically cubic) on subintervals. The most common, cubic splines, enforce that the connecting piecewise polynomials and their first and second derivatives are continuous at the interior data points (called knots). This results in a curve that is extremely smooth and visually pleasing, effectively eliminating the wild oscillations of high-degree polynomials. Splines are the workhorse for computer-aided design (CAD), computer graphics animation paths, and geographic mapping, where smoothness is paramount.

Least Squares Approximation and Orthogonal Polynomials

Often, data is contaminated with noise or measurement error, and forcing a curve to pass exactly through every point is neither desirable nor representative of an underlying trend. Least squares approximation addresses this by finding the function from a chosen family (e.g., polynomials of a fixed, lower degree) that minimizes the sum of the squares of the residuals (the differences between the observed values and the function's predictions). For a set of $m$ data points $(x_i,y_i)$ and an approximating polynomial of degree $n<m-1$, we solve for coefficients $a_0,...,a_n$ to minimize:

$$S=\sum _{i=0}^m(y_i-(a_0+a_1{x}_i+...+a_n{x}_i^n){)}^2.$$

Solving this minimization problem leads to the famous normal equations. However, solving these equations directly can be numerically ill-conditioned. A superior approach employs orthogonal polynomials, such as Legendre or Chebyshev polynomials. These are families of polynomials orthogonal with respect to a specific inner product (e.g., integration over $[-1,1]$). Using them as a basis for approximation decouples the normal equations, making the coefficient calculation stable, efficient, and independent—you can add a higher-degree term without recomputing all lower-degree coefficients.

Minimax Approximation and the Chebyshev Equioscillation Theorem

While least squares minimizes the average squared error, some applications require control over the maximum error. Minimax approximation (or uniform approximation) seeks the function from a given class that minimizes the maximum absolute deviation from the true function over an interval. For polynomial approximation, the remarkable Chebyshev Equioscillation Theorem provides the optimality condition: the best minimax polynomial approximation of a given degree is characterized by the error function oscillating with equal amplitude and alternating sign at least $n+2$ times over the interval.

Chebyshev polynomials play a starring role here as well. They can be used to find near-minimax approximations efficiently and are the optimal nodes for polynomial interpolation to minimize the Runge phenomenon. This deep connection between interpolation nodes, orthogonal polynomials, and error minimization is a cornerstone of the theory. Minimax principles are crucial in digital signal processing filter design and scientific computing where error bounds must be strictly guaranteed.

Common Pitfalls

1. Ignoring the Runge Phenomenon with High-Degree Polynomials: Using a single polynomial to interpolate many equally-spaced data points is a classic error. The resulting oscillations render the model useless for prediction between points. Correction: Use piecewise polynomials (splines) for large data sets or employ Chebyshev nodes for polynomial interpolation if a single polynomial is necessary.

1. Misapplying Interpolation to Noisy Data: Interpolation forces a model to hit every data point exactly. If your data contains measurement error, this "perfection" is misleading and overfits the noise. Correction: Use approximation methods like least squares to capture the underlying trend, accepting small residuals to gain a more robust model.

1. Assuming All Splines are the Same: Not all piecewise interpolants are proper splines. A common mistake is to create a piecewise function that is continuous in value but has sharp corners (discontinuous first derivatives). Correction: Ensure you specify the required continuity conditions. For most smooth applications, you need cubic splines with $C^2$ continuity (continuous value, slope, and curvature).

1. Overlooking Numerical Stability in Least Squares: Solving the normal equations via the classic $A^{T}Ax=A^{T}b$ approach is algebraically correct but can fail computationally if the matrix $A^{T}A$ is ill-conditioned. Correction: Use numerically stable algorithms based on orthogonalization techniques like QR decomposition, or employ an orthogonal polynomial basis from the start.

Summary

• Polynomial Interpolation (Lagrange, Newton) provides an exact fit through discrete points but is susceptible to the Runge phenomenon for high degrees on equally spaced nodes, leading to unstable oscillations.
• Spline interpolation solves this instability by using low-degree, piecewise polynomials (e.g., cubic) joined smoothly at knots, making it the preferred method for smooth curve fitting in graphics and design.
• Least squares approximation is the fundamental method for fitting models to noisy data by minimizing the sum of squared residuals, with orthogonal polynomials providing a stable and efficient basis for computation.
• Minimax approximation aims to minimize the maximum absolute error, with the Chebyshev Equioscillation Theorem characterizing the optimal solution; Chebyshev polynomials are deeply linked to optimal interpolation and near-minimax fits.
• The choice between interpolation (exact fit) and approximation (trend fit), and between different methods within each category, depends critically on the data's nature, the presence of noise, and the required guarantees on error.