084. Calculez les sommes de Newton

Cet article est organisé en trois parties.

La première désigne la définition d’une somme de Newton associée à un polynôme. La deuxième montre les relations qu’il y a entre les sommes de Newton et les coefficients dudit polynôme avec un moyen efficace de les mémoriser. La troisième partie est une démonstration de ces relations qui fait appel à la division euclidienne et à la dérivation d’un polynôme scindé.

Dans tout ce qui suit, vous désignez par $n$ un entier naturel non nul. Soient $\K$ un corps et $P$ un polynôme à coefficients dans $\K$ de degré $n.$

Première partie : définissez les sommes de Newton d’un polynôme

Il existe $n+1$ éléments de $\K\comma$ notés $a_0,\dots,a_n$ tels que :

P(X)=a_0X^n+a_1X^{n-1}+\cdots+a_{n-1}X+a_n.

Note. Contrairement à beaucoup de notations usuelles sur les polynômes, le coefficient dominant de $P$ est noté $a_0.$

Il existe un surcorps $\L$ de $\K$ dans lequel le polynôme $P$ est scindé. Le polynôme $P$ possède donc $n$ racines appartenant à $\L\comma$ certaines étant éventuellement répétées, notées $\lambda_1,\dots,\lambda_n\comma$ telles que :

P(X)=a_0(X-\lambda_1)\cdots(X-\lambda_n).

Vous définissez $n$ sommes de Newton, à partir des racines du polynôme $P\comma$ de la façon suivante :

