TP 1

Interpolation de Lagrange.

Le polynôme d’interpolation de Lagrange associés à n + 1 points (xi , yi ), i ∈ J0, nK, de R2

est par définition l’unique polynôme pn de degré au plus n tel que

pn (xi ) = yi , ∀i = 0, .., n. (1)

Illustration graphique (n = 4) : y
y = p4 (x)
y0 +
y1 +
y4 +
y3 +
y2 +
x
x0 x1 x2 x3 x4

L’objectif de ce tp est de construire des fonctions python qui permettent de calculer et d’évaluer
le polynôme d’interpolation de Lagrange associé à des points donnés (xi , yi ), i ∈ J0, nK.

Question 1 : Utilisation des matrices de Vandermonde

Le polynôme pn étant de degré au plus n, nous le cherchons, pour cette question, sous la
forme
Xn
pn (z) = ak z k , ∀z ∈ R,
k=0
où les n + 1 coefficients ak , k ∈ J0, nK, sont à déterminer de telle sorte que pn satisfasse (1).
Il est alors facile de voir que les n + 1 conditions (1) reviennent à dire que les coefficients ak
sont solutions du système linéaire suivant
1 x0 x20 . . . xn0
    
a0 y0
 1 x x2 . . . xn   a   y 
 1 1 1  1   1 
..   ..   ..  .
=
 .. ..
  
 . . .   .   . 
1 xn x2n . . . xnn an yn
La matrice de ce système linéaire est appelée matrice de Vandermonde.

1) Construire une fonction python qui prend en paramètre une suite de points x = (xi )i∈J0,nK
et renvoie la matrice de Vandermonde associée :
a) en utilisant deux boucles for : fonction vandermonde1.
b) en utilisant une seule boucle for : fonction vandermonde2.
c) * en utilisant aucune boucle for : fonction vandermonde3.
2) Tester vos fonctions avec le vecteur x = [0, 1, 2, 3]. Comparer le résultat retourné par les
différentes fonctions au résultat attendu.
3) * Comparer les temps d’exécution des fonctions vandermonde1, vandermonde2 et van-
dermonde3. Choisir un vecteur x (aléatoire) de taille 100 et chronométrer le temps nécessaire
à 200 exécutions successives de chacune des fonctions. Observez vous une différence ?
4) Construire une fonction python solvand qui prend en paramètres deux vecteurs x =
(xi )i∈J0,nK et y = (yi )i∈J0,nK , et renvoie le vecteur a = (ak )k∈J0,nK des coefficients du polynôme
d’interpolation pn .
5) Tester la fonction solvand avec les vecteurs x = [0, 1, 2, 3] et y = [1, 2, 9, 28]. Le résultat
attendu est pn (z) = 1 + z 3 .

Question 2 : Evaluation d’un polynôme.

Dans cette question, nous cherchons à évaluer, en un point z ∈ R, un polynôme p défini
par la liste de ces coefficients a = (ak )k∈J0,nK ; c’est-à-dire que nous cherchons à calculer la
valeur p(z) donnée par :
X n
p(z) = ak z k . (2)
k=0
1) Ecrire une fonction python evalp1 , basée sur la formule (2), qui prend en paramètres un
réel z et le vecteur de coefficients a = (ak )k∈J0,nK du polynôme p et renvoie la valeur p(z).
2) * Si votre fonction evalp1 utilise une boucle for, proposer une autre fonction evalp2
permettant de calculer p(z), toujours basée sur la formule (2), mais sans l’utilisation d’une
boucle.
3) * Ecrire une fonction python horner calculant p(z) en utilisant l’algorithme de Hörner
rappelé ci-dessous.
Etant donné un réel z et un polynôme p défini par le vecteur de ses coefficients a =
(ak )k∈J0,nK , l’algorithme de Hörner consiste à définir par récurrence la suite (uk )k∈J0,nK sui-
vante : 
u0 = an
uk = an−k + uk−1 z, pour 1 ⩽ k ⩽ n.
La nième itérée un contient alors la valeur p(z).
4) * Comparer les temps d’exécution des fonctions evalp1, evalp2 et horner. Choisir un
vecteur a (aléatoire) de taille 100, z = 2 et chronométrer le temps nécessaire à 200 exécution
successives de chacune des fonctions.
5) Programmer enfin une fonction evalpV qui prend en paramètre un vecteur de réels z =
(zj )j∈J1,mK et le vecteur de coefficients a = (ak )k∈J0,nK du polynôme p et renvoie le vecteur
[p(z1 ), ..., p(zm )] contenant les valeurs de p aux points zj .

Question 3 : Utilisation des différences divisées de Newton.

Le polynôme d’interpolation pn associé aux n + 1 points (xi , yi ))i∈J0,nK peut s’exprimer de
la manière suivante :
n
X
pn (z) = y0 + [y0 , y1 , ..., yj ](z − x0 )(z − x1 )...(z − xj−1 ), (3)
j=1

