Approximation

Overview

Approximation theory addresses a fundamental problem in numerical analysis and applied mathematics: how to represent a complex or unknown function using simpler, more tractable mathematical forms. While interpolation constructs functions that pass exactly through a given set of data points, approximation encompasses a broader class of techniques that includes polynomial approximation, rational function approximation, and least-squares fitting. The goal is to find a manageable mathematical expression that captures the essential behavior of the target function, balancing accuracy with computational efficiency.

In scientific computing, approximation methods are essential for evaluating special functions, solving differential equations, accelerating numerical algorithms, and compressing data representations. These techniques appear throughout numerical analysis, control systems engineering, signal processing, and computational physics. By replacing expensive function evaluations with simpler polynomial or rational expressions, approximation methods enable faster simulations and analytical insights into system behavior.

Polynomial Interpolation

Polynomial interpolation constructs a polynomial that passes exactly through a specified set of data points. The Lagrange interpolating polynomial is the canonical approach: given k+1 distinct points (x_0, y_0), \ldots, (x_k, y_k), there exists a unique polynomial L(x) of degree at most k such that L(x_i) = y_i for all i.

The Lagrange form expresses the polynomial as a sum of basis polynomials:

L(x) = \sum_{j=0}^{k} y_j \ell_j(x), \quad \text{where } \ell_j(x) = \prod_{\substack{m=0 \\ m \neq j}}^{k} \frac{x - x_m}{x_j - x_m}

Each Lagrange basis polynomial \ell_j(x) equals 1 at node x_j and 0 at all other nodes, ensuring the polynomial passes through each data point exactly.

While conceptually elegant, the direct Lagrange form is numerically unstable for more than about 20 points. Modern implementations use Newton’s divided differences or the barycentric form for improved numerical stability. Additionally, polynomial interpolation with equally spaced nodes can suffer from Runge’s phenomenon, where large oscillations develop near the boundaries of the interval. Using Chebyshev nodes or spline-based methods often provides better results.

The LAGRANGE_INTERP function computes the Lagrange polynomial through a set of points and returns its coefficients.

Rational Approximation

Rational approximation represents functions as ratios of polynomials:

R(x) = \frac{P(x)}{Q(x)} = \frac{a_0 + a_1 x + \cdots + a_m x^m}{1 + b_1 x + \cdots + b_n x^n}

Rational functions offer several advantages over pure polynomials. They can represent functions with poles (vertical asymptotes), approximate functions over infinite intervals, and often converge faster than polynomial series. This makes them especially valuable for approximating transcendental functions like e^x, \log(x), and \tan(x).

Padé approximants, introduced by French mathematician Henri Padé in 1890, are the most important class of rational approximations. A Padé approximant [m/n] is constructed so that its Taylor series expansion matches the Taylor series of the target function up to order m + n. This “diagonal” matching provides remarkably accurate approximations with relatively few terms.

Padé approximants are widely used in: - Numerical analysis: Approximating special functions (Bessel functions, error functions) - Control theory: Simplifying transfer functions for system analysis - Computational physics: Resumming divergent perturbation series - Computer arithmetic: Fast evaluation of elementary functions in math libraries

The PADE function computes the Padé approximant to a polynomial, expressing it as a ratio of two polynomials with specified degrees.

Choosing Between Methods

The choice between polynomial and rational approximation depends on the target function’s properties: - Smooth, well-behaved functions: Polynomial or spline interpolation - Functions with poles or branch cuts: Rational approximation (Padé) - Periodic functions: Fourier series or trigonometric polynomials - Large datasets or piecewise behavior: Splines (see Splines and Univariate categories)

Native Excel capabilities

Excel provides limited native support for approximation theory: - LINEST: Fits a polynomial to data using least-squares regression. Users can create polynomial terms (x, x^2, x^3, etc.) in separate columns and apply linear regression. This is not exact interpolation but rather a least-squares approximation. - TREND and GROWTH: Linear and exponential trend fitting, useful for forecasting but not general approximation. - Chart Trendlines: Excel’s charting features can display polynomial, exponential, logarithmic, and power trendlines with equations. However, these are visualization tools with limited programmability.

Excel has no native support for: - Lagrange polynomial computation or evaluation - Padé approximants or rational function fitting - High-degree polynomial interpolation with numerical stability - Barycentric forms or Chebyshev interpolation

Python functions provide access to the full suite of approximation methods from SciPy’s interpolate module, with robust numerical implementations and theoretical guarantees.

Third-party Excel add-ins

• NumXL: A comprehensive statistical and econometric add-in that includes polynomial interpolation and regression capabilities. It offers tools for time series analysis with various smoothing and approximation methods.
• XLSTAT: A statistical software package that provides polynomial regression, smoothing techniques, and curve-fitting tools. While not focused on approximation theory per se, it offers robust polynomial and nonlinear regression functionality.
• Polynomial Curve Fitting Add-in: Various third-party developers offer specialized curve-fitting add-ins, though these are typically limited to least-squares polynomial fitting rather than exact interpolation or rational approximation.

Tools

Tool	Description
LAGRANGE_INTERP	Compute the Lagrange interpolating polynomial through a set of points.
PADE	Compute Pade rational approximation to a polynomial.