théorème de Sturm

Imaginez la courbe d'un polynôme qui traverse plusieurs fois l'axe horizontal. Sans résoudre l'équation, on voudrait savoir combien de traversées se cachent entre deux bornes. La suite de Sturm transforme ce problème en un comptage de signes.

Pour un polynôme sans racine multiple, on évalue une même liste de polynômes aux deux extrémités de l'intervalle. La diminution du nombre de changements de signe donne exactement le nombre de racines réelles situées à l'intérieur.

Le théorème de Sturm est un résultat d'algèbre qui dénombre les racines réelles d'un polynôme sur un intervalle. Dans le cadre de la définition source, le polynôme P est à coefficients réels et toutes ses racines sont simples. La suite commence par P, puis par sa dérivée P′. Chaque terme suivant est l'opposé du reste de la division euclidienne des deux termes précédents. Le procédé s'arrête lorsqu'un reste constant non nul est atteint.

Pour un réel x qui n'est pas une racine de P, on évalue tous les termes de la suite en x. On omet les éventuelles valeurs nulles, puis on compte les changements entre deux signes consécutifs. Ce nombre est noté V(x). Si les deux bornes a et b vérifient a < b et ne sont pas des racines de P, le nombre de racines dans l'intervalle ouvert ]a, b[ vaut $V(a)-V(b)V(a)-V(b)$.

En répétant le comptage sur des sous-intervalles, on sépare les racines : chaque intervalle qui donne 1 en contient exactement une. Le théorème localise et compte ; une méthode itérative intervient ensuite si l'on veut une valeur numérique de cette racine.

Soit P un polynôme réel dont toutes les racines sont simples. On pose S₀ = P et S₁ = P′, puis, pour chaque indice i, S_i+1 est l'opposé du reste de la division de S_i−1 par S_i.

Si a < b et si P(a) et P(b) sont non nuls, alors le nombre de racines réelles de P dans ]a, b[ est $V(a)-V(b)V(a)-V(b)$. Ici, V(x) désigne le nombre de changements de signe dans S₀(x), S₁(x), … jusqu'au dernier terme constant, après omission des valeurs nulles.

Le domaine est celui des polynômes à coefficients réels. Dans la version retenue ici, P ne possède que des racines simples, la borne a est strictement inférieure à la borne b et aucune borne n'annule P. Ces trois points se vérifient avant le comptage. Les divisions euclidiennes doivent être poursuivies avec l'opposé de chaque reste jusqu'au terme constant non nul.

Si une borne est une racine, la simple liste de signes contient un zéro et la lecture directe devient ambiguë pour l'intervalle ouvert. Il faut remplacer cette borne par un nombre voisin situé à l'intérieur de l'intervalle, suffisamment proche pour ne franchir aucune autre racine, puis refaire le comptage. Si P a une racine multiple, P et P′ ont un facteur commun : la chaîne décrite dans la source n'atteint plus le même terme constant. Il faut d'abord traiter ce facteur commun ou employer une version généralisée du théorème.

Prenons le polynôme P défini par P(x) = x³ − x et l'intervalle ]−2; 0,5[. Les données sont donc a = −2 et b = 0,5. Les trois racines −1, 0 et 1 sont simples, mais leur position ne sera utilisée qu'au contrôle final.

1. La dérivée est S₁(x) = 3x² − 1. L'opposé du reste de la division de P par S₁ donne S₂(x) = 2x/3. La division suivante donne le terme constant S₃(x) = 1.

2. À gauche, les valeurs sont P(−2) = −6, S₁(−2) = 11, S₂(−2) = −4/3 et S₃(−2) = 1. La succession −, +, −, + comporte donc V(−2) = 3 changements.

3. À droite, les valeurs sont P(0,5) = −3/8, S₁(0,5) = −1/4, S₂(0,5) = 1/3 et S₃(0,5) = 1. La succession −, −, +, + comporte V(0,5) = 1 changement. La figure rend ces deux comptages visibles.

4. Le théorème donne 3 − 1 = 2 racines dans ]−2; 0,5[. Contrôle refaisable : P(x) = x(x − 1)(x + 1), donc −1 et 0 appartiennent à l'intervalle, tandis que 1 reste à l'extérieur.

Pour savoir si un intervalle contient une racine, on construit une seule fois la suite de Sturm, puis on compare les variations de signes aux deux bornes. Une différence nulle exclut toute racine intérieure ; une différence égale à 1 en garantit exactement une.

Pour séparer plusieurs racines, on découpe l'intervalle et l'on recommence le comptage sur chaque morceau. Le bon critère d'arrêt est l'obtention d'intervalles qui contiennent chacun une seule racine.

Pour obtenir ensuite des décimales, le comptage ne suffit plus. Une méthode numérique itérative prend le relais sur chaque intervalle isolé ; elle est préférable lorsque la question porte sur la valeur approchée plutôt que sur le nombre exact de racines.

Le comptage de Sturm et le calcul numérique d'une racine. Le premier renvoie un entier exact pour un intervalle ; le second fournit une valeur approchée. Dans l'exemple, Sturm établit qu'il existe deux racines dans ]−2; 0,5[, tandis qu'une méthode itérative servirait à approcher séparément chacune d'elles.

Localiser et exhiber une factorisation. Le théorème peut certifier la présence de racines sans écrire P comme produit de facteurs. La factorisation x(x − 1)(x + 1) n'est utilisée dans l'exemple que comme contrôle indépendant, pas comme étape de la suite de Sturm.

Racine sur une borne. Si P(a) = 0 ou P(b) = 0, un zéro apparaît dans la liste des signes et la formule pour l'intervalle ouvert ne s'applique pas directement sous la convention présentée. Il faut choisir une borne voisine qui n'annule pas P sans franchir d'autre racine.

Racine multiple. La définition source suppose toutes les racines simples. Si P et P′ ont un facteur commun non constant, cette hypothèse échoue et le dernier reste attendu peut être nul au lieu d'être constant non nul. Il faut isoler le facteur commun ou choisir une formulation de Sturm qui traite les multiplicités.

Mauvais signe du reste. Employer le reste lui-même au lieu de son opposé change les variations et peut fausser le résultat. Pour P(x) = x³ − x, le troisième terme est bien 2x/3, et non −2x/3.

Résultat exact, valeurs encore inconnues. Une différence de variations égale à 2 certifie deux racines, mais ne donne aucune décimale. Il faut ensuite séparer les deux racines dans des sous-intervalles, puis appliquer une méthode itérative à chacune.

La méthode de Newton prolonge naturellement la séparation obtenue par Sturm : elle montre comment approcher numériquement une racine déjà isolée.