# Polynomial interpolation
**Polynomial interpolation** is the problem of finding a polynomial that passes exactly through a given set of data points: given \( n+1 \) distinct nodes \( x_0, \ldots, x_n \) and values \( f_0, \ldots, f_n \), there is a unique polynomial \( P_n \) of degree at most \( n \) with \( P_n(x_k) = f_k \) for every \( k \).[1](https://dlmf.nist.gov/3.3) It is a foundational tool of numerical analysis, used wherever discrete samples of a function must be turned into a form that can be evaluated, differentiated, or integrated between the samples.[2](https://technav.ieee.org/topic/interpolation/)
| Key fact | Detail |
|---|---|
| Existence and uniqueness | For \( n+1 \) distinct nodes there is exactly one interpolating polynomial of degree \( \le n \); the problem is well-posed.[1](https://dlmf.nist.gov/3.3) • [3](https://epubs.siam.org/doi/pdf/10.1137/S0036144502417715) |
| Error formula | If \( f \in C^{n+1} \), then \( f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \, \omega_{n+1}(x) \) for some \( \xi \) in the interval, where \( \omega_{n+1} \) is the nodal polynomial \( \prod_{i=0}^{n} (x - x_i) \).[1](https://dlmf.nist.gov/3.3) |
| Best nodes | On \([-1,1]\) the Chebyshev nodes minimize the maximum of \( |\omega_{n+1}| \), giving \( \le 2^{-n} \); no other node placement does better.[4](https://www.gilgamath.com/pdfs/numas.pdf) |
| Chebyshev error bound | \( \|f - p\|_\infty \le \|f^{(n+1)}\|_\infty / (2^n (n+1)!) \) for interpolation at Chebyshev nodes.[5](https://maxjensen.github.io/Computational_Methods_lecture_notes/4.1_interpolation.html) |
| Runge phenomenon | With equispaced nodes, interpolants diverge exponentially as the degree grows, and no method based on equispaced data fully avoids this.[6](https://www.chebfun.org/docs/guide/guide04.html) |
| Stable evaluation | The barycentric formula evaluates the interpolant stably and efficiently even for degrees in the millions.[7](https://www.chebfun.org/docs/guide/guide01.html) |
| Fast algorithms | For Chebyshev nodes, interpolation and integration run via the FFT; for other nodes, fast-multipole-based schemes need \( O(N \log(1/\varepsilon)) \) operations for interpolation with \( N \) nodes and precision \( \varepsilon \).[8](https://epubs.siam.org/doi/10.1137/0733082) |
## The interpolation problem and its forms
The classical problem is to find \( p \in \Pi_n \), the space of polynomials of degree at most \( n \), satisfying \( p(x_j) = f_j \) for \( j = 0, \ldots, n \). The solution exists, is unique, and depends continuously on the data.[3](https://epubs.siam.org/doi/pdf/10.1137/S0036144502417715) A truncated [Taylor series](https://www.edgepedia.org/taylor-series) can be viewed as the simplest interpolating polynomial, using a single node but matching several derivatives there.[9](https://www.maths.dur.ac.uk/users/anthony.yeates/na17.pdf)
**Lagrange form.** The interpolant is written as \( P_n(z) = \sum_{k=0}^{n} \ell_k(z) f_k \), where the basis polynomials \( \ell_k \) satisfy \( \ell_k(z_j) = \delta_{k,j} \).[1](https://dlmf.nist.gov/3.3) The formula was proposed by Edward Waring and Leonard Euler and published in 1795 by [Joseph-Louis Lagrange](https://www.edgepedia.org/joseph-louis-lagrange); its practical advantage is flexibility when new nodes are added, since previously computed terms can be reused.[10](https://www.imaginary.org/sites/default/files/snapshots/1609b-szpond_final.pdf)
**Newton form.** [Isaac Newton](https://www.edgepedia.org/isaac-newton) introduced divided differences in his *Regula Differentiarum* in 1676, building the interpolant recursively from the data.[10](https://www.imaginary.org/sites/default/files/snapshots/1609b-szpond_final.pdf) Newton's form leads naturally to [Hermite interpolation](https://www.edgepedia.org/hermite-interpolation), where derivatives as well as values are matched, and to multistep formulas for ordinary differential equations.[3](https://epubs.siam.org/doi/pdf/10.1137/S0036144502417715)
**Barycentric form.** Dividing the Lagrange formula by the interpolant of the constant function 1 gives the barycentric formula, in which the weights \( w_j \) appear symmetrically in numerator and denominator. According to Berrut and Trefethen it is the most efficient representation of \( P_n \).[1](https://dlmf.nist.gov/3.3) A practical advantage over [Newton interpolation](https://www.edgepedia.org/newton-interpolation) is that the weights depend only on the nodes, not on the data: they are computed in \( O(n^2) \) operations once, after which each new set of function values is interpolated in \( O(n) \) operations, whereas Newton interpolation requires a new divided-difference tableau for every new function.[3](https://epubs.siam.org/doi/pdf/10.1137/S0036144502417715) For Chebyshev points the weights have simple explicit closed forms.[3](https://epubs.siam.org/doi/pdf/10.1137/S0036144502417715)
## Error theory
When \( f \) is \( n+1 \) times continuously differentiable, the error has an exact remainder form analogous to the Taylor remainder, with the nodal polynomial \( \omega_{n+1} \) replacing \( (x-a)^{n+1} \):[11](https://roesner.pages.ub.uni-bielefeld.de/lectures/computational-physics/semester/sose2026/lecture/02_interpolation/04_properties.html)
\[ f(x) - P_n(x) = \frac{f^{(n+1)}(\xi_x)}{(n+1)!} \, \omega_{n+1}(x) \]
for some \( \xi_x \) in the interval.[1](https://dlmf.nist.gov/3.3) Since \( f \) and its derivatives cannot be controlled, the only lever on the error is the choice of nodes, which shapes \( \omega_{n+1} \).[4](https://www.gilgamath.com/pdfs/numas.pdf)
**Chebyshev nodes.** The roots of [Chebyshev polynomials](https://www.edgepedia.org/chebyshev-polynomials), \( \tilde{x}_i = \cos\bigl( \frac{2i+1}{2(n+1)} \pi \bigr) \), minimize the maximum magnitude of the error polynomial on \([-1,1]\); for these nodes \( \tilde{\omega}_{n+1}(x) = 2^{-n} T_{n+1}(x) \), and the error bound becomes \( \|f - p\|_\infty \le \|f^{(n+1)}\|_\infty / (2^n (n+1)!) \).[5](https://maxjensen.github.io/Computational_Methods_lecture_notes/4.1_interpolation.html) The nodes cluster near the interval endpoints, which suppresses the large oscillations of the error polynomial seen with equal spacing.[5](https://maxjensen.github.io/Computational_Methods_lecture_notes/4.1_interpolation.html) For a general interval \([\alpha, \beta]\) the nodes are rescaled linearly, and the bound acquires a factor \( (\beta - \alpha)^{n+1} / 2^{2n+1} \).[4](https://www.gilgamath.com/pdfs/numas.pdf) Chebyshev-node collocation does not work for every continuous function; no node choice does.[12](https://lemesurierb.people.charleston.edu/numerical-methods-and-analysis-python/main/polynomial-collocation-chebychev.html)
**Runge's phenomenon.** With equispaced nodes the barycentric weights vary by factors of order \( 2^n \), so small data near the center of the interval produce oscillations near the edges up to \( 2^n \) times larger; polynomial interpolation at equally spaced points is therefore highly ill-conditioned for large \( n \).[3](https://epubs.siam.org/doi/pdf/10.1137/S0036144502417715) The Lebesgue function, which measures how much interpolation can amplify data errors, reaches a size of about \( 10^4 \) for 20 equispaced points on \([-1,1]\) and grows far worse at 40 points.[6](https://www.chebfun.org/docs/guide/guide04.html) As the degree increases, equispaced interpolants diverge exponentially, and no approximation method based on equispaced data can completely avoid this.[6](https://www.chebfun.org/docs/guide/guide04.html) This sits alongside the Weierstrass approximation theorem, which guarantees that some sequence of polynomials converges uniformly to any continuous function; an unrefined interpolation scheme, however, does not generally deliver such polynomials.[5](https://maxjensen.github.io/Computational_Methods_lecture_notes/4.1_interpolation.html)
## Computation at scale
For functions tabulated at [Chebyshev nodes](https://www.edgepedia.org/chebyshev-nodes), spectral interpolation and indefinite integration can be performed stably and efficiently through the fast [Fourier transform](https://www.edgepedia.org/fourier-transform).[8](https://epubs.siam.org/doi/10.1137/0733082) For many other node sets, such as Gaussian nodes, the classical schemes are stable but slow, requiring \( O(N^2) \) operations for \( N \) nodes. Algorithms of Dutt, Gu, and Rokhlin reduce this to \( O(N \log(1/\varepsilon)) \) operations for evaluating Lagrange interpolants at multiple points, and \( O(N \log N + N \log(1/\varepsilon)) \) for integration and differentiation, where \( \varepsilon \) is the working precision; the interpolation and integration schemes are stable, while differentiation has a condition number proportional to \( N^2 \).[8](https://epubs.siam.org/doi/10.1137/0733082)
The Chebfun software system builds on this machinery: it represents smooth functions by piecewise polynomial interpolation in Chebyshev points, equivalently by Chebyshev polynomial expansions via the FFT, choosing the number of points adaptively; a simple function may need 20 or 30 points, while the process remains stable for functions requiring a million.[7](https://www.chebfun.org/docs/guide/guide01.html) • [13](https://www.chebfun.org/about/) For analytic functions on a Bernstein ellipse, Chebyshev interpolation converges spectrally, but when a singularity lies close to the interval the rate drops to nearly one; splitting the interval and blending local interpolants with a partition of unity restores fast convergence, and in one reported case reduced the node count from 25,743 for a global interpolant to 523.[14](https://arxiv.org/abs/1708.02611)
## Piecewise alternatives
A single high-degree polynomial is not the only way to interpolate. Piecewise polynomial methods split the range at breakpoints and fit a low-degree polynomial on each interval, matching derivatives across the breaks: second derivatives for cubic splines, first derivatives for monotone interpolants.[15](https://docs.scipy.org/doc/scipy/tutorial/interpolate/splines_and_polynomials.html) This avoids the oscillation that afflicts high-degree global interpolants and is widely used in engineering simulation and computer-aided design.[2](https://technav.ieee.org/topic/interpolation/) When the data are noisy, fitting methods such as least-squares regression, which minimize overall error without passing through every point, are preferred over exact interpolation.[2](https://technav.ieee.org/topic/interpolation/)
## Uses and cautions
Extrapolation, meaning evaluation outside the range of the data, is unreliable: polynomial behavior there is unconstrained and can be wildly wrong even when the interpolation inside the range is excellent.[11](https://roesner.pages.ub.uni-bielefeld.de/lectures/computational-physics/semester/sose2026/lecture/02_interpolation/04_properties.html)
## References
1. [DLMF §3.3 Interpolation, NIST Digital Library of Mathematical Functions](https://dlmf.nist.gov/3.3)
2. [Interpolation, IEEE Technology Navigator](https://technav.ieee.org/topic/interpolation/)
3. [J.-P. Berrut and L. N. Trefethen (2004). Barycentric Lagrange Interpolation. SIAM Review 46(3).](https://epubs.siam.org/doi/pdf/10.1137/S0036144502417715)
4. [Numerical Methods Course Notes, Chapter 7: Interpolation](https://www.gilgamath.com/pdfs/numas.pdf)
5. [Polynomial interpolation, Computational Methods MATH0058 lecture notes](https://maxjensen.github.io/Computational_Methods_lecture_notes/4.1_interpolation.html)
6. [Chebfun Guide, Chapter 4: Chebfun and Approximation Theory](https://www.chebfun.org/docs/guide/guide04.html)
7. [Chebfun Guide, Chapter 1: Getting Started with Chebfun](https://www.chebfun.org/docs/guide/guide01.html)
8. [A. Dutt, M. Gu, and V. Rokhlin. Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation. SIAM Journal on Numerical Analysis.](https://epubs.siam.org/doi/10.1137/0733082)
9. [Numerical Analysis II Lecture Notes, Durham University](https://www.maths.dur.ac.uk/users/anthony.yeates/na17.pdf)
10. [A few shades of interpolation, Snapshots of modern mathematics (IMAGINARY)](https://www.imaginary.org/sites/default/files/snapshots/1609b-szpond_final.pdf)
11. [Properties of interpolation, Computational Physics lecture notes, Universität Bielefeld](https://roesner.pages.ub.uni-bielefeld.de/lectures/computational-physics/semester/sose2026/lecture/02_interpolation/04_properties.html)
12. [Choosing the Collocation Points: the Chebyshev Method, Numerical Methods and Analysis with Python](https://lemesurierb.people.charleston.edu/numerical-methods-and-analysis-python/main/polynomial-collocation-chebychev.html)
13. [About Chebfun](https://www.chebfun.org/about/)
14. [K. W. Aiton and T. A. Driscoll. An adaptive partition of unity method for Chebyshev polynomial interpolation. arXiv:1708.02611.](https://arxiv.org/abs/1708.02611)
15. [Piecewise polynomials and splines, SciPy v1.18.0 Manual](https://docs.scipy.org/doc/scipy/tutorial/interpolate/splines_and_polynomials.html)
---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Numerical, string, and geometric algorithms › Numerical methods and approximation*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license