DEA algorithmique
Attention
Pour visualiser convenablement les formules mathématiques sous
netscape, il faut ajouter la ligne suivante à votre fichier
.Xdefaults:
Netscape*documentFonts.charset*adobe-fontspecific: iso-8859-1
et redémarrer netscape.
1 Simplification de systèmes polynomiaux réels univariés
Résoudre les équations suivantes :
ax2+bx+c=0
4x8+48x7+256x6+792x5+1590x4+2196x3+2104x2+1290x+459=0
1.1 Présentation du problème
On cherche le nombre de solutions réelles d'un système composé de
plusieurs égalités et inégalités polynômiales en une indéterminée à
coefficients rationnels, de la forme
P1(x)=...=Pj(x)=0; Q1(x)>0; ...; Qk(x)>0.
On peut remplacer les Pi par leur pgcd P car une racine commune
de ces polynômes est racine de leur pgcd.
Pour résoudre ce système, il suffit de connaître toutes les racines de
P et des Qi.
Pour cela la première opération va consister à isoler les racines des
polynômes P et Qi.
Une racine a d'un polynôme P est isolée si l'on donne
deux nombres rationnels a et b tels que a a
b et si le polynôme P n'a qu'une racine dans l'intervalle
[a,b]. Cet intervalle s'appelle l'intervalle d'isolement de
a. Étant donné une racine isolée d'un polynôme P, on peut
toujours rendre la largeur de son intervalle d'isolement aussi petite
que l'on veut par dichotomie sur l'intervalle d'isolement de sa partie
sans facteurs multiples P/pgcd(P,P'). L'isolement initial
des racines va être rendu possible par les suites de Sturm.
Les racines de P qui sont aussi racines de Qi sont à éliminer. On
travaille donc sur Pk avec
On isole les racines de Pk avec un intervalle d'isolement
suffisamment petit pour qu'il ne contienne pas de racine d'un des
Qi, c'est-à-dire que les intervalles d'isolement des racines de
Pk et des racines des Qi sont disjoints.
Si [a, b] est l'intervalle d'isolement d'une racine de Pk, alors
on compte cette racine si Qi(a) > 0.
1.2 Nombres de racines réelles d'un polynôme à coefficients entiers: sui
tes de Sturm
Rappel de la méthode
Soit P un polynôme à coefficients entiers sans facteurs
multiples. La suite de Sturm associée au polynôme P est la
suite de polynômes de degrés décroissants définie de la façon
suivante :
P0(x)=P(x), P1(x)=P'(x) Pi+2(x)=-reste(Pi+1(x),Pi(x))
avec i k deg(P).
où reste(F,G) désigne le reste de la division euclidienne de F par
G et Pk est un polynôme constant.
Quel est le lien entre la suite de Sturm associée à un polynôme P et
la suite des termes successifs de l'application de l'algorithme
d'Euclide à P et P'?
Soit y un nombre réel qui n'est pas une racine du polynôme P, la
variation au point y de la suite de Sturm associée à P,
notée V(y), est le nombre de changements de signe (sans tenir compte
des zéros) de la suite P0(y), P1(y), ..., Pk(y).
Si a et b sont deux nombres réels tels que a < b et ne sont
pas des racines réelles de P, alors le nombre de racines réelles de
P dans l'intervalle [a,b] est V(a)-V(b).
On peut étendre la méthode à a=-¥ et b=¥ en prenant pour
V(¥) le nombre de changements de signe entre les coefficients
principaux des éléments de la suite de Sturm, et pour V(-¥) le
même nombre après avoir changé les signes des coefficients principaux
des éléments de degré impair. En particulier, le nombre de racines
réelles est une fonction des signes des coefficients principaux.
Pour commencer la recherche des racines réelles d'un polynôme, on
utilise les bornes fournies par le résultat suivant : soit a
une racine du polynôme P, alors
|
|a|
max |
æ
ç
ç
ç
ç
ç
è |
|
½
½
½
½ |
|
|
|
½
½
½
½ |
,
|
½
½
½
½ |
|
|
|
½
½
½
½ |
|
,
...,
|
½
½
½
½ |
|
|
|
½
½
½
½ |
|
,
|
½
½
½
½ |
|
|
|
½
½
½
½ |
|
ö
÷
÷
÷
÷
÷
ø |
et
|
|a|
2 max |
æ
ç
ç
ç
ç
ç
è |
|
½
½
½
½ |
|
|
|
½
½
½
½ |
,
|
½
½
½
½ |
|
|
|
½
½
½
½ |
|
,
...,
|
½
½
½
½ |
|
|
|
½
½
½
½ |
|
,
|
½
½
½
½ |
|
|
|
½
½
½
½ |
|
ö
÷
÷
÷
÷
÷
ø |
.
|
Applications
Calculez le nombre de solutions réelles du deuxième polynôme
ci-dessus, ainsi que du polynôme suivant :
x14+3x13+3x12+x11-x3-3x2-3x-1
pour cela vous déterminerez tout d'abord la suite de Sturm vous-même
et examinerez son comportement, puis vous utiliserez la fonction de la
librairie qui effectue ce travail.
Appliquez cet algorithme au polynôme W(x)=(x+1)(x+2)...(x+20),
puis au polynôme W(x)=W(x)+2-23x19. Que constatez-vous?
Quels sont les intervalles d'isolation des racines ?
Ecrire une fonction suiteSturm(f) qui calcule la suite de Sturm de f,
une fonction nb_racines(f,a,b) qui calcule le nombre de racines
réelles dans l'intervalle [a,b[, et une fonction isole(f,a,b,e)
qui calcule des intervalles d'isolation des racines de f comprises entre
a et b avec une précision e.
2 Racines d'un polynôme multivarié, bases de Gröbner
Consulter l'aide en ligne de la fonction gbasis.
Déterminer une base de Gröbner de l'idéal engendré par les trois
polynômes
g1=x3yz-xz2, g2=xy2z-xyz, g3=x2y2-z
pour les ordres plex (lexicographique) et tdeg
(lexicographique inverse) et les variables ordonnées x > y >
z. En déduire l'intersection de ces trois surfaces.
Soit le système suivant :
g1=x2+y2+z2+1, g2=x2+2y2-yz-1, g3=x+z3-1
Déterminer une base de Gröbner de l'idéal engendré par ces trois
polynômes pour les ordres plex et tdeg et les variables ordonnées
x > y > z, puis pour l'ordre tdeg et les variables ordonnées y >
z > x.
On ajoute le polynôme x3+2xy-2 à ce système, déterminer une base
standard du nouveau système.
Consulter l'aide en ligne des fonctions solvable et finite.
Appliquez-les aux exemples précédents.
Valérie Ménissier-Morain et Philippe Aubry
Monday 15 November 1999
This document was translated from LATEX by HEVEA.