Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Lecture on Numerical Analysis
Dr.-Ing. Michael Dumbser
M. Dumbser
1/9
15 / 09 / 2008
Analisi Numerica
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
Interpolation
f
•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.
f1
f3
f0
f2
pn(x)
• Interpolating function pn(x)
(usually a polynomial)
• Interpolated function value
x
M. Dumbser
2/9
x
x
0
1
x
x
x
2
3
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
Polynomial Interpolation
The interpolation polynomial pn(x) must satisfy the following properties:
(1) pn(x) is from the space Pn of polynomials with maximal degree n
(2) pn(xi)=fi.
1.
Direct approach: pn(x) = a0 + a1x + a2x2 + a3x3 + … + anxn = S ajxj. This satisfies (1).
Using (2) leads to a linear equation system to be solved for the ai
2.
Lagrange interpolation: pn(x) = S fj Lj(x) with the special Lagrangian interpolation
polynomials
Li ( x ) 
x  x0 x  x1 x  xi 1 x  xi 1 x  xn 1 x  xn 
xi  x0 xi  x1 xi  xi 1 xi  xi 1 xi  xn 1 xi  xn 
No linear equation system must be solved (formally, the matrix of the
corresponding linear system is the identity matrix, so one obtains directly ai=fi).
3.
Newton interpolation:
 j 1

pn ( x )   a j   ( x  xk ) 
j 0
 k 0

n
pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + … + an(x-x0)(x-x1)…(x-xn-1)
M. Dumbser
3/9
The system matrix is a lower triangular matrix, which means the linear system
for the aj can be solved very efficiently.
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
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
4/9
Analisi Numerica
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
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 fi to be interpolated by the interpolation
polynomial pn(x) satisfy
(1) f(xi)=fi.
Then the approximation error f(x) - pn(x) made by the interpolation polynomial
pn(x) is given by:
f ( n1) ( ( x))
f ( x)  pn ( x )  ( x) 
(n  1)!
n
( x )   ( x  x j )
j 0
Where  is a value from the smallest interval I=[x0,x1,…,xn,x] containing all xi and x.
Remarks:
• The value for  depends on the position x.
• For values of x that are not contained in the interval [x0,x1,…xn], i.e. for
extrapolation problems, the error grows very quickly. This can be verified
quickly looking at (x).
M. Dumbser
5/9
• The interpolation error is connected to the (n+1)-th derivative of the
generating function f(x)
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
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
f ( x) 
1
1  25 x 2
x   1,1
Observation: increaslingly severe
oscillations of the interpolation
polynomial at the boundaries
of the interpolation interval.
polynomial degree
n=4
M. Dumbser
6/9
polynomial degree
n=8
polynomial degree
n = 12
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
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]:
n
S ( x )   Si ( x )
Usually, the following boundary
conditions are enforced:
i 1
Si ( x)  P3
Si ( xi 1 )  f i 1 , Si ( xi )  f i
Si ( x)  0 if
Si' ( xi )  Si'1 ( xi )
Si'' ( xi )  Si''1 ( xi )
M. Dumbser
7/9
x  [ xi 1 , xi ]
S '' ( a )  S '' ( b )  0
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
Spline Interpolation
f
Si-1(x)
Si(x)
Si+1(x)
Di
x
x
x
x
0
1
2
xi-1
xi
xn-1
xn
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
8/9
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
Spline Interpolation
We define a measure for the total bending (curvature) of a two-times differentiable
function f(x) as follows:
   f '' ( x ) dx
b
f
2
2
a
Theorem 1:
f S  f
2
2
n
 S  2( f ( x )  S ( x )) S ( x )   ( f ( x )  S ( x )) S ( x )x 
2
b
a
xi
i 1
Using the natural boundary conditions S ( a )  S (b)  0 and the other properties of
the spline function, we immediately obtain the minimum norm property:
Theorem 2:
S  f
2
2
The proofs for both theorems are shown on the blackboard and are recommended
as an exercise at home.
M. Dumbser
9/9
i 1
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
Spline Interpolation
We define a measure for the total bending (curvature) of a two-times differentiable
function f(x):
   f '' ( x ) dx
b
f
2
2
a
Theorem 1:
f S  f
2
2
n
 S  2( f ( x )  S ( x )) S ( x )   ( f ( x )  S ( x )) S ( x )x 
2
b
a
xi
i 1
Using the natural boundary conditions S ( a )  S (b)  0 and the other properties of
the spline function, we immediately obtain the minimum norm property:
Theorem 2:
S  f
2
2
The proofs are shown on the blackboard and are recommended as an exercise at
home.
M. Dumbser
10 / 9
i 1
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
Spline Interpolation
Finally, with the method of moments, we obtain the following expression for the natural
cubic spline:
Si ( x)  M i 1
x  xi 3  M x  xi 1 3  A x  x   B
6hi
i
6hi
i
i
i
with
f i 1  f i
hi
Ai 
 M i 1  M i 
hi
6
2
h
Bi  f i  M i i
6
hi  xi 1  xi
hi 1
hi f i 1  f i f i  f i 1
 hi  hi 1 
M i 1
 Mi 

  M i 1 
6
6
hi
hi 1
 3 
Recall that the boundary conditions for the natural cubic spline are:
M. Dumbser
11 / 9
S (a)  M1  S (b)  M N 1  0
Università degli Studi di Trento
Dipartimento d‘Ingegneria Civile ed Ambientale
Dr.-Ing. Michael Dumbser
Analisi Numerica
Polynomial Interpolation
Exercise
1.
Write a Maple worksheet that interpolates a set of n+1 points (xi,fi) using the
polynomial interpolation of Lagrange.
2.
Apply the method to the function
f ( x )  exp(  x )
3.
Apply the method to the function
f ( x) 
4.
M. Dumbser
12 / 9
x  0,2
1
1  25 x 2
Discuss the results
x   1,1