M. Dumbser
Lecture on Numerical Analysis
Dr.-Ing. Michael Dumbser
15 / 09 / 2008
Interpolation
x
0x
1x
2x
3f
0f
1f
2f
3x f
x
•Set of given function values at given points. These may come e.g. from measurements made in the real world (temperature, snow thickness, rainfall) or may come from laboratory experiments.
• Interpolating function p
n(x) (usually a polynomial)
• Interpolated function value
p
n(x)
M. Dumbser 3 / 9
Polynomial Interpolation
The interpolation polynomial p
n(x) must satisfy the following properties:
(1) p
n(x) is from the space P
nof polynomials with maximal degree n (2) p
n(x
i)=f
i.
1. Direct approach: p
n(x) = a
0+ a
1x + a
2x
2+ a
3x
3+ … + a
nx
n= a
jx
j.This satisfies (1).
Using (2) leads to a linear equation system to be solved for the a
i2. Lagrange interpolation: p
n(x) = f
jL
j(x) with the special Lagrangian interpolation polynomials
No linear equation system must be solved (formally, the matrix of the
corresponding linear system is the identity matrix, so one obtains directly a
i=f
i).
3. Newton interpolation:
p
n(x) = a
0+ a
1(x-x
0) + a
2(x-x
0)(x-x
1) + … + a
n(x-x
0)(x-x
1)…(x-x
n-1)
The system matrix is a lower triangular matrix, which means the linear system for the a can be solved very efficiently.
n
j
j
k
k j
n x a x x
p
0
1
0
) (
) (
i i i i i i i i i n n i n n
i x x x x x x x x x x x x
x x x
x x
x x
x x
x x x x
L
1 1
1 1
0
1 1
1 1
) 0
(
Joseph-Louis Lagrange
Joseph-Louis Lagrange o Giuseppe Ludovico Lagrangia (* 25. January 1736 in Torino; † 10. April 1813 in Paris)
• Father (with French origin) wanted him to study law
• Lagrange learnt on his own in only one year all the knowledge about mathematics available at that time.
• With 19 professor at the Royal School of Artillery in Torino
• 1766 director of the Prussian Academy of Sciences Successor of Leonhard Euler in Berlin
• 1788 publication of the famous „Mécanique analytique“
• From 1797 professor at the Ecole Polytechnique in Paris
• Buried in the pantheon in Paris
M. Dumbser
Approximation Error of Polynomial Interpolation
Suppose there exists a so-called generating function f(x) which is (n+1)-times differentiable for which the function values f
ito be interpolated by the interpolation polynomial p
n(x) satisfy
(1) f(x
i)=f
i.
)!
1 (
)) ( ) (
( )
( )
(
) 1 (
n
x x f
x p x
f
n n
Then the approximation error f(x) - p
n(x) made by the interpolation polynomial p
n(x) is given by:
n
j
x j
x x
0
) (
)
(
Where is a value from the smallest interval I=[x
0,x
1,…,x
n,x] containing all x
iand x.
Remarks:
• The value for depends on the position x.
• For values of x that are not contained in the interval [x
0,x
1,…x
n], i.e. for extrapolation problems, the error grows very quickly. This can be verified quickly looking at (x).
• The interpolation error is connected to the (n+1)-th derivative of the
generating function f(x)
Problems with Polynomial Interpolation
For general functions f(x) the accuracy of polynomial interpolation does not increase when increasing the degree of the interpolation polynomial. It may even happen that the error increases considerably when increasing the polynomial degree.
Example of Carl Runge: Polynomial interpolation of 2
25 1
) 1
( x x
f
polynomial degree n = 4
polynomial degree n = 8
polynomial degree n = 12
Observation: increaslingly severe oscillations of the interpolation
polynomial at the boundaries of the interpolation interval.
1 , 1
x
M. Dumbser
Spline Interpolation
Motivated by the problems arising with very high order polynomial interpolation,
engineers and mathematicians developed the concept of spline interpolation. The key idea hereby is, to use piecewise polynomials defined on sub-intervals. The piecewise polynomials are connected to each other in such a manner that the function value and the first two derivatives are continuous.
Typically, cubic splines are used, consisting of piecewise polynomials of degree three.
Definition of a cubic spline interpolant on the interval I=[a,b]:
i n S i x
x S
1
) ( )
(
) ( )
(
) ( )
(
] , [
if 0 ) (
) ( ,
) (
) (
'' 1 ''
' 1 '
1 1
1 3
i i
i i
i i
i i
i i
i
i i
i i
i i i
x S
x S
x S
x S
x x
x x
S
f x
S f
x S
P x
S
Usually, the following boundary conditions are enforced:
0 ) ( )
( ''
'' a S b
S
Spline Interpolation
x
0x
2x
n-1x
nx f
x
1x
i-1x
i
iS
i(x)
S
i+1(x) S
i-1(x)
Historically, numerical spline interpolation was first developed by engineers. It was inspired by a tool commonly used in naval engineering. The tool consists in a bar that was fixed on the given points by nails and which then bends (deforms) according to these boundary conditions.
In fact, this property of the bar is mathematically mimicked by the spline
interpolation functions via the so-called minimum norm property.
M. Dumbser
Spline Interpolation
Theorem 1:
n
i
x x b
a f x S x S x
iix S x S x
f S
f S
f
1 2
2 2
)
1( )) ( )
( ( )
( )) ( )
( ( 2
We define a measure for the total bending (curvature) of a two-times differentiable function f(x) as follows:
0 ) ( )
(
a S b S
b
a
dx x
f
f 2 '' ( ) 2
Theorem 2:
2
2 f
S
Using the natural boundary conditions and the other properties of the spline function, we immediately obtain the minimum norm property:
The proofs for both theorems are shown on the blackboard and are recommended
as an exercise at home.
Spline Interpolation
Theorem 1:
n
i
x x b
a f x S x S x
iix S x S x
f S
f S
f
1 2
2 2
)
1( )) ( )
( ( )
( )) ( )
( ( 2
We define a measure for the total bending (curvature) of a two-times differentiable function f(x):
0 ) ( )
(
a S b S
b
a
dx x
f
f 2 '' ( ) 2
Theorem 2:
2
2 f
S
Using the natural boundary conditions and the other properties of the spline function, we immediately obtain the minimum norm property:
The proofs are shown on the blackboard and are recommended as an exercise at
home.
M. Dumbser
