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.

A rational interpolant is a rational function agreeing with given data at every interpolation node. If the representation is required to have no zero denominator at those nodes, this condition is part of the problem, in addition to the degree restrictions. Even when removable common factors are cancelled before evaluation, the resulting rational function must still take the prescribed values. For example, at the data $(0,0),(1,1)$ there is no interpolant $a/(x-b)$: the first value forces $a=0$ when its denominator is nonzero, and then the second value cannot be one. The cleared equations nevertheless have the unique coefficient solution $a=0,b=1$.

Rational interpolation seeks a rational function $q/r$ with prescribed bounds on the polynomial degrees of its numerator and denominator and prescribed values at distinct interpolation nodes. A rational interpolant must have a well-defined value at each interpolation node. With a specified numerator-denominator representation, this requires $r(x_i)\ne 0$ for every $i$. A normalization such as a monic polynomial denominator removes the common scaling freedom but does not guarantee existence or uniqueness. Multiplying by a zero denominator can create spurious solutions to the rational interpolation linearization.

For rational interpolation with $\mathrm{deg}q\le m$ and a monic denominator $r(x)=x^{\ell }-{\sum }_{j=0}^{\ell -1}{b}_j{x}^j$, multiplying through gives the linear systemThese equations are equivalent to the fraction conditions only when all $r(x_i)$ are nonzero. If $f_i=x_i^{m+1}$ and $m+\ell =n$, the coefficient matrix is the Vandermonde matrix with rows $(1,x_i,\dots ,x_i^n)$, so distinct interpolation nodes give a unique coefficient solution. More constructively, divide $W(x)={\prod }_{i=0}^n(x-x_i)$ by $x^{m+1}$ as $W=x^{m+1}R+S$, $\mathrm{deg}S\le m$. Then $r=R$, $q=-S$, since $x^{m+1}r-q$ is the unique monic degree-$n+1$ polynomial vanishing at all the interpolation nodes. The quotient may vanish at a node, so unique solvability of this linear system does not prove existence of a rational interpolant.

The Runge phenomenon is the failure of increasing-degree polynomial interpolation at equally spaced interpolation nodes to converge to some smooth target functions, with large oscillations near the ends of the interval. It is a property of the approximation problem, and can occur even with exact arithmetic. A numerically stable evaluation method cannot remove it. Endpoint clustering, as in Chebyshev-Lobatto nodes, changes the approximation problem and can greatly improve it.^[ref]

Take $f(x)=1/(1+25x^2)$ on $[-1,1]$ and polynomial degree at most $10$. Use either $x_k=-1+k/5$ or $x_k=\cos (k\pi /10)$ for $k=0,\dots ,10$. Each interpolation polynomial passes through all eleven of its own samples, yet the first has severe endpoint oscillations and the second stays much closer to the target function. Evaluating both by the barycentric interpolation formula on $20,001$ equally spaced points, including the endpoints, gives sampled maximum absolute errors of approximately $1.915659$ and $0.132197$, respectively: about a $14.49$-fold reduction. These are maxima over the stated grid, not certified maxima over the continuous interval. The generator separately checks exact reproduction of all stored nodal values.

The polynomial interpolation error formula explains why interpolation nodes enter the analysis. If $f$ has $n+1$ continuous derivatives on an interval containing $x$ and all the interpolation nodes, then for a suitable ${\xi }_x$ in that interval,At an interpolation node the error is zero directly. Away from the interpolation nodes, both the product and the high-order derivative matter. A short proof applies Rolle's theorem repeatedly to $f(t)-p_n(t)-[f(x)-p_n(x)]{\prod }_i(t-x_i)/{\prod }_i(x-x_i)$, which vanishes at $n+2$ distinct points.^[ref]

The successful comparison here does not assert that Chebyshev-Lobatto nodes solve every approximation problem for every function. The derivatives, the polynomial degree, and measurement errors still matter. The Lebesgue constant of interpolation measures worst-case amplification of nodal errors, while the polynomial reproduction error bound relates interpolation to the best uniform approximation available at that polynomial degree.

A divided difference depends on the chosen interpolation nodes and their data, but is unchanged by any permutation $\sigma$ of those same interpolation nodes. The explicit sum in divided difference makes this visible: a permutation merely rearranges its summands.^[ref]

There is also a short explanation using Lagrange cardinal polynomials. The coefficient of $x^k$ in the $j$th Lagrange cardinal polynomial is $1/{\prod }_{i\ne j}(x_j-x_i)$. Taking that coefficient in their weighted sum gives exactly the explicit divided difference formula. Since polynomial interpolation has a unique answer for a fixed set of distinct interpolation nodes, this coefficient cannot depend on their ordering. If the interpolation polynomial has polynomial degree below $k$, the coefficient is zero.

For the four-point example in divided difference table, every ordering gives third divided difference $1$. This does not make every Newton polynomial coefficient invariant: $f[-1,0]=-1$ whereas $f[3,2]=17$, because these use different pairs of interpolation nodes. Even at second order, $f[-1,0,2]=1$ and $f[3,2,0]=5$ use different triples. The node order in Newton interpolation determines which subsets occur along the top row.