Gröbner-basis

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de computeralgebra, de computationele algebraïsche meetkunde en de computationele commutatieve algebra is een Gröbner-basis een bijzonder soort voortbrengende deelverzameling van een ideaal I in de ring K[x1,x2,...,xn] van veeltermen in n veranderlijken over een lichaam K.

Men kan het begrip Gröbner-basis zien als een niet-lineaire veralgemening in meerdere veranderlijken van:

De theorie van Gröbner-basissen voor veeltermringen werd in 1965 ontwikkeld door Bruno Buchberger. Buchberger vernoemde de Gröbner-basissen naar zijn promotiebegeleider Wolfgang Gröbner. De "Association for Computing Machinery" kende Buchberger in 2007 de "Paris Kanellakis Theory and Practice Award" toe voor dit werk.

Een analoog concept voor lokale ringen werd in 1964 onafhankelijk ontwikkeld door Heisuke Hironaka. Hironake noemde zijn constructie standaardbasissen. De analoge theorie voor vrije Lie-algebra's werd in 1962 ontwikkeld door A.I. Shirshov, maar diens werk bleef buiten de Sovjet-Unie grotendeels onbekend.

Monomiale ordening[bewerken]

In bronnen over computeralgebra wordt het woord eenterm meestal gebruikt voor een product van machten van veranderlijken met coëfficiënt 1, dus in de betekenis 'monische eenterm'. De constante 1 is dan de enige eenterm van de nulde graad. Deze terminologie komt overeen met de alternatieve definitie van het Wikipedia-artikel eenterm.

De definitie van een Gröbnerbasis veronderstelt dat op voorhand een monomiale ordening > van K[x1,x2,...,xn] wordt gegeven. Dat is een welordening op de verzameling eentermen die verenigbaar is met de vermenigvuldiging van eentermen in de zin dat als p, q en r eentermen zijn en p > q, dan ook p.r > q.r.[1]

Als een monomiale ordening gegeven is, dan noemen we de leidende term LT(f) van een veelterm f (die niet de nulveelterm is) de term van f waarvan de overeenkomstige eenterm (de term zonder zijn coëfficiënt) groter is dan alle andere eentermen van f.[2]

Voorbeeld van een monomiale ordening[bewerken]

De lexicografische ordening rangschikt eentermen volgens dalende graad in de eerste veranderlijke. Als twee eentermen dezelfde graad hebben in x1, rangschikken we ze volgens dalende graad in de tweede veranderlijke, enzovoort. Als twee eentermen dezelfde graad hebben in alle veranderlijken afzonderlijk, zijn ze aan elkaar gelijk. Voorbeeld

x_1^3x_2^2 > x_1^2x_2^7 > x_1^2x_2^6

Voorbeeld van een leidende term[bewerken]

In de lexicografische ordening is de leidende term LT(g) van de veelterm

g(x_1,x_2) = -2x_1^3x_2^2 + 3x_1^2x_2^7 + 8x_1^2x_2^6 - 1

gelijk aan

-2x_1^3x_2^2.

Definitie[bewerken]

Zij > een monomiale ordening van K[x1,x2,...,xn], en I een ideaal van die ring. Een eindige deelverzameling {g1, ... , gt} van I heet Gröbnerbasis voor I ten opzichte van de ordening > als het ideaal voortgebracht door de leidende termen van de elementen van I ook al wordt voortgebracht door de leidende termen van de gi.[1]

Anders gezegd: een Gröbnerbasis is een eindige verzameling {g1, ... , gt} veeltermen van I zodat voor elke veelterm f van I (behalve 0), LT(f) deelbaar is door minstens één van de LT(gi).[3]

Voorbeeld en tegenvoorbeeld[bewerken]

De nulpunten van f(x,y) vormen de rode parabool; de nulpunten van g(x,y) vormen de drie blauwe verticale rechten. Hun intersectie bestaat uit drie punten.

Zij R = Q[x,y] de ring der veeltermen in twee veranderlijken met rationale coëfficiënten en beschouw het ideaal I = <f,g> voortgebracht door de veeltermen

f(x,y)=x^2-y
g(x,y)=x^3-x

Twee andere elementen van I zijn de veeltermen

h(x,y)=-(x^2+y-1)f(x,y)+x.g(x,y)=y^2-y
k(x,y)=-x.f(x,y)+g(x,y)=xy-x

Als we de lexicografische ordening met x > y hanteren, geldt

\hbox{LT}(f) = x^2
\hbox{LT}(g) = x^3
\hbox{LT}(h) = y^2
\hbox{LT}(k) = xy

Het ideaal voortgebracht door {LT(f),LT(g)} bevat alleen veeltermen die deelbaar zijn door x2 en daar is LT(h) = y2 niet bij; daaruit volgt dat {f, g} geen Gröbnerbasis is voor I.

Daarentegen kan men als volgt nagaan dat {f, k, h} wel degelijk een Gröbnerbasis is voor I.

Merk daartoe op dat f en g, en dus ook h en k en alle andere veeltermen in het ideaal I, de volgende drie nulpunten in het (x,y)-vlak gemeenschappelijk hebben, zoals aangegeven in de figuur: {(1,1),(-1,1),(0,0)}. Die drie punten liggen niet op één lijn, dus I bevat geen enkele veelterm van de eerste graad. Ook kan I geen veeltermen bevatten van de bijzondere vorm

m(x,y)=cx+p(y)

met c een rationaal getal verschillend van 0 en p een veelterm waarin alleen de veranderlijke y voorkomt; immers, een dergelijke veelterm m kan nooit twee verschillende nulpunten hebben met dezelfde waarde voor y (in dit geval de punten (1,1) en (-1,1)).

Uit dit alles volgt dat I behalve de nulveelterm alleen veeltermen bevat waarvan de leidende term minstens graad 2 heeft, en dus is hun leidende term deelbaar door minstens één van het drietal

{x2, xy, y2} = {LT(f),LT(k),LT(h)}.

Dat betekent dat {f, k, h} een Gröbnerbasis is voor I ten opzichte van de lexicografische ordening met x > y.

Eigenschappen[bewerken]

De basisstelling van Hilbert zegt dat alle idealen in K[x1,x2,...,xn] eindig voortgebracht worden. Men kan aantonen dat voor een willekeurige gegeven monomiale ordening ieder niet-triviaal ideaal een Gröbnerbasis heeft. De naam Gröbnerbasis wordt verantwoord door de eigenschap dat iedere Gröbnerbasis een basis (d.w.z., een voortbrengende verzameling) is.[1]

Bronnen, noten en/of referenties
  1. a b c Cox, David; Little, John en O'Shea, Donal, Ideals, Varieties, and Algorithms -- An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer Undergraduate Texts in Mathematics, 3e uitgave 2007
  2. Joswig, Michael en Theobald, Thorsten, Polyhedral and Algebraic Methods in Computational Geometry, Springer Universitext 2013
  3. Cox, David A.; Little, John en O'Shea, Donal, Using Algebraic Geometry, Springer Graduate Texts in Mathematics 185, 2e uitgave 2005

Externe links[bewerken]