084. Les sommes de Newton

Dans cet article, vous trouverez :

  • la définition d’une somme de Newton associée à un polynôme,
  • 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,
  • une démonstration de ces relations qui fait appel à la division euclidienne et à la dérivation d’un polynôme scindé.

Qu’entend-on par sommes de Newton vis-à-vis d’un polynôme ?

Soit $P$ un polynôme à coefficients dans un corps $\K$, de degré $n\geq 1$.

Il existe des coefficients $(a_0,a_1,\dots,a_n)$ tels que $P(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n.$

Notez que, 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 $P$ est scindé.

Il existe donc $n$ racines appartenant à $\L$, certaines étant éventuellement répétées, notées $\lambda_1$, … , $\lambda_n$, telles que $P(x)=a_0(x-\lambda_1)\cdots(x-\lambda_n).$

Les sommes de Newton, notées $N_1$ pour “Newton 1”, …, $N_n$ pour “Newton $n$”, sont définies de la façon suivante :

$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$,

$\dots$

$N_n = \lambda_1^n+\cdots+\lambda_n^n=\sum_{k=1}^n\lambda_k^n.$

Autrement dit, pour tout entier $i$ compris entre $1$ et $n$,

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

Note : vous trouverez aussi des sommes de Newton définies pour $i\geq n+1$. Elles ne seront pas traitées dans cet article, le point de difficulté à lever étant de comprendre le lien entre les premières relations.

Comment mémoriser efficacement les relations qui lient les sommes de Newton ?

La relation fondamentale

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

Comme $\lambda_k$ est une racine de $P$, vous déduisez :

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

Pour plus de clarté, on écrira le dernier coefficient fois $1$.

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

Maintenant sommez ces $n$ relations.

$\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\times 1\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 la relation de base fondamentale qui lie toutes les sommes.

$\boxed{a_0N_n+a_1N_{n-1}+\cdots+a_{n-1}N_1+na_n=0.}$

$\boxed{\sum_{i=0}^{n-1} a_iN_{n-i} + na_n=0.}$

Comment se souvenir des autres relations ?

Considérez le polynôme de degré $1$ qui n’utilise que les premiers coefficients de $P$ 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’_1$. Si vous appliquez la relation fondamentale avec sa somme de Newton $N’_1 = \lambda’_1$, vous obtenez $a_0N’_1+a_1=0.$

Ce qui est remarquable c’est que cette relation reste valable pour la somme $N_1$ associée au polynôme de départ $P$ : $a_0N_1+a_1=0.$

De même pour le degré $2$. Posez $P_2(x)=a_0x^2+a_1x+a_2$. Notez $\lambda’_1$ et $\lambda’_2$ les deux racines de $P_2$, posez $N’_1 = \lambda’_1+\lambda’_2$ et $N’_2 = {\lambda’}_1^2$ $+{\lambda’}_2^2$.

D’après la relation fondamentale $a_0N’_2+a_1N’_1+2a_2=0.$

Cette relation se transpose aussi.

Vous avez $a_0N_2+a_1N_1+2a_2=0$ où $N_1$ et $N_2$ sont les deux premières sommes de Newton associées au polynôme de départ $P$.

Vous en déduisez toutes les relations liant les sommes de Newton. Il y en a $n$ au total.

$\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\\
\cdots & \cdots\\
a_0N_n+a_1N_{n-1}+\cdots+a_{n-1}N_1+na_n &=0.
\end{align*}$

Conclusion : toutes les formules de Newton avec des sigmas

Pour tout entier $k$ compris entre $1$ et $n$ :

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

Et maintenant, démontrez les relations qu’il y a entre les sommes de Newton et les coefficients du polynôme

Ecartez d’office le cas où $P$ est de degré $1$. Il y a une seule racine $\lambda_1$ qui vérifie $a_0\lambda_1+a_1=0$, or $N_1 = \lambda_1.$

Dans la suite $n$ désignera un entier naturel supérieur ou égal à $2$.

A partir du polynôme $P$ défini par $P(x)=a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n$, vous allez définir les polynômes tronqués $P_0$, $P_1$, …, $P_n$ de la façon suivante :

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

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

Quand vous effectuez la division euclidienne de $P(x)$ par $x-\lambda_i$ dans le corps $\L(x)$, vous obtenez $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_n(\lambda_i).$

Faites une disgression et voyez pourquoi on obtient une telle relation par division euclidienne

Comment bien comprendre le processus ?

Supposez temporairement que le polynôme $P$ est de degré $3$ dans $\L[x]$, $P(x)=a_0x^3+a_1x^2+a_2x+a_3$. Soit $\lambda$ un élément de $\L$.

Vous allez effectuer la division de $P$ par $x-\lambda$, pas à pas.

$\begin{align*}
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)(a_0x^2+(a_0\lambda+a_1)x+(a_0\lambda^2+a_1\lambda +a_2)) + ((a_0\lambda^2+a_1\lambda +a_2))\lambda)+ a_3\\
&=(x-\lambda)(a_0x^2+(a_0\lambda+a_1)x+(a_0\lambda^2+a_1\lambda +a_2)) +P(\lambda).\\
\end{align*}$

Note. Dans le processus vous pouvez reconnaître la méthode de Hörner pour calculer $P(\lambda)$.

