Interpolation. Splines.

Interpolation with higher order polynomials is prone to the Runge

phenomenon.

1/27
Piecewise linear interpolation

2/27
Piecewise parabolic interpolation

3/27
Piecewise parabolic interpolation

3/27
Piecewise polynomials. Splines.

Condider a set of breakpoints on the interval x ∈ [a, b]

a = x0 ⩽ x1 ⩽ · · · ⩽ xm−1 ⩽ xm = b,

A spline function, S(x), is a

piecewise polynomial on [a, b].

▶ S(x) has degree n if the max degree of all polynomial pieces is

n.
▶ S(x) ∈ C p if S(x) and its p derivatives, S ′ (x), S ′′ (x), · · · ,
S (p) (x) are continuous on x ∈ [a, b].
4/27
 Cubic splines

Hermite form of a cubic polynomial

5/27
Piecewise cubic polynomials

Given
a = x0 < x1 < · · · < xm−1 < xm = b,

A cubic polynomial, p3,k (x), on

each interval [xk−1 , xk ], for
k = 1, · · · , m

6/27
A single interval: a linear function

Construct p1 (x) with p1 (xa ) = ya and p1 (xb ) = yb

x − xa xb − x
p1 (x) = yb + ya
h h
where h = xb − xa .

7/27
A single interval: a cubic function

Construct p3 (x) with

p3 (xa ) = ya p′3 (xa ) = sa

p3 (xb ) = yb p′3 (xb ) = sb

8/27
A single interval: a cubic function

Construct p3 (x) with

p3 (xa ) = ya p′3 (xa ) = sa

p3 (xb ) = yb p′3 (xb ) = sb

(x − xa ) (xb − x) [ ]
p3 (x) = p1 (x) + A (x − xa ) + B (xb − x)
h h

And nd A and B given sa and sb .

8/27
9/27
A single interval: a cubic function

x = xa : sa = p′3 (xa ) = m + B
x = xb : sb = p′3 (xb ) = m − A

with
yb − ya
m= .
h

So that we have an explicit form of a (unique) cubic parabola on

[xa , xb ] with given tangents (sa , sb ) and values (ya , yb ) at the edges:

(x − xa ) (xb − x) [ ]
p3 (x) = p1 (x) + (m−sb ) (x−xa )+(sa −m) (xb −x)
h h

10/27
Cubic splines

11/27
Multiple intervals: a piecewise cubic function

Given
a = x0 < x1 < · · · < xm−1 < xm = b,

use p3,k (x) on each interval

[xk−1 , xk ], for k = 1, · · · , m

(x − xa ) (xb − x) [ ]
p3 (x) = p1 (x) + (m−sb ) (x−xa )+(sa −m) (xb −x)
h h

12/27
Multiple intervals: a piecewise cubic function

continuity : by construction
p3 (x) = p1 (x) + . . .

13/27
Multiple intervals: a piecewise cubic function

continuity : by construction
p3 (x) = p1 (x) + . . .

rst derivative : use consistent tangents at internal breakpoints

⇒ S(x) ∈ C 1 on x ∈ [a, b]

13/27
Multiple intervals: a piecewise cubic function

continuity : by construction
p3 (x) = p1 (x) + . . .

rst derivative : use consistent tangents at internal breakpoints

⇒ S(x) ∈ C 1 on x ∈ [a, b]

second derivative : select internal tangents, sk , so that

p′′3,k−1 (xk ) = p′′3,k (xk )

for k = 1, · · · , m.

NB: m − 1 conditions for m + 1 tangents.

Need two more boundary conditions.
13/27
Work out second derivatives on intervals

On a single interval [xa , xb ]:

sb − m
p′′3 (x) = − 2 [(xb − x) − 2(x − xa )]
h2
sa − m
−2 [2(xb − x) − (x − xa )]
h2
Thus
sb − m sa − m
p′′3 (xa ) = −2 −4
h h
′′ sb − m sa − m
p3 (xb ) = 4 +2
h h

14/27
Match second derivatives at breakpoints

For p3,k (x), x ∈ [xk−1 , xk ], for

k = 1, · · · , m de ne

hk = xk − xk−1
yk − yk−1
mk =
hk

