www.wikidata.de-de.nina.az

Gröbnerbasis Eine nach Bruno Buchberger 1965 bzw Standardbasis nach Heisuke Hironaka 1964 ist ein endliches Erzeugendens

Gröbnerbasis

Eine Gröbnerbasis (nach Bruno Buchberger, 1965) bzw. Standardbasis (nach Heisuke Hironaka, 1964) ist ein endliches Erzeugendensystem zu einem Ideal im Polynomring über dem Körper , das besonders gut dafür geeignet ist, zu entscheiden, ob ein gegebenes Polynom zum Ideal gehört oder nicht.

Buchberger entwickelte diese 1965 in seiner Dissertation bei Wolfgang Gröbner und benannte sie nach ihm.

Motivation: Idealzugehörigkeitsproblem und verallgemeinerte Polynomdivision Bearbeiten

Das Idealzugehörigkeitsproblem Bearbeiten

Es sei , also das Ideal von den Polynomen erzeugt, dann gehört ein Polynom genau dann zu , wenn sich als Linearkombination

mit Polynomen schreiben lässt.

Man kann nun versuchen, so eine Darstellung mit Hilfe der Polynomdivision mit Rest zu finden, indem man so lange dividiert, bis der erhaltene Rest verschwindet und damit die Division aufgeht:

Dabei treten aber zwei Probleme auf:

  1. Bei multivariaten Polynomen lassen sich die Terme nicht mehr ohne Weiteres „der Größe nach“ ordnen, was für die Polynomdivision aber notwendig ist.
  2. Können wir denn überhaupt sicher sein, dass durch wiederholte Polynomdivision immer der Rest 0 erscheint?

Das erste Problem lässt sich recht einfach lösen, indem eine Monomordnung gewählt wird. Dann können die Terme jedes Polynomes nach dieser Ordnung angeordnet werden; vor allem können wir nun vom Leitterm eines Polynoms sprechen, also des bezüglich der Monomordnung größten Monoms mit seinem Koeffizienten. Als Nachteil bleibt, dass die Anordnung der Monome und auch das Ergebnis der Polynomdivisionen von der Wahl der Monomordnung abhängen.

Das zweite Problem ist schwieriger, denn es ist tatsächlich nicht lösbar, wenn die erzeugenden Polynome fest vorgegeben sind. Es kann nur gelöst werden, indem das Erzeugendensystem passend geändert wird. Eine Gröbnerbasis stellt sich als ein geeignetes Erzeugendensystem heraus.

Verallgemeinerte Polynomdivision Bearbeiten

Die Aufgabe der verallgemeinerten Polynomdivision ist nun also: Für ein Polynom und mehrere Polynome sollen Polynome gefunden werden, die die Gleichung

erfüllen.

Dazu bietet sich folgendes Vorgehen an:

  1. Beginne mit .
  2. Falls , brich ab, sonst vergleiche der Reihe nach alle , ob sie teilen.
  3. Falls etwa , so ersetze durch und durch und gehe zu Schritt 2.
  4. Falls von keinem geteilt wird, so ersetze durch und durch und gehe zu Schritt 2.

Dann ist in jedem Schritt die Gleichung

erfüllt, und schließlich, wenn , ist die gewünschte Darstellung gefunden.

Mit dieser Division haben wir das Problem wie gewünscht auf ein kleineres Polynom reduziert, denn es ist genau dann, wenn . Falls , ist das klar, und . Ist aber , können wir auf diesem Weg nicht entscheiden, ob oder :

Beispiel: Seien , und . Testet man die erzeugenden Polynome der Reihe nach (also in aufsteigender Reihenfolge der Indizes) und wendet die beschriebene Division an, erhält man:

Offenbar gilt aber , also auch (nämlich ). Man kann also im Allgemeinen aus nicht folgern, dass und damit gilt.

Definition Bearbeiten

