Rappels sur les corps réels clos

Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Algorithme de Sturm

Manh-Linh Nguyen

Cours « Corps réels clos et structures o -minimales »

23 avril 2020

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Résumé

1 Rappels sur les corps réels clos

2 Théorème de Sturm

3 Application

4 Résoudre un système d’équations polynomiales

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Un corps ordonné R est réel clos s’il satisfait l’une des conditions
équivalentes suivantes.
1 R n’admet pas d’extension algébrique ordonnée.
2 Tout élément positif de R a une racine carrée, et tout polynôme de
degré impaire dans R [X ] a une racine.
p p
3 12 / R , et R ( 1) est algébriquement clos.

Si R est réel clos, la structure (R, +, , ·, 0, 1, <) est o-minimale.

Si R est ordonné, char R = 0. Ainsi, si f 2 R[X ], on a équivalence
p
1 f est séparable (i.e. ses racines dans R ( 1) sont simples).
0 ⇥
2 gcd(f , f ) 2 R .
3 f est sans facteur carré.

Théorème des valeurs intermédiaires. Si R est réel clos,

f 2 R[X ], u < v 2 R et f (u)f (v ) < 0, alors il existe x 2 (u, v ) tel
que f (x) = 0.

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Suite de Sturm
Soient u < v 2 R, et f 2 R[X ] sans facteur carré.
On veut compter le nombre de racines de f dans [u, v ].
Définition
Une suite de Sturm pour f sur [u, v ] est une suite de polynômes

S = (f = f0 , f 0 = f1 , . . . , fm )

satisfaisant les conditions suivantes.

1 fm 2 R ⇥ .
2 Il n’existe pas de x 2 [u, v ] et 0 6 j 6 m 1 tels que
fj (x) = fj+1 (x) = 0.
3 Si fj (x) = 0 pour x 2 [u, v ] et 1 6 j 6 m 1, alors
fj 1 (x)fj+1 (x) < 0.
4 fj (u) 6= 0 et fj (v ) 6= 0 pour tout 0 6 j 6 m.
Manh-Linh Nguyen Algorithme de Sturm
 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

L’énoncé du théorème

Soient S = (f0 , . . . , fm ) une suite de polynômes dans R[X ], et x 2 R tels

que fj (x) 6= 0 pour tout 0 6 j 6 m.

Définition
La variation de signes de S en x et

WS (x) := #{0 6 j 6 m 1 : fj (x)fj+1 (x) < 0}.

Théorème (Sturm)
Si S est une suite de Sturm pour f sur [u, v ], le nombre de racines de f
sur [u, v ] est égal à WS (u) WS (v ).

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

La preuve du théorème

Soient ↵1 < · · · < ↵r toutes les racines des f0 , . . . , fm 1 sur [u, v ].

Quitte à subdiviser u = u0 < u1 < · · · < ur = v , avec
ui 1 < ↵i < ui , on peut supposer que r = 1.
u = u0 ↵1 u1 ↵2 u2 ur 1 ↵r ur = v
...
1 1 1 1 1 1 1 1

Posons ↵ := ↵1 . (Rappel : fm 2 R ⇥ ).
Soit J := {0 6 j 6 m 1 : fj (↵) = 0}. Si j 2
/ J, on aura
fj (u)fj (v ) > 0 par TVI.
Si j 2 J et j > 0, on aura fj 1 (↵)fj+1 (↵) < 0. De plus, j 1,
j +12 / J, donc fj 1 (u)fj 1 (v ) > 0 et fj+1 (u)fj+1 (v ) > 0.
Si 0 2 J, alors f (u)f (v ) < 0 et f 0 ne change pas sa signe sur [u, v ].
Ainsi f est strictement monotone sur [u, v ]. Dans les deux cas,
f (u)f 0 (u) < 0 et f (v )f 0 (v ) > 0.
Manh-Linh Nguyen Algorithme de Sturm
 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Les chemins bleus indiquent que les deux extrémités ont même signe. Les
chemins rouges indiquent que les deux extrémités ont des signes
opposées.
Si 0 2 J j 2 J, j > 0 j0 2
/J

f0 (u) f1 (u) ... fj 1 (u) fj (u) fj+1 (u) ... fj 0 (u) ...

f0 (v) f1 (v) ... fj 1 (v) fj (v) fj+1 (v) ... fj 0 (v) ...

Si f (↵) = 0 (i.e. 0 2 J), WS (u) WS (v ) = |J| (|J| 1) = 1.

Si 0 2
/J j 2 J, j > 0 j0 2
/J

f0 (u) ... fj 1 (u) fj (u) fj+1 (u) ... fj 0 (u) ...

f0 (v) ... fj 1 (v) fj (v) fj+1 (v) ... fj 0 (v) ...

Si f (↵) 6= 0 (i.e. 0 2
/ J), WS (u) WS (V ) = |J| |J| = 0.
Manh-Linh Nguyen Algorithme de Sturm
 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

