Théorème de Sturm - Sturm's theorem

En mathématiques , la suite de Sturm d'un polynôme univarié $p$ est une suite de polynômes associée à $p$ et à sa dérivée par une variante de l'algorithme d' Euclide pour les polynômes . Le théorème de Sturm exprime le nombre de racines réelles distinctes de $p$ situées dans un intervalle en termes de nombre de changements de signes des valeurs de la séquence de Sturm aux bornes de l'intervalle. Appliquée à l'intervalle de tous les nombres réels, elle donne le nombre total de racines réelles de $p$ .

Alors que le théorème fondamental de l'algèbre donne facilement le nombre total de racines complexes , compté avec la multiplicité , il ne fournit pas de procédure pour les calculer. Le théorème de Sturm compte le nombre de racines réelles distinctes et les situe dans des intervalles. En subdivisant les intervalles contenant des racines, il peut isoler les racines en petits intervalles arbitraires, chacun contenant exactement une racine. Cela donne le plus ancien algorithme d' isolation de racine réelle et un algorithme de recherche de racine de précision arbitraire pour les polynômes univariés.

Pour le calcul sur les réels , le théorème de Sturm est moins efficace que d'autres méthodes basées sur la règle des signes de Descartes . Cependant, il fonctionne sur tout champ réel fermé et, par conséquent, reste fondamental pour l'étude théorique de la complexité computationnelle de la décidabilité et de l'élimination des quantificateurs dans la théorie du premier ordre des nombres réels.

La séquence de Sturm et le théorème de Sturm portent le nom de Jacques Charles François Sturm , qui a découvert le théorème en 1829.

Le théorème

La chaîne de Sturm ou suite de Sturm d'un polynôme univarié $P (x)$ à coefficients réels est la suite de polynômes tels que ${\style d'affichage P_{0},P_{1},\ldots ,}$

