Polynomial interpolation is the construction of a polynomial that takes specified values at a finite set of distinct input points, called nodes. Given distinct nodes and their associated values, there is exactly one polynomial of degree at most satisfying all the prescribed conditions. It is a central technique in interpolation, numerical analysis, and approximation theory, with applications in numerical integration, differentiation, differential equations, and algebraic computation.
Exact agreement at the nodes does not necessarily imply good approximation between them. The placement of the nodes, the behavior of the underlying function, and the numerical method used to represent and evaluate the polynomial all influence the quality of the result.
Definition and uniqueness
Let be distinct real numbers, and let be prescribed values. The interpolation problem is to find
such that
The degree bound is essential: without it, infinitely many polynomials satisfy the conditions. Once one solution is known, every polynomial of the form
where is any polynomial, has the same values at the nodes.
Uniqueness follows from the root bound for polynomials. If and both solve the problem, then has degree at most but has distinct roots. It must therefore be the zero polynomial.
Existence follows, for example, from the explicit Lagrange formula. More abstractly, evaluation at the nodes is an invertible linear map from the -dimensional vector space of polynomials of degree at most to the space of data vectors.
The same existence and uniqueness statement holds over any field, including the complex numbers and finite fields, provided the nodes are distinct elements of that field.
Principal representations
Different interpolation formulas describe the same polynomial. Their differences concern how it is constructed, updated, stored, and evaluated.
Monomial form and the Vandermonde system
Substituting the interpolation conditions into the monomial expansion gives a system of linear equations:
The coefficient matrix is a Vandermonde matrix. Its determinant is
which is nonzero precisely when the nodes are distinct.
This representation is conceptually direct, but the monomial coefficients can be highly sensitive to small perturbations. Solving a Vandermonde system and then evaluating the resulting monomial expansion is therefore not generally the preferred way to perform interpolation.
Lagrange form
Define the cardinal polynomials
They satisfy
The interpolating polynomial is
This formula proves existence directly and separates the role of the nodes from the role of the data. The cardinal polynomials depend only on the nodes; changing the values changes only their coefficients.
It also shows that interpolation is linear in the data and reproduces every polynomial of degree at most exactly.
Newton form and divided differences
The Newton representation is
Its coefficients are divided differences. For data sampled from a function , they are defined recursively by
and
Then
A standard divided-difference table requires arithmetic operations, while nested evaluation of the resulting polynomial requires operations per point. Newton form is particularly convenient when nodes are added: the existing expansion is retained and one further term is appended.
Barycentric form
A widely used evaluation formula is barycentric interpolation. Define the weights
For distinct from every node,
Although this is written as a quotient, in exact arithmetic it equals the polynomial interpolant. At a node, the value is assigned directly as .
Once the weights are available, evaluation costs operations. Multiplying all weights by the same nonzero constant leaves the formula unchanged, allowing convenient rescaling. For several important node families, explicit weights avoid the direct product computation.
Barycentric evaluation often has favorable numerical stability, especially for well-chosen nodes within the interpolation interval. It does not, however, eliminate sensitivity inherent in the interpolation problem itself.
Example
Consider the three data points
Their divided differences are
The Newton interpolant is therefore
It takes the prescribed values at all three nodes. At the intermediate point , it gives
This is the value of the interpolating polynomial, not necessarily the value of an unknown function that generated the observations.
Approximation error
Suppose the data are exact samples , where has a continuous st derivative on an interval containing the nodes and the evaluation point . For not equal to a node, there exists a point in the smallest interval containing these points such that
At a node, the error is zero. Consequently, on an interval containing all nodes,
where
The formula separates two influences: the smoothness and derivative growth of the function, and the geometry of the nodes through the nodal product.
It does not imply that increasing the degree always improves the approximation. The derivative bound itself depends on , and the nodal product can behave poorly. The formula also concerns exact function values, not errors introduced by measurement noise or finite-precision computation.
Node selection and convergence
Runge phenomenon
High-degree interpolation at equally spaced nodes can exhibit large oscillations near the ends of an interval. The classical Runge phenomenon occurs for
As the number of equally spaced nodes increases, the interpolants fail to converge uniformly to this smooth function.
This behavior does not contradict polynomial approximation theorems: the existence of good polynomial approximations does not mean that interpolating at arbitrary prescribed nodes produces them.
Chebyshev nodes
A standard alternative on is the set of Chebyshev nodes
These nodes cluster near the endpoints. They are the roots of the Chebyshev polynomial , a member of a classical family of orthogonal polynomials.
Among all monic polynomials of degree , the nodal polynomial associated with these roots minimizes the maximum absolute value on :
A related choice, the Chebyshev–Lobatto nodes, includes both endpoints:
Both families substantially improve high-degree interpolation behavior relative to equally spaced nodes. If a function extends analytically to a suitable complex neighborhood of the interval, Chebyshev interpolation converges geometrically. For functions of limited smoothness, convergence is generally slower.
No fixed sequence of node sets guarantees uniform convergence of the polynomial interpolants for every continuous function on a nondegenerate compact interval.
Conditioning, stability, and data errors
The sensitivity of interpolation to perturbations in the sampled values is described by the Lebesgue function
and the Lebesgue constant
If the data are perturbed by amounts satisfying , then the change in the exact interpolant satisfies
and hence
Thus the Lebesgue constant acts as an absolute condition number for the map from data values to the interpolating function in the maximum norm.
It also relates interpolation to best approximation. If
then
For Chebyshev nodes, grows only logarithmically with ; for equally spaced nodes, it grows exponentially.
Conditioning must be distinguished from algorithmic stability. A stable implementation can limit additional error from floating-point arithmetic, but cannot remove amplification inherent in the selected nodes. Conversely, monomial coefficient recovery may be badly conditioned even when values of the interpolant can be evaluated accurately in a different representation.
Evaluation outside the span of the nodes is extrapolation. There, the cardinal polynomials and the associated sensitivity can grow rapidly.
Related methods and extensions
Piecewise polynomial interpolation. Instead of fitting one polynomial over an entire interval, a method can fit low-degree polynomials on subintervals. Spline interpolation imposes continuity conditions where the pieces meet. It often avoids the endpoint oscillations of high-degree global interpolation, although the locality of data influence depends on the spline construction.
Hermite interpolation. Hermite interpolation prescribes derivative values as well as function values. In the standard univariate construction, a total of conditions consisting of consecutive derivatives at distinct nodes determines a unique polynomial of degree at most . Interpolation of a function and its first derivatives at a single point gives its degree- Taylor polynomial.
Least-squares approximation. Interpolation enforces exact agreement at the data points. Least-squares approximation instead minimizes an aggregate residual and need not pass through every observation. With noisy data, exact interpolation may reproduce unwanted fluctuations; smoothing and regularization modify the fitting problem rather than solving the same interpolation conditions.
Multivariate interpolation. In several variables, the number of points alone does not guarantee uniqueness: their geometric arrangement matters. For example, three points determine a unique affine polynomial in two variables only when they are not collinear. Tensor-product grids and interpolation on simplices provide structured constructions.
Applications
Polynomial interpolation supplies a common foundation for several computational methods:
- Numerical integration: integrating the Lagrange representation gives quadrature formulas. Equally spaced nodes lead to Newton–Cotes formulas; specially selected nodes yield other families with different accuracy and stability properties.
- Numerical differentiation: differentiating an interpolating polynomial produces derivative approximations from sampled values and provides a systematic derivation of finite-difference weights.
- Differential equations: collocation and spectral methods represent approximate solutions using polynomials and impose governing equations at selected points.
- Finite elements: polynomial shape functions in the finite element method interpolate local degrees of freedom on individual mesh elements.
- Algebraic reconstruction: interpolation over finite fields reconstructs polynomials from exact samples and underlies constructions used in error-correcting codes and secret sharing.
In each setting, polynomial degree, node placement, data accuracy, and representation determine whether interpolation serves as a reliable computational building block.