= Polynomial interpolation
{title2=$p_n(x_i)=y_i,\quad\deg p_n\leq n$}
{wiki}
<Polynomial interpolation> constructs a <polynomial> that passes exactly through prescribed data. Given $n+1$ distinct <interpolation nodes> $x_0,\ldots,x_n$ and values $y_0,\ldots,y_n$, there is exactly one <interpolation polynomial> $p_n$ of <polynomial degree> at most $n$ with $p_n(x_i)=y_i$ for every $i$. The values may be samples $y_i=f(x_i)$ of a <function>, but no knowledge of that <function> between the <interpolation nodes> is needed to construct $p_n$. The <Lagrange polynomial> and <Newton polynomial> are two representations of this same answer.https://fncbook.com/polynomial/[Toby A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation, §9.1, Theorems 9.1.1–9.1.2]{ref}
For example, the three data points $(0,1),(1,2),(2,5)$ give the <quadratic polynomial>
$$
p_2(x)=x^2+1,\qquad p_2(0)=1,\quad p_2(1)=2,\quad p_2(2)=5.
$$
Thus <polynomial interpolation> supplies $p_2(1/2)=5/4$ as an intermediate value. Whether this approximates an unknown underlying <function> well is a separate question about <polynomial interpolation error>.
Both hypotheses in the uniqueness statement matter. The <Lagrange cardinal polynomials> prove existence constructively. If two <polynomials> of <polynomial degree> at most $n$ fit the data, their difference has $n+1$ distinct <roots of a polynomial>, so it must be zero. Repeated <interpolation nodes> with conflicting values have no solution, and repeated equal values provide no additional independent condition; prescribed <derivatives> instead lead to <Hermite interpolation>. Without the <polynomial degree> restriction there are infinitely many solutions:
$$
p(x)=p_n(x)+q(x)\prod_{i=0}^n(x-x_i),
$$
where $q$ is any <polynomial>. By the <factor theorem>, this describes every <polynomial> fitting the same data. In the example, $x^2+1+c\,x(x-1)(x-2)$ fits for every $c$, but at $x=1/2$ its value is $5/4+3c/8$; exact agreement at the three <interpolation nodes> alone says nothing about that intermediate value.
The usefulness of <polynomial interpolation> is that data become an explicit <function> whose values, <derivatives>, and <integrals> can be calculated. Differentiating or integrating the <Lagrange cardinal polynomials> produces <differentiation weights from nodal evaluations> or a <quadrature rule>. Exact passage through observations is the defining constraint. In <polynomial regression>, <linear least squares> instead chooses a <polynomial degree> and minimizes a sum of squared residuals, generally without passing through every observation. Interpolating noisy values reproduces their errors at the <interpolation nodes> and can amplify them between <interpolation nodes>; <polynomial interpolation> does not itself smooth measurement noise. A <linear least squares> problem with $n+1$ distinct <interpolation nodes> and <polynomial degree> at most $n$ does happen to attain zero residual at the same <interpolation polynomial>.
Back to article page
