Théorème de Sturm

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections Cet article concerne les fonctions polynômes. Pour les équations différentielles, voir Théorie de Sturm-Liouville.

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 polynôme comprises dans un intervalle donné. La méthode effective de calcul correspondante s'appelle l'algorithme de Sturm[1].

Suite de Sturm[modifier | modifier le code]

On se donne un polynôme P=x^n +a_{n-1}x^{n-1}+\ldots + a_1 x + a_0. La suite de Sturm ou chaîne de Sturm à partir du polynôme P est une suite finie de polynômes P_0, P_1, \dots, P_m . Elle est construite par récurrence :

  • P_0=P~ ;
  • P_1=P^\prime, où P' est la dérivée de P, c'est à dire le polynôme P^\prime=nx^{n-1} + \ldots + a_1 ;
  • Pour i \geq 2, P_i est l'opposée du reste de la division de P_{i-1} et P_{i-2}.
  • 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_0~ et sa dérivée P_1~ :

\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_0, T_1, \ldots, T_{m-1}, 1 que l'on obtient en divisant les P_1, P_2, \ldots, P_{m-1} par P_{m}~.

Énoncé du théorème[modifier | modifier le code]

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 \sigma(\xi)~ le nombre de changements de signe (zéro n'est pas compté comme un changement de signe) dans la suite

P(\xi), P_1(\xi), P_2(\xi),\ldots, P_m(\xi).

Le théorème de Sturm nous 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 :

\sigma(a)-\sigma(b)~.

Exemple[modifier | modifier le code]

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.

\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}

En divisant p0 par p1 on obtient le reste -\tfrac{3}{16}x^2-\tfrac{3}{4}x-\tfrac{15}{16}, et en le multipliant par −1 on obtient p_2(x)=\tfrac{3}{16}x^2+\tfrac{3}{4}x+\tfrac{15}{16}. Ensuite, on divise p1 par p2 et en multipliant le reste par −1, on obtient p_3(x)=-32x-64. Puis on divise p2 par p3 et en multipliant le reste par −1, on obtient p_4(x)=-\tfrac{3}{16}.

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

p_0(x) = x^4+x^3-x-1
p_1(x) = 4x^3+3x^2-1
p_2(x) = \tfrac{3}{16}x^2+\tfrac{3}{4}x+\tfrac{15}{16}
p_3(x) = -32x-64
p_4(x) = -\tfrac{3}{16}

Pour trouver le nombre de racines totales, ie. entre −∞ et +, on évalue p0, p1, p2, p3, et p4 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) = x4 + x3x − 1 se factorise en (x2 − 1)(x2 + x + 1), où on voit que x2 − 1 a deux racines (−1 et 1) alors que x2 + x + 1 n'a pas de racines réelles.

Applications[modifier | modifier le code]

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[2] :

M=1+{\max}_{i=0}^{n-1}|a_i|[3] ou M=\max\left(1,\sum_{i=0}^{n-1}|a_i|\right)[4].

Notes et références[modifier | modifier le code]

  1. (en) Peter Bürgisser, Michael Clausen et Amin Shokrollahi, Algebraic Complexity Theory, Springer Science & Business Media,‎ (ISBN 9783662033388, lire en ligne) (exercice 3.10, p. 93).
  2. Pour d'autres exemples, voir l'article Théorie des équations (mathématiques).
  3. Augustin Louis Cauchy, « Sur la résolution des équations numériques et sur la théorie de l'élimination », dans Exercices de mathématiques,‎ (lire en ligne), p. 92.
  4. (en) Holly P. Hirst et Wade T. Macey, « Bounding the Roots of Polynomials », The College Mathematics Journal, MAA, vol. 28, no 4,‎ , p. 292-295 (DOI 10.2307/2687152).