L’algorithme de Sturm
Comment construire une suite de Sturm pour f ? En effet, la construction
d’une telle suite ne dépend pas en général de l’intervalle [u, v ].
Théorème (Algorithme de Sturm)
Soit S = (f0 , f1 , . . . , fm ) la suite de polynômes donnée par

f0 = f , f1 = f 0 ,
fk = rem(fk 2 , fk 1 ) pour tout k > 2 ;

où

rem(p, q) designe le reste dans la division euclidienne de p par q,

m est le plus petit entier tel que fm 2 R ⇥ .

Si fj (u) 6= 0 et fj (v ) 6= 0 pour tout 0 6 j 6 m, alors S est une suite de

Sturm pour f sur [u, v ].

L’algorithme se termine, car f est séparable.

Manh-Linh Nguyen Algorithme de Sturm
 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Vérification de l’algorithme

fm 2 R ⇥ . C’est la construction de S.
Il n’existe pas de x 2 [u, v ] et 0 6 j 6 m 1 tels que
fj (x) = fj+1 (x) = 0. Sinon, soit (x, j) un contre-exemple avec j plus
petit. Si j > 0, écrivons fj 1 = fj q fj+1 , où q 2 R[X ], qui implique
que fj 1 (x) = fj (x) = 0, contradiction. Si j = 0, f (x) = f 0 (x) = 0,
qui contradit la séparabilité de f .
Si fj (x) = 0 pour x 2 [u, v ] et 1 6 j 6 m 1, alors
fj 1 (x)fj+1 (x) < 0. En effet, si fj 1 = fj q fj+1 , où q 2 R[X ], alors
fj 1 (x) = fj+1 (x) 6= 0 selon la partie précédente.
fj (u) 6= 0 et fj (v ) 6= 0. C’est la construction de S.

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Isolation des racines

Soit f 2 R[X ]. On veut isoler les racines de f dans R, c’est-à-dire trouver

les intervalles, sur chacun desquels f a une unique racine. Cela donnera
une approximation rugueuse des racines de f .
On peut effectivement calculer gcd(f , f 0 ) enQutilisant l’algorithme
r
d’Euclide. Soit rad(f ) := gcd(ff ,f 0 ) . Si f = a i=1 Prdr , avec Pi 2 R[X ]
unitaires, irréducibles, deux-à-deux distincts, di > 1, et a 2 R ⇥ , alors
r
Y
rad(f ) = Pr .
i=1

Ainsi, rad(f ) est sans facteur carré, et les racines de f sont celles de
rad(f ). On suppose qu’alors f est unitare et sans facteur carré.

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Isolation des racines

Lemme (Borne de Cauchy)
1
Soit f = X n + a1 x n + · · · + an 2 R[X ]. Si ↵ 2 R est une racine de f ,

|↵| < 1 + |a1 | + · · · + |an |.

En effet, si |↵| > 1, on aura

1 1
|↵|n = |↵n | = | a1 ↵ n ··· an | 6 |a1 ||↵|n + · · · + |an |
n 1 n 1
6 |↵| (|a1 | + · · · + |an |) < |↵| (1 + |a1 | + · · · + |an |).
d’où le résultat. p
Remarque. La borne est valable pour les racines dans C = R( 1).
Soit S = (f0 , f1 , . . . , fm ) la suite associée à f construite par l’algorithme
de Sturm. Soit M > 0 la borne de Cauchy de f . Quitte à augmenter M si
nécessaire, tel que fj (±M) 6= 0 pour tout 0 6 j 6 m, on obtient
#{x 2 R : f (x) = 0} = WS ( M) WS (M).
Manh-Linh Nguyen Algorithme de Sturm
 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Isolation des racines

On suppose que u < v 2 R, et fj (u), fj (v ) 6= 0 pour tout 0 6 j 6 m.

Pour isoler les racines de f sur un intervalle [u, v ], on applique
l’algorithme suivant.
1 Si WS (u) WS (v ) = 0, jeter l’intervalle et terminer.
Si WS (u) WS (v ) = 1, garder l’intervalle et terminer.
Si WS (u) WS (v ) > 2,
u+v
2 Compter w := 2 .

3 Perturber w tel que fj (w ) 6= 0 pour tout 0 6 j 6 m.

4 Appliquer l’algorithme à [u, w ] et [w , v ].

On obtient des intervalles {[ui , vi ]} tels que toute racine de f appartient

à exactement l’un de ces intervalles. De plus, comme fm (ui ) = fm (vi ), on
a nécessairement f (ui )f (vi ) < 0.

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Raffinement des racines

Étant donné un intervalle [u, v ] sur lequel f a exactement une racine x,
est f (u)f (v ) < 0, on peut calculer ↵ avec une précision arbitraire.
Methode de bisection.
u+v
1 Posons x := 2 .

2 Si f (x) = 0, terminer l’algorithme.

3 Si f (x)f (u) < 0. Répéter l’algorithme pour l’intervalle [u, u+v
2 ].
Sinon répéter l’algorithme pour l’intervalle [ u+v
2 , v ].
Après n itérations, la racine estimée est x, avec une erreur de "n 6 v
2n
u
.
Methode de Newton-Raphson. Soit xold 2 [u, v ] quelconque.
1 xnew := xold f (xold )/f 0 (xold ).
2 Répéter l’algorithem avec xnew en tant que xold .
max |f 00 |
2
Après n itérations, l’erreur "n satisfait "n 6
[u,v ]
2 min |f 0 | "n 1 .
[u,v ]

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Exemple (à l’aide de Maple)

