Finite differences and interpolation · Lecture 18

Spline Interpolation and the Runge Phenomenon

Why one polynomial through many equally spaced points can be disastrous, how Chebyshev points and piecewise polynomials fix it, and how a natural cubic spline is built from one tridiagonal system.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: more data, worse curve

Interpolate the smooth bell-shaped $f(x) = \dfrac{1}{1 + 25x^2}$ on $[-1, 1]$ with $n$ equally spaced points and one polynomial of degree $n - 1$ .

5 points: largest error 0.44, poor but tame
11 points: the curve swings to 1.92 near the ends; the function itself never exceeds 1
21 points: error 60. More data made it worse
The same happens to any long data set (sensor logs, profiles, fonts): we need a different idea

points $n$	largest error
5	0.44
9	1.05
11	1.92
15	7.19
21	59.8

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

2 / 20

Today's goals

Explain the Runge phenomenon from the interpolation error term
Reduce it with Chebyshev points when the points can be chosen
Build linear and natural cubic splines and state their conditions
Set up and solve the tridiagonal system for the spline (Thomas, Lecture 13)
Choose between polynomial, spline and least-squares fits

Last time

Lagrange and divided differences: one polynomial through all the points.

Today

When one polynomial fails, use many small ones joined smoothly.

Finite differences and interpolation · you are here

L15 · Finite Differences and Operators→L16 · Newton's Forward and Backward Interpolation→L17 · Lagrange and Divided-Difference Interpolation→L18 · Spline Interpolation and the Runge Phenomenon

Builds on: L13, L17

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

3 / 20

Start here

The idea in one picture

Nine dots from a bell-shaped curve.One polynomial through all nine: it swings wildly near the ends (Runge phenomenon).A spline: a separate small cubic between each pair of dots.At each dot the pieces agree in value, slope and bending, so the join is invisible.

In plain words

One polynomial through many points can swing wildly
Use many small cubic pieces instead, one per interval
Join them so smoothly that the joints cannot be seen

New words today

Runge phenomenon: wild swings of a high-degree polynomial near the ends
spline: a curve made of smoothly joined pieces
knot: a point where two pieces meet
natural spline: no bending at the two ends

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

4 / 20

Why it happens: the node polynomial

Interpolation error with n + 1 points (Lectures 16–17)

\begin{aligned} f(x) - P_n(x) &= \frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega(x) \\ \omega(x) &= (x - x_0)(x - x_1)\cdots(x - x_n) \end{aligned}

Chebyshev points: crowd the points towards the ends

x_i = \cos\frac{(2i+1)\pi}{2(n+1)}, \qquad i = 0, \dots, n

With equal spacing $|\omega(x)|$ is much larger near the ends than in the middle
For Runge's $f$ the derivatives $f^{(n+1)}$ also grow very fast with $n$
Chebyshev points make $|\omega|$ as small and even as possible: 11 points give error 0.11 instead of 1.92
But data usually come at fixed places: we cannot choose the points

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

5 / 20

Explore: the Runge phenomenon

Increase $n$ for the equally spaced polynomial: the ends explode
Turn on Chebyshev points (hollow dots): the error now falls
Turn on the splines: small errors with equal spacing
Try $|x|$ and the step: polynomials struggle with corners and jumps

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

6 / 20

Piecewise idea 1: the linear spline

On each interval [xᵢ, xᵢ₊₁], a straight line

S(x) = y_i + \frac{y_{i+1} - y_i}{x_{i+1} - x_i}(x - x_i)

Error on an interval of width h

|f(x) - S(x)| \le \frac{h^2}{8}\max|f''|

Each piece uses only its two neighbours: no wild swings
Error falls like $h^2$ : halve the spacing, quarter the error
But the curve has corners: the slope jumps at every data point
Fine for tables and plots; not smooth enough for motion, fonts or physics

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

7 / 20

Piecewise idea 2: the cubic spline

One cubic on each interval [xᵢ, xᵢ₊₁], joined smoothly

S(x_i) = y_i, \qquad S,\; S',\; S'' \text{ continuous}

Unknowns Mᵢ = S″(xᵢ); for each inner point (spacings hᵢ = xᵢ₊₁ − xᵢ)

h_{i-1}M_{i-1} + 2(h_{i-1} + h_i)M_i + h_iM_{i+1} = 6\left(\frac{y_{i+1} - y_i}{h_i} - \frac{y_i - y_{i-1}}{h_{i-1}}\right)

Natural spline: no curvature at the two ends

M_0 = M_n = 0

