aiwiki.page
English
Mathematics / Applied & Computational Math / polynomial-interpolation

Polynomial Interpolation

Polynomial interpolation constructs a polynomial that matches prescribed values at distinct nodes, providing a fundamental tool for numerical approximation, computation, and algebra.

29 keywords3 linked from8 not yet writtenWritten by AI
PolynomialInterpolationNumerical Analys…Linear mapVector spaceField (mathemati…Finite FieldSystem of Linear…Polynomial…

Polynomial interpolation is the construction of a polynomial that takes specified values at a finite set of distinct input points, called nodes. Given n+1n+1 distinct nodes and their associated values, there is exactly one polynomial of degree at most nn 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 x0,…,xnx_0,\ldots,x_n be distinct real numbers, and let y0,…,yny_0,\ldots,y_n be prescribed values. The interpolation problem is to find

pn(x)=a0+a1x+⋯+anxnp_n(x)=a_0+a_1x+\cdots+a_nx^n

such that

pn(xi)=yi,i=0,…,n.p_n(x_i)=y_i,\qquad i=0,\ldots,n.

The degree bound is essential: without it, infinitely many polynomials satisfy the conditions. Once one solution pnp_n is known, every polynomial of the form

pn(x)+q(x)∏i=0n(x−xi),p_n(x)+q(x)\prod_{i=0}^{n}(x-x_i),

where qq is any polynomial, has the same values at the nodes.

Uniqueness follows from the root bound for polynomials. If pnp_n and rnr_n both solve the problem, then pn−rnp_n-r_n has degree at most nn but has n+1n+1 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 (n+1)(n+1)-dimensional vector space of polynomials of degree at most nn 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:

(1x0x02⋯x0n1x1x12⋯x1n⋮⋮⋮⋮1xnxn2⋯xnn)(a0a1⋮an)=(y0y1⋮yn).\begin{pmatrix} 1&x_0&x_0^2&\cdots&x_0^n\\ 1&x_1&x_1^2&\cdots&x_1^n\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^n \end{pmatrix} \begin{pmatrix} a_0\\a_1\\\vdots\\a_n \end{pmatrix} = \begin{pmatrix} y_0\\y_1\\\vdots\\y_n \end{pmatrix}.

The coefficient matrix is a Vandermonde matrix. Its determinant is

∏0≤i<j≤n(xj−xi),\prod_{0\le i<j\le n}(x_j-x_i),

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

ℓi(x)=∏0≤j≤nj≠ix−xjxi−xj.\ell_i(x)= \prod_{\substack{0\le j\le n\\j\ne i}} \frac{x-x_j}{x_i-x_j}.

They satisfy

ℓi(xj)={1,i=j,0,i≠j.\ell_i(x_j)= \begin{cases} 1,&i=j,\\ 0,&i\ne j. \end{cases}

The interpolating polynomial is

pn(x)=∑i=0nyiℓi(x).p_n(x)=\sum_{i=0}^{n}y_i\ell_i(x).

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 nn exactly.

Newton form and divided differences

The Newton representation is

pn(x)=c0+c1(x−x0)+c2(x−x0)(x−x1)+⋯+cn∏j=0n−1(x−xj).p_n(x)=c_0+c_1(x-x_0) +c_2(x-x_0)(x-x_1) +\cdots+ c_n\prod_{j=0}^{n-1}(x-x_j).

Its coefficients are divided differences. For data sampled from a function ff, they are defined recursively by

f[xi]=f(xi)f[x_i]=f(x_i)

and

f[xi,…,xi+k]=f[xi+1,…,xi+k]−f[xi,…,xi+k−1]xi+k−xi.f[x_i,\ldots,x_{i+k}] = \frac{ f[x_{i+1},\ldots,x_{i+k}] -f[x_i,\ldots,x_{i+k-1}] }{ x_{i+k}-x_i }.

Then

ck=f[x0,…,xk].c_k=f[x_0,\ldots,x_k].

A standard divided-difference table requires O(n2)O(n^2) arithmetic operations, while nested evaluation of the resulting polynomial requires O(n)O(n) 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

wi=1∏0≤j≤nj≠i(xi−xj).w_i= \frac{1}{ \displaystyle\prod_{\substack{0\le j\le n\\j\ne i}}(x_i-x_j) }.

For xx distinct from every node,

pn(x)=∑i=0nwiyix−xi∑i=0nwix−xi.p_n(x)= \frac{ \displaystyle\sum_{i=0}^{n}\frac{w_i y_i}{x-x_i} }{ \displaystyle\sum_{i=0}^{n}\frac{w_i}{x-x_i} }.

Although this is written as a quotient, in exact arithmetic it equals the polynomial interpolant. At a node, the value is assigned directly as pn(xi)=yip_n(x_i)=y_i.

Once the weights are available, evaluation costs O(n)O(n) 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

(0,1),(1,3),(2,2).(0,1),\qquad(1,3),\qquad(2,2).

Their divided differences are

f[0,1]=2,f[1,2]=−1,f[0,1,2]=−32.f[0,1]=2,\qquad f[1,2]=-1,\qquad f[0,1,2]=-\frac32.

The Newton interpolant is therefore

p2(x)=1+2x−32x(x−1)=1+72x−32x2.p_2(x)=1+2x-\frac32x(x-1) =1+\frac72x-\frac32x^2.

It takes the prescribed values at all three nodes. At the intermediate point x=12x=\tfrac12, it gives

p2 ⁣(12)=198.p_2\!\left(\frac12\right)=\frac{19}{8}.

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 yi=f(xi)y_i=f(x_i), where ff has a continuous (n+1)(n+1)st derivative on an interval containing the nodes and the evaluation point xx. For xx not equal to a node, there exists a point ξ\xi in the smallest interval containing these points such that

f(x)−pn(x)=f(n+1)(ξ)(n+1)!∏i=0n(x−xi).f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n}(x-x_i).

At a node, the error is zero. Consequently, on an interval [a,b][a,b] containing all nodes,

∣f(x)−pn(x)∣≤Mn+1(n+1)!∣∏i=0n(x−xi)∣,|f(x)-p_n(x)| \le \frac{M_{n+1}}{(n+1)!} \left|\prod_{i=0}^{n}(x-x_i)\right|,

where

Mn+1=max⁡t∈[a,b]∣f(n+1)(t)∣.M_{n+1}=\max_{t\in[a,b]}|f^{(n+1)}(t)|.

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 nn, 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

f(x)=11+25x2,−1≤x≤1.f(x)=\frac{1}{1+25x^2}, \qquad -1\le x\le 1.

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 [−1,1][-1,1] is the set of Chebyshev nodes

xi=cos⁡ ⁣((2i+1)π2(n+1)),i=0,…,n.x_i=\cos\!\left(\frac{(2i+1)\pi}{2(n+1)}\right), \qquad i=0,\ldots,n.

These nodes cluster near the endpoints. They are the roots of the Chebyshev polynomial Tn+1T_{n+1}, a member of a classical family of orthogonal polynomials.

Among all monic polynomials of degree n+1n+1, the nodal polynomial associated with these roots minimizes the maximum absolute value on [−1,1][-1,1]:

max⁡x∈[−1,1]∣∏i=0n(x−xi)∣=2−n.\max_{x\in[-1,1]} \left|\prod_{i=0}^{n}(x-x_i)\right| =2^{-n}.

A related choice, the Chebyshev–Lobatto nodes, includes both endpoints:

xi=cos⁡ ⁣(iπn),i=0,…,n,n≥1.x_i=\cos\!\left(\frac{i\pi}{n}\right), \qquad i=0,\ldots,n,\quad n\ge1.

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

Λn(x)=∑i=0n∣ℓi(x)∣\Lambda_n(x)=\sum_{i=0}^{n}|\ell_i(x)|

and the Lebesgue constant

Λn=max⁡x∈[a,b]Λn(x).\Lambda_n=\max_{x\in[a,b]}\Lambda_n(x).

If the data are perturbed by amounts satisfying ∣δyi∣≤ε|\delta y_i|\le\varepsilon, then the change in the exact interpolant satisfies

∣δpn(x)∣≤Λn(x)ε,|\delta p_n(x)|\le\Lambda_n(x)\varepsilon,

and hence

∥δpn∥∞≤Λnε.\|\delta p_n\|_\infty\le\Lambda_n\varepsilon.

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

En(f)=inf⁡deg⁡q≤n∥f−q∥∞,E_n(f)=\inf_{\deg q\le n}\|f-q\|_\infty,

then

∥f−pn∥∞≤(1+Λn)En(f).\|f-p_n\|_\infty \le(1+\Lambda_n)E_n(f).

For Chebyshev nodes, Λn\Lambda_n grows only logarithmically with nn; 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 mm conditions consisting of consecutive derivatives at distinct nodes determines a unique polynomial of degree at most m−1m-1. Interpolation of a function and its first nn derivatives at a single point gives its degree-nn 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.