ASI 3

Méthodes numériques
pour l’ingénieur

Interpolation
f(x)

1
 Approximation de fonctions
• Soit une fonction f (inconnue explicitement)
– connue seulement en certains points x0,x1…xn
– ou évaluable par un calcul coûteux.
• Principe :
– représenter f par une fonction simple, facile à évaluer
• Problème :
– il existe une infinité de solutions !

2
1
0
-1
-2
-3
-4
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8
2
 Approximation de fonctions
• Il faut se restreindre à une famille de fonctions
– polynômes,
– exponentielles,
– fonctions trigonométriques…

-1

-2

-3

-4
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8

3
 Théorème d’approximation de Weierstrass
soit f une fonction définie et continue sur l' intervalle a, b
Alors, e  0, il existe un polynôme P( x), définit sur a, b tel que :
f ( x)  P( x)  e  x  a, b f (x)  e
f(x)+ e

P(x)
P(x)

f(x)
f (x)

f (x)  e
f(x)-e

plus e , est petit,

plus l' ordre du polynome est grand

ab ab
Interpolation :
n  1 points, n  1 contraintes, n  1 équations, n  1 inconnues : ordre n4
 Interpolation polynomiale
• Le problème : les données, la solution recherchée
 x0 , y0  f ( x0 ) ,...,  xi , yi  f ( xi ) ,...,  xi , yi  f ( xi ) 
P( x) tel que P( xi )  f ( xi ), i  0, n
• mauvaise nsolution : résoudre le système linéaire
P( x)   ai x i  Va  y V : matrice de Vandermonde
i 0

• la combinaison linéaire de polynômes est un polynôme

P( x)  y0 P0 ( x)  ...  yi Pi ( x)  yn Pn ( x)

tel que Pi ( xi )  1 et Pi ( x j )  0 ji

ainsi P ( xi )  y0 P0 ( xi )  ...  yi Pi ( xi )  yn Pn ( xi )
  
0 1 0 5
 Interpolation polynomiale : Lagrange

• Théorème
– Soient n+1 points distincts xi réels et n+1 réels yi,
il existe un unique polynôme p  Pn tel que
p(xi) = yi pour i = 0 à n
démonstration n

– Construction de p : p( x )   yi Li ( x )
i 0
x  x 
n
L (x)
j
avec Li polynôme de Lagrange i
x  x 
j 0
j i
i j

– Propriétés de Li L est un polynôme d’ordre n

• Li(xi)=1
• Li(xj)=0 (j  i)
6
 Lagrange : exemple n°1
• Exemple avec n=1
– on connaît 2 points (x0,y0) et (x1,y1)
– on cherche la droite y=ax+b (polynôme de degré 1)
qui passe par les 2 points :
• y0 = a x 0 + b a = (y0 - y1) / (x0 - x1)
y1
• y1 = a x 1 + b b = (x0 y1 - x1 y0) / (x0 - x1)
y0
y0  y1 x0 y 1  x1 y 0
– y x x0 x1
x0  x1 x0  x1
x  x1 x  x0 x  x1 x  x0
y  y0  y1  y0  y1
x0  x1 x0  x1 x0  x1 x1  x0
L0(x) L1(x)
7
 Lagrange : exemple n°2
• Exemple avec n=2
– on connaît 3 points (0,1), (2,5) et (4,17)
– polynômes de Lagrange associés :
L0 ( x ) 
 x  2 x  4 
L1 ( x ) 
x x  4 
L2 ( x ) 
x x  2 
8 4 8

0 2 4 0 2 4 0 2 4

8
 Lagrange : exemple n°2
– calcul du polynôme d'interpolation
30

25

• p(x)=L0(x) + 5 L1(x) + 17 L2(x) 20

15

10

0
-1 0 1 2 3 4 5

• en simplifiant, on trouve p(x)=x2+1

9
 Lagrange : l’algorithme

Fonction y = lagrange(x,xi,yi)
pour i  1 jusqu' à n
pour j  1 jusqu' à n, j  i;
x  xi ( j )
l l*
xi (i )  xi ( j )
fait
y  y  yi * l
fait

Complexité du calcul : n2
10
 Lagrange : exemple n°3
• Exemple avec n=2 (fonction à approcher y=ex)
– on connaît 3 points (0,1), (2,7.3891) et (4,54.5982)
– Polynôme d'interpolation
• p(x) =L0(x) + 7.3891 L1(x) + 54.5982 L2(x)
60

50

40

30

20

10

-10
-1 0 1 2 3 4 5

11
 Lagrange : exemple n°3
– Erreur d'interpolation e(x) = f(x) - p(x)
60

50

40

30

20

10

-10

-20
-1 0 1 2 3 4 5

12
 Lagrange : erreur d'interpolation
• Théorème :
– si f est n+1 dérivable sur [a,b],  x  [a,b], notons :
• I le plus petit intervalle fermé contenant x et les xi
• (x)=(x-x0)(x-x1)…(x-xn)
– alors, il existe   I tel que e x  
f    x 
( n 1 )