p′′3,k (xk ) = p′′3,k+1 (xk )

sk − mk sk−1 − mk sk+1 − mk+1 sk − mk+1

4 +2 = −2 −4
hk hk hk+1 hk+1

15/27
Cubic splines

A C 2 continuous spline interpolator with breakpoints

a = x0 < x1 < · · · < xm−1 < xm = b,

is de ned by a solution of an (almost) tridiagonal system of linear

equations
2 2 1 1 mk mk+1
sk ( + ) + sk−1 + sk+1 = 3( + ),
hk hk+1 hk hk hk hk+1
where k = 1, · · · , m − 1.

16/27
Cubic splines

A C 2 continuous spline interpolator with breakpoints

a = x0 < x1 < · · · < xm−1 < xm = b,

is de ned by a solution of an (almost) tridiagonal system of linear

equations
2 2 1 1 mk mk+1
sk ( + ) + sk−1 + sk+1 = 3( + ),
hk hk+1 hk hk hk hk+1
where k = 1, · · · , m − 1.

Need two more equations:

▶ m + 1 unknowns sk for k = 0, · · · , m
▶ m − 1 equations for k = 1, · · · , m − 1

16/27
Cubic splines: boundary conditions

“Fundamental spline” Known f ′ (a) and f ′ (b) or f ′′ (a) and f ′′ (b).

“Natural spline” Set f ′′ (a) = f ′′ (b) = 0.

“Not-a-knot” Require continuous third derivative at second and

second-to-last breakpoints.

17/27
Cubic spline interpolation: continuity

18/27
Approximation errors

Let f (x) ∈ C 4 on x ∈ [a, b] and

M4 = max |f (4) (x)|;

x∈[a,b]

Then, for an interpolating spline S3 (x) with not-a-knot or

fundamental boundary conditions,

max |f (x) − S3 (x)| ⩽ C M4 h4 ,

x∈[a,b]

where C is some constant and h = maxk |xk − xk−1 |.

However, the natural spline has the approximation error ∝ h2 .

19/27
Local piecewise interpolation

20/27
Piecewise polynomial interpolation

Given a = x0 < x1 < · · · < xm−1 < xm = b,

A cubic interpolating polynomial in the Hermite form

(x − xa ) (xb − x) [ ]
p3 (x) = p1 (x) + (m−sb ) (x−xa )+(sa −m) (xb −x)
h h

21/27
Cubic spline interpolation

▶ C 2 continuous on [a, b]
▶ Need two boundary conditions
▶ Construction is O(N )

22/27
Cubic spline interpolation

▶ C 2 continuous on [a, b]
▶ Need two boundary conditions
▶ Construction is O(N )
▶ Not guaranteed to be monotonic

May or may not need the C 2 continuity.

22/27
Local interpolating schemes

Other, local, prescriptions for sk are possible. For example,

yk+1 − yk−1
sk =
xk+1 − xk−1

Produces a local C 1 continuous interpolant.

23/27
Monotone interpolants

Outliers or sharp features in data: C 2 splines may overshoot.

Use a local scheme for sk , with weighting and clipping.

24/27
Monotone interpolants

Outliers or sharp features in data: C 2 splines may overshoot.

Use a local scheme for sk , with weighting and clipping.

Most popular schemes: Akima splines and PCHIP algorithm.

24/27
Monotone piecewise cubic interpolant: PCHIP

PCHIP algorithm
Let hk = x+1 − xk , and

mk = (yk+1 − yk )/hk

▶ if sign mk−1 ̸= sign mk , then sk = 0

▶ if mk−1 = 0 or mk = 0, then sk = 0
▶ otherwise,
w1 + w2 w1 w2
= +
sk mk−1 mk
where w1 = 2hk + hk−1 and w2 = hk + 2hk−1

25/27
Monotone piecewise cubic interpolant: PCHIP

26/27
Interpolation

▶ Lagrange interpolating polynomial

▶ Piecewise interpolators: splines
▶ Local piecewise interpolators

▶ Other forms of the interpolating polynomial: Newton, Krogh

▶ Spline curves
▶ Bezier curves
▶ B-splines, rational interpolation

▶ Smoothing splines
▶ Computer graphics, CAD, animation
▶ Image processing, computer vision
27/27