Résolution de systèmes polynomiaux

Éric Schost
Eric.Schost@polytechnique.fr

Le but de ce projet est de présenter quelques techniques de résolution de systèmes d'équations polynomiales. En ce qui nous concerne, sur un exemple, nous serons intéressés par la transformation d'un ensemble d'équations de la forme

x²+y²+z² = 1, x²+z² =y, x=z

en un ensemble d'équations équivalentes de la forme

z⁴+

z²-

=0, x=z, y=-2z².

La deuxième forme est manifestement plus sympathique : on y lit qu'il y a 4 solutions complexes (dont 2 réelles), et il n'est pas difficile d'en trouver des approximations numériques. Par comparaison, il est bien moins évident de répondre à ces questions sur la première formulation. Le deuxième système est une base de Gröbner associée aux équations initiales.

On peut considérer comme second exemple le système

54-5y+99z-61xy-50x²-12yz,

1-47x-91xy-47z²-61yz+41y²,

-86+23xy-84x²+19x²y-50xyz+88xz² ;

un des ses bases de Gröbner est de la forme

x - P_x(z), y - P_y(z), Q(z),

où P_x,P_y sont des polynômes en z de degré 11, et Q un polyôme en z de degré 12. On voit donc que le système initial a 12 solutions ; pour en trouver des approximations, il suffit de trouver des approximations des racines de Q, et les injecter dans P_x et P_y. Ce projet demande d'écrire de quoi calculer de telles bases de Gröbner.

1 Description

1.1 Rappel : division euclidienne

