WikiDer > Gröbner Sockel

In dem Computeralgebra, die rechnerische algebraische Geometrie und das rechnerische kommutative Algebra ist ein Gröbner-Basis ein besonderes generativ Teilmenge von a Idealich im Ring k[X₁,X₂,...,X_nein] von Polynome im nein umstellen a Körperk.

Man kann das Konzept der Gröbner-Basis als nichtlineare Verallgemeinerung in mehreren Variablen sehen von:

• es Euklids Algorithmus zur Berechnung von größte gemeinsame Teiler (von Polynomen in einer Variablen),
• Gauss-Eliminierung vor dem Linearsysteme, und
• Probleme von der Integer-Programmierung.

Die Theorie der Gröbnerbasen für Polynomringe wurde 1965 entwickelt von Bruno Buchberger. Buchberger benannte die Gröbner-Basen nach seinem Doktorvater Wolfgang Gröbner. Die "Association for Computing Machinery" verlieh Buchberger 2007 für diese Arbeit den "Paris Kanellakis Theory and Practice Award".

Ein analoges Konzept für lokale Ringe wurde 1964 unabhängig entwickelt von Heisuke Hironaka. Hironaka nannte seine Konstruktion Standardbasen. Die analoge Theorie kostenlos Lügenalgebras wurde 1962 von A.I. Shirshov, aber seine Arbeit blieb außerhalb der Sovietunion weitgehend unbekannt.

Monomordnung

In Computeralgebra-Quellen wird das Wort . verwendet ein Begriff wird normalerweise für ein Potenzprodukt von Variablen mit dem Koeffizienten 1 verwendet, was "monisches Mononom" bedeutet. Die Konstante 1 ist dann das einzige Mononom nullten Grades. Diese Terminologie entspricht der alternativen Definition des Wikipedia-Artikels ein Begriff.

Die Definition einer Gröbner-Basis setzt voraus, dass a Monomordnung > von k[X₁,X₂,...,X_nein] wird gegeben werden. Das ist ein gut sortiert auf der Menge der Mononome, die mit der Multiplikation von Mononomen in dem Sinne kompatibel ist, dass wenn p, q und r sind Mononome und p > q, dann p.r > q.r.^[1]

Wenn eine monomische Ordnung gegeben ist, dann nennen wir die Leitbegriff LT(f) eines Polynoms f (was nicht das Nullpolynom ist) der Term von f dessen entsprechender Eins-Term (der Term ohne seinen Koeffizienten) größer ist als alle anderen Eins-Terme von f.^[2]

Beispiel für eine monomische Ordnung

Das lexikografisch Die Reihenfolge ordnet Monoterme in absteigendem Grad in der ersten Variablen. Wenn zwei Mononome den gleichen Grad in . haben X₁, wir ordnen sie nach absteigendem Grad in der zweiten Variablen und so weiter. Wenn zwei Mononome in allen Variablen separat den gleichen Grad haben, sind sie einander gleich. Beispiel

${displaystyle x_{1}^{3}x_{2}^{2}>x_{1}^{2}x_{2}^{7}>x_{1}^{2}x_{2}^{ 6}}$

Abgesehen von einer Umkehrung des <-Zeichens ist dies das klassische Konzept lexikographische Ordnung wenn wir die Menge der Mononome in nein identifiziere Variablen mit dem kartesischen Produkt von nein Kopien der natürlichen Zahlen, also wenn wir jeden einzelnen Term mit der geordneten Folge seiner Exponenten identifizieren.

Beispiel für einen Leitbegriff

In der lexikographischen Ordnung ist der führende Term LT(G) des Polynoms

${displaystyle g(x_{1},x_{2})=-2x_{1}^{3}x_{2}^{2} 3x_{1}^{2}x_{2}^{7} 8x_{ 1}^{2}x_{2}^{6}-1}$

gleicht

${displaystyle -2x_{1}^{3}x_{2}^{2}.}$

Definition

Sie > eine monomische Anordnung von k[X₁,X₂,...,X_nein], und ich ein Ideal dieses Rings. Eine endliche Teilmenge {G₁, ... , G_t} von ich heißt Gröbner-Basis für ich bzgl. der Ordnung > als Ideal erzeugt durch die Leitterme der Elemente von ich obwohl es von den führenden Termini der G_ich.^[1]

