Monomordnung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine Monomordnung oder Termordnung ist eine lineare Ordnung auf der Menge der Monome über einer endlichen Variablenmenge. Monomordnungen werden zur Definition der Division mit Rest von Polynomen in mehreren Variablen benötigt. Eine Gröbnerbasis bzgl. definiert den Rest dieser Division eindeutig.

Definition[Bearbeiten | Quelltext bearbeiten]

Eine lineare Ordnung auf der Menge

der Monome in den Variablen heißt Monomordnung, falls gilt

(1) Für alle Monome gilt

(2) Das Monom ist das kleinste Monom, also

Äquivalente Definitionen[Bearbeiten | Quelltext bearbeiten]

Es sind auch andere äquivalente Definitionen üblich. So ist es etwa möglich die Bedingung (2) durch eine andere Bedingung auszutauschen. In der Literatur[1] finden sich zum Beispiel

(2') Die Ordnung ist eine Wohlordnung

oder auch äquivalenten dazu

(2*) Bezüglich der Ordnung gibt es keine unendlichen absteigenden Ketten von Monomen.

Die Eigenschaft (2*) ist Grundlage vieler Terminierungsbeweise für Algorithmen im Zusammenhang mit Gröbnerbasen.

Beispiele für Monomordnungen[Bearbeiten | Quelltext bearbeiten]

Monome in einer Variablen[Bearbeiten | Quelltext bearbeiten]

Falls wir nur eine Variable haben, also gilt, gibt es nur eine Monomordnung . Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall sein muss.

(Rein) Lexikalische Ordnung[Bearbeiten | Quelltext bearbeiten]

Bezüglich der lexikalischen oder lexikographischen Ordnung gilt genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von negativ ist. Das heißt, es kann rekursiv definiert werden

Totalgradordnung[Bearbeiten | Quelltext bearbeiten]

Die Totalgradordnung oder graduierte lexikalische Ordnung ist definiert durch

Blockordnungen[Bearbeiten | Quelltext bearbeiten]

Jedes Monom über einer Variablenmenge kann auf eindeutige Weise in ein Produkt zerlegt werden, so dass in nur Variablen aus und in nur Variablen aus vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen und auf Monomen über den Variablen aus bzw. die Blockordnung auf Monomen in definiert als

Begriffe im Zusammenhang mit Polynomen[Bearbeiten | Quelltext bearbeiten]

Eine Monomordnung erlaubt es die Monome in einem Polynom anzuordnen. Für ein Polynom kann dann zum Beispiel der Multigrad , der Leitkoeffizient , das Leitmonom oder der Leitterm von bezüglich der Monomordnung definiert werden.[2] Es gilt

Für den Polynomring in einer Variablen ergeben sich daraus die üblichen Definitionen für den Grad des Polynoms, seinen Leitkoeffizienten und seinen Leitterm.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Cox, Little, O'Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.
  2. Cox, Little, O'Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Becker T., Weispfenning V.: Gröbner Bases, Springer-Verlag 1993.
  • David A. Cox, John B. Little, Donal O’Shea: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra (= Undergraduate Texts in Mathematics). 3. Auflage. Springer, New York 2007, ISBN 978-0-387-35650-1, 2.2. Orderings on the Monomials in .