25 Polynomial Interpolation
Constructing a polynomial that passes exactly through a given set of data points.
25.1 Existence and Uniqueness
Given \(n+1\) distinct points \((x_i, y_i)\), there exists a unique polynomial \(P_n(x)\) of degree at most \(n\) such that \(P_n(x_i) = y_i\) for all \(i = 0, ..., n\).
Count the number of coefficients in a degree-\(n\) polynomial.
Write the interpolation equations as a Vandermonde linear system.
Use distinctness of the nodes to explain why the Vandermonde matrix is nonsingular.
Conclude the result above.
25.2 Lagrange Form
Provides an explicit construction for the interpolating polynomial.
\[ \begin{align} L_i(x) = \prod_{j=0, j \neq i}^n \frac{x - x_j}{x_i - x_j}. \end{align} \] The interpolating polynomial is \(P_n(x) = \sum_{i=0}^n y_i L_i(x)\).
Show that \(L_i(x_j)=0\) when \(i\neq j\).
Show that \(L_i(x_i)=1\).
Use the previous two steps to prove that \(P_n(x_j)=y_j\) for every node.
Explain why uniqueness follows from the result above.
Computational Cost: Evaluation of the Lagrange form costs \(O(n^2)\) operations. Adding a new point requires recomputing all basis polynomials.
25.3 Barycentric Interpolation
A numerically stable and efficient refinement of the Lagrange form.
\[ \begin{align} P_n(x) = \frac{\sum_{i=0}^n \frac{w_i}{x - x_i} y_i}{\sum_{i=0}^n \frac{w_i}{x - x_i}}, \quad \text{where } w_i = \frac{1}{\prod_{j \neq i} (x_i - x_j)}. \end{align} \]
Advantages: Evaluation costs only \(O(n)\) once the weights \(w_i\) are computed (\(O(n^2)\)). This is the standard recommended approach for general polynomial interpolation.
25.4 Interpolation Error
Let \(P_n\) interpolate \(f\) at distinct nodes \(x_0,...,x_n\). If \(f\) has \(n+1\) continuous derivatives, then for each \(x\) there exists \(\xi_x\) in the interval containing the nodes and \(x\) such that \[ \begin{align} f(x)-P_n(x) = \frac{f^{(n+1)}(\xi_x)}{(n+1)!} \prod_{j=0}^n (x-x_j). \end{align} \]
Define \(\omega(x)=\prod_{j=0}^n(x-x_j)\).
For a fixed \(x\), construct \(g(t)=f(t)-P_n(t)-c\omega(t)\) so that \(g(x)=0\).
Count the zeros of \(g\).
Apply Rolle’s theorem \(n+1\) times.
Solve for \(c\) and derive the result above.
25.5 Runge’s Phenomenon
Equally spaced points are often a poor choice for high-degree interpolation.
The Runge Phenomenon: For certain functions, such as \(f(x) = 1/(1+25x^2)\) on \([-1, 1]\), the interpolation error near the boundaries increases exponentially as the degree \(n \to \infty\).
The Chebyshev nodes from the result above, \[ \begin{align} x_i = \cos\left( \frac{2i+1}{2n+2} \pi \right), \quad i = 0, ..., n. \end{align} \] make the interpolation error polynomial small on \([-1,1]\). By the result above and the result above, this directly improves the worst-case interpolation error bound.
Translate the node formula above into the indexing convention of the result above.
Use the result above to compute \(\|\omega_{n+1}\|_\infty\) for these nodes.
Compare this with the error polynomial for equally spaced nodes numerically for \(n=10,20,40\).
Explain why Chebyshev nodes reduce Runge oscillations without claiming that every function converges uniformly under every interpolation scheme.
25.6 Cubic Splines
For large datasets, high-degree polynomial interpolation is avoided in favor of piecewise polynomials.
A piecewise cubic function \(S(x)\) that is \(C^2\) continuous (continuous values, first, and second derivatives) at the internal nodes.
(Spline linear system) Computing the coefficients of a cubic spline requires solving a sparse tridiagonal linear system, which can be done in \(O(n)\) time.
25.7 Exercises
Construct the Lagrange form for points \((-1, 1), (0, 0), (1, 1)\). Verify it is \(P_2(x) = x^2\).
Use the barycentric formula to interpolate \(f(x) = \sin(x)\) at 5 Chebyshev nodes.
Compare the error plots for \(f(x) = 1/(1+25x^2)\) using 15 equally spaced nodes vs. 15 Chebyshev nodes.