Travaux Dirigés Polynômes no1
Cours de Combinatoire et Calcul algébrique
—Master MPRI—
Interpolation / Différences finies / Polynômes de Newton
La méthode des différences finies permet entre autre de calculer itérativement les valeurs
prises par un polynôme sur les entiers sans faire aucune multiplication après un pré-calcul.
Cette méthode est également très utilisé en calcul numérique pour calculer des approxima-
tions des dérivées.
Pour n + 1 couples (xi , yi ), on cherche une fonction Φ telle que Φ(xi ) = yi pour 0 ≤ i ≤ n. Dans le
cas de l’interpolation polynomiale, on cherche la fonction Φ sous la forme d’un polynôme. On ramène
donc le problème à chercher un polynôme P de degré n tel que P (xi ) = yi pour 0 ≤ i ≤ n.
1 Interpolation de Lagrange
x Exercice 1. (Existence et unicité)
Montrer qu’étant donné n + 1 couples distincts (x0 , y0 ), . . . , (xn , yn ) tels que xi 6= xj il existe un
unique polynôme P de degré n tel que P (xi ) = yi pour 0 ≤ i ≤ n. On admettra la formule suivante
qui donne le déterminant de Vandermonde :
1 x0 x20 . . . xn0
1 x1 x21 . . . xn1 Y
.. .. .. = (xi − xj ) (1)
. . . i>j
1 xn x2n . . . xnn
Application : Calculer le polynôme interpolant en remplaçant les coordonnées des points dans
l’expression du polynôme et résoudre le système linéaire : Trouver le polynôme interpolant une fonction
passant par les points (−1, 2), (1, 4), (3, 2) et (5, 1).
x Exercice 2. (Deuxième méthode : méthode de Lagrange)
Le polynôme interpolateur de Lagrange est de la forme
n
X
Π(x) := yi Li (x) (2)
i=0
où les
n
Y x − xj
Li (x) := . (3)
xi − xj
j=0, j6=i
sont appelés polynômes caractéristiques de Lagrange.
1. Montrer que Li (xi ) = 1 et Li (xk ) = 0 si i 6= k.
2. En déduire que pour n + 1 couples distincts (x0 , y0 ), . . . , (xn , yn ), le polynôme de Lagrange
réalise bien une interpolation.
3. Calculer le polynôme interpolant de la fonction passant par les points
(−1, 3), (0, 1), (1, 2), (3, −1) et (4, −5).
1
2 Différences finies
Soit P (X) un polynôme. L’opérateur de différence finie noté ∆ agit sur le polynôme P (X) par
∆P (X) := P (X + 1) − P (X) . (4)
x Exercice 3. Quelques propriétés de l’opérateur ∆
1. Soit Q(X) := X 3 + 2X 2 + X + 2. Calculer ∆Q(X).
2. Montrer que ∆ est linéaire, c’est-à-dire que si a et b sont des constantes et si P (X) et Q(X)
des polynômes, alors
∆(aP (X) + bQ(X)) = a∆P (X) + b∆Q(x) . (5)
3. Montrer que pour deux polynômes P et Q, on a
∆(P (X)Q(X)) = Q(X + 1)∆P (X) + P (X)∆Q(X) . (6)
x Exercice 4. Itération de l’opérateur ∆
On définit par récurrence ∆0 P (X) := P (X) et ∆n+1 P (X) := ∆(∆n P (X)) pour tout n ≥ 0.
4. En reprenant le polynôme Q(X) de l’exercice 1, Calculer ∆n Q(X) pour tout les n ≥ 0. Que
remarquez vous ?
Pd
5. Montrer généralement, que si P (X) := i=0 ai X i est un polynôme de degré d (i.e. : ad 6= 0),
alors ∆P (X) est un polynôme de degré d − 1. Quel est le coefficient dominant de ∆P (X) ?
6. En déduire que ∆d P est un polynôme constant égal à d!ad .
x Exercice 5. Calcul des valeurs d’un polynôme sur les entiers
7. Soit P = aX + b un polynôme de degré 1 donné par P (0) et P (1). Quel est le polynôme ∆P ?
Est-il possible sans calculer P (X) de calculer P (2), P (3), . . . ?
8. Si P = aX 2 +bX+c est un polynôme de degré 2 donné par P (0), P (1) et P (2). Comment calculer
∆2 P ? Comment calculer ∆P (2), ∆P (3), ∆P (4) . . . ? Comment calculer P (3), P (4), . . . ?
9. Soit P (X) un polynôme de degré d dont on connait les valeurs en 0, 1, . . ., d. Comment calculer
sans aucune multiplication ad ?
10. Donner un algorithme qui calcule sans aucune multiplication les valeurs de P en d + 1, d + 2, . . .
x Exercice 6. Test de logique
Continuer les suites suivantes
11. U = 1, 3, 5, 7, 9, . . . ;
12. V = 1, 5, 11, 19, 29, . . . ;
13. W = 1, 9, 29, 67, 129, 221, . . . ;
14. X = 1, 13, 73, 241, 601, 1261, 2353, . . . ;
2
x Exercice 7. Polynômes de Newton
Pour tout n ≤ 0, on appelle polynôme de Newton d’ordre n le polynôme
X(X − 1)(X − 2)(X − 3) . . . (X − n + 1)
An (X) := (7)
n!
15. Quel est le degré de An (X) ?
16. Montrer que pour n > 0 on a ∆An (X) = An−1 (X).
17. Montrer que pour tout polynôme P (X) de degré d il existe un unique d+1-uplets de coefficients
(c0 , . . . cd ) tels que
Xd
P (X) = ci An (X) . (8)
i=0
18. Comment calculer efficacement les ci ?
19. En déduire un algorithme d’interpolation d’une fonction f dont on connaît les valeurs sur les
entiers 0, 1, . . ., n.