Une idée sous-jacente à la notion de base de Gröbner est une généralisation de la division euclidienne (que l'on connaît pour les polynômes en une variable) à des situations en plusieurs variables. Si k est un corps, pour tous F et G de k[X], il existe d'uniques quotient et reste Q,R tels que G=QF+R, avec deg R < degF. L'algorithme de division euclidienne est un processus itératif permettant de calculer le reste R.

Notons degF = D et degG = D' et supposons que D' est au moins égal à D (sinon, il n'y a rien à faire). La boucle élémentaire de la division euclidienne de G par F consiste à réécrire G modulo F de manière à faire disparaître son terme de plus haut degré. Pour cela, on pose la soustraction G-coeff(G,D')/coeff(F,D) X^D'-DF, ce qui fait descendre le degré d'au moins 1. On itère ensuite le procédé jusqu'à ce que le degré descende en dessous de celui de F.

Avec plus de recul, l'idée principale derrière ce procédé consiste à associer aux polynômes F et G des termes de tête, à savoir les termes de plus haut degré. La division avec reste de G par F passe alors par une suite de réécritures : tant que le terme de tête de F divise le terme de tête de G, on peut annuler ce dernier par une combinaison linéaire adéquate. La technologie des bases de Gröbner est une extension de ce processus en plusieurs variables.

1.2 Ordres monomiaux et division avec reste

Pour étendre les techniques de division avec reste, il faut pouvoir associer à tout polynôme un terme de tête. Pour cela, il faut définir une relation d'ordre sur les monômes. On appelle ordre monomial une relation d'ordre < sur les monômes de k[X₁,...,X_n] telle que pour tous monômes n,m,m', 1 < n et m < m' implique nm < nm'. Plus explicitement, soient X^α et X^β deux monômes, avec α=(α₁,...,α_n) et β=(β₁,...,β_n). Des ordres parmi les plus fréquemment utilisés sont les suivants.

Ordre lexicographique (lex).: On dit que X^β< X^α pour l'ordre lexicographique si α_i > β_i pour le premier indice i tel que α_i ≠ β_i. C'est l'ordre du dictionnaire sur les ``mots'' α et β.
Ordre du degré, raffiné par l'ordre lexicographique inverse (grevlex).: On dit que X^β< X^α pour cet ordre si ∑_iβ_i < ∑_i α_i, ou, en cas d'égalité, si α_i < β_i pour le dernier indice i tel que α_i ≠ β_i.

La notion d'ordre monomial permet d'associer à tout polynôme F son terme de tête, c'est le terme correspondant au monôme le plus grand (attention : dans le terme de tête, on prend en compte le coefficient). On peut dès lors écrire un algorithme de division avec reste pour les polynômes à plusieurs variables, qui généralise celui donné dans le cas d'une variable ; étant donnés des polynômes F₁,...,F_s et G, cet algorithme calcule des quotients Q₁,...,Q_s et un reste R tels que G=Q₁F₁ + ⋯ + Q_s F_s + R. Le terme de tête du polynôme F_i est noté L_i, pour i ≤ s.

Poser Q₁ = ⋯ = Q_S = R =0
Tant que G ≠ 0, faire
1. Soit L_G le terme de tête de G
2. Si il existe i tel que L_G est divisible par L_i faire
  - Q_i = Q_i + L_G/L_i
  - G = G - (L_G/L_i) F_i
3. Sinon
  - G=G-L_G
  - R=R+L_G

L'exemple suivant montre cependant que sans prendre de précaution supplémentaire, le reste n'est pas unique (il dépend de l'ordre dans lequel on choisit les diviseurs). Dans Q[X₁,X₂] muni de l'ordre lexicographique, considérons les polynômes F₁=X₁X₂+1,F₂ = X₂²-1 et G=X₁X₂²-X₁ (le trait indique le terme de tête). Si on effectue d'abord la réduction par F₂, on obtient 0. Par contre, si on réduit d'abord par F₁, on obtient comme reste R=-X₂-X₁, qui ne se réduit pas à zéro.

1.3 Bases de Gröbner et algorithme de Buchberger

Dans l'exemple précédent, l'unicité du reste a été mise en défaut par l'existence de R=-X₁-X₂ qui peut s'écrire sous la forme Q₁ F₁ +Q₂ F₂, mais dont le terme de tête n'est divisible ni par le terme de tête de F₁ ni par celui de F₂. La définition d'une base de Gröbner vise précisément à éviter ce genre de phénomène.

Définition. Soit < un ordre monomial sur k[X₁,...,X_n] et F₁,...,F_r des polynômes de k[X₁,...,X_n]. Une famille de polynômes G₁,...,G_s forme une base de Gröbner pour F₁,...,F_s et pour l'ordre < si

tout G_i s'écrit sous la forme ∑_j Q_i,j F_j ;
le terme de tête de tout élément de la forme ∑_i Q_i F_i est divisible par le terme de tête de l'un des G_i.

Cette base est réduite si pour tout i, aucun des monômes de G_i n'est divisible par le terme de tête d'un des G_j, j ≠ i.

On montre que pour tous F₁,...,F_r, il existe une unique base de Gröbner réduite ; en outre, l'algorithme de division par les polynômes {G₁,...,G_s} produit un reste unique, quels que soient les choix effectués : cela permet de généraliser l'algorithme d'Euclide. Enfin, un système d'équations et sa base de Gröbner ont les mêmes ensembles de solutions.

Dans les exemples de l'introduction, la deuxième forme du système est une base de Gröbner pour les équations initiales, pour l'ordre lexicographique. C'est un phénomène général : dans une base lexicographique, on trouve des polynômes en la dernière variable uniquement, en les deux dernières variables, etc ..., ce qui facilite par exemple la résolution numérique, par propagation. Les bases pour l'ordre grevlex n'ont pas cette propriété, mais sont généralement bien plus faciles à calculer.

Soit F un système et G sa base de Gröbner réduite (pour un ordre quelconque). Voici d'autres résultats que l'on peut lire sur G.

F est inconsistant ssi G={1}.
F a un nombre fini de solutions ssi pour tout i, il existe un polynôme de G dont le terme de tête est X_i^α_i.
Si c'est le cas, le nombre de solutions est égal au nombre de monômes qui ne sont divisibles par aucun des termes de tête des éléments de G (attention, on compte ici les solutions avec leurs éventuelles multiplicités).

Il reste à dire comment calculer une base de Gröbner. On passe d'un système F₁,...,F_r à une base de Gröbner par un processus de complétion par l'adjonction de paires critiques, que l'on appelle S-polynômes. Soient F et G deux polynômes de k[X₁,...,X_n], a X^α=a X₁^α₁⋯ X_n^α_n et bX^β=b X₁^β₁⋯ X_n^β_n les termes de tête de F et G. Pour i=1,...,n, soit γ_i=max(α₁,β_i), et notons X^γ= X₁^γ₁⋯ X_n^γ_n. On appelle S-polynôme de F et G le polynôme

X^γ

a X^α

F -

X^γ

b X^β

L'idée derrière cette définition est de forcer l'annulation des termes de tête des deux membres par collision.

À l'aide de cette définition, l'algorithme de Buchberger consiste à adjoindre au système initial de générateurs tous les S-polynômes que l'on peut en déduire, jusqu'à stabilisation du processus. On montre que cet algorithme calcule une base de Gröbner.

Poser G=F
Faire
1. Poser G'=G.
2. Pour p,q dans G', faire
  - Soit R le reste du S-polynôme de p,q par G'
  - Si R≠ 0, faire G=G ∪ {R}.
Jusqu'à ce que G=G'.

À la sortie, la base G n'est pas réduite : on réduit G en considérant successivement tous les éléments g de G, et en réduisant g par G-{g} : si le reste r est différent de g, on remplace g par r dans G (si r=0, on supprime g de G). On montre que le processus s'arrête, et calcule une base réduite.

2 Travail demandé

La première étape à réaliser pour ce projet est l'implantation des algorithmes décrits ci-dessus : calcul d'une base de Gröbner réduite, et calcul du nombre de solutions d'un système, si ce nombre de solutions est fini.

Jusqu'ici, on n'a pas spécifié qui était le corps k : concrètement, on pense à des corps finis Z/pZ (p premier) ou à Q. Pour pouvoir traiter ces deux cas simultanément (et potentiellement n'importe quel autre corps), on écrira du code générique, en utilisant les mécanismes d'héritage. De même, on s'attachera à écrire un code le plus générique possible vis-à-vis de l'ordre monomial utilisé.

Lorsqu'on travaille sur Q, la taille des coefficients "explose" rapidement : il ne suffira pas de travailler avec des int ni des long, et on aura besoin d'entiers en précision arbitraire. Une solution est d'utiliser la bibliothèque BigInteger.

À titre indicatif, vous pourrez tester votre code sur les systèmes cycliques : pour n fixé, on obtient le système cyclique d'ordre n en posant les équations

X₁ + X₂ + ⋯ + X_n	=	0,
X₁ X₂ + X₂ X₃ + X₃ X₄ + ⋯ + X_n X₁	=	0,
X₁ X₂ X₃ + X₂ X₃ X₄ + ⋯ + X_n X₁ X₂	=	0,
	⋮
X₁ X₂ ⋯ X_n-1 + ⋯ + X_n X₁ ⋯ X_n-2	=	0,
X₁ ⋯ X_n	=	1.

Jusqu'à quelle valeur de n pouvez vous effectuer les calculs ?

Enfin, pour aller plus loin, on propose les extensions suivantes :

Changement d'ordre :: l'expérience montre que les bases pour l'ordre lexicographique sont plus "intéressantes" que celles pour l'ordre grevlex, mais plus longues à calculer. Les techniques de changement d'ordre consistent à calculer une base grevlex pour commencer, puis à en déduire une base lexicographique. L'ingrédient essentiel est de l'algèbre linéaire.
Critères de Buchberger et techniques modulaires :: une large part des calculs consiste à réduire des S-polynômes par la base en cours de construction. S'il y a moyen de prédire qu'une réduction donne 0, on peut directement rejeter le S-polynôme en question, et c'est autant de temps de gagné.

Les critères de Buchberger premettent d'effectuer ce type de prédiction. Une autre possibilité, lorsqu'on travaille sur Q, est de commencer par réduire le système modulo un nombre premier p et d'effectuer le calcul modulo p, en gardant trace des réductions à 0.
Isolation des racines réelles :: Enfin, lorsqu'on travaille sur Q, dans le cas où le système a un nombre fini de solutions (complexes), on propose d'écrire un algorithme pour approcher les solutions réelles (il existe également des algorithmes pour trouver les racines complexes, mais ils sont plus délicats à mettre en place). L'ingrédient principal est la règle des signes de Descartes pour les polynômes en une variable.

Références.

Une référence très abordable est le livre de D. Cox, J. Little, D. O'Shea, Ideals, varieties and algorithms, Springer, 1992.

Pour les extensions décrites ci-dessus, on pourra consulter le livre de D. Cox, J. Little, D. O'Shea, Using algebraic geometry, Springer, 1998. Avant d'aborder ces extensions, il est vivement conseillé de prendre contact avec l'auteur du sujet pour obtenir davantage d'explications, et un guide plus précis de la littérature.

Enfin, pour vérifier vos résultats, n'hésitez pas à utiliser un logiciel comme Maple, installé dans les salles informatiques de l'X, qui permet d'effectuer tous ces calculs.

Ce document a été traduit de L^AT_EX par H^EV^EA.