Ein Erzeugendensystem von ist eine Gröbnerbasis (bezüglich einer Monomordnung ) von , falls für jedes Polynom ein existiert, dessen Leitmonom das Leitmonom von teilt.

Eine Gröbnerbasis heißt reduziert, falls alle normiert sind, und kein Monom von durch die Leitterme der anderen Gröbnerbasispolynome dargestellt werden kann, also kein Monom von in liegt. Man kann zeigen, dass jedes Ideal (für eine gegebene Monomordnung) eine eindeutig bestimmte reduzierte Gröbnerbasis besitzt.

Anwendungen Bearbeiten

Das Konzept von Gröbnerbasen gibt zunächst eine Lösung des Idealzugehörigkeitsproblems. Damit verbunden lassen sich aber auch andere Probleme lösen (oder zumindest vereinfachen).

Lösung des Idealzugehörigkeitsproblems Bearbeiten

Wird mit dem oben beschriebenen Verfahren eine nicht weiter reduzierbare Darstellung

bezüglich einer Gröbnerbasis des Ideals gefunden, so gilt genau dann, wenn . Da aber eine Gröbnerbasis ist, gilt das wiederum genau dann, wenn , da nach Annahme kein Leitmonom eines das Leitmonom von teilt.

Mit dem Buchberger-Algorithmus können Gröbnerbasen berechnet werden. Damit ist das Problem, ob ein Polynom zu einem Ideal gehört oder nicht, von Computeralgebrasystemen lösbar.

Beispiel: Wenn wie im Beispiel oben die erzeugenden Polynome gegeben sind, sowie , dann hatte die Polynomdivision Rest geliefert.

Wenden wir zunächst den Buchberger-Algorithmus auf dieses Beispiel an, so erhalten wir die (nicht reduzierte) Gröbnerbasis von . Bezüglich dieses Divisors ist die Division hier noch nicht abgeschlossen, denn es ist mit :

Wir sehen hier auch, dass die Darstellung bezüglich der Gröbnerbasis nicht eindeutig ist (da ), sondern von der Reihenfolge der erzeugenden Polynome und der gewählten Monomordnung abhängt.

Polynomiale Gleichungssysteme Bearbeiten

Ein polynomiales Gleichungssystem besteht aus endlich vielen Gleichungen , wobei gegebene Polynome in Unbestimmten über einem Körper und deren gemeinsame Nullstellen gesucht sind. Die Lösungsmenge eines solchen Gleichungssystems beschreibt eine algebraische Varietät. Diese ist offenbar gleich , wobei das von den Polynomen erzeugte Ideal ist.

Soll ein bestimmtes polynomiales Gleichungssystem gelöst werden, genügt es also das Ideal zu betrachten, das von den Polynomen erzeugt wird. Dann kann es hilfreich sein, mit Hilfe des Buchberger-Algorithmus und einer geeigneten lexikographischen Monomordnung eine reduzierte Gröbnerbasis zu finden. Dann bleibt zwar das Problem, die Nullstellen dieser Polynome zu finden (z. B. näherungsweise durch numerische Verfahren), aber die zu untersuchenden Polynome haben immerhin eine kleinere Anzahl an Variablen und kleineren Grad.

Beispiel: Welche Lösungen hat das folgende Gleichungssystem?

Mit Hilfe des Computers erhält man für die lexikographische Monomordnung die (reduzierte) Gröbnerbasis und . Die gesuchten Lösungen sind also genau die Lösungen des einfacheren Gleichungssystems

Und wir sehen, dass die Lösungsmenge aus nur zwei Punkten besteht: (die zwei weiteren Lösungen sind in nicht enthalten).

Gleichheit von Idealen und algebraischen Varietäten Bearbeiten

Da (zu einer gegebenen Monomordnung) die reduzierte Gröbnerbasis eines Ideals eindeutig bestimmt ist, kann die Gleichheit von Idealen untersucht werden, indem (zu irgendeiner Monomordnung) die reduzierten Gröbnerbasen gebildet werden. Die Ideale sind genau dann gleich, wenn diese reduzierten Gröbnerbasen gleich sind.

