Monomordnung

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Leitterm)
Zur Navigation springen Zur Suche springen

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.

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

Grad-revers-lex-Ordnung (Degree reverse lexicographical order)

[Bearbeiten | Quelltext bearbeiten]

Hier gilt[2]:

Matrix-Ordnungen

[Bearbeiten | Quelltext bearbeiten]

Sei invertierbar mit der Eigenschaft, dass in jeder Spalte der erste von Null verschiedene Eintrag positiv ist. Dann gilt[3]:

Insbesondere kann man jede beliebige Monomordnung als Matrixordnung in darstellen. So ergibt sich beispielsweise für die Totalordnung (graduiert lexikographische Ordnung) folgende Matrix: . Die Grad-revers-lex-Ordnung kann folgendermaßen in eine Matrix umgesetzt werden: .

Blockordnungen oder Eliminationsordnungen

[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.[4] 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.

  • T. Becker, V. Weispfenning: Gröbner Bases, a computational approach to commutative algebra. Springer-Verlag, 1993, ISBN 3-540-97971-9.
  • 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 .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 1, Lemma 2.
  2. Winfried Bruns: Computer-Algebra. (PDF) Abgerufen am 31. Juli 2019.
  3. M. Roczen, H. Wolter, W. Pohl, D. Popescu, R. Laza: Lineare Algebra individuell – Kapitel 2: Algebraische Gleichungen. (PDF) Abgerufen am 31. Juli 2019.
  4. D. A. Cox, J. B. Little, D. O’Shea: Ideals, Varieties, and Algorithms. 2007, 2.2. Definition 7.