Mit anderen Worten: Eine Gröbner-Basis ist eine endliche Menge {G₁, ... , G_t} Polynome von ich so dass für jedes Polynom f von ich (außer 0), LT(f) ist teilbar durch mindestens eines der LT(G_ich).^[3]

Beispiel und Gegenbeispiel

Die Nullstellen von f(x,y) bilden die rote Parabel; die Nullstellen von g(x,y) bilden die drei blauen vertikalen Linien. Ihr Schnittpunkt besteht aus drei Punkten.

Sie R = Q[X,ja] den Ring von Polynomen in zwei Variablen mit rationalen Koeffizienten und betrachten das Ideal ich = <f,G> erzeugt durch die Polynome

${Anzeigestil f(x,y)=x^{2}-y}$

${Anzeigestil g(x,y)=x^{3}-x}$

Zwei weitere Elemente von ich sind die Polynome

${Anzeigestil h(x,y)=-(x^{2} y-1)f(x,y) x.g(x,y)=y^{2}-y}$

${Anzeigestil k(x,y)=-x.f(x,y) g(x,y)=xy-x}$

Wenn wir die lexikographische Ordnung mitnehmen X > ja behandeln, gilt

${displaystyle {hbox{LT}}(f)=x^{2}}$

${displaystyle {hbox{LT}}(g)=x^{3}}$

${displaystyle {hbox{LT}}(h)=y^{2}}$

${displaystyle {hbox{LT}}(k)=xy}$

Das von {LT(f),LT(G)} enthält nur durchnom teilbare Polynome X² und es gibt LT(ha) = ja² nicht bei; es folgt dem {f, G} keine Gröbner-Basis ist für ich.

Andererseits kann man wie folgt überprüfen, dass {f, k, ha} ist tatsächlich eine Gröbner-Basis für basis ich.

Bitte beachte, dass f und G, und deshalb auch ha und k und alle anderen Polynome im Ideal ich, die nächsten drei Nullen im (X,ja) Ebene gemeinsam, wie in der Abbildung gezeigt: {(1,1),(-1,1),(0,0)} Diese drei Punkte liegen nicht auf derselben Linie, also ich enthält keine Polynome ersten Grades. O kann auch ich enthalten keine Polynome der Sonderform

${Anzeigestil m(x,y)=cx p(y)}$

mit c eine andere rationale Zahl als 0 und p ein Polynom, in dem nur die Variable ja verhindert; schließlich ist ein solches Polynom ich kann nie zwei verschiedene Nullen mit dem gleichen Wert für have haben ja (in diesem Fall die Punkte (1,1) und (-1,1)).

Aus all dem folgt, dass ich außer dem Nullpolynom enthält nur Polynome, deren führender Term mindestens den Grad 2 hat und deren führender Term also durch mindestens eines der drei teilbar ist

{X², xy, ja²} = {LT(f),LT(k),LT(ha)}.

Das bedeutet, dass {f, k, ha} ist eine Gröbner-Basis für ich relativ zur lexikographischen Ordnung mit X > y.

Eigenschaften

Das Hilberts Grundsatzbert sagt, dass alle Ideale in k[X₁,X₂,...,X_nein] sind endlich produziert. Es kann gezeigt werden, dass für jede gegebene monomische Ordnung jedes nicht-triviale Ideal eine Gröbner-Basis hat. Der Name Gröbner-Basis wird durch die Eigenschaft begründet, dass jede Gröbner-Basis eine Basis (d. h. ein erzeugender Satz) ist.^[1]

Externe Links

• (und) B. Buchberger, Groebner-Basen: Eine kurze Einführung für Systemtheoretiker im Tagungsband EUROCAST 2001.
• (und) B. Buchberger und Zapletal, A.Grobner Bases Bibliographie.
• (und) Online-Gröbner-Grundlagen, Galway, Irland
• (und) Java-Applet zur Berechnung von Gröbner-Basen von Fabrizio
• (und) Gröbner-Grundlagentheorie Universität Leicester
• (und) Gröbner-Basis auf MathWorld