On veut trouver les racines de f = X 6 4X 3 + X 2 sur R, avec
tolérence d’érreur 10 4 .
Si |x| > 2, |x|6 > 4|x|3 + |x| + 2. Donc les racines de f sont contenues
dans ( 2, 2).
Calculons une suite de Sturm S = (f0 , f1 , . . . , f5 ).

f0 = f = X 6 4X 3 + X 2,
0 5 2
f1 = f = 6X 12X + 1,
5
f2 = rem(f0 , f1 ) = 2X 3 X +2
6
25 3
f3 = rem(f1 , f2 ) = 18X 2 X+ ,
24 2
92687 5159
f4 = rem(f2 , f3 ) = X
93312 2592
12568084416
f5 = rem(f3 , f4 ) = .
175324081

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Exemple (à l’aide de Maple)

f0 ( 2) f1 ( 2) f2 ( 2) f3 ( 2) f4 ( 2) f5 ( 2)
92 239 ⇡ 12 ⇡ 76 ⇡ 4 ⇡ 72
f0 (2) f1 (2) f2 (2) f3 (2) f4 (2) f5 (2)
32 145 ⇡ 16 ⇡ 71 ⇡ 0.004 ⇡ 72
Le nombre des racines de f est WS ( 2) WS (2) = 3 1 = 2.
Pour isoler les deux racines de f , calculons

f0 (0) f1 (0) f2 (0) f3 (0) f4 (0) f5 (0)

2 1 2 ⇡ 1.5 ⇡ 2 ⇡ 72

D’où WS (0) = 2, WS ( 2) WS (0) = WS (0) WS (2) = 1.

Ainsi, une racine de f est dans ( 2, 0), et l’autre racine est dans (0, 2).

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Exemple (à l’aide de Maple)

Sur chacun des intervalles ( 2, 0) et (0,

⌃ 2), on applique
⌥ bisection.
L’érreur est " 6 22n . Il nous faut donc log2 102 4 = 15 itérations.

n 1 2 3 ... 15
u 2 1 1 ... 0.8517 . . .
v 0 0 0.5 ... 0.8516 . . .
xn 1 0.5 0.75 ... 0.8516 . . .
f (xn ) 2 1.9844 . . . 0.8845 . . . ... 0.0005 . . .
n 1 2 3 ... 15
u 0 1 1.5 ... 1.6001 . . .
v 2 2 2 ... 1.6002 . . .
xn 1 1.5 1.75 ... 1.6002 . . .
f (xn ) 4 2.6094 . . . 7.3054 . . . ... 0.0015 . . .
On trouve deux racines approximées : 0.8516 et 1.6002.

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Base de Gröbner

La base de Gröbner nous permet de résoudre un système

d’équations polynomiales à plusieurs variables en triangularisant le
système (rappelez l’élimination de Gauss).
Géométriquement, résoudre un système f1 = · · · = fm = 0 (où
f1 , . . . , fm 2 R[X1 , . . . , Xn ] est équivalent à trouver les points de R n
annulés par les éléments d’ideal

I = (f1 , . . . , fm ) ✓ R[X1 , . . . , Xn ].

On veut trouver un « joli » système de générateurs {g1 , . . . , gr }

pour I . Par exemple, gr 2 R[Xn ], gr 1 2 R[Xn 1 , Xn ], . . . En suite,
on peut commencer par trouver les racines de gr (qui est un
problème « traité »), puis gr 1 , . . .
Pour ce faire, il suffit d’appliquer l’algorithme de Buchberger à I ,
muni de l’ordre lexicographique sur les monômes de R[X1 , . . . , Xn ].

Manh-Linh Nguyen Algorithme de Sturm

 Rappels sur les corps réels clos
Théorème de Sturm
Application
Résoudre un système d’équations polynomiales

Exemple
On veut résoudre le système
8
2 2 2
>
<x + y + z =4
2 2
x + 2y =5
>
:
xz = 1.

Un « joli » système de générateurs (dit base de Gröbner) pour

l’idéal I = (x 2 + y 2 + z 2 4, x 2 + 2y 2 5, xz 1) ✓ R[x, y , z] est

{x + 2z 3 3z, y 2 z2 1, 2z 4 3z 2 + 1}.

On peut résoudre 2z 4 3z 2 + 1 = 0, puis y 2 z 2 1 = 0, puis

x + 2z 3 3z = 0. Il y a 8 solutions (x, y , z), à savoir
p p p p
(±1, ± 2, 1), (± 2, ± 6/2, 1/ 2).

Consultez Chapitres 1 et 2 de [D. A. Cox, J. Little, D. O’Shea, Using

Algebraic Geometry, Graduate Texts in Mathematics, Springer (1998)].
Manh-Linh Nguyen Algorithme de Sturm