\left\{\begin{align*} N_1 &= \lambda_1+\cdots+\lambda_n = \sum_{k=1}^n\lambda_k\\ N_2 &= \lambda_1^2+\cdots+\lambda_n^2= \sum_{k=1}^n\lambda_k^2\\ &\vdots\\ N_n &= \lambda_1^n+\cdots+\lambda_n^n=\sum_{k=1}^n\lambda_k^n. \end{align*} \right.

Autrement dit, pour tout entier $i$ appartenant à l’intervalle $\llbracket 1, n\rrbracket\comma$ vous avez :

N_i =\sum_{k=1}^n\lambda_k^i.

Note. Il est également possible de définir les sommes de Newton lorsque $i\geq n+1.$ Elles ne seront pas traitées dans cet article.

Deuxième partie : mémorisez efficacement les formules de Newton

Obtenez la relation fondamentale

Soit $k$ un élément de l’intervalle $\llbracket 1, n\rrbracket.$ Comme $\lambda_k$ est une racine du polynôme $P\comma$ vous déduisez :

a_0\lambda_k^n+a_1\lambda_k^{n-1}+\cdots+a_{n-1}\lambda_k+a_n=0.

Cette relation étant valable quel que soit $k\in\llbracket 1, n\rrbracket\comma$ vous sommez :

\begin{align*} &\sum_{k=1}^n \left(a_0\lambda_k^n+a_1\lambda_k^{n-1}+\cdots+a_{n-1}\lambda_k+a_n\right)=0\\ &a_0\sum_{k=1}^n \lambda_k^n + a_1 \sum_{k=1}^n \lambda_k^{n-1}+\cdots + a_{n-1}\sum_{k=1}^n\lambda_k + a_n \sum_{k=1}^n 1 = 0. \end{align*}

Vous obtenez ainsi la relation fondamentale :

\boxed{\left\{\begin{align*} &a_0N_n+a_1N_{n-1}+\cdots+a_{n-1}N_1+na_n=0\\ &\sum_{i=0}^{n-1} a_iN_{n-i} + na_n=0. \end{align*} \right. }

Obtenez les autres formules

Considérez le polynôme de degré $1$ qui n’utilise que les premiers coefficients du polynôme $P\comma$ en commençant par son coefficient dominant.

Posez $P_1(x) = a_0X+a_1.$ Le polynôme $P_1$ n’a qu’une seule racine $\lambda^{\prime}_1.$ Si vous appliquez la relation fondamentale avec sa somme de Newton $N^{\prime}_1 = \lambda^{\prime}_1\comma$ vous obtenez $a_0N^{\prime}_1+a_1=0.$

Ce qui est remarquable, c’est que cette relation va rester valable pour la somme $N_1$ associée au polynôme de départ $P.$ Ainsi, vous avez :

\boxed{a_0N_1+a_1=0.}

De même, pour le degré $2\comma$ vous posez $P_2(X)=a_0X^2+a_1X+a_2$ et vous supposez que ce polynôme est scindé. Notez $\lambda^{\prime}_1$ et $\lambda^{\prime}_2$ les deux racines de $P_2\comma$ posez $N^{\prime}_1 = \lambda^{\prime}_1+\lambda^{\prime}_2$ et $N^{\prime}_2 = {\lambda^{\prime}}_1^2+{\lambda^{\prime}}_2^2.$

D’après la relation fondamentale, vous avez $a_0N^{\prime}_2+a_1N^{\prime}_1+2a_2=0.$

Cette relation se transpose aussi au polynôme $P$ ce qui fournit :

\boxed{a_0N_2+a_1N_1+2a_2=0.}

En poursuivant, vous avez mémorisé les relations qu’il y a entre les diverses sommes de Newton. Précisément :

\boxed{\begin{align*} a_0N_1+a_1 &= 0\\ a_0N_2+a_1N_1+2a_2 &=0\\ a_0N_3+a_1N_2+a_2N_1+3a_3 &=0\\ \vdots & \\ a_0N_n+a_1N_{n-1}+\cdots+a_{n-1}N_1+na_n &=0. \end{align*} }

Concluez

Les formules de Newton sont au nombre de $n.$ Pour tout entier $k$ compris appartenant à l’intervalle $\llbracket 1, n\rrbracket\comma$ vous avez :

\boxed{\sum_{i=0}^{k-1} a_iN_{k-i} + ka_k=0.}

Troisième partie : démontrez les formules de Newton

Si $n=1\comma$ alors le polynôme $P$ est de degré $1.$ Il possède une seule racine qui est $\lambda_1\comma$ avec $a_0\lambda_1+a_1=0.$ Comme $N_1 = \lambda_1\comma$ le résultat est acquis.

Vous supposez dans la suite que $n\geq 2.$

À partir du polynôme $P$ défini par $P(X)=a_0X^n+a_1X^{n-1}+\cdots+a_{n-1}X+a_n\comma$ vous allez définir $n$ polynômes, notés $P_0,\dots P_{n-1}\comma$ de la façon suivante :

\left\{\begin{align*} P_0(x) &= a_0\\ P_1(x) &= a_0x+a_1\\ P_2(x) &= a_0x^2+a_1x+a_2\\ \vdots & \\ P_{n-1}(x) &= a_0x^{n-1}+a_1x^{n-2}+\cdots+a_{n-1}. \end{align*} \right.

Effectuez la division euclidienne du polynôme $P$ par $X-\lambda$

Construisez le processus sur un exemple

Supposez dans cette section uniquement que le polynôme $P$ est de degré $3\comma$ soit $P(X)=a_0X^3+a_1X^2+a_2X+a_3.$ Soit $\lambda$ un élément de $\L.$

Vous effectuez la division de $P$ par $X-\lambda\comma$ pas à pas :

\begin{align*} P(X) &= a_0X^3+a_1X^2+a_2X+a_3 \\ &=a_0X^2\times X + a_1X^2+a_2X+a_3\\ &=a_0X^2( (X-\lambda)+\lambda)+a_1X^2+a_2X+a_3\\ &=(X-\lambda)(a_0X^2) +(a_0\lambda+a_1)X^2+a_2X+a_3\\ &=(X-\lambda)(a_0X^2) +(a_0\lambda+a_1)X\times X+a_2X+a_3\\ &=(X-\lambda)(a_0X^2) +(a_0\lambda+a_1)X\times ((X-\lambda)+\lambda)+a_2X+a_3\\ &=(X-\lambda)(a_0X^2) +(a_0\lambda+a_1)X(X-\lambda) + (a_0\lambda^2+a_1\lambda) X+a_2X+a_3\\ &=(X-\lambda)(a_0X^2+(a_0\lambda+a_1)X) + (a_0\lambda^2+a_1\lambda +a_2)X+ a_3\\ &=(X-\lambda)(a_0X^2+(a_0\lambda+a_1)X) + (a_0\lambda^2+a_1\lambda +a_2) ((X-\lambda)+\lambda)+ a_3\\ &=(X-\lambda)\bigl(a_0X^2+(a_0\lambda+a_1)X+(a_0\lambda^2+a_1\lambda +a_2)\bigr)\\ &\quad + (a_0\lambda^2+a_1\lambda +a_2)\lambda+ a_3\\ &=(X-\lambda)\bigl(a_0X^2+(a_0\lambda+a_1)X+(a_0\lambda^2+a_1\lambda +a_2)\bigr) +P(\lambda)\\ &=(X-\lambda)\bigl(P_0(\lambda)X^2+P_1(\lambda)X+P_2(\lambda)\bigr) +P(\lambda).\\ \end{align*}

Note. Dans le processus, vous pouvez reconnaître la méthode de Hörner.

Effectuez la démonstration dans le cas général

Le polynôme $P$ est de degré $n\geq 2.$ Soit $\lambda$ un élément de $\L.$ L’exemple précédent suggère de définir un polynôme $Q$ de $\L[X]$ en posant :

\begin{align*} Q(X)&= \sum_{k=0}^{n-1}P_k(\lambda) X^{n-1-k}\\ &=\sum_{k=0}^{n-1}\sum_{i=0}^k a_i\lambda^{k-i}X^{n-1-k}. \end{align*}

Vous allez vérifier directement que le polynôme $Q$ est bien le quotient de la division euclidienne de $P$ par $X-\lambda.$ Vous posez $E(X)=Q(X)(X-\lambda)+P(\lambda)$ et effectuez le développement suivant :

\begin{align*} E(X) &= \left(\sum_{k=0}^{n-1}\sum_{i=0}^k a_i\lambda^{k-i}X^{n-1-k}\right)(X-\lambda)+P(\lambda)\\ &= \sum_{k=0}^{n-1}\sum_{i=0}^k a_i\lambda^{k-i}X^{n-k}\\ &\quad-\sum_{k=0}^{n-1}\sum_{i=0}^k a_i\lambda^{k+1-i}X^{n-1-k}+P(\lambda). \end{align*}

Maintenant vous isolez le terme pour $k=0$ du premier sigma et le terme pour $k=n-1$ du deuxième sigma. Ainsi :

\begin{align*} E(X) &=a_0X^n + \sum_{k=1}^{n-1}\sum_{i=0}^k a_i\lambda^{k-i}X^{n-k}-\sum_{k=0}^{n-2}\sum_{i=0}^k a_i\lambda^{k+1-i}X^{n-1-k}\\ &\qquad – \sum_{i=0}^{n-1} a_i\lambda^{n-i}+ P(\lambda). \end{align*}

Une première simplification apparaît dans le terme constant de $E(X).$ Vous obtenez :

\begin{align*} E(X) &=a_0X^n + \sum_{k=1}^{n-1}\sum_{i=0}^k a_i\lambda^{k-i}X^{n-k}\\ &\qquad-\sum_{k=0}^{n-2}\sum_{i=0}^k a_i\lambda^{k+1-i}X^{n-1-k}+a_n. \end{align*}

Maintenant, dans le premier sigma qui est double, vous allez isoler $i=k$ du reste. Cela fournit :

\begin{align*} E(X) &=a_0X^n + \sum_{k=1}^{n-1}\left(a_kX^{n-k}+\sum_{i=0}^{k-1} a_i\lambda^{k-i}X^{n-k}\right)\\ &\qquad-\sum_{k=0}^{n-2}\sum_{i=0}^k a_i\lambda^{k+1-i}X^{n-1-k}+a_n\\ &=a_0X^n + \sum_{k=1}^{n-1}a_kX^{n-k}+\sum_{k=1}^{n-1}\sum_{i=0}^{k-1} a_i\lambda^{k-i}X^{n-k}\\ &\qquad-\sum_{k=0}^{n-2}\sum_{i=0}^k a_i\lambda^{k+1-i}X^{n-1-k}+a_n. \end{align*}

Dans le second double sigma, vous effectuez un changement de variable, en posant $k^{\prime}=k+1.$ D’où :

\begin{align*} E(X) &=a_0X^n + \sum_{k=1}^{n-1}a_kX^{n-k}+\sum_{k=1}^{n-1}\sum_{i=0}^{k-1} a_i\lambda^{k-i}X^{n-k}\\ &\qquad-\sum_{k^{\prime}=1}^{n-1}\sum_{i=0}^{k^{\prime}-1} a_i\lambda^{k^{\prime}-i}X^{n-k^{\prime}}+a_n. \end{align*}

Il apparaît une somme téléscopique. Les deux doubles sigmas se simplifient. Vous déduisez :

\begin{align*} E(X) &= a_0X^n + \sum_{k=1}^{n-1}a_kX^{n-k} + a_n\\ &= P(X). \end{align*}

Ainsi vous avez démontré que, pour tout $\lambda\in\L\comma$ vous avez :

\begin{align*} P(X) &=Q(X)(X-\lambda)+P(\lambda)\\ &= (X-\lambda)\left(\sum_{k=0}^{n-1}P_k(\lambda) X^{n-1-k}\right)+P(\lambda). \end{align*}

Maintenant, revenez au calcul des sommes de Newton

Soit $i$ un entier compris entre $1$ et $n.$

Quand vous effectuez la division euclidienne du polynôme $P$ par $X-\lambda_i\comma$vous obtenez ce qui suit :

P(X)=(X-\lambda_i)\left(P_0(\lambda_i)x^{n-1} + P_1(\lambda_i)x^{n-2} + \cdots + P_{n-1}(\lambda_i)\right) + P(\lambda_i).

Comme $\lambda_i$ est racine du polynôme $P\comma$ vous avez, en passant dans le corps $\L(X)$ l’égalité suivante :

\frac{P(X)}{X-\lambda_i} = P_0(\lambda_i)X^{n-1} + P_1(\lambda_i)X^{n-2} + \cdots + P_{n-1}(\lambda_i).

Cette relation étant vérifiée pour toutes les racines du polynôme $P\comma$ par somme, vous obtenez :

\begin{align*} \sum_{i=1}^n \frac{P(X)}{X-\lambda_i} &= \left(\sum_{i=1}^n P_0(\lambda_i)\right)X^{n-1} + \left(\sum_{i=1}^n P_1(\lambda_i)\right)X^{n-2} \\ &\quad+ \cdots + \left(\sum_{i=1}^n P_{n-1}(\lambda_i)\right)\\ &= na_0X^{n-1}+ (a_0N_1+na_1)X^{n-2} \\ &\quad+ \cdots + (a_0N_{n-1}+a_1N_{n-2}+\cdots+a_{n-2}N_1+na_{n-1}). \end{align*}

Vous allez faire le lien avec la dérivation. Partez du fait que $P(X) = a_0(x-\lambda_1)\cdots(x-\lambda_n).$ Il vient :

\begin{align*} P^{\prime}(X)&=\sum_{i=1}^n \prod_{j\in\llbracket 1, n\rrbracket\setminus \{i\}} a_0(X-\lambda_j) \\ &= \sum_{i=1}^n \frac{P(X)}{X-\lambda_i}\\ &=na_0X^{n-1}+ (a_0N_1+na_1)X^{n-2} \\ &\quad+ \cdots + (a_0N_{n-1}+a_1N_{n-2}+\cdots+a_{n-2}N_1+na_{n-1}). \end{align*}

Or :

\begin{align*} P^{\prime}(X)=na_0X^{n-1}+(n-1)a_{1}X^{n-2}+\cdots+a_{n-1}. \end{align*}

Vous avez obtenu les coefficients du polynôme dérivé de $P$ de deux façons différentes.

Par identification des coefficients à partir du deuxième à gauche. Pour tout entier $i$ appartenant à l’intervalle $\llbracket 1, n-1\rrbracket\comma$ vous avez :

\begin{align*} ia_{n-i} =a_0 N_{n-i}+a_1N_{n-i-1}+\cdots +a_{n-i-1}N_1 +na_{n-i}. \end{align*}

Soit :

\begin{align*} a_0 N_{n-i}+a_1N_{n-i-1}+\cdots +a_{n-i-1}N_1 +(n-i)a_{n-i}=0. \end{align*}

Effectuez le changement de variable $k=n-i.$ Quand $i$ varie entre $1$ et $n-1\comma$ $k$ varie de $1$ à $n-1$ aussi. Ainsi, pour tout entier naturel $k$ appartenant à l’intervalle $\llbracket 1, n-1\rrbracket\comma$ vous avez :

\left\{\begin{align*} &a_0 N_{k}+a_1N_{k-1}+\cdots +a_{k-1}N_1 +ka_{k}=0\\ &\sum_{i=0}^{k-1} a_iN_{k-i} + ka_k=0. \end{align*} \right.

Comme la relation $\sum_{i=0}^{n-1} a_iN_{n-i} +na_n=0$ a déjà été établie, vous en déduisez que, pour tout entier $k\in\llbracket 1, n\rrbracket\comma$ vous avez :

\boxed{\sum_{i=0}^{k-1} a_iN_{k-i} + ka_k=0.}

Le lien entre les sommes de Newton et les coefficients du polynôme associé est maintenant établi.

Prolongements

Vous souhaitez voir sur un exemple comment calculer les sommes de Newton ?

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 316.

Vous souhaitez trouver une application de ce résultat en algèbre linéaire ?

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 085.