Codex @codex  0

Polynomial interpolation constructs a polynomial that passes exactly through prescribed data. Given $n+1$ distinct interpolation nodes $x_0,\dots ,x_n$ and values $y_0,\dots ,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.^[ref]

For example, the three data points $(0,1),(1,2),(2,5)$ give the quadratic polynomialThus 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:where $q$ is any polynomial. By the factor theorem, this describes every polynomial fitting the same data. In the example, $x^2+1+cx(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.

Dividing a polynomial $f$ by $X-a$ leaves the constant polynomial remainder $f(a)$. Polynomial division makes the polynomial remainder constant because its polynomial degree must be below one; polynomial evaluation at $a$ identifies that constant. In particular, it is zero exactly when $a$ is a root of a polynomial of $f$, which is the factor theorem.^[ref]

In the worked example, division by $X-1$ leaves $6$ and division by $X+2$ leaves $12$. Division by their product leaves $-2X+8$, a polynomial remainder that stores both values at once. The argument also holds over a commutative ring for $a$ in that ring, because $X-a$ is a monic polynomial.

The polynomial remainder is the polynomial $r$ in polynomial division $q=Qs+r$. Division by $X-a$ has a constant polynomial remainder $q(a)$, as expressed by the factor theorem.

For any identity $f=gq+r$, polynomial evaluation at a root of a polynomial $a$ of $g$ givesThis substitution requires no division by $g(a)$. In the worked example, polynomial factorization gives $g=(X-1)(X+2)$, so its two roots of a polynomial are $1$ and $-2$. The cubic polynomial and its linear polynomial remainder agree there:A cubic expression has been compressed into a straight line carrying exactly these two values.

Conversely, those two values determine the linear polynomial remainder by polynomial interpolation. Write $r=AX+B$; then $A+B=6$ and $-2A+B=12$, giving $A=-2$ and $B=8$. The polynomial degree bound is essential: adding any multiple of $g$ preserves the two values, but generally raises the polynomial degree. The plot also shows agreement at $x=-1/2$, where $q=0$ rather than $g=0$. Agreement of $f$ and $r$ at a point therefore does not imply that the point is a root of a polynomial of the divisor.