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[1].

Suite de Sturm

On se donne un polynôme P = x^n + a_{n – 1} x^n – 1 + ... + a₁ x + a₀. La suite de Sturm ou chaîne de Sturm à partir du polynôme P est une suite finie de polynômes P₀, P₁, ..., P_m. Elle est construite par récurrence :

• P₀ = P ;
• P₁ = P', où P' est la dérivée de P, c'est-à-dire le polynôme P' = nx^n – 1 + ... + a₁ ;
• Pour i ≥ 2, P_i est l'opposée du reste de la division de P_{i – 2} par P_{i – 1}.
• 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 à P₀ et sa dérivée P₁ :

${\displaystyle {\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}}}$

Si P possède uniquement des racines distinctes, le dernier terme est une constante non nulle. Si ce terme est nul, P admet des racines multiples, et on peut dans ce cas appliquer le théorème de Sturm en utilisant la suite T₀, T₁, ..., T_{m – 1}, 1 que l'on obtient en divisant les P₁, P₂, ..., P_{m – 1} par P_m.

Énoncé du théorème

Le nombre de racines réelles distinctes dans un intervalle [a , b] d'un polynôme à coefficients réels, dont a et b 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 σ(ξ) le nombre de changements de signe (zéro n'est pas compté comme un changement de signe) dans la suite

${\displaystyle P(\xi ),P_{1}(\xi ),P_{2}(\xi ),\ldots ,P_{m}(\xi )}$.

Le théorème de Sturm dit que pour deux nombres réels a, b, a < b, où a et b ne sont pas des racines de P, le nombre de racines dans l'intervalle [a , b] est :

${\displaystyle \sigma (a)-\sigma (b)~}$.

Démonstration

Une démonstration est donnée en référence[2].

Exemple

Supposons que l'on souhaite connaître le nombre de racines dans un certain intervalle du polynôme p(x) = x^4 + x^3 – x –1. On commence par calculer les deux premiers termes.

${\displaystyle {\begin{aligned}p_{0}(x)&=p(x)=x^{4}+x^{3}-x-1\\p_{1}(x)&=p'(x)=4x^{3}+3x^{2}-1\end{aligned}}}$

En divisant p₀ par p₁ on obtient le reste –3/16x^2 – 3/4x – 15/16, et en le multipliant par −1 on obtient p₂(x) = 3/16x^2 + 3/4x + 15/16. Ensuite, on divise p₁ par p₂ et en multipliant le reste par −1, on obtient p₃(x) = –32x –64. Puis on divise p₂ par p₃ et en multipliant le reste par −1, on obtient p₄(x) = –3/16.

Finalement, la suite de Sturm du polynôme P est donc :

${\displaystyle p_{0}(x)=x^{4}+x^{3}-x-1}$

${\displaystyle p_{1}(x)=4x^{3}+3x^{2}-1}$

${\displaystyle p_{2}(x)={\tfrac {3}{16}}x^{2}+{\tfrac {3}{4}}x+{\tfrac {15}{16}}}$

${\displaystyle p_{3}(x)=-32x-64}$

${\displaystyle p_{4}(x)=-{\tfrac {3}{16}}}$

Pour trouver le nombre de racines totales, ie. entre −∞ et +∞, on évalue p₀, p₁, p₂, p₃, et p₄ en −∞ et on note la séquence de signes correspondante : + − + + −. Elle contient trois changements de signe (+ à −, puis − à +, puis + à −). On fait la même chose en +∞ et obtient la séquence de signes + + + − −, qui contient juste un changement de signe. D'après le théorème de Sturm, le nombre total de racines du polynôme P est 3 − 1 = 2. Nous pouvons faire une vérification en remarquant que p(x) = x^4 + x^3 − x − 1 se factorise en (x^2 − 1)(x^2 + x + 1), où on voit que x^2 − 1 a deux racines (−1 et 1) alors que x^2 + x + 1 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 a et b de telle sorte que toutes les racines réelles soient dans l'intervalle [a , b] : par exemple [a , b] = [–M , M] convient, avec, au choix[3] :

${\displaystyle M=1+{\max }_{i=0}^{n-1}|a_{i}|}$[4] ou ${\displaystyle M=\max \left(1,\sum _{i=0}^{n-1}|a_{i}|\right)}$[5].

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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sturm's theorem » (voir la liste des auteurs).

• 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

1. (en) Peter Bürgisser, Michael Clausen et Amin Shokrollahi, Algebraic Complexity Theory, Springer Science & Business Media, 14 mars 2013, 618 p. (ISBN 978-3-662-03338-8, lire en ligne) (exercice 3.10, p. 93).
2. [PDF] Sandrine Caruso, « Suite de Sturm. ».
3. Pour d'autres exemples, voir l'article Théorie des équations (mathématiques).
4. Voir Théorème de Lagrange sur les polynômes.
5. (en) Holly P. Hirst et Wade T. Macey, « Bounding the Roots of Polynomials », The College Mathematics Journal, MAA, vol. 28, n^o 4,‎ septembre 1997, p. 292-295 (DOI 10.2307/2687152).