Auf diese Weise kann man auch rein rechnerisch die Gleichheit von algebraischen Varietäten untersuchen, da diese durch ihre erzeugenden Ideale eindeutig bestimmt sind. Sind die reduzierten Gröbnerbasen gleich, dann sind die erzeugenden Ideale und damit auch die erzeugten Varietäten gleich.

Literatur Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine Grobnerbasis nach Bruno Buchberger 1965 bzw Standardbasis nach Heisuke Hironaka 1964 ist ein endliches Erzeugendensystem zu einem Ideal I displaystyle I im Polynomring K X 1 X n displaystyle K X 1 ldots X n uber dem Korper K displaystyle K das besonders gut dafur geeignet ist zu entscheiden ob ein gegebenes Polynom zum Ideal gehort oder nicht Buchberger entwickelte diese 1965 in seiner Dissertation bei Wolfgang Grobner und benannte sie nach ihm Inhaltsverzeichnis 1 Motivation Idealzugehorigkeitsproblem und verallgemeinerte Polynomdivision 1 1 Das Idealzugehorigkeitsproblem 1 2 Verallgemeinerte Polynomdivision 2 Definition 3 Anwendungen 3 1 Losung des Idealzugehorigkeitsproblems 3 2 Polynomiale Gleichungssysteme 3 3 Gleichheit von Idealen und algebraischen Varietaten 4 LiteraturMotivation Idealzugehorigkeitsproblem und verallgemeinerte Polynomdivision BearbeitenDas Idealzugehorigkeitsproblem Bearbeiten Es sei I g 1 g n K X 1 X k displaystyle I g 1 ldots g n subseteq K X 1 dots X k nbsp also das Ideal I displaystyle I nbsp von den Polynomen g 1 g n displaystyle g 1 ldots g n nbsp erzeugt dann gehort ein Polynom f displaystyle f nbsp genau dann zu I displaystyle I nbsp wenn sich f displaystyle f nbsp als Linearkombination f a 1 g 1 a n g n displaystyle f a 1 g 1 dots a n g n nbsp mit Polynomen a 1 a n K X 1 X k displaystyle a 1 dots a n in K X 1 dots X k nbsp schreiben lasst Man kann nun versuchen so eine Darstellung mit Hilfe der Polynomdivision mit Rest zu finden indem man so lange dividiert bis der erhaltene Rest verschwindet und damit die Division aufgeht f a 1 g 1 r 1 displaystyle f a 1 g 1 r 1 nbsp f a 1 g 1 a 2 g 2 r 2 displaystyle f a 1 g 1 a 2 g 2 r 2 nbsp Dabei treten aber zwei Probleme auf Bei multivariaten Polynomen p K X 1 X k displaystyle p in K X 1 ldots X k nbsp lassen sich die Terme nicht mehr ohne Weiteres der Grosse nach ordnen was fur die Polynomdivision aber notwendig ist Konnen wir denn uberhaupt sicher sein dass durch wiederholte Polynomdivision immer der Rest 0 erscheint Das erste Problem lasst sich recht einfach losen indem eine Monomordnung gewahlt wird Dann konnen die Terme jedes Polynomes nach dieser Ordnung angeordnet werden vor allem konnen wir nun vom Leitterm LT displaystyle operatorname LT nbsp eines Polynoms sprechen also des bezuglich der Monomordnung grossten Monoms mit seinem Koeffizienten Als Nachteil bleibt dass die Anordnung der Monome und auch das Ergebnis der Polynomdivisionen von der Wahl der Monomordnung abhangen Das zweite Problem ist schwieriger denn es ist tatsachlich nicht losbar wenn die erzeugenden Polynome fest vorgegeben sind Es kann nur gelost werden indem das Erzeugendensystem passend geandert wird Eine Grobnerbasis stellt sich als ein geeignetes Erzeugendensystem heraus Verallgemeinerte Polynomdivision Bearbeiten Die Aufgabe der verallgemeinerten Polynomdivision ist nun also Fur ein Polynom f displaystyle f nbsp und mehrere Polynome g 1 g n displaystyle g 1 dots g n nbsp sollen Polynome a 1 a n r displaystyle a 1 dots a n r nbsp gefunden werden die die Gleichung f a 1 g 1 a n g n r displaystyle f a 1 g 1 dots a n g n r nbsp erfullen Dazu bietet sich folgendes Vorgehen an Beginne mit a 1 a n r 0 displaystyle a 1 dots a n r 0 nbsp Falls f 0 displaystyle f 0 nbsp brich ab sonst vergleiche der Reihe nach alle LT g i displaystyle operatorname LT g i nbsp ob sie LT f displaystyle operatorname LT f nbsp teilen Falls etwa a LT g i LT f displaystyle a operatorname LT g i operatorname LT f nbsp so ersetze a i displaystyle a i nbsp durch a i a displaystyle a i a nbsp und f displaystyle f nbsp durch f a g i displaystyle f ag i nbsp und gehe zu Schritt 2 Falls LT f displaystyle operatorname LT f nbsp von keinem LT g i displaystyle operatorname LT g i nbsp geteilt wird so ersetze r displaystyle r nbsp durch r LT f displaystyle r operatorname LT f nbsp und f displaystyle f nbsp durch f LT f displaystyle f operatorname LT f nbsp und gehe zu Schritt 2 Dann ist in jedem Schritt die Gleichung f urspr a 1 g 1 a n g n r f aktuell displaystyle f text urspr a 1 g 1 dots a n g n r f text aktuell nbsp erfullt und schliesslich wenn f aktuell 0 displaystyle f text aktuell 0 nbsp ist die gewunschte Darstellung gefunden Mit dieser Division haben wir das Problem wie gewunscht auf ein kleineres Polynom reduziert denn es ist f I displaystyle f in I nbsp genau dann wenn r I displaystyle r in I nbsp Falls r 0 displaystyle r 0 nbsp ist das klar und f I displaystyle f in I nbsp Ist aber r 0 displaystyle r neq 0 nbsp konnen wir auf diesem Weg nicht entscheiden ob r I displaystyle r in I nbsp oder r I displaystyle r not in I nbsp Beispiel Seien g 1 x displaystyle g 1 x nbsp g 2 x 2 1 displaystyle g 2 x 2 1 nbsp und f g 1 g 2 x 2 x 1 displaystyle f g 1 g 2 x 2 x 1 nbsp Testet man die erzeugenden Polynome der Reihe nach also in aufsteigender Reihenfolge der Indizes und wendet die beschriebene Division an erhalt man f x g 1 x 1 x 1 g 1 1 displaystyle f xg 1 x 1 x 1 g 1 1 nbsp Offenbar gilt aber f g 1 g 2 I displaystyle f g 1 g 2 in I nbsp also auch r 1 I displaystyle r 1 in I nbsp namlich 1 x g 1 g 2 displaystyle 1 xg 1 g 2 nbsp Man kann also im Allgemeinen aus r 0 displaystyle r neq 0 nbsp nicht folgern dass r I displaystyle r not in I nbsp und damit f I displaystyle f not in I nbsp gilt Definition BearbeitenEin Erzeugendensystem G g 1 g n displaystyle G g 1 ldots g n nbsp von I displaystyle I nbsp ist eine Grobnerbasis bezuglich einer Monomordnung lt displaystyle lt nbsp von I displaystyle I nbsp falls fur jedes Polynom f I 0 displaystyle f in I setminus 0 nbsp ein g i displaystyle g i nbsp existiert dessen Leitmonom das Leitmonom von f displaystyle f nbsp teilt Eine Grobnerbasis G displaystyle G nbsp heisst reduziert falls alle g G displaystyle g in G nbsp normiert sind und kein Monom von g displaystyle g nbsp durch die Leitterme der anderen Grobnerbasispolynome dargestellt werden kann also kein Monom von g displaystyle g nbsp in LT g g G g displaystyle langle operatorname LT g g in G setminus g rangle nbsp liegt Man kann zeigen dass jedes Ideal fur eine gegebene Monomordnung eine eindeutig bestimmte reduzierte Grobnerbasis besitzt Anwendungen BearbeitenDas Konzept von Grobnerbasen gibt zunachst eine Losung des Idealzugehorigkeitsproblems Damit verbunden lassen sich aber auch andere Probleme losen oder zumindest vereinfachen Losung des Idealzugehorigkeitsproblems Bearbeiten Wird mit dem oben beschriebenen Verfahren eine nicht weiter reduzierbare Darstellung f k 1 g 1 k n g n r displaystyle f k 1 g 1 ldots k n g n r nbsp bezuglich einer Grobnerbasis G g 1 g n displaystyle G g 1 ldots g n nbsp des Ideals I displaystyle I nbsp gefunden so gilt f I displaystyle f in I nbsp genau dann wenn r I displaystyle r in I nbsp Da aber G displaystyle G nbsp eine Grobnerbasis ist gilt das wiederum genau dann wenn r 0 displaystyle r 0 nbsp da nach Annahme kein Leitmonom eines g i displaystyle g i nbsp das Leitmonom von r displaystyle r nbsp teilt Mit dem Buchberger Algorithmus konnen Grobnerbasen berechnet werden Damit ist das Problem ob ein Polynom zu einem Ideal gehort oder nicht von Computeralgebrasystemen losbar Beispiel Wenn wie im Beispiel oben die erzeugenden Polynome g 1 x g 2 x 2 1 displaystyle g 1 x g 2 x 2 1 nbsp gegeben sind sowie f g 1 g 2 x 2 x 1 displaystyle f g 1 g 2 x 2 x 1 nbsp dann hatte die Polynomdivision Rest 1 displaystyle 1 nbsp geliefert Wenden wir zunachst den Buchberger Algorithmus auf dieses Beispiel an so erhalten wir die nicht reduzierte Grobnerbasis x x 2 1 1 displaystyle x x 2 1 1 nbsp von I displaystyle I nbsp Bezuglich dieses Divisors ist die Division hier noch nicht abgeschlossen denn es ist mit g 3 1 displaystyle g 3 1 nbsp f x g 1 x 1 x 1 g 1 1 x 1 g 1 1 g 3 displaystyle f xg 1 x 1 x 1 g 1 1 x 1 g 1 1 g 3 nbsp Wir sehen hier auch dass die Darstellung bezuglich der Grobnerbasis nicht eindeutig ist da f g 1 g 2 x 1 g 1 g 3 displaystyle f g 1 g 2 x 1 g 1 g 3 nbsp sondern von der Reihenfolge der erzeugenden Polynome und der gewahlten Monomordnung abhangt Polynomiale Gleichungssysteme Bearbeiten Ein polynomiales Gleichungssystem besteht aus endlich vielen Gleichungen f 1 x 0 f k x 0 displaystyle f 1 x 0 ldots f k x 0 nbsp wobei f 1 f k K x 1 x n displaystyle f 1 ldots f k in K x 1 ldots x n nbsp gegebene Polynome in n displaystyle n nbsp Unbestimmten uber einem Korper K displaystyle K nbsp und deren gemeinsame Nullstellen x K n displaystyle x in K n nbsp gesucht sind Die Losungsmenge x K n f 1 x f k x 0 displaystyle x in K n f 1 x cdots f k x 0 nbsp eines solchen Gleichungssystems beschreibt eine algebraische Varietat Diese ist offenbar gleich x K n f x 0 f I displaystyle x in K n f x 0 quad forall f in I nbsp wobei I f 1 f k displaystyle I f 1 ldots f k nbsp das von den Polynomen erzeugte Ideal ist Soll ein bestimmtes polynomiales Gleichungssystem gelost werden genugt es also das Ideal zu betrachten das von den Polynomen erzeugt wird Dann kann es hilfreich sein mit Hilfe des Buchberger Algorithmus und einer geeigneten lexikographischen Monomordnung eine reduzierte Grobnerbasis zu finden Dann bleibt zwar das Problem die Nullstellen dieser Polynome zu finden z B naherungsweise durch numerische Verfahren aber die zu untersuchenden Polynome haben immerhin eine kleinere Anzahl an Variablen und kleineren Grad Beispiel Welche Losungen x y z R 3 displaystyle x y z in mathbb R 3 nbsp hat das folgende Gleichungssystem x 2 y 2 z 2 1 0 displaystyle x 2 y 2 z 2 1 0 nbsp x 2 y z 2 0 displaystyle x 2 y z 2 0 nbsp x z 0 displaystyle x z 0 nbsp Mit Hilfe des Computers erhalt man fur die lexikographische Monomordnung x gt y gt z displaystyle x gt y gt z nbsp die reduzierte Grobnerbasis g 1 x z g 2 y 2 z 2 displaystyle g 1 x z g 2 y 2z 2 nbsp und g 3 z 4 1 2 z 2 1 4 displaystyle g 3 z 4 frac 1 2 z 2 frac 1 4 nbsp Die gesuchten Losungen sind also genau die Losungen des einfacheren Gleichungssystems x z displaystyle x z nbsp y 2 z 2 displaystyle y 2z 2 nbsp z 4 1 2 z 2 1 4 0 displaystyle z 4 frac 1 2 z 2 frac 1 4 0 nbsp Und wir sehen dass die Losungsmenge aus nur zwei Punkten besteht z 2 z 2 z z 1 2 5 1 displaystyle left z 2z 2 z z pm frac 1 2 sqrt sqrt 5 1 right nbsp die zwei weiteren Losungen 1 2 5 1 displaystyle pm frac 1 2 sqrt sqrt 5 1 nbsp sind in R displaystyle mathbb R nbsp nicht enthalten Gleichheit von Idealen und algebraischen Varietaten Bearbeiten Da zu einer gegebenen Monomordnung die reduzierte Grobnerbasis eines Ideals eindeutig bestimmt ist kann die Gleichheit von Idealen untersucht werden indem zu irgendeiner Monomordnung die reduzierten Grobnerbasen gebildet werden Die Ideale sind genau dann gleich wenn diese reduzierten Grobnerbasen gleich sind Auf diese Weise kann man auch rein rechnerisch die Gleichheit von algebraischen Varietaten untersuchen da diese durch ihre erzeugenden Ideale eindeutig bestimmt sind Sind die reduzierten Grobnerbasen gleich dann sind die erzeugenden Ideale und damit auch die erzeugten Varietaten gleich Literatur BearbeitenHeisuke Hironaka Resolution of singularities of an algebraic variety over a field of characteristic zero In Annals of Mathematics 79 1964 Nr 1 S 109 326 Bruno Buchberger Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal PDF 1 8 MB Osterreich Universitat Innsbruck Diss 1965 Bruno Buchberger Ein algorithmisches Kriterium fur die Losbarkeit eines algebraischen Gleichungssystems PDF 475 kB Aequationes Mathematicae 4 1970 374 383 T Becker B V Weispfenning Grobner bases a computational approach to commutative algebra Graduate Texts in Mathematics readings in mathematics Bd 141 New York Springer Verlag 1993 David Cox Little John O Shea Donald Ideals varieties and algorithms New York Springer Verlag 1997 Joachim von z Gathen Jurgen Gerhard Modern Computer Algebra Cambridge University Press 1999 Abgerufen von https de wikipedia org w index php title Grobnerbasis amp oldid 235723941