Horner, Taylor, et la translation qui dépouille

Exercice de TD · niveau 2 · mathématiques (PTSI), chapitre 10 — Polynômes · D. Dérivation, Taylor, multiplicités

Énoncé

Soit $P = a_{n} X^{n} + \dots + a_{1} X + a_{0} \in K [X]$ , avec $n \geq 1$ et $a_{n} \neq = 0$ , et soit $c \in K$ .

a) (Schéma de Horner.) On pose $b_{n} = a_{n}$ et $b_{k} = c b_{k + 1} + a_{k}$ pour $k = n - 1, \dots, 0$ . Montrer que $P = (X - c) Q + b_{0}$ avec $Q = b_{n} X^{n - 1} + \dots + b_{2} X + b_{1}$ ; en déduire que $P (c) = b_{0}$ , obtenu avec $n$ multiplications.

b) Montrer que $P^{'} (c) = Q (c)$ : une seconde passe de Horner, sur $Q$ , donne $P^{'} (c)$ .

c) On divise $Q$ par $X - c$ , puis le nouveau quotient par $X - c$ , et ainsi de suite ; on note $r_{0} = P (c), r_{1}, \dots, r_{n - 1}$ les restes successifs et $r_{n}$ le dernier quotient, qui est constant. Montrer que $P = \sum_{k = 0}^{n} r_{k} (X - c)^{k}$ , puis que $r_{k} = \frac{P ^{(k)} ( c )}{k !}$ : la formule de Taylor en $c$ est une suite de divisions par $X - c$ . Combien de multiplications coûte ce changement d'origine ?

d) Montrer que le coefficient de $Y^{n - 1}$ dans $P (Y + c)$ est $n a_{n} c + a_{n - 1}$ ; en déduire l'unique $c$ qui l'annule, et l'interpréter à l'aide de la somme des racines lorsque $P$ est scindé. Application : calculer $P (Y + 2)$ pour $P = X^{3} - 6 X^{2} + 11 X - 6$ par la méthode du c), et en déduire les racines de $P$ .

Corrigé

Ce qu'on a le droit d'utiliser. La division euclidienne et son unicité, la méthode de Horner, la dérivée d'un produit, la formule de Taylor et l'unicité de l'écriture $P = \sum c_{k} (X - c)^{k}$ (établie dans la démonstration du cours), la somme des racines d'un polynôme scindé. La stratégie : prendre au sérieux le « bonus » du cours — Horner évalue et divise — et l'itérer.

a) Horner divise. Développons : $(X - c) Q = \sum_{k = 1}^{n} b_{k} X^{k} - \sum_{k = 0}^{n - 1} c b_{k + 1} X^{k}$ . Le coefficient de $X^{n}$ est $b_{n} = a_{n}$ ; pour $1 \leq k \leq n - 1$ , celui de $X^{k}$ est $b_{k} - c b_{k + 1} = a_{k}$ ; le coefficient constant est $- c b_{1} = a_{0} - b_{0}$ . Donc $(X - c) Q + b_{0} = P$ — c'est la division euclidienne par $X - c$ , par unicité —, et en $c$ , $P (c) = b_{0}$ , chaque étape $b_{k} = c b_{k + 1} + a_{k}$ coûtant une multiplication.

