Théorème de Sturm
En mathématiques, et plus précisément en analyse, le théorème de Sturm, établi en 1829 par Charles Sturm, permet de calculer le nombre de racines réelles distinctes d'une fonction polynomiale comprises dans un intervalle donné. La méthode effective de calcul correspondante s'appelle l'algorithme de Sturm<ref>Modèle:Ouvrage (exercice 3.10, p. 93).</ref>.
Suite de Sturm
On se donne un polynôme Modèle:Math. La suite de Sturm ou chaîne de Sturm à partir du polynôme Modèle:Mvar est une suite finie de polynômes Modèle:Math. Elle est construite par récurrence :
- Modèle:Math ;
- Modèle:Math, où Modèle:Mvar est la dérivée de Modèle:Mvar, c'est-à-dire le polynôme Modèle:Math ;
- Pour Modèle:Math, Modèle:Mvar est l'opposée du reste de la division de Modèle:Math par Modèle:Math.
- La construction s'arrête au dernier polynôme non nul.
Pour obtenir cette suite, on calcule les restes intermédiaires que l'on obtient en appliquant l'algorithme d'Euclide à Modèle:Math et sa dérivée Modèle:Math :
- <math>\begin{matrix}
P_0&=&P_1 Q_1 & - & P_2\\ P_1&=&P_2 Q_2 & - & P_3\\ \vdots &\vdots& \vdots& \vdots& \vdots\\ P_{m-2} & =& P_{m-1} Q_{m-1} & -& P_m \\ P_{m-1} & =& P_{m} Q_{m} & -& 0 \\ \end{matrix} </math>
Si Modèle:Mvar possède uniquement des racines distinctes, le dernier terme est une constante non nulle. Si ce terme est nul, Modèle:Mvar admet des racines multiples, et on peut dans ce cas appliquer le théorème de Sturm en utilisant la suite Modèle:Math que l'on obtient en divisant les Modèle:Math par Modèle:Mvar.
Énoncé du théorème
Le nombre de racines réelles distinctes dans un intervalle Modèle:Math d'un polynôme à coefficients réels, dont Modèle:Mvar et Modèle:Mvar ne sont pas des racines, est égal au nombre de changements de signe de la suite de Sturm aux bornes de cet intervalle.
Plus formellement, notons Modèle:Math le nombre de changements de signe (zéro n'est pas compté comme un changement de signe) dans la suite
- <math>P(\xi), P_1(\xi), P_2(\xi),\ldots, P_m(\xi)</math>.
Le théorème de Sturm dit que pour deux nombres réels Modèle:Mvar, Modèle:Mvar, Modèle:Math, où Modèle:Mvar et Modèle:Mvar ne sont pas des racines de Modèle:Mvar, le nombre de racines dans l'intervalle Modèle:Math est :
- <math>\sigma(a)-\sigma(b)~</math>.
Exemple
Supposons que l'on souhaite connaître le nombre de racines dans un certain intervalle du polynôme Modèle:Math. On commence par calculer les deux premiers termes.
- <math>\begin{align} p_0(x) &=p(x)=x^4+x^3-x-1 \\
p_1(x)&=p'(x)=4x^3+3x^2-1 \end{align}</math>
En divisant Modèle:Math par Modèle:Math on obtient le reste Modèle:Math, et en le multipliant par Modèle:Math on obtient Modèle:Math. Ensuite, on divise Modèle:Math par Modèle:Math et en multipliant le reste par Modèle:Math, on obtient Modèle:Math. Puis on divise Modèle:Math par Modèle:Math et en multipliant le reste par Modèle:Math, on obtient Modèle:Math.
Finalement, la suite de Sturm du polynôme Modèle:Mvar est donc :
- <math>p_0(x) = x^4+x^3-x-1</math>
- <math>p_1(x) = 4x^3+3x^2-1</math>
- <math>p_2(x) = \tfrac{3}{16}x^2+\tfrac{3}{4}x+\tfrac{15}{16}</math>
- <math>p_3(x) = -32x-64</math>
- <math>p_4(x) = -\tfrac{3}{16}</math>
Pour trouver le nombre de racines totales, ie. entre Modèle:Math et +Modèle:Math, on évalue Modèle:Math et Modèle:Math en Modèle:Math et on note la séquence de signes correspondante : Modèle:Math. Elle contient trois changements de signe (Modèle:Math à Modèle:Math, puis Modèle:Math à Modèle:Math, puis Modèle:Math à Modèle:Math). On fait la même chose en +Modèle:Math et obtient la séquence de signes Modèle:Math, qui contient juste un changement de signe. D'après le théorème de Sturm, le nombre total de racines du polynôme Modèle:Mvar est Modèle:Math Nous pouvons faire une vérification en remarquant que Modèle:Math se factorise en Modèle:Math, où on voit que Modèle:Math a deux racines (Modèle:Math et Modèle:Math) alors que Modèle:Math n'a pas de racines réelles.
Applications
On peut utiliser ce théorème pour calculer le nombre total de racines réelles distinctes, en choisissant les bornes Modèle:Mvar et Modèle:Mvar de telle sorte que toutes les racines réelles soient dans l'intervalle Modèle:Math : par exemple Modèle:Math convient, avec, au choix<ref>Pour d'autres exemples, voir l'article Théorie des équations (mathématiques).</ref> :
On peut aussi utiliser ce théorème pour trouver les racines d'un polynôme quelconque par dichotomie, et, par là même, optimiser un critère polynomial quelconque (en trouvant les racines de sa dérivée).
Notes et références
- C. Sturm, « Sur la résolution des équations numériques », dans Sciences mathématiques et physiques, tome VI, Paris, 1835, p. 271-318
- Edouard Callandreau, « Célèbres problèmes mathématiques », Editions Albin Michel, Paris, 1949, 1 volume, 478p