où les coefficients [y0 , y1 , ..., yj ], j ∈ J0, nK, appelés j ièmes différences divisées, sont définies de
façon récursive par
j=0 : [yi ] = yi , ∀i ∈ J0, nK,
[yi+1 , ..., yi+j ] − [yi , ..., yi+j−1 ]
j ∈ J1, nK : [yi , yi+1 , ..., yi+j ] = , ∀i ∈ J0, n − jK.
xi+j − xi
Il est commode de rassembler ces coefficients dans un tableau appelée table des différences
divisées :
i xi [yi ] [yi−1 , yi ] [yi−2 , yi−1 , yi ] · · · [yi−n , ..., yi−1 , yi ]
0 x0 y0
1 x1 y1 [y0 , y1 ]
2 x2 y2 [y1 , y2 ] [y0 , y1 , y2 ]
.. .. .. .. .. ..
. . . . . .
n xn yn [yn−1 , yn ] [yn−2 , yn−1 , yn ] · · · [y0 , y1 , y2 , ..., yn ]
1) Ecrire une fonction python diffdiv qui prend en paramètre deux vecteurs x et y, et renvoie
la table des différences divisées associée.
2) Ecrire ensuite une fonction python evalpV diffdiv, basée sur la formule (3), qui prend en
paramètre trois vecteurs x, y et z, et qui renvoie la liste des valeurs [pn (z1 ), ..., pn (zm )] aux
points zj du polynôme d’interpolation pn associé aux points (xi , yi ) .
3) Reprendre l’exemple de la Question 1, 5) pour tester votre fonction.
4) * Il est possible d’appliquer l’algorithme de Hörner pour évaluer l’expression (3). Comme
dans la question 2), ecrire une fonction python horner diffdiv qui prend en paramètre trois
vecteurs x, y et z, et qui renvoie la liste des valeurs [pn (z1 ), ..., pn (zm )] aux points zj du po-
lynôme d’interpolation pn associé aux points (xi , yi ), mais cette fois en appliquant l’algorithme
de Hörner.
Etant donné un réel z et le polynôme d’interpolation pn associé aux points (xi , yi ), i ∈
J0, nK, l’évaluation de pn en z par l’algorithme de Hörner consiste à définir par récurrence la
suite (vk )k∈J0,nK suivante :

v0 = [y0 , ...yn ]
vk = [y0 , ..., yn−k ] + vk−1 (z − xn−k ), pour 1 ⩽ k ⩽ n.

La nième itérée vn contient alors la valeur pn (z).

Exercices d’application.

Exercice 1 : Estimation de la vitesse d’une voiture.

On dispose de 10 mesures expérimentales obtenues en mesurant, toutes les 5 secondes, la
vitesse (en km/h) d’une voiture. Voici ces mesures :

(0, 55), (5, 60), (10, 58), (15, 54), (20, 55), (25, 60), (30, 54), (35, 57), (40, 52), (45, 49).

1) Tracer sur la même figure sur l’intervalle [0, 45] : (i) le polynôme d’interpolation aux 10
points ci-dessus, (ii) le polynôme d’interpolation aux 3 premiers points, (iii) le polynôme
d’interpolation aux 3 derniers points.
2) Comparer les estimations de la vitesse du véhicule à t = 42.5s obtenues pour les trois
approximations (i), (ii) et (iii). Laquelle vous parait la plus acceptable ?
3) Qu’obtient-on comme approximations en t = 47s ?
Exercice 2 : Phénomène de Runge.
Une question naturelle est de savoir si, quand on augmente le nombre de points d’interpo-
lation (et donc le degré du polynôme), on approche de mieux en mieux la fonction interpolée.
1
Soit f la fonction définie sur [−5, 5], par f (x) = .
1 + x2
1) Points équirépartis. Pour n ∈ N, on définit les points xj = −5 + 10 j/n pour j ∈ J0, nK. On
cherche le polynôme pn de degré au plus n qui interpole la fonction f aux points (xj )j∈J0,nK .
a) Tracer la courbe représentative de la fonction f sur l’intervalle [−5, 5].
b) Ajouter sur la même figure, les courbes représentative de p6 , p10 , p15 , puis p20 et p40 .
Que remarquez-vous ?

2) * Points de Tchebychev. Pour n ∈ N, nous definissons maintenant

xj = 5 cos(π(2j + 1)/(2n + 2)) avec j ∈ J0, nK.

Reprendre les questions 1) a) et b) avec les polynômes interpolateurs en ces points. Commenter.

Exercice 3 : * Influence des erreurs d’arrondis.

On interpole la fonction f , définie pour x ∈ [−1, 1] par f (x) = sin(2πx), avec 17 noeuds
équirépartis (xi )i∈[0,16] sur [−1, 1].
1) A partir des f (xi ), génerer des données aléatoirement perturbées f˜i telles que

max |f (xi ) − f˜i | ⩽ 9.5 ∗ 10−4 .

i∈[0,16]

2) Tracer, sur la même figure, les courbes représentatives des polynômes d’interpolation cor-
respondants aux points (xi , f (xi ))i∈J0,nK d’une part et (xi , f˜i )i∈J0,nK d’autre part. Comparer et
conclure.