Polynomial Interpolation

Polynomials are the most fundamental tool of numerical computation. Unlike trigonometric, exponential, or rational functions, polynomials can be evaluated using only addition and multiplication, making them cheap and numerically stable to compute. This chapter builds from the ground up: starting with the mathematical structure of polynomials and the theoretical guarantees that justify approximating with them, through three classical interpolation methods, and finishing with the sophisticated techniques needed to make those methods reliable in practice.

---

Learning Objectives

By the end of this chapter you should be able to:

1. Identify the degree, number of coefficients, and vector space properties of a polynomial.
2. State the Weierstrass Approximation Theorem and explain its implications for approximation accuracy.
3. Construct and apply the Taylor Series expansion of a function about a point, and bound the truncation error using the remainder term.
4. Set up and solve the Vandermonde linear system to find an interpolating polynomial.
5. Construct the Lagrange interpolating polynomial using basis polynomials $L_k(x)$ and prove why adding a new node forces a full rebuild.
6. Build and extend Newton’s divided difference table, and explain why it handles new nodes efficiently.
7. Apply Cauchy’s interpolation error theorem to compute an upper bound on the error of a polynomial interpolant.
8. Formulate the Hermite interpolating polynomial and explain its advantage over standard interpolation for a fixed dataset.
9. Describe Runge’s phenomenon, identify its root causes, and compute Chebyshev nodes for a given interval.

---

Chapter Sections

#	Section	Key Concepts
1	Polynomial Basics & Vector Spaces	Degree, coefficients, basis, dimension, functional vs. polynomial space
2	Weierstrass Theorem & Taylor Series	Approximation theorem, Taylor expansion, truncation error bound
3	Vandermonde Matrix Interpolation	Linear system setup, matrix inversion, computational cost
4	Lagrange Interpolation	Basis polynomials, Kronecker delta property, recomputation limitation
5	Newton Divided Differences	Divided difference table, incremental node addition, reuse advantage
6	Interpolation Error & Cauchy’s Theorem	Error formula, node product $W(x)$, upper bound calculation
7	Hermite Interpolation	Derivative conditions, degree $2n+1$, $h_k$ and $\hat{h}_k$ basis families
8	Runge’s Phenomenon & Chebyshev Nodes	Endpoint oscillation, semicircle construction, Chebyshev formula