b) La dérivée par une seconde passe. En dérivant $P = (X - c) Q + b_{0}$ , $P^{'} = Q + (X - c) Q^{'}$ , et en $c$ , $P^{'} (c) = Q (c)$ . Exemple : pour $P = 2 X^{3} - 3 X^{2} + X - 5$ et $c = 2$ , la première passe donne $2$ , puis $2 \times 2 - 3 = 1$ , puis $1 \times 2 + 1 = 3$ , puis $3 \times 2 - 5 = 1$ : $P (2) = 1$ et $Q = 2 X^{2} + X + 3$ ; la seconde passe donne $2$ , puis $5$ , puis $13$ : $P^{'} (2) = 13$ . Contrôle : $P^{'} = 6 X^{2} - 6 X + 1$ vaut bien $24 - 12 + 1 = 13$ en $2$ .

c) Taylor par divisions successives. Notons $Q_{0} = P$ et $Q_{k} = (X - c) Q_{k + 1} + r_{k}$ la division de $Q_{k}$ par $X - c$ ; chaque division abaisse le degré d'un, et $Q_{n}$ est la constante $r_{n} = a_{n}$ . En remontant, $P = r_{0} + (X - c) Q_{1} = r_{0} + (X - c) (r_{1} + (X - c) Q_{2}) = \dots = k = 0 \sum n r_{k} (X - c)^{k} .$ Or l'écriture d'un polynôme de degré $n$ sous la forme $\sum_{k = 0}^{n} c_{k} (X - c)^{k}$ est unique, et la formule de Taylor en donne les coefficients, $\frac{P ^{(k)} ( c )}{k !}$ : $r_{k} = \frac{P ^{(k)} ( c )}{k !}$ . Le coût : diviser un polynôme de degré $d$ par $X - c$ coûte $d$ multiplications, et les degrés successifs sont $n, n - 1, \dots, 1$ , soit $\frac{n ( n + 1 )}{2}$ multiplications — sans calculer une seule dérivée.

d) La translation qui dépouille. Dans $P (Y + c) = \sum_{k} a_{k} (Y + c)^{k}$ , seuls les termes $k = n$ et $k = n - 1$ contiennent $Y^{n - 1}$ : $a_{n} (Y + c)^{n}$ en apporte $n a_{n} c$ (binôme, « $n - 1$ parmi $n$ » vaut $n$ ) et $a_{n - 1} (Y + c)^{n - 1}$ en apporte $a_{n - 1}$ . Le coefficient de $Y^{n - 1}$ est donc $n a_{n} c + a_{n - 1}$ , nul pour l'unique valeur $c = - \frac{a _{n - 1}}{n a _{n}}$ . Si $P$ est scindé, la somme de ses racines vaut $- \frac{a _{n - 1}}{a _{n}}$ : $c$ est la moyenne des racines, et translater l'origine au barycentre des racines tue le terme de degré $n - 1$ . Application : $c = \frac{6}{3} = 2$ , et l'on divise successivement par $X - 2$ :

les coefficients $1, - 6, 11, - 6$ donnent $1$ , puis $- 4$ , puis $3$ , puis $0$ : $r_{0} = 0$ , quotient $X^{2} - 4 X + 3$ ;
ce quotient donne $1$ , puis $- 2$ , puis $- 1$ : $r_{1} = - 1$ , quotient $X - 2$ ;
ce quotient donne $1$ , puis $0$ : $r_{2} = 0$ , et $r_{3} = 1$ .

Donc $P (Y + 2) = Y^{3} - Y = Y (Y - 1) (Y + 1)$ , et les racines de $P$ sont $X = Y + 2 \in {1, 2, 3}$ , de moyenne $2$ ; on vérifie que $(X - 1) (X - 2) (X - 3) = X^{3} - 6 X^{2} + 11 X - 6$ .

Le point délicat. Au c), $r_{k} = \frac{P ^{(k)} ( c )}{k !}$ ne vient pas d'un calcul de dérivées mais de l'unicité de l'écriture en puissances de $X - c$ : deux méthodes qui produisent une telle écriture produisent la même.

Ce que l'exercice installe. La formule de Taylor d'un polynôme est une suite de divisions par $X - c$ . C'est le calcul de Newton en 1669 sur $x^{3} - 2 x - 5 = 0$ : il pose $x = 2 + p$ , trouve par ces divisions $p^{3} + 6 p^{2} + 10 p - 1 = 0$ , néglige $p^{2}$ et $p^{3}$ devant $10 p$ , obtient $p \approx 0, 1$ , et recommence — la racine vaut $2, 0945514 \dots$ ; c'est le germe de la méthode de Newton, qui fera le problème du TD 8. Et la translation au barycentre ramène toute équation du troisième degré à la forme $Y^{3} + p Y + q = 0$ , celle de l'exercice suivant.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.