Polynomial interpolation is the simplest finite representation of a function, but it already shows the tension between approximation power and numerical stability.
Interpolation polynomial
Definition. Given distinct nodes \(x_0,\ldots,x_n\) and values \(f(x_j)\), the interpolation polynomial \(p_n\) is the unique polynomial of degree at most \(n\) satisfying \(p_n(x_j)=f(x_j)\) for all \(j\).
Lagrange formula
Proposition. The interpolant is \(p_n(x)=\sum_{j=0}^n f(x_j)\ell_j(x)\), where \(\ell_j(x)=\prod_{m\ne j}(x-x_m)/(x_j-x_m)\). This formula proves existence and uniqueness, but is not always the best computational form.
Error formula
Theorem. If \(f\in C^{n+1}[a,b]\), then for each \(x\) there is \(\xi_x\in(a,b)\) such that \(f(x)-p_n(x)=f^{(n+1)}(\xi_x)\prod_{j=0}^n(x-x_j)/(n+1)!\). The node geometry is therefore as important as smoothness.
Runge phenomenon
Remark. High-degree interpolation at equally spaced nodes can diverge near the endpoints even for smooth functions. Chebyshev nodes reduce the growth of the interpolation operator and are usually the right baseline for global polynomial interpolation.
Divided differences
Definition. Divided differences build the Newton form of the interpolating polynomial incrementally. They are useful for adding nodes, estimating derivatives, and understanding interpolation as repeated slope extraction.
Unisolvence and divided differences
Theorem. For distinct nodes \(x_0,\ldots,x_n\) and data \(y_0,\ldots,y_n\), there is a unique polynomial \(p_n\) of degree at most \(n\) satisfying \(p_n(x_i)=y_i\).
Proof. The Lagrange formula \[ p_n(x)=\sum_{i=0}^ny_i\ell_i(x),\qquad \ell_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}, \] proves existence. The difference of two interpolants has \(n+1\) distinct zeros but degree at most \(n\), so it is zero.
Newton form, \[ p_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j), \] supports incremental nodes and \(O(n)\) evaluation by nested multiplication. Divided differences remain meaningful with repeated nodes through derivatives, leading to Hermite interpolation.
Interpolation remainder
Theorem. If \(f\in C^{n+1}[a,b]\), then for every \(x\in[a,b]\), \[ f(x)-p_n(x) =\frac{f^{(n+1)}(\xi_x)}{(n+1)!} \omega_{n+1}(x), \qquad \omega_{n+1}(x)=\prod_{j=0}^n(x-x_j), \] for some \(\xi_x\in(a,b)\).
Proof. If \(x\) is not a node, choose \[ C=\frac{f(x)-p_n(x)}{\omega_{n+1}(x)} \] and define \(g(t)=f(t)-p_n(t)-C\omega_{n+1}(t)\). It has zeros at all nodes and at \(x\). Repeated Rolle's theorem gives a point \(\xi_x\) where \(g^{(n+1)}(\xi_x)=0\), yielding the formula.
Lebesgue constants and data amplification
The interpolation operator satisfies \[ \|I_nf\|_\infty\le\Lambda_n\|f\|_\infty,\qquad \Lambda_n=\max_x\sum_{i=0}^n|\ell_i(x)|. \] Moreover, \[ \|f-I_nf\|_\infty \le(1+\Lambda_n) \inf_{p\in\mathcal P_n}\|f-p\|_\infty. \] Thus convergence depends on both approximability and stability of the nodes. Equally spaced nodes have exponentially growing \(\Lambda_n\), enabling Runge oscillation; Chebyshev nodes have \(\Lambda_n=O(\log n)\).
Chebyshev nodes
The roots \[ x_j=\cos\frac{(2j+1)\pi}{2n+2},\qquad j=0,\ldots,n, \] minimize the maximum of the monic nodal polynomial: \[ \min_{\substack{q\text{ monic}\\\deg q=n+1}} \|q\|_{\infty,[-1,1]}=2^{-n}, \] attained by \(2^{-n}T_{n+1}\). This controls the remainder factor and spreads nodes near endpoints where equispaced interpolation is least stable.
Barycentric evaluation
With weights \[ w_i=\left(\prod_{j\ne i}(x_i-x_j)\right)^{-1}, \] the interpolant is evaluated stably as \[ p_n(x)= \frac{\sum_iw_i y_i/(x-x_i)} {\sum_iw_i/(x-x_i)}. \] At a node its limiting value is assigned exactly. This form avoids explicitly forming large polynomial coefficients and supports \(O(n)\) evaluation.