n  1!
– NB :  dépend de x

• Utilité = on contrôle l’erreur d’approximation donc .

la qualité de l’approximation
13
 Lagrange : choix de n
• Supposons que l'on possède un nb élevé de points pour
approcher f … faut-il tous les utiliser ?
– (calculs lourds)

• Méthode de Neville :
– on augmente progressivement n
– on calcule des Li de manière récursive
– on arrête dès que l'erreur est inférieure à un seuil
(d’ou l’utilité du calcul de l’erreur)

14
 La méthode de Neuville
• Définition
Pm1 ,m2 ,...,mk ( x) polynôme de Lagrange calculé sur
xm , ym , xm , ym ,..., xm , ym 
les k points 1 1 2 2 k k
• Théorème
x  x j P0,1,..., j 1, j 1,...,n ( x)   x  xi P0,1,...,i1,i1,...,n ( x)
P( x) 
xi  x j
• Démonstration
P( xi )  f ( xi ); P( x j )  f ( x j ) et P( xk )  f ( xk )

• Application systématique Qi , j  Pi  j ,i  j 1,...,i 1,i

x0 P0  Q0,0
x1 P1  Q1,0 P0,1  Q1,1
x2 P2  Q2,0 P1, 2  Q2,1 P0,1, 2  Q2, 2
x3 P3  Q3,0 P2,3  Q3,1 P1, 2,3  Q3, 2 P0,1, 2, 4  Q3,3 15
 L’algorithme de Neuville
Fonction y = Neuville(x,xi,yi)
pour i  1 jusqu' à n
Q(i,0)  yi (i )
fait
pour i  1 jusqu' à n
pour j  1 jusqu' à i
 x  xi (i  j ) Q(i,j  1 )   x  xi (i) Q(i  1,j  1 )
Q(i,j) 
xi (i )  xi (i  j )
fait
y  Q(n, n)
fait

Complexité du calcul : n2
16
 Interpolation polynomiale : Newton
• Polynômes de Newton :
– base = {1, (x-x0), (x-x0)(x-x1), …, (x-x0)(x-x1)…(x-xn-1)}

– on peut ré-écrire p(x) :

p(x)=a0 + a1(x-x0) + a2(x-x0)(x-x1)+…+ an(x-x0)(x-x1)…(x-xn-1)

– calcul des ak : méthode des différences divisées

17
 Newton : différences divisées
• Définition :
– Soit une fonction f dont on connaît les valeurs en des points
distincts a, b, c, …
– On appelle différence divisée d’ordre 0, 1, 2,...,n
les expressions définies par récurrence sur l’ordre k :
– k=0 f [a] = f (a)
– k=1 f [a,b] = ( f [b] - f [a] ) / ( b - a )
– k=2 f [a,b,c] = ( f [a,c] - f [a,b] ) / ( c - b )

– … f [X,a,b] = ( f [X,b] - f [X,a] ) / ( b - a )

aX, bX, ab
18
 Newton : différences divisées
• Théorèmes :
– détermination des coefficients de p(x) dans la base de
Newton :

f [x0, x1,…, xk] = ak avec k = 0 … n

– erreur d'interpolation :

e(x) = f [x0, x1,…, xn, x] (x)

19
 Newton : différences divisées
• Calcul pratique des coefficients :

a0
x0 f [x0] a1
x1 f [x1] f [x0, x1] a2
x2 f [x2] f [x1, x2] f [x0, x1, x2]
… … … ...
… … … f [xn-3, xn-2, xn-1] an
xn f [xn] f [xn-1, xn] f [xn-2, xn-1, xn] … f [x0, ..., xn]

20
 Newton : exemple
• (ex. n°2) : n=2 (0,1), (2,5) et (4,17)

a
0
0 f [x0]=1

2 f [x1]=5 f [x0, x1] a1

=(1-5)/(0-2)=2
4 f [x2]=17 f [x1, x2] f [x0, x1, x2] a2
=(5-17)/(2-4)=6 = (2-6)/(0-4)=1

p(x)=1 + 2x + x(x-2) (et on retombe sur p(x) = 1 + x2)

21
 Newton : l’algorithme
Fonction a = Newton(xi,yi)
pour i  1 jusqu' à n
F (i,0)  yi (i )
fait
pour i  1 jusqu' à n
pour j  1 jusqu' à i
F(i,j  1 )  F(i  1,j  1 )
F(i,j) 
xi (i )  xi (i  j )
fait
fait
pour i  1 jusqu' à n
a (i)  F (n, i )
fait

Complexité du calcul : n2 22
 A bas les polynômes
• Ex : y=2(1+tanh(x)) - x/10 avec 9 points
– entre les points, le polynôme fait ce qu'il veut…
et plus son degré est élevé plus il est apte à osciller !
6

-2

-4

-6
-6 -4 -2 0 2 4 6
23