{\begin{aligned}P_{0}&=P,\\P_{1}&=P',\\P_{i+1}&=-\operatorname {rem} (P_{i-1 },P_{i}),\end{aligned}}

pour $i 1$ , où $P'$ est la dérivée de $P$ , et est le reste de la division euclidienne de par La longueur de la séquence de Sturm est au plus le degré de $P$ . $\operatorname {rem} (P_{i-1},P_{i})$ ${\style d'affichage P_{i-1}}$ ${\style d'affichage P_{i}.}$

Le nombre de variations de signe à $ξ$ de la séquence Sturm de $P$ est le nombre de zéros-en-ignorant les changements du signe séquence des nombres réels

P_{0}(\xi ),P_{1}(\xi ),P_{2}(\xi ),\ldots .

Ce nombre de variations de signe est notée ici $V (ξ)$ .

Le théorème de Sturm stipule que, si $P$ est un polynôme sans carré , le nombre de racines réelles distinctes de $P$ dans l' intervalle semi-ouvert $(a, b]$ est $V (a) - V (b)$ (ici, $a$ et $b$ sont nombres réels tels que $a < b$ ).

Le théorème s'étend aux intervalles non bornés en définissant le signe en $+\infty$ d'un polynôme comme le signe de son coefficient dominant (c'est-à-dire le coefficient du terme de plus haut degré). A $-\infty$ le signe d'un polynôme est le signe de son coefficient dominant pour un polynôme de degré pair, et le signe opposé pour un polynôme de degré impair.

Dans le cas d'un polynôme sans carré, si ni $a$ ni $b ne$ sont des racines multiples de $p$ , alors $V (a) - V (b)$ est le nombre de racines réelles distinctes de $P$ .

La preuve du théorème est la suivante : lorsque la valeur de $x$ augmente de $a$ à $b$ , elle peut passer par un zéro de certains ( $i$ $> 0$ ); lorsque cela se produit, le nombre de variations de signe de ne change pas. Lorsque $x$ passe par une racine du nombre de variations de signe de diminue de 1 à 0. Ce sont les seules valeurs de $x$ où un signe peut changer. ${\style d'affichage P_{i}}$ ${\style d'affichage (P_{i-1},P_{i},P_{i+1})}$ ${\style d'affichage P_{0}=P,}$ ${\style d'affichage (P_{0},P_{1})}$

Exemple

Supposons que nous souhaitions trouver le nombre de racines dans une plage pour le polynôme . Donc ${\style d'affichage p(x)=x^{4}+x^{3}-x-1}$

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

Le reste de la division euclidienne de $p 0$ par $p 1$ est de le multiplier par $-1$ nous obtenons $-{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};$

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

.

Ensuite, en divisant $p 1$ par $p 2$ et en multipliant le reste par $-1$ , nous obtenons

{\style d'affichage p_{3}(x)=-32x-64}

.

En divisant maintenant $p 2$ par $p 3$ et en multipliant le reste par $-1$ , nous obtenons

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

.

Comme il s'agit d'une constante, cela termine le calcul de la séquence de Sturm.

Pour trouver le nombre de racines réelles de on doit évaluer les suites des signes de ces polynômes en $-\infty$ et $\infty$ , qui sont respectivement $(+, -, +, +, -)$ et $(+, +, +, -, -)$ . Ainsi ${\style d'affichage p_{0}}$

{\style d'affichage V(-\infty )-V(+\infty )=3-1=2,}

ce qui montre que $p$ a deux racines réelles.

Cela peut être vérifié en notant que $p (x)$ peut être factorisé comme $(x 2 - 1)(x 2 + x + 1)$ , où le premier facteur a les racines $-1$ et $1$ , et le second facteur n'a pas de racines réelles. Cette dernière assertion résulte de la formule quadratique , ainsi que du théorème de Sturm, qui donne les suites de signes $(+, -, -)$ en $-\infty$ et $(+, +, -)$ en $+\infty$ .

Généralisation

Les séquences de Sturm ont été généralisées dans deux directions. Pour définir chaque polynôme de la séquence, Sturm a utilisé le négatif du reste de la division euclidienne des deux précédents. Le théorème reste vrai si l'on remplace le négatif du reste par son produit ou quotient par une constante positive ou le carré d'un polynôme. Il est également utile (voir ci-dessous) de considérer des séquences où le deuxième polynôme n'est pas la dérivée du premier.

Une suite de Sturm généralisée est une suite finie de polynômes à coefficients réels

P_{0},P_{1},\dots ,P_{m}

tel que

les degrés sont décroissants après le premier : pour $i$ $= 2, ...,$ $m$ ; $\deg P_{i}<\deg P_{i-1}$
${\style d'affichage P_{m}}$ n'a pas de racine réelle ou ne change pas de signe près de ses racines réelles.
si $P i (ξ) = 0$ pour $0 < i < m$ et $Ç$ un nombre réel, alors $P i -1 (ξ) P i + 1 (ξ) <0$ .

La dernière condition implique que deux polynômes consécutifs n'ont pas de racine réelle commune. En particulier, la séquence de Sturm d'origine est une séquence de Sturm généralisée, si (et seulement si) le polynôme n'a pas de racine réelle multiple (sinon les deux premiers polynômes de sa séquence de Sturm ont une racine commune).

Lors du calcul de la séquence de Sturm originale par division euclidienne, il peut arriver que l'on rencontre un polynôme qui a un facteur qui n'est jamais négatif, tel a ou . Dans ce cas, si on continue le calcul avec le polynôme remplacé par son quotient par le facteur non négatif, on obtient une suite de Sturm généralisée, qui peut aussi être utilisée pour calculer le nombre de racines réelles, puisque la preuve du théorème de Sturm s'applique toujours ( à cause de la troisième condition). Cela peut parfois simplifier le calcul, bien qu'il soit généralement difficile de trouver de tels facteurs non négatifs, sauf pour les puissances paires de $x$ . ${\style d'affichage x^{2}}$ ${\style d'affichage x^{2}+1}$

Utilisation de séquences de pseudo-restes

En calcul formel , les polynômes considérés ont des coefficients entiers ou peuvent être transformés pour avoir des coefficients entiers. La séquence de Sturm d'un polynôme à coefficients entiers contient généralement des polynômes dont les coefficients ne sont pas des entiers (voir l'exemple ci-dessus).

Pour éviter le calcul avec des nombres rationnels , une méthode courante consiste à remplacer la division euclidienne par une pseudo-division pour calculer les plus grands diviseurs communs polynomiaux . Cela revient à remplacer la séquence reste de l' algorithme euclidien par une pseudo séquence reste , une pseudo séquence reste étant une séquence de polynômes tels qu'il existe des constantes et tel que soit le reste de la division euclidienne de par (Les différentes sortes de pseudo -les séquences restantes sont définies par le choix de et sont généralement choisies pour ne pas introduire de dénominateurs lors de la division euclidienne, et sont un diviseur commun des coefficients du reste résultant ; voir la séquence pseudo-reste pour plus de détails.) Par exemple, la séquence des restes de l'algorithme euclidien est une séquence pseudo-reste avec pour chaque $i$ , et la séquence de Sturm d'un polynôme est une séquence pseudo-reste avec et pour chaque $i$ . $p_{0},\ldots ,p_{k}$ ${\style d'affichage a_{i}}$ ${\style d'affichage b_{i}}$ $b_{i}p_{i+1}$ $a_{i}p_{i-1}$ ${\style d'affichage p_{i}.}$ ${\style d'affichage a_{i}}$ ${\style d'affichage b_{i};}$ ${\style d'affichage a_{i}}$ ${\style d'affichage b_{i}}$ ${\style d'affichage a_{i}=b_{i}=1}$ ${\style d'affichage a_{i}=1}$ ${\style d'affichage b_{i}=-1}$

Diverses séquences de pseudo-restes ont été conçues pour calculer les plus grands diviseurs communs de polynômes à coefficients entiers sans introduire de dénominateurs (voir Séquence de pseudo-restes ). Elles peuvent toutes être rendues des séquences de Sturm généralisées en choisissant le signe de l' opposé du signe de la Cela permet l'utilisation du théorème de Sturm avec des séquences pseudo-restes. ${\style d'affichage b_{i}}$ $a_{i}.$

Isolement de la racine

Pour un polynôme à coefficients réels, l'isolement de racine consiste à trouver, pour chaque racine réelle, un intervalle qui contient cette racine, et aucune autre racine.

Ceci est utile pour la recherche de racine , permettant la sélection de la racine à trouver et fournissant un bon point de départ pour des algorithmes numériques rapides tels que la méthode de Newton ; elle est également utile pour certifier le résultat, car si la méthode de Newton converge en dehors de l'intervalle, on peut immédiatement en déduire qu'elle converge vers la mauvaise racine.

L'isolement des racines est également utile pour le calcul avec des nombres algébriques . Pour calculer avec des nombres algébriques, une méthode courante consiste à les représenter comme une paire d'un polynôme auquel le nombre algébrique est une racine et un intervalle d'isolement. Par exemple, peut être représenté sans ambiguïté par ${\sqrt {2}}$ ${\style d'affichage (x^{2}-2,[0,2]).}$

Le théorème de Sturm fournit un moyen d'isoler les racines réelles qui est moins efficace (pour les polynômes à coefficients entiers) que d'autres méthodes impliquant la règle des signes de Descartes . Cependant, elle reste utile dans certaines circonstances, principalement à des fins théoriques, par exemple pour des algorithmes de géométrie algébrique réelle faisant intervenir des infinitésimaux .

Pour isoler les racines réelles, on part d'un intervalle contenant toutes les racines réelles, ou les racines d'intérêt (souvent, typiquement dans les problèmes physiques, seules les racines positives sont intéressantes), et on calcule et Pour définir cet intervalle de départ, on peut utiliser bornes sur la taille des racines (voir Propriétés des racines polynomiales § Bornes sur les racines polynomiales (complexes) ). Ensuite, on divise cet intervalle en deux, en choisissant $c$ au milieu de Le calcul de fournit le nombre de racines réelles dans et et on peut répéter la même opération sur chaque sous-intervalle. Lorsque l'on rencontre, au cours de ce processus, un intervalle qui ne contient aucune racine, il peut être supprimé de la liste des intervalles à considérer. Quand on rencontre un intervalle contenant exactement une racine, on peut arrêter de le diviser, car c'est un intervalle d'isolement. Le processus s'arrête finalement, lorsqu'il ne reste que des intervalles d'isolement. ${\style d'affichage (a,b]}$ ${\style d'affichage V(a)}$ ${\style d'affichage V(b).}$ ${\style d'affichage (a,b].}$ ${\style d'affichage V(c)}$ ${\style d'affichage (a,c]}$ ${\style d'affichage (c,b],}$

Ce processus d'isolement peut être utilisé avec n'importe quelle méthode pour calculer le nombre de racines réelles dans un intervalle. L' analyse de la complexité théorique et les expériences pratiques montrent que les méthodes basées sur la règle des signes de Descartes sont plus efficaces. Il s'ensuit que, de nos jours, les séquences de Sturm sont rarement utilisées pour l'isolement des racines.

Application

Les séquences de Sturm généralisées permettent de compter les racines d'un polynôme lorsqu'un autre polynôme est positif (ou négatif), sans calculer explicitement ces racines. Si l'on connaît un intervalle isolant pour une racine du premier polynôme, cela permet aussi de trouver le signe du deuxième polynôme à cette racine particulière du premier polynôme, sans calculer une meilleure approximation de la racine.

Soit $P (x)$ et $Q (x)$ deux polynômes à coefficients réels tels que $P$ et $Q$ n'ont pas de racine commune et $P$ n'a pas de racines multiples. En d'autres termes, $P$ et $P' Q$ sont des polynômes premiers entre eux . Cette restriction n'affecte pas vraiment la généralité de ce qui suit car les calculs GCD permettent de réduire le cas général à ce cas, et le coût du calcul d'une séquence de Sturm est le même que celui d'un GCD.

Soit $W (a)$ le nombre de variations de signe en $a$ d'une séquence de Sturm généralisée à partir de $P$ et $P' Q$ . Si $a < b$ sont deux nombres réels, alors $W (a) - W (b)$ est le nombre de racines de $P$ dans l'intervalle tel que $Q$ $($ $a$ $) > 0$ moins le nombre de racines dans le même intervalle tel que $Q$ $($ $a$ $) < 0$ . Combiné avec le nombre total de racines de $P$ dans le même intervalle donné par le théorème de Sturm, cela donne le nombre de racines de $P$ telles que $Q$ $($ $a$ $) > 0$ et le nombre de racines de $P$ telles que $Q$ $($ $a$ $) < 0$ . ${\style d'affichage (a,b]}$

Voir également

Les références

Basu, Saugata ; Pollack, Richard ; Roy, Marie-Françoise (2006). "Article 2.2.2". Algorithmes en géométrie algébrique réelle (PDF) (2e éd.). Springer . p. 52-57. ISBN 978-3-540-33098-1.
Sturm, Jacques Charles François (1829). "Mémoire sur la résolution des équations numériques". Bulletin des Sciences de Férussac . 11 : 419-425.
Sylvestre, JJ (1853). « Sur une théorie des relations syzygétiques de deux fonctions intégrales rationnelles, comprenant une application à la théorie des fonctions de Sturm, et celle de la plus grande mesure commune algébrique » (PDF) . Phil. Trans. R. Soc. Londres . 143 : 407-548. doi : 10.1098/rstl.1853.0018 . JSTOR 108572 .
Thomas, Joseph Miller (1941). « Le théorème de Sturm pour les racines multiples ». Revue Nationale de Mathématiques . 15 (8) : 391-394. doi : 10.2307/3028551 . JSTOR 3028551 . MR 0005945 .
Heindel, Lee E. (1971), "Algorithmes arithmétiques entiers pour la détermination du zéro réel polynomial", Proc. SYMSAC '71 : 415, doi : 10.1145/800204.806312 , MR 0300434
Panton, Don B.; Verdini, William A. (1981). « Un programme fortran pour appliquer le théorème de Sturm dans le comptage des taux de rendement internes ». J. Financ. Quant. Anal . 16 (3) : 381-388. doi : 10.2307/2330245 . JSTOR 2330245 .
Akritas, Alkiviadis G. (1982). "Réflexions sur une paire de théorèmes de Budan et Fourier". Math. Mag . 55 (5) : 292-298. doi : 10.2307/2690097 . JSTOR 2690097 . MR 0678195 .
Petersen, Paul (1991). « Théorie de Sturm multivariée ». Notes de cours dans Comp. Sciences . Notes de cours en informatique. 539 : 318-332. doi : 10.1007/3-540-54522-0_120 . ISBN 978-3-540-54522-4. MR 1229329 .
Yap, Chee (2000). Problèmes fondamentaux en algèbre algorithmique . Presse de l'Université d'Oxford . ISBN 0-19-512516-9.
Rahman, QI ; Schmeisser, G. (2002). Théorie analytique des polynômes . Monographies de la Société mathématique de Londres. Nouvelle Série. 26 . Oxford : Oxford University Press . ISBN 0-19-853493-0. Zbl 1072.30006 .
Baumol, Guillaume. Dynamique économique , chapitre 12, section 3, « Informations qualitatives sur les racines réelles »
DG Hook et PR McAree, "Using Sturm Sequences To Bracket Real Roots of Polynomial Equations" dans Graphic Gems I (éd. A. Glassner), Academic Press, pp. 416-422, 1990.

Languages

In other projects