Abstract
We study in this paper the function approximation error of linear interpolation and extrapolation. Several upper bounds are presented along with the conditions under which they are sharp. All results are under the assumptions that the function has Lipschitz continuous gradient and is interpolated on an affinely independent sample set. Errors for quadratic functions and errors of bivariate linear extrapolation are analyzed in depth.
Introduction
Linear interpolation is a fundamental tool in numerical analysis, essential for methods ranging from finite element analysis to derivative-free optimization (DFO). While error bounds for interpolation—predicting values within the convex hull of sample points—are well-established, the accuracy of extrapolation (predicting values outside this hull) has remained a significant challenge due to the complex influence of sample point geometry. This paper addresses this gap by providing new, "sharp" (mathematically tight) upper bounds for linear interpolation and extrapolation errors, specifically for functions with Lipschitz continuous gradients.
Problem Formulation
In DFO, algorithms frequently predict function values at points distant from the current sample set. Existing error bounds often fail to account for the specific geometry of the sample points, such as "skinny" or "obtuse" configurations, leading to overly conservative estimates. The authors aim to determine the absolute maximum possible error for any given sample set and target point, assuming only that the function's gradient is Lipschitz continuous.
Methodology
The research approaches the error bound problem through a dual optimization lens:
- Minimizing the Upper Bound: The authors generalize the standard Taylor expansion by expanding the function around an optimal center $u$, then optimizing $u$ to minimize the resulting error bound.
- Maximizing the Error: They identify the "worst-case" function—typically a quadratic function—that maximizes the error for a given point set to prove the bound's sharpness.
Key mathematical frameworks employed include barycentric coordinates to define target point positions, eigendecomposition of a geometry matrix $G$ to capture sample set orientation, and piecewise quadratic constructions.
Key Insights
- The Optimal Center ($w$): The tightest error bound is achieved by calculating a weighted center $w$ based on the absolute values of the target point's barycentric coordinates.
- Geometric Sensitivity: The difficulty of finding sharp bounds increases significantly with "obtuse" geometries (where angles between sample points exceed 90 degrees). While non-obtuse cases often follow a single formula, obtuse geometries necessitate more complex, asymmetric bounds.
- Quadratic Worst-Cases: In many scenarios, the maximum error is produced by a quadratic function whose Hessian aligns with the principal directions of the sample set's geometry.
Key Results
The authors introduced a generalized upper bound: $$|m(y_0) - f(y_0)| \le \frac{L}{2} \sum_{i=0}^{n+1} |\ell_i| \|y_i - w\|^2$$ where $w$ is an optimized center point. This bound is proven sharp for specific "cone" regions during extrapolation. For the bivariate case ($n=2$), the paper provides a complete set of formulas for sharp error bounds that cover both interpolation and extrapolation regions, resolving issues in previously loose obtuse regions.
Limitations and Future Work
While the 2D case is fully resolved, extending these results to higher dimensions ($n \ge 3$) is complex due to the exponential growth in the types of "obtuse" simplices. Additionally, calculating the sharpest bound requires eigendecomposition, which may introduce computational overhead in high-dimensional optimization loops. Future research remains open for finding sharp bounds for gradient error ($\|\nabla m - \nabla f\|$), a non-convex and significantly harder problem.
Summary updated