Each piece has 4 coefficients: $4n$ unknowns, and the joining rules give $4n - 2$ equations; two end conditions complete it
The $M_i$ equations are tridiagonal and diagonally dominant: Thomas algorithm, $O(n)$
Like a thin flexible ruler (a draughtsman's spline) bent through pins

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

8 / 20

The method, step by step

Natural cubic spline, step by step

Sort the points; compute the spacings $h_i = x_{i+1} - x_i$
Write one $M$ -equation for each inner point $i = 1, \dots, n-1$ ; set $M_0 = M_n = 0$
Solve the tridiagonal system for $M_1, \dots, M_{n-1}$ (Thomas)
To evaluate at $x$ : find the interval $[x_i, x_{i+1}]$ containing it
Use $S(x) = \dfrac{M_i(x_{i+1}-x)^3 + M_{i+1}(x - x_i)^3}{6h_i} + \Big(y_i - \dfrac{M_ih_i^2}{6}\Big)\dfrac{x_{i+1}-x}{h_i} + \Big(y_{i+1} - \dfrac{M_{i+1}h_i^2}{6}\Big)\dfrac{x - x_i}{h_i}$

Pseudocode

input x[0..n], y[0..n], X
h[i] ← x[i+1] − x[i]
for i = 1 … n−1:          # tridiagonal rows
    a[i] ← h[i−1];  c[i] ← h[i]
    b[i] ← 2(h[i−1] + h[i])
    d[i] ← 6((y[i+1]−y[i])/h[i]
             − (y[i]−y[i−1])/h[i−1])
M ← thomas(a, b, c, d);  M[0] ← M[n] ← 0
i ← interval containing X
return S_i(X)             # formula in step 5

Setup $O(n)$ once; each evaluation is one interval search and one cubic.

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

9 / 20

Problem 1: a natural cubic spline by hand

Fit a natural cubic spline to

(1, 1)

,

(2, 2)

,

(3, 5)

,

(4, 11)

and find

y(1.5)

and

y(2.5)

.

1

h = 1

,

M_0 = M_3 = 0

. Point 1:

M_0 + 4M_1 + M_2 = 6(1 - 2\cdot2 + 5) = 12

; point 2:

M_1 + 4M_2 + M_3 = 6(2 - 2\cdot5 + 11) = 18

2

Solve

4M_1 + M_2 = 12

,

M_1 + 4M_2 = 18

:

\;M_1 = 2

,

M_2 = 4

3

On

[1, 2]

:

S = \dfrac{2(x-1)^3}{6} + \Big(1 - 0\Big)(2 - x) + \Big(2 - \dfrac{2}{6}\Big)(x - 1) = 1 + \tfrac23(x-1) + \tfrac13(x-1)^3

4

S(1.5) = 1 + \tfrac13 + \tfrac{1}{24} = 1.375

; on

[2, 3]

the same recipe gives

S(2.5) = 3.125

M = (0, 2, 4, 0)

;

\;y(1.5) \approx 1.375

,

\;y(2.5) \approx 3.125

.

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

10 / 20

Classical vs numerical

Same data, two approaches: 11 points of Runge's function

Single formula

One polynomial (degree 10)

Passes through all 11 points
Largest error 1.92, near the ends
At $x = 0.9$ : 1.58 instead of 0.047

vs

Piecewise

Natural cubic spline

Passes through all 11 points
Largest error 0.022
Setup: one 9×9 tridiagonal solve

When one polynomial cannot work

1001 points

A single polynomial of degree 1000 through equally spaced points is useless: astronomically large swings, and coefficients that cannot even be represented. The spline needs one tridiagonal solve ( $\approx 8000$ operations) and its largest error on Runge's function is $4\times10^{-8}$ .

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

11 / 20

A natural cubic spline in Python and C

Builds the tridiagonal system for $M_1, \dots, M_{n-1}$
Thomas algorithm from Lecture 13
Evaluates $S$ with the step-5 formula
Prints $M$ and $S(1.5)$ , $S(2.5)$ for Problem 1

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

12 / 20

When splines are not enough

Limitations shown failing

Jumps: at a step the cubic spline overshoots (about 11% here) and wiggles; the linear spline does not
End conditions: "natural" ( $M = 0$ ) is wrong if the true curve bends at the ends; errors are largest there
Noise: a spline still passes through every noisy point (use smoothing splines or least squares)
Extrapolation: outside the data the end cubic is a guess

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

13 / 20

Practice

Practice problem

Problem 2"Fit a natural cubic spline to the points

(0, 1)

,

(1, 2)

,

(2, 9)

,

(3, 28)

and estimate

y(1.5)

."

How to write a complete answer

State the conditions: $S$ cubic on each interval, $S, S', S''$ continuous, $M_0 = M_3 = 0$
$M$ -equations with $h = 1$ : $4M_1 + M_2 = 6(1 - 4 + 9) = 36$ , $\;M_1 + 4M_2 = 6(2 - 18 + 28) = 72$
Solve: $M_1 = 4.8$ , $M_2 = 16.8$
On $[1, 2]$ at $1.5$ : $\tfrac{4.8(0.125) + 16.8(0.125)}{6} + (2 - 0.8)(0.5) + (9 - 2.8)(0.5) = 4.15$ ; mention that the data are $x^3 + 1$ (true 4.375) and that the natural end condition causes the difference

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

14 / 20

When to use it

Cubic splines: method profile

Best case

Many points, smooth underlying curve: error $\sim h^4$ , no Runge swings
Any spacing; setup $O(n)$ with the Thomas algorithm
Smooth slope and curvature: good for motion and shapes

Worst case

Jumps and sharp corners: overshoot
Noisy data: reproduces the noise exactly
Wrong end conditions: largest errors at the ends

Best suited for

Fonts, CAD, animation paths, robot trajectories
Resampling signals and filling gaps in data
Smooth look-up tables (physical properties, calibration curves)

Avoid when

Data with errors (use least squares or smoothing splines, Lecture 23)
Monotone data that must stay monotone (use PCHIP)
Extrapolation

Rule of thumb: few points → one polynomial (or Chebyshev); many points → cubic spline; noisy points → least squares.

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

15 / 20

Comparative analysis: interpolating 11 points of Runge's function

Method	Largest error ( $n = 11$ )	Largest error ( $n = 21$ )	Smoothness	Setup cost	Choose points?
Polynomial, equal spacing	1.92	59.8	$C^\infty$ but wild	$O(n^2)$	no
Polynomial, Chebyshev points	0.109	0.015	$C^\infty$	$O(n^2)$	yes (needed)
Linear spline	0.067	0.042	corners ( $C^0$ )	none	no
Natural cubic spline	0.022	0.0032	$C^2$	$O(n)$ tridiagonal	no

Errors measured on 4001 points in $[-1, 1]$ (lab tool). Only the spline gets better steadily with equally spaced data.

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

16 / 20

Roadmap

End of Module 4: what comes next

We can now fill in values between data points in every common situation. Next we compute with them:

What it does well (keep this)

Difference tables and operators
Newton, Lagrange, divided differences
Runge phenomenon and Chebyshev points
Cubic splines from a tridiagonal solve

LimitationHow it is overcomeWhere

Slopes from tabulated data

→

Differentiate the interpolant

Lecture 19 →

Areas from tabulated data

→

Integrate the interpolant (trapezoidal, Simpson)

Lecture 20 →

Noisy data: do not pass through every point

→

Least squares and regression

Lecture 23 →

Choosing smooth, non-wiggly models in ML

→

Overfitting and regularisation

Lecture 24 →

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

17 / 20

Applications

Where this method runs in the real world

Click a card to see splines at work.

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

18 / 20

Checkpoint

Checkpoint · think, then discuss with your neighbourFor a natural cubic spline through equally spaced points (

h = 1

), what is the equation for

M_1

when

y_0, y_1, y_2 = 0, 1, 4

?

A

M_0 + 4M_1 + M_2 = 12

B

M_0 + 4M_1 + M_2 = 6

C

4M_1 = 4

D

M_0 + 2M_1 + M_2 = 12

A.

h_0M_0 + 2(h_0 + h_1)M_1 + h_1M_2 = 6\big((4 - 1) - (1 - 0)\big) = 12

, i.e.

M_0 + 4M_1 + M_2 = 12

.

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

19 / 20

Summary

Key points

Runge: one polynomial through many equally spaced points swings wildly near the ends
Chebyshev points tame it, if the points can be chosen
Splines: low-degree pieces joined smoothly; natural cubic spline from a tridiagonal system in $M_i$
Cubic spline error falls like $h^4$ ; watch jumps, noise and end conditions

Opening problem: solved

With 11 equally spaced points the single polynomial has error 1.92; the natural cubic spline has 0.022, and with 21 points 0.003, while the polynomial grows to 60.

Homework

Find the natural cubic spline through $(0, 0)$ , $(1, 1)$ , $(2, 8)$ and evaluate it at 0.5 and 1.5. Compare with $x^3$ .
Use the lab tool: for which $n$ does the equally spaced polynomial error on Runge's function first exceed 1?
Explain in words why Chebyshev points reduce the Runge phenomenon.
Show that the linear spline error is at most $\tfrac{h^2}{8}\max|f''|$ on one interval.

Next lecture

Module 5: numerical differentiation. Slopes from tabulated data, by differentiating the interpolation formulas.

Md Mahbub E Noor

Lecture 18: Splines and the Runge Phenomenon

University of Barishal

20 / 20

Spline Interpolation and the Runge Phenomenon

The problem: more data, worse curve

Today's goals

The idea in one picture

Why it happens: the node polynomial

Explore: the Runge phenomenon

Piecewise idea 1: the linear spline

Piecewise idea 2: the cubic spline

Natural cubic spline, step by step

Problem 1: a natural cubic spline by hand

Same data, two approaches: 11 points of Runge's function

One polynomial (degree 10)

Natural cubic spline

1001 points

A natural cubic spline in Python and C

Limitations shown failing

Practice problem

Cubic splines: method profile

Comparative analysis: interpolating 11 points of Runge's function

End of Module 4: what comes next

Where this method runs in the real world

🔤 Fonts and vector graphics

🤖 Robot and camera paths

🎵 Audio and speech resampling

📊 Spline features in machine learning

Checkpoint

Summary