Analyse numrique :
Approximation de fonctions
Pagora 1A
Chapitre 3
29 janvier - 1er fvrier 2013
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
1 / 64
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
2 / 64
Introduction
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
3 / 64
Introduction
Description du problme
On cherche calculer les valeurs dune fonction f (x) pour toutes
valeurs de x mais on ne connat pas explicitement f . Par exemple,
f nest connue quen certains points x exprimentaux.
f est calcule par un code numrique trs coteux.
On remplace f par une fonction simple dont lvaluation est aise (ex :
utilisation de polynmes, fonctions rationnelles, ...)
2 grandes familles dapproches.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
4 / 64
Introduction
Mthode des moindres carrs
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
5 / 64
Introduction
Interpolation polynmiale
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
6 / 64
Mthode des moindres carrs
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
7 / 64
Mthode des moindres carrs
Description du problme
De quoi dispose t-on ?
Ensemble de donnes : n points (xi , yi ), i = 1, . . . , n
Fonction modle : f (x, ) avec vecteur contenant m paramtres
Objectif : ajuster les paramtres pour que f (x, ) approche au
mieux les donnes (xi , yi ).
Comment faire ? En trouvant les paramtres minimisant
S() =
n
X
(yi f (xi , ))2
i=1
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
8 / 64
Mthode des moindres carrs
Rappel
La drive permet de connatre les variations dune fonction (croissance,
dcroissance, ...). En particulier, si la drive est nulle en un point, la
tangente est horizontale en ce point et donc la fonction ne croit ni ne
dcroit (minimum ou maximum).
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
9 / 64
Mthode des moindres carrs
Exercice introductif
On dispose de n points (xi , yi ), i = 1, . . . , n et on suppose que la fonction
modle est de la forme
f (x, 0 ) = 0
Trouver 0 minimisant
S(0 ) =
n
X
(yi f (xi , 0 ))2
i=1
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
10 / 64
Mthode des moindres carrs
Exercice introductif (correction)
Trouver 0 minimisant
S(0 ) =
n
X
(yi 0 )2
i=1
Pour cela, on calcule la drive de S
0
S (0 ) = 2
n
X
(yi 0 )
i=1
et on rsout S 0 (0 ) = 0 do
n
1X
yi
0 =
n
i=1
cest dire la moyenne des yi .
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
11 / 64
Mthode des moindres carrs
Mthode gnrale
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
12 / 64
Mthode des moindres carrs
Mthode gnrale
Rsoudre le problme gnral
La fonction modle f (x, ) se rgle par m paramtres 1 , . . . , m contenus
dans le vecteur .
Le minimum dune somme de carrs
S() =
n
X
(yi f (xi , ))2
i=1
se trouve en cherchant o le gradient de S vaut 0 soit
n
X
S()
f (xi , )
= 2
(yi f (xi , ))
=0
k
k
k = 1, . . . , m
i=1
= un systme m quations non-linaires rsoudre.
= rarement de solutions analytiques.
= mthodes numriques (ex : adaptation mthode du point fixe pour m
variables cherches).
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
13 / 64
Mthode des moindres carrs
Rgression linaire
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
14 / 64
Mthode des moindres carrs
Rgression linaire
Rgression linaire
La fonction modle est de la forme
f (x, a, b) = ax + b
On cherche le minimum de
S(a, b) =
n
X
(yi axi b)2
i=1
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
15 / 64
Mthode des moindres carrs
Rgression linaire
Recherche du minimum
Le minimum de S est atteint pour (a, b) solution du systme suivant :
n
X
=
2
xi (yi axi b) = 0
a
i=1
n
X
(yi axi b)
= 0
i=1
On note x et y les moyennes des valeurs xi et yi :
n
1X
x=
xi
n
i=1
Analyse numrique (Pagora 1A)
1X
y=
yi
n
Approximation de fonctions
i=1
29/01/13 - 1/02/13
16 / 64
Mthode des moindres carrs
Rgression linaire
Exercice
Exprimer b en fonction de a, x, y puis exprimer a.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
17 / 64
Mthode des moindres carrs
Rgression linaire
Exercice (correction)
b = y ax
Le systme est maintenant
Pn
i=1 xi [(yi y ) a(xi x)] = 0
Pn
i=1 [(yi
y ) a(xi x)]
= 0
Si on multiplie la ligne 2 par x puis on la soustraie la premire, on obtient
n
X
(xi x) [(yi y ) a(xi x)] = 0
i=1
n
X
a=
(xi x) (yi y )
i=1
n
X
i=1
Analyse numrique (Pagora 1A)
n
X
=
2
(xi x)
xi yi x y
i=1
n
X
xi2 x 2
i=1
Approximation de fonctions
29/01/13 - 1/02/13
18 / 64
Mthode des moindres carrs
Moindres carrs linaires
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
19 / 64
Mthode des moindres carrs
Moindres carrs linaires
Moindres carrs linaires : gnralisation rgression linaire
On suppose maintenant que la fonction modle est de la forme :
m
X
f (x, ) =
k k (x)
k=1
On cherche pour obtenir le minimum de S atteint lorsque
n
X
S()
f (xi , )
= 2
(yi f (xi , ))
=0
k = 1, . . . , m
k
k
i=1
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
20 / 64
Mthode des moindres carrs
Moindres carrs linaires
Cration dun systme linaire rsoudre
On a pour i = 1, . . . , n et k = 1, . . . , m :
Xik =
Posons la matrice et
X11 X12
X21 X22
X= .
..
..
.
f (xi , )
= k (xi )
k
les vecteurs
Xn1 Xn2
. . . X1m
. . . X2m
..
..
.
.
. . . Xnm
1
2
..
.
m
y=
y1
y2
..
.
yn
On a minimum de S si solution du systme
Analyse numrique (Pagora 1A)
XT X = XT y
Approximation de fonctions
29/01/13 - 1/02/13
21 / 64
Mthode des moindres carrs
Moindres carrs linaires
Exercice
tablir le systme XT X = XT y.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
22 / 64
Mthode des moindres carrs
Moindres carrs linaires
Exercice (correction)
tablir le systme XT X = XT y.
Le minimum de S est atteint pour
n
m
X
X
Xik yi
j Xij = 0
i=1
k = 1, . . . , m
j=1
Do
n
X
i=1
Xik yi =
n
X
Xik
i=1
m
X
j Xij =
j=1
m
X
j=1
n
X
!
Xik Xij
k = 1, . . . , m
i=1
Et sous forme matricielle,
Analyse numrique (Pagora 1A)
XT X = XT y
Approximation de fonctions
29/01/13 - 1/02/13
23 / 64
Mthode des moindres carrs
Prise en compte des statistiques derreur
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
24 / 64
Mthode des moindres carrs
Prise en compte des statistiques derreur
Mesures exprimentales
En gnral, les mesures faites sur yi sont entches derreur. Notons i une
estimation de lcart-type du bruit qui affecte chaque mesure.
Exemple : On cherche dterminer la valeur de la rsistance R du
composant lectronique resistance.
Pour cela, on prescrit diffrentes intensits i (nos xi ) la rsistance et on
mesure la tension U par un voltmtre. La loi dOhm nous dit que U = Ri.
Les mesures de tension (nos yi ) sont entches derreur du fait de la
prcision du voltmtre (on a par exemple i = 0.05V ).
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
25 / 64
Mthode des moindres carrs
Prise en compte des statistiques derreur
Prise en compte des incertitudes
Au lieu de chercher minimiser la quantit
S() =
n
X
(yi f (xi , ))2
i=1
on va chercher minimiser
n
n
X
yi f (xi , ) 2 X
=
wi (yi f (xi , ))2
2 () =
i
i=1
Analyse numrique (Pagora 1A)
i=1
Approximation de fonctions
29/01/13 - 1/02/13
26 / 64
Mthode des moindres carrs
Prise en compte des statistiques derreur
Exercice
On dispose de n points (xi , yi ), i = 1, . . . , n et on suppose que la fonction
modle est de la forme
f (x, 0 ) = 0
Chaque mesure yi est entche dune erreur dont lcart-type est estim
i = 1wi .
Trouver 0 minimisant
2 (0 ) =
n
X
wi (yi f (xi , 0 ))2
i=1
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
27 / 64
Mthode des moindres carrs
Prise en compte des statistiques derreur
Exercice (correction)
Trouver 0 minimisant
2
(0 ) =
n
X
wi (yi f (xi , 0 ))2
i=1
La drive vaut
0
2 (0 ) = 2
n
X
wi (yi 0 )
i=1
et on rsout
0
2 (
0)
= 0, do
n
X
0 =
wi yi
i=1
n
X
wi
i=1
moyenne pondre des yi .
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
28 / 64
Interpolation polynmiale
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
29 / 64
Interpolation polynmiale
Introduction : interpolation linaire par morceaux
Exercice : on dispose de n + 1 points (xi , yi ), i = 0, . . . , n. On suppose
x0 < x1 < xn . On construit f fonction dinterpolation entre x0 et xn tel que
les points (xi , yi ) soient relis entre eux par des droites. Exprimer f
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
30 / 64
Interpolation polynmiale
Interpolation linaire par morceaux (correction)
Exercice : on dispose de n + 1 points (xi , yi ), i = 0, . . . , n. On suppose
x0 < x1 < xn . On construit f fonction dinterpolation entre x0 et xn tel que
les points (xi , yi ) soient relis entre eux par des droites. Exprimer f
f (x) =
yi+1 yi
(x xi ) + yi
xi+1 xi
Analyse numrique (Pagora 1A)
sur x [xi , xi+1 ]
Approximation de fonctions
29/01/13 - 1/02/13
31 / 64
Interpolation polynmiale
Thorie
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
32 / 64
Interpolation polynmiale
Thorie
Rgularit dune fonction
Dans la nature, la plupart des fonctions rencontres sont trs
rgulires.
On peut mesurer la rgularit dune fonction par le biais de ses
drives. Plus une fonction est diffrentiable, plus la courbe qui lui est
associe est lisse.
Le problme de linterpolation linaire par morceaux est que la
fonction dinterpolation est continue mais nest pas drivable.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
33 / 64
Interpolation polynmiale
Thorie
Interpolation polynmiale
Ide (simple) : Trouver un polynme P(x) passant par tous les points
donns (xi , yi ) donc tel que
P(xi ) = yi
i = 0, . . . , n
Degr dun polynme : P est un polynme de degr k si
P(x) = a0 + a1 x + . . . + ak x k
avec
ak 6= 0
Existence et unicit de P :
si k < n, en gnral pas de solution (moindres carrs)
si k > n, infinit de solutions
si k = n, solution unique (sous certaines conditions) => preuve ?
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
34 / 64
Interpolation polynmiale
Thorie
Rsolution dun systme linaire
On cherche un polynme P de la forme
P(x) = a0 + a1 x + . . . + an x n
tel que P(xi ) = yi pour i = 0, . . . , n.
Pour trouver les ak , il
1
1
..
.
faut rsoudre le systme linaire suivant
x0 . . . x0n
a0
y0
x1 . . . x1n
a1 y1
..
.. .. = ..
.
. . .
1 xn . . . xnn
Analyse numrique (Pagora 1A)
an
Approximation de fonctions
yn
29/01/13 - 1/02/13
35 / 64
Interpolation polynmiale
Thorie
Matrice de Vandermonde et unicit de la solution
M=
1 x0 . . . x0n
1 x1 . . . x1n
.. ..
..
. .
.
1 xn . . . xnn
Le systme admet une unique solution si et seulement si la matrice M est
inversible. Or M est une matrice de Vandermonde, elle est inversible si
Y
det(M) =
(xi xj ) 6= 0
0i<jn
Le systme admet une unique solution si et seulement si les xi ,
i = 0, . . . , n, sont deux deux disjoints.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
36 / 64
Interpolation polynmiale
Forme lagrangienne
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
37 / 64
Interpolation polynmiale
Forme lagrangienne
Comment calculer le polynme dinterpolation
La mthode consistant inverser la matrice de Vandermonde ou de
rsoudre le systme linaire est coteuse et instable numriquement
(risque dexplosions numriques artificielles).
Pour viter ces problmes, plusieurs mthodes explicites (sans
rsolution de systmes linaires) existent
elles vitent de calculer les coefficients ak du polynme P.
elles utilisent une autre reprsentation du polynme P.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
38 / 64
Interpolation polynmiale
Forme lagrangienne
Forme lagrangienne du polynme dinterpolation
On dispose dun ensemble de n + 1 points (xi , yi ), i = 0, . . . , n tel que si
i 6= j, xi 6= xj .
Linterpolation polynmiale sous forme lagrangienne not L est une
combinaison linaire
n
X
L(x) =
yj `j (x)
j=0
de polynmes de Lagrange
`j (x) =
n
Y
k=0,k6=j
x xj1 x xj+1
x xk
x x0
x xn
=
...
...
xj xk
xj x0
xj xj1 xj xj+1
xj xn
Les polynmes de Lagrange sont de degr n donc L est au maximum de
degr n.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
39 / 64
Interpolation polynmiale
Forme lagrangienne
Exemple
On dispose des points (0, 3), (2, 1), (4, 2), (9, 5).
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
40 / 64
Interpolation polynmiale
Forme lagrangienne
Exercice
Vrifier que L(xi ) = yi pour i = 0, . . . , n.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
41 / 64
Interpolation polynmiale
Forme lagrangienne
Exercice (correction)
Vrifier que L(xi ) = yi pour i = 0, . . . , n.
Pour i 6= j
`j (xi ) =
n
Y
k=0,k6=j
xi xk
xi x0
xi xi
xi xn
=
...
...
=0
xj xk
xj x0
xj xi
xj xn
et
n
Y
`j (xj ) =
k=0,k6=j
donc
L(xi ) =
n
X
xj xk
=1
xj xk
yj `j (xi ) = yi
j=0
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
42 / 64
Interpolation polynmiale
Phnomne de Runge
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
43 / 64
Interpolation polynmiale
Phnomne de Runge
Exercice introductif
On considre lensemble de points suivants
1
1
1,
, (0, 1) , 1,
26
26
Que vaut L ?
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
44 / 64
Interpolation polynmiale
Phnomne de Runge
Exercice introductif (correction)
On considre lensemble de points suivants
1
1
, (0, 1) , 1,
1,
26
26
Que vaut L ?
`0 (x) =
x(x 1)
1
1
= x2 x
2
2
2
`1 (x) = (x + 1)(x 1) = x 2 + 1
`2 (x) =
x(x + 1)
1
1
= x2 + x
2
2
2
Do
L(x) = y0 `0 (x) + y1 `1 (x) + y2 `2 (x) =
Analyse numrique (Pagora 1A)
Approximation de fonctions
25 2
x +1
26
29/01/13 - 1/02/13
45 / 64
Interpolation polynmiale
Phnomne de Runge
Phnomne de Runge
Considrons la fonction
f (x) =
1
1 + 25x 2
x [1, 1]
Runge (1856 1927) a montr que si cette fonction est interpole aux
points quidistants xi entre 1 et 1
xi = 1 + (i 1)
2
n
i = 0, . . . , n
par un polynme Pn de degr n alors
lim
max |f (x) Pn (x)| =
n+
1x1
Lorsquon augmente le nombre de points, on constate que le polynme se
met osciller fortement entre les points xi avec une amplitude de plus en
plus grande.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
46 / 64
Interpolation polynmiale
Phnomne de Runge
Phnomne de Runge : illustration
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
47 / 64
Interpolation polynmiale
Splines
Plan
1
Introduction
Mthode des moindres carrs
Mthode gnrale
Rgression linaire
Moindres carrs linaires
Prise en compte des statistiques derreur
Interpolation polynmiale
Thorie
Forme lagrangienne
Phnomne de Runge
Splines
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
48 / 64
Interpolation polynmiale
Splines
Contourner le phnomne de Runge ?
Linterpolation polynmiale (sous la forme dcrite juste avant) nest pas
toujours bien adapte lapproximation de fonctions.
Solutions :
Choisir les points xi dinterpolation afin de minimiser les oscillations
du polynme dinterpolation.
Utiliser la mthode des moindres carrs avec k < n.
Segmenter : approcher la fonction par des polynmes par morceaux
(splines).
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
49 / 64
Interpolation polynmiale
Splines
Interpolation linaire par morceaux
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
50 / 64
Interpolation polynmiale
Splines
Spline cubique
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
51 / 64
Interpolation polynmiale
Splines
Spline cubique
On dispose dun ensemble de n + 1 points (xi , yi ), i = 0, . . . , n tel que
x0 < x1 < . . . xn .
La spline cubique S interpolant ces points concide sur chaque intervalle
[xi , xi+1 ] avec un polynme pi de degr 3 de la forme :
S(x) = pi (x) = fi + fi 0 (x xi ) +
f 000
fi 00
(x xi )2 + i (x xi )3
2!
3!
Les coefficients dterminer sont les fi , fi 0 , fi 00 et fi 000 .
On a n + 1 points dinterpolations donc n intervalles [xi , xi+1 ] et 4n
inconnues dterminer.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
52 / 64
Interpolation polynmiale
Splines
Conditions naturelles imposes
On veut naturellement que
S(xi ) = pi (xi ) = yi
S(xi+1 ) = pi (xi+1 ) = yi
i = 0, . . . , n 1
i = 0, . . . , n 1
ce qui permet dassurer la continuit de la spline cubique S.
On a donc 4n inconnues et 2n relations utilises pour les conditions
usuelles. On se sert des 2n degrs de liberts restant pour imposer que la
spline S soit C 2 .
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
53 / 64
Interpolation polynmiale
Splines
Conditions C 2
Pour que S soit C 2 sur [x0 , xn ], il faut que
0
S 0 (xi+1 ) = pi0 (xi+1 ) = pi+1
(xi+1 )
i = 0, . . . , n 2
00
S 00 (xi+1 ) = pi00 (xi+1 ) = pi+1
(xi+1 )
i = 0, . . . , n 2
On vient dimposer 2 (n 1) conditions, il reste encore 2 degrs de
libert.
En gnral, pour terminer on prend S 00 (x0 ) = p000 (x0 ) = 0 et
00 (x ) = 0 (splines naturelles) mais de nombreux autres choix
S 00 (xn ) = pn1
n
sont possibles.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
54 / 64
Interpolation polynmiale
Splines
Illustration
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
55 / 64
Interpolation polynmiale
Splines
Exercice : comment valuer les coefficients fi , fi 0 , fi 00 et fi 000
Exprimer pi (x), pi0 (x) et pi00 (x) en fonction des fi , fi 0 , fi 00 et fi 000 .
Montrer partir de la condition pi (xi ) = yi que
fi = yi
i = 0, . . . , n 1
Notons hi = xi+1 xi pour i = 0, . . . , n 1 et f [xi , xi+1 ] =
Montrer partir de la condition pi (xi+1 ) = yi+1 que
fi 0 = f [xi , xi+1 ]
Analyse numrique (Pagora 1A)
fi 00
f 000
hi i hi2
2
6
Approximation de fonctions
yi +1 yi
.
hi
i = 0, . . . , n 1
29/01/13 - 1/02/13
56 / 64
Interpolation polynmiale
Splines
Exercice : comment valuer les coefficients fi , fi 0 , fi 00 et fi 000
4
00 (x
Montrer partir de la condition pi00 (xi+1 ) = pi+1
i+1 ) que
fi 000 =
00 f 00
fi+1
i
hi
i = 0, . . . , n 2
00 (x ). On a donc f 000 =
On pose fn00 = pn1
n
n1
1
1 00
fi 0 = f [xi , xi+1 ] hi fi 00 hi fi+1
3
6
6
00
fn00 fn1
hn1 .
Montrer que
i = 0, . . . , n 1
0 (x
Montrer partir de la condition pi0 (xi+1 ) = pi+1
i+1 ) que
00
00
hi fi 00 + 2(hi + hi+1 )fi+1
+ hi+1 fi+2
= 6(f [xi+1 , xi+2 ] f [xi , xi+1 ])
pour i = 0, . . . , n 2.
Il ne reste plus qu imposer f000 et fn00 pour obtenir tous les coefficients.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
57 / 64
Interpolation polynmiale
Splines
Rsum construction spline cubique (cas splines naturelles)
But : dterminer les 4n coefficients : fi , fi 0 , fi 00 et fi 000 , i = 0, . . . , n 1.
Cas splines naturelles, f000 = fn00 = 0. Pour obtenir les fi 00 il faut
rsoudre le systme suivant :
f 00
2(h0 + h1 )
h1
0
...
1
f200
h1
2(h1 + h2 )
h2
0
.
..
0
hn3
2(hn3 + hn2 )
hn2
00
...
0
hn2
2(hn2 + hn1 )
fn1
3(f [x1 , x2 ] f [x0 , x1 ])
3(f [x2 , x3 ] f [x1 , x2 ])
..
.
3(f [xn1 , xn ] f [xn2 , xn1 ])
La matrice est creuse, le systme est facile rsoudre numriquement.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
58 / 64
Interpolation polynmiale
Splines
Rsum construction spline cubique (cas splines naturelles)
On a automatiquement fi = yi pour i = 0, . . . , n 1.
On calcule les fi 0 et fi 000 partir des formules
1 00
1
fi 0 = f [xi , xi+1 ] hi fi 00 hi fi+1
3
6
fi 000 =
00 f 00
fi+1
i
hi
i = 0, . . . , n 1
i = 0, . . . , n 1
et on obtient la fonction C 2 spline cubique S tel que S(xi ) = yi
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
59 / 64
Interpolation polynmiale
Splines
Exercice : correction
1
Exprimer pi (x), pi0 (x) et pi00 (x) en fonction des fi , fi 0 , fi 00 et fi 000 .
pi (x) = fi + fi 0 (x xi ) +
fi 00
f 000
(x xi )2 + i (x xi )3
2
6
pi0 (x) = fi 0 + fi 00 (x xi ) +
fi 000
(x xi )2
2
pi00 (x) = fi 00 + fi 000 (x xi )
2
Montrer partir de la condition pi (xi ) = yi que
fi = yi
i = 0, . . . , n 1
fi 00
f 000
(xi xi )2 + i (xi xi )3 = fi
2
6
pi (xi ) = yi = fi = yi
pi (xi ) = fi + fi 0 (xi xi ) +
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
60 / 64
Interpolation polynmiale
Splines
Exercice : correction
Notons hi = xi+1 xi pour i = 0, . . . , n 1 et f [xi , xi+1 ] =
Montrer partir de la condition pi (xi+1 ) = yi+1 que
fi 0 = f [xi , xi+1 ]
f 000
fi 00
hi i hi2
2
6
yi +1 yi
.
hi
i = 0, . . . , n 1
f 00
f 000
pi (xi+1 ) = fi +fi 0 hi + i hi2 + i hi3 = yi+1
|{z}
2
6
=yi
fi 0 hi = yi+1 yi
fi 00 2 fi 000 3
h
h
2 i
6 i
En divisant par hi , on trouve le rsultat.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
61 / 64
Interpolation polynmiale
Splines
Exercice : correction
00 (x
Montrer partir de la condition pi00 (xi+1 ) = pi+1
i+1 ) que
fi 000 =
00 f 00
fi+1
i
hi
i = 0, . . . , n 2
00
00
pi00 (xi+1 ) = fi 00 + fi 000 hi = fi+1
= pi+1
(xi+1 )
En divisant par hi , on trouve le rsultat.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
62 / 64
Interpolation polynmiale
Splines
Exercice : correction
00 (x ). On a donc f 000 =
On pose fn00 = pn1
n
n1
1 00
1
fi 0 = f [xi , xi+1 ] hi fi 00 hi fi+1
3
6
fi 0 = f [xi , xi+1 ]
00
fn00 fn1
hn1 .
Montrer que
i = 0, . . . , n 1
f 00 fi 00
fi 00
f 000
f 00
hi i hi2 = f [xi , xi+1 ] i hi i+1
hi
2
6
2
6
Do le rsultat.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
63 / 64
Interpolation polynmiale
Splines
Exercice : correction
6
0 (x
Montrer partir de la condition pi0 (xi+1 ) = pi+1
i+1 ) que
00
00
hi fi 00 + 2(hi + hi+1 )fi+1
+ hi+1 fi+2
= 6(f [xi+1 , xi+2 ] f [xi , xi+1 ])
pour i = 0, . . . , n 2.
pi0 (xi+1 ) = fi 0 + fi 00 hi +
fi 000 2
0
= pi+1 (xi+1 )
h = fi+1
2 i
f 00 fi 00
1
1 00
f [xi , xi+1 ] hi fi 00 hi fi+1
+ fi 00 hi + i+1
hi
3
6
2
1
1
00
00
= f [xi+1 , xi+2 ] hi+1 fi+1
hi+1 fi+2
3
6
En simplifiant, on vrifie le rsultat.
Analyse numrique (Pagora 1A)
Approximation de fonctions
29/01/13 - 1/02/13
64 / 64
