degré au plus k. Soit q un entier tel que 0qk, q =i et q =j . On a U (x q )=y q =V (x q ), donc
P (x q ) =
1
x i −x j
(x q −x j )U (x q ) − (x q −x i )V (x q )
=
1
x i −x j
x q − x j − x q + x i )y q = y q
On a aussi
P (x i ) =
1
x i −x j
(x i −x j )U (x i ) − (x i −x i )V (x i )
= U (x i ) = y i
et de même P (x j ) = y j .
Méthode. Supposons qu’on a calculé le polynôme P 0,1 (interpolation en x 0 , x 1 ) et
le polynôme P 1,2 (interpolation en x 1 , x 2 ). D’après la formule ci-dessus, le polynôme
d’interpolation en x 0 , x 1 , x 2 est P 0,1,2 =
1
x 2 −x 0
(x−x 0 )P 1,2 − (x−x 2 )P 0,1
.
Afin d’éviter des indices trop compliqués, posons Q i,0 = y i et
Q i,d le polynôme d’interpolation aux d+1 points x i−d , x i−d+1 , . . . , x i , si i d 1.
Supposons qu’on ait calculé tous les polynômes Q i,1 pour i 1, c’est-à-dire tous
les polynômes d’interpolation en deux points consécutifs x i−1 , x i . Alors d’après la
formule, le polynôme d’interpolation en trois points consécutifs x i−2 , x i−1 , x i est
Q i,2 =
1
x i −x i−2
(x−x i−2 )Q i,1 − (x−x i )Q i−1,1
(on a appliqué la formule (∗) en choisissant les points extrêmes x i−2 et x i parmi
les trois points x i−2 , x i−1 , x i .)
Le polynôme Q i,3 d’interpolation en quatre points consécutifs x i−3 ,x i−2 ,x i−1 ,x i s’exprime maintenant au moyen des polynômes d’interpolation en x i−2 , x i−1 , x i et en
x i−3 , x i−2 , x i−1 , c’est-à-dire au moyen de Q i,2 et Q i−1,2 . De manière générale, si l’on
connaît tous les polynômes Q i,d−1 , alors
Q i,d =
1
x i −x i−d
(x−x i−d )Q i,d−1 − (x−x i )Q i−1,d−1
Avec notre définition Q i,0 = y i , cette égalité est encore vraie pour d = 1. On peut
ainsi calculer de proche en proche Q n,n qui est le polynôme d’interpolation aux
points x 0 , x 1 , . . . , x n , c’est-à-dire le polynôme cherché.
Algorithme de Neuville
initialisation :
variable x
nombres x 0 , x 1 , . . . , x n deux à deux différents
nombres y 0 , y 1 , . . . , y n
Q i,0 ← y i pour 0 i n
boucle : pour i = 1, 2, . . . n, faire
pour d = 1, 2 . . . , i : Q i,d ←
1
x i −x i−d
(x−x i−d )Q i,d−1 − (x−x i )Q i−1,d−1
fin : Q n,n est le polynôme d’interpolation pour les points (x i , y i ).
346 – INTERPOLATION POLYNOMIALE
P (x q ) =
1
x i −x j
(x q −x j )U (x q ) − (x q −x i )V (x q )
=
1
x i −x j
x q − x j − x q + x i )y q = y q
On a aussi
P (x i ) =
1
x i −x j
(x i −x j )U (x i ) − (x i −x i )V (x i )
= U (x i ) = y i
et de même P (x j ) = y j .
Méthode. Supposons qu’on a calculé le polynôme P 0,1 (interpolation en x 0 , x 1 ) et
le polynôme P 1,2 (interpolation en x 1 , x 2 ). D’après la formule ci-dessus, le polynôme
d’interpolation en x 0 , x 1 , x 2 est P 0,1,2 =
1
x 2 −x 0
(x−x 0 )P 1,2 − (x−x 2 )P 0,1
.
Afin d’éviter des indices trop compliqués, posons Q i,0 = y i et
Q i,d le polynôme d’interpolation aux d+1 points x i−d , x i−d+1 , . . . , x i , si i d 1.
Supposons qu’on ait calculé tous les polynômes Q i,1 pour i 1, c’est-à-dire tous
les polynômes d’interpolation en deux points consécutifs x i−1 , x i . Alors d’après la
formule, le polynôme d’interpolation en trois points consécutifs x i−2 , x i−1 , x i est
Q i,2 =
1
x i −x i−2
(x−x i−2 )Q i,1 − (x−x i )Q i−1,1
(on a appliqué la formule (∗) en choisissant les points extrêmes x i−2 et x i parmi
les trois points x i−2 , x i−1 , x i .)
Le polynôme Q i,3 d’interpolation en quatre points consécutifs x i−3 ,x i−2 ,x i−1 ,x i s’exprime maintenant au moyen des polynômes d’interpolation en x i−2 , x i−1 , x i et en
x i−3 , x i−2 , x i−1 , c’est-à-dire au moyen de Q i,2 et Q i−1,2 . De manière générale, si l’on
connaît tous les polynômes Q i,d−1 , alors
Q i,d =
1
x i −x i−d
(x−x i−d )Q i,d−1 − (x−x i )Q i−1,d−1
Avec notre définition Q i,0 = y i , cette égalité est encore vraie pour d = 1. On peut
ainsi calculer de proche en proche Q n,n qui est le polynôme d’interpolation aux
points x 0 , x 1 , . . . , x n , c’est-à-dire le polynôme cherché.
Algorithme de Neuville
initialisation :
variable x
nombres x 0 , x 1 , . . . , x n deux à deux différents
nombres y 0 , y 1 , . . . , y n
Q i,0 ← y i pour 0 i n
boucle : pour i = 1, 2, . . . n, faire
pour d = 1, 2 . . . , i : Q i,d ←
1
x i −x i−d
(x−x i−d )Q i,d−1 − (x−x i )Q i−1,d−1
fin : Q n,n est le polynôme d’interpolation pour les points (x i , y i ).
346 – INTERPOLATION POLYNOMIALE