Chapter 1 – Interpolation and Polynomial Approximation

Explore key interpolation concepts with short theory blocks and interactive exercises: existence and uniqueness, divided differences, Newton and Hermite interpolation, Chebyshev nodes versus Runge’s phenomenon, and least-squares approximation.

Existence and uniqueness of the interpolation polynomial

Conditions on data points for a unique interpolating polynomial.

Key idea. Given n plus one data points with distinct x values, there exists a unique polynomial of degree at most n that interpolates all those points. If two y values are prescribed at the same x, no interpolating polynomial can satisfy both constraints simultaneously.

Exercise 1 – Do we have a unique interpolant?

Consider the following data sets. Decide whether a (unique) polynomial interpolant of degree at most two exists.

Data set A

xy
01
12
25

Data set B

xy
01
12
13
Show explanation

For data set A, the x values are all distinct, so a unique polynomial of degree at most two exists. For data set B, the same x equals one is paired with two different y values, so no function, hence no polynomial, can pass exactly through all three pairs.

Divided differences

Building the Newton interpolation coefficients from data.

Key idea. Divided differences are recursive slopes: begin with function values, form first divided differences, then use them to form higher orders. They provide the coefficients of the Newton form of the interpolating polynomial.

Exercise 2 – Compute the divided differences

Work with the fixed data set A from above:

ixif(xi)
001
112
225

Click the button to generate the divided difference table for these three nodes.

Show hint

First differences are like slopes between consecutive points. Second differences are differences of those slopes divided by the difference in x across two steps.

Newton interpolation method

Using divided differences to evaluate the interpolating polynomial.

Key idea. The Newton interpolating polynomial is built incrementally from divided differences, adding one term per new node. This form is convenient for evaluating the polynomial and for extending it when extra data points become available.

Exercise 3 – Evaluate the Newton interpolant

Using the same data set A, the Newton form is precomputed for you in the script. Evaluate it at a point of your choice.

Show Newton form used 
p(x) = a0
     + a1 (x - x0)
     + a2 (x - x0)(x - x1)

where the coefficients a0, a1, a2 are the divided differences f[x0], f[x0,x1], f[x0,x1,x2].

Chebyshev interpolation and Runge phenomenon

Comparing equispaced and Chebyshev nodes on a classic test function.

Key idea. High-degree interpolation at equally spaced nodes on a large interval can oscillate strongly near the endpoints, a behavior called Runge’s phenomenon. Chebyshev nodes cluster near the boundary and typically give much smaller interpolation errors for the same degree.

Exercise 4 – Compare error at a boundary

Consider the Runge function f(x) = 1 / (1 + 25 x²) on the interval from minus one to one. Compare the interpolation error at x = 1 when using equispaced nodes versus Chebyshev nodes.

Show explanation

For fixed degree, equidistant nodes on a wide interval force the interpolant to bend sharply near the endpoints. Chebyshev nodes mitigate this by placing more nodes where the function is hardest to approximate, thereby reducing the oscillations and error.

Hermite interpolation (values and derivatives)

Interpolating both function values and slopes at the nodes.

Key idea. Hermite interpolation incorporates derivative information at nodes, giving a polynomial that matches both function values and slopes. For two nodes with given values and derivatives, there is a unique cubic interpolant that satisfies all four conditions.

Exercise 5 – Evaluate a cubic Hermite interpolant

Work with the following data on the interval from zero to one: f(0) = 0, f'(0) = 1, f(1) = 1, f'(1) = 0. This defines a smooth S-shaped cubic Hermite interpolant between the endpoints.

Show Hermite basis formula 
Let t = (x - x0) / (x1 - x0).

H(x) = h00(t) * f0
     + h10(t) * (x1 - x0) * f0'
     + h01(t) * f1
     + h11(t) * (x1 - x0) * f1'

with basis functions:
h00(t) =  2 t³ - 3 t² + 1
h10(t) =      t³ - 2 t² + t
h01(t) = -2 t³ + 3 t²
h11(t) =      t³ -     t²

Least-squares polynomial approximation

Fitting polynomials to overdetermined data by minimizing squared error.

Key idea. When there are more data points than polynomial coefficients, an exact interpolant is usually impossible, so least-squares chooses the polynomial that minimizes the sum of squared residuals. In matrix form, this leads to the normal equations for the coefficient vector of the polynomial basis.

Exercise 6 – Fit a line vs a quadratic

Use the following noisy samples of the function cosine of x on the interval from zero to three. Compare the least-squares line and quadratic, and examine the fitted coefficients.

xy (noisy)
0.01.02
0.50.87
1.00.55
2.0-0.41
3.0-0.97
Show theory reminder 
Given data (xi, yi) and a polynomial
p(x) = c0 + c1 x + ... + cm x^m,

set up the design matrix A with entries A[i,j] = xi^j.
The least-squares coefficients satisfy the normal equations:

(Aᵀ A) c = Aᵀ y.
t>