Interpolation and Approximation

Interpolation and Approximation

Interpolation constructs a function passing through given data points. Approximation fits a simpler function near—but not necessarily through—the data. Both are essential when data is known only at discrete points but values elsewhere are needed.

Polynomial Interpolation

Given n + 1 distinct points (x₀, y₀), ..., (x_n, y_n), there is a unique polynomial P_n(x) of degree ≤ n with P_n(x_i) = y_i. Several equivalent formulas exist; choice depends on the application.

Lagrange Interpolation

The Lagrange form expresses P_n(x) = Σ y_i L_i(x), where L_i(x) are the Lagrange basis polynomials. Lagrange interpolation is concise and ideal for symbolic work but inefficient for evaluating at many points and unstable when adding new data.

Newton's Divided-Difference Form

Newton's divided-difference form writes P_n(x) = f[x₀] + f[x₀, x₁](x − x₀) + ... The divided-difference table can be updated incrementally as new points are added, making the method more efficient for dynamic data. Forward- and backward-difference forms are used for equispaced data.

Runge's Phenomenon

High-degree polynomial interpolation on equally spaced nodes can produce violent oscillations near the interval endpoints—Runge's phenomenon. Remedies include using Chebyshev nodes clustered near the endpoints, or piecewise interpolation with splines.

Spline Interpolation

Cubic splines are piecewise cubic polynomials with continuous first and second derivatives at data points. They produce smooth curves without Runge oscillations. Boundary conditions (natural, clamped, not-a-knot) determine behaviour at the endpoints. Splines are ubiquitous in computer graphics, CAD, and engineering visualization.

Least-Squares Approximation

When data is noisy, we prefer a best-fitting function rather than one passing through every point. Least-squares fitting minimizes the sum of squared residuals. Linear least squares reduces to solving the normal equations A^TA x = A^Tb. For large or ill-conditioned problems, QR decomposition or singular-value decomposition (SVD) is preferred.

Orthogonal Polynomials and Chebyshev Approximation

For polynomial approximation of continuous functions, Chebyshev polynomials minimize the maximum error and produce numerically stable expansions. Legendre, Hermite, and Laguerre polynomials arise in specialized contexts such as integration and probability.

Bivariate and Multivariate Interpolation

Interpolation in multiple dimensions uses tensor products of 1D schemes or more flexible scattered-data methods like radial basis functions. Computer graphics uses bilinear and bicubic interpolation for image resampling and texture mapping.

Error Bounds

The error in polynomial interpolation depends on the spacing of nodes and the derivatives of the underlying function. For n + 1 points, |f(x) − P_n(x)| is bounded by |f⁽ⁿ⁺¹⁾(ξ)| / (n + 1)! times the product (x − x₀)(x − x₁)...(x − x_n). Well-chosen nodes minimize this bound.

Summary

Interpolation and approximation are foundational: almost every numerical method somewhere replaces a function by a polynomial or piecewise polynomial. Choosing the appropriate method—Lagrange for theory, splines for smooth visualization, least squares for noisy data—is an essential skill in numerical computing.