La division euclidienne pour tout degré $n\geq 2$

Supposez que le polynôme $P$ soit de degré $n\geq 2$ à coefficients dans $\L$. Soit $\lambda$ un élément de $\L$.

L’exemple précédent suggère de poser $Q(x)=\sum_{k=0}^{n-1}\sum_{i=0}^k a_i\lambda^{k-i}x^{n-1-k}$ comme polynôme qui va être le quotient de la division euclidienne de $P(x)$ par $x-\lambda$. Le reste de cette division doit être $P(\lambda).$

Vérifiez-le en effectuant le développement de l’expression $E$ définie par $E(x)=Q(x)(x-\lambda)+P(\lambda).$

Par développement du $x$ et du $\lambda$ dans le sigma, vous obtenez :

$E(x) = \sum_{k=0}^{n-1}\sum_{i=0}^k a_i\lambda^{k-i}x^{n-k}-\sum_{k=0}^{n-1}\sum_{i=0}^k a_i\lambda^{k+1-i}x^{n-1-k} + P(\lambda).$

Maintenant vous isolez le terme pour $i=0$ du premier sigma et le terme pour $i=n-1$ du deuxième sigma. Aussitôt :

$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} – \sum_{i=0}^{n-1} a_i\lambda^{n-i}+ P(\lambda).$

Une première simplification apparaît dans le terme constant de $E(x)$.

$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} +a_n.$

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

$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)-\sum_{k=0}^{n-2}\sum_{i=0}^k a_i\lambda^{k+1-i}x^{n-1-k} +a_n.$

Vous poursuivez le développement du premier sigma.

$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}-\sum_{k=0}^{n-2}\sum_{i=0}^k a_i\lambda^{k+1-i}x^{n-1-k} +a_n.$

Dans le second double sigma, vous effectuez un changement de variable, en posant $k’=k+1$.

$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}-\sum_{k’=1}^{n-1}\sum_{i=0}^{k’-1} a_i\lambda^{k’-i}x^{n-k’} +a_n.$

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

$E(x) = a_0x^n + \sum_{k=1}^{n-1}a_kx^{n-k} + a_n$.

$E(x)$ coïncide avec $P(x)$.

Aussitôt $\boxed{P(x) =(x-\lambda)\left( \sum_{k=0}^{n-1}\left(\sum_{i=0}^k a_i\lambda^{k-i}\right)x^{n-1-k}\right)+P(\lambda).}$

Maintenant, revenez au calcul des sommes de Newton

Comme $\lambda_i$ est racine de $P$, $P_n(\lambda_i)=P(\lambda_i)=0.$ Aussitôt :

$\dfrac{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).$

Vous sommez cette relation sur toutes les racines.

$\begin{align*}
\displaystyle\sum_{i=1}^n \dfrac{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} &+ \cdots &+ \left(\sum_{i=1}^n P_{n-1}(\lambda_i)\right)\\
&= na_0x^{n-1} &+ (a_0N_1+na_1)x^{n-2} &+ \cdots &+ (a_0N_{n-1}+a_1N_{n-2}+\cdots+a_{n-2}N_1+na_{n-1})
\end{align*}$

Partant de $P(x) = a_0(x-\lambda_1)\cdots(x-\lambda_n)$, en dérivant :

$P'(x)=\displaystyle\sum_{i=1}^n \prod_{j\neq i} a_0(x-\lambda_j) = \sum_{i=1}^n \dfrac{P(x)}{x-\lambda_i}$

Du coup :

$\begin{align*}
P'(x) &= na_0x^{n-1} &+ (a_0N_1+na_1)x^{n-2} &+ \cdots &+ (a_0N_{n-1}+a_1N_{n-2}+\cdots+a_{n-2}N_1+na_{n-1})\\
na_0x^{n-1}+(n-1)a_{1}x^{n-2}+\cdots+a_{n-1}&= na_0x^{n-1} &+ (a_0N_1+na_1)x^{n-2} &+ \cdots &+ (a_0N_{n-1}+a_1N_{n-2}+\cdots+a_{n-2}N_1+na_{n-1}).
\end{align*}$

Par identification des coefficients à partir du deuxième à gauche, il vient :

$\begin{align*}
\forall i\in \N, 1\leq i\leq n-1&\Rightarrow ia_{n-i} =a_0 N_{n-i}+a_1N_{n-i-1}+\cdots +a_{n-i-1}N_1 +na_{n-i}\\
&\Rightarrow 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$, $k$ varie de $1$ à $n-1$ aussi.

Pour tout entier naturel $k$ compris entre $1$ et $n-1$, vous avez :

$a_0 N_{k}+a_1N_{k-1}+\cdots +a_{k-1}N_1 +ka_{k}=0.$

Avec un sigma, cela s’écrit $\sum_{i=0}^{k-1} a_iN_{k-i} + ka_k=0.$

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 $k$ compris entre $1$ et $n$, $\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.

Pensez aux résultats qui en découlent

Les sommes de Newton serviront à établir une démonstration de la méthode de Faddeev, qui constitue une amélioration de la méthode de Leverrier. Vous pourrez par la suite calculer le polynôme caractéristique d’une matrice ainsi que l’inverse de cette matrice le cas échéant.

Réagissez !

C’est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées.