Ich möchte heute etwas über den Divisionssatz schreiben, welcher den euklidischen Algorithmus und die Polynomdivision verallgemeinert. Das Ziel ist es, darzustellen dass der Algorithmus nicht immer einwandfrei funktioniert, um die Gröbner-Basen eines Ringideals zu motivieren.
Problemstellung
Vorbereitungen
2.1 Termordnungen
2.2 einige Definitionen
Der Divisionssatz
3.1 Beispiele
3.2 Der Divisionssatz
3.3 Algorithmus
3.4 Beweis
Befasst man sich in der Algebra mit Polynomringen in mehreren Variablen, stößt man recht früh auf einige Probleme, zum Beispiel:
\stress(1)\normal\ Das array("Ideal Membership Problem")__:
Gegeben ist ein f\el\IK\[x_1 , ... , x_n ] und ein Ideal \II=span(f_1,...,f_s) und man will entscheiden, ob f\el\II oder f\notel\II.
\stress(2)\normal\ Lösungen für array(polynomiale Gleichungssysteme)__ zu bestimmen:
Finde alle Lösungen in \IK^n für ein System von polynomialen Gleichungen f_1(x_1 , ... , x_n )= ... =f_s(x_1 , ... , x_n )=0.
\stress(3)\normal\ Bestimmen von polynomialen Gleichungssystemen bei gegebener
Lösungsmenge.
In der Schule schon lernt man Methoden, mit denen Spezialfälle dieser Probleme gelöst werden können.
Man lernt die Polynomdivision sowie den euklidischen Algorithmus kennen, und mit dem Wissen das \IK\[x] ein Hauptidealring ist, kann man Problem \stress\(1)\normal\ für den Fall einer Unbestimmten lösen.
Selbst einen Spezialfall für Problem \stress\(2)\normal\ kann man mit Hilfe der
Schulmathematik lösen. Treten in einem polynomiellen Gleichungssystem die n Unbestimmten nur in der ersten Potenz auf, und gibt es keine
gemischten Terme, so kann man das System mit Hilfe des array(Gauß\-Algorithmus)__ lösen. Zum Beispiel kann man so das polynomielle Gleichungssystem
1: 3*x+5*y-6*z=2
2: 4*x+7*y-9*z=3
lösen.
Das Problem, das sich jetzt stellt ist, diese Methoden auf den Polynomring in endlich vielen Unbestimmten zu verallgemeinern. Als Koeffizientenbereich möchte ich hier allerdings nur Körper betrachten und keine Ringe, was selbstverständlich auch geht.
Wer sich für das eher Technische in Kapitel 2 und 3 nicht interessiert, dem sei aber auf jeden Fall das 4. Kapitel empfohlen, denn es sind unter anderem die Schwächen des Divisionssatzes, die das breite Feld der Gröbner-Basen motivieren.
Bevor wir zum Divisionssatz kommen, sind einige Vorbetrachtungen nötig, ohne die es nicht geht. Ich versuche mich hier allerdings so kurz wie möglich zu fassen, obwohl die einzelnen Vorbereitungen eigene Artikel verdient hätten.
2.1 Termordnungen
Zunächst brauchen wir eine Struktur auf den Elementen unseres Polynomrings, um unter 2.2 einige wichtige Begriffe definieren zu können.
Und zwar brauchen wir auf den Monomen in \IK\[x_1 , ... , x_n ] eine
Ordnungsrelation <=.
Für den Fall einer Unbestimmten ordnen wir die Monome eines Polynoms kanonisch nach dem Grad, also wäre x^5 array(<=)_k x^6 und x array(<=)_k x^2, wobei das k hier für "kanonisch" steht. Im Fall mehrerer Unbestimmte ist diese
Ordnungsrelation jedoch nicht mehr ausreichend, was auf den Begriff der Termordnung__, array(monomialer Ordnung)__ oder Monomordnung__ führt.
\boxon \stress\(Definition)\normal\ Monomordnung__: Eine Monomordnung auf \IK\[x_1 , .. , x_n ] ist eine Relation > auf \IN^n mit folgenden Eigenschaften:
\stress\(M1)\normal\ > ist eine Totalordnung auf \IN^n
\stress\(M2)\normal\ Falls \a>\b und \g\el\IN^n, dann ist \a+\g>\b+\g
\boxoff
Ohne Beweis möchte ich nun das folgende Lemma angeben, das später beim Beweis des Divisionssatzes benötigt wird:
\stress\(Lemma 1)\normal\: Eine Totalordnung > auf \IN^n ist genau dann eine Wohlordnung, wenn jede streng absteigende Folge in \IN^n \a(1)>\a(2)>...> stationär wird, also abbricht.
Ich möchte hier nur 2 Beispiele für Monomordnungen angeben, da dies doch eher technisch ist und nicht wirklich dem Verständnis dient.
Beispiele für Termordnungen
Eine wohl intuitiv klare Monomordnung ist die array(lexikographische Ordnung)__:
\stress\(Definition)\normal\ lexikographische Ordnung: Sei \a=(\a_1 , ... , \a_n ) und \b=(\b_1 , ... , \b_n )\el\IN^n. Dann ist \a array(>)_lex \b, falls der erste von Null verschiedene Eintrag der Differenz \a-\b positiv ist.
Beispiel:__ (1,2,0) array(>)_lex (0,3,4) da \a-\b=(1,-1,-4)
Die lexikopgraphische Ordnung ist das Analogon für die alphabetische Ordnung, d.h. Wörter, die mit x anfangen, kommen vor Wörtern, die mit y beginnen, und so weiter. Wer Lust hat, kann gerne zeigen, daß die eben definierte Ordnung eine Monomordnung ist, ich werde dies hier nicht machen.
Die lexikographische Ordnung kann man zur array(graduiert lexikographische Ordnung)__ verfeinern:
\stress\(Definition)\normal\ graduiert lexikographische Ordnung:
Sei \a, \b\el\IN^n. Wir sagen \a array(>)_deglex \b falls abs(\a)=sum(\a_k,k=1,n) > abs(\b)=sum(\b_k,k=1,n), oder abs(\a)=abs(\b) und \a array(>)_lex \b.
Das heißt nichts anderes, als daß geguckt wird, bei welchem Monom die Summe der Exponenten am größten ist. Gibt es 2 Monome, der Exponentensumme gleich ist, wird als 2. Vergleichskriterium die zuvor definierte
lexikographische Ordnung als Entscheidungshilfe genommen.
Es gibt natürlich noch die verschiedensten Monomordnungen. Genannt seien hier nur noch die gewichteten Gradordnungen, invers-lexikographische Ordnungen, Blockordnungen und die Matrixordnungen. Es ist möglich, eine Unterscheidung zwischen diesen Ordnungen zu machen, und zwar klassifiziert man die Ordnungen noch in "globale Ordnungen", "gemischte Ordnungen" und "lokale Ordnungen". Das hängt jeweils davon ab, ob die 1 (oder allgemein ein konstantes Monom) als größtes oder kleinstes Monom bezüglich dieser Ordnung angesehen wird. Ich betrachte hier allerdings nur globale Ordnungen, da nur bei diesen der Divisionssatz funktioniert.
2.2 Einige Definitionen
Ich will hier einige Schreibweisen definieren, welche das ganze etwas übersichtlicher halten sollen.
\stress\(D1)\normal\ Für den Polynomring \IK\[x_1 , ... , x_n ] schreibe ich abkürzend \IK_n.
\stress\(D2)\normal\ Ein Monom der Form (x_1)^\a_1* ... * (x_n)^\a_n ist kurz X^\a, wobei \a dann der Exponentenvektor ist, also \a=(\a_1 , ... , \a_n)
\stress\(D3)\normal\ Der Leitterm__ eines Polynoms f ist das bezüglich einer Monomordnung >
größte Monom. Kurzschreibweise: lt(f)
\stress\(D4)\normal\ Der Leitkoeffizient__ ist der Koeffizient des Leittermes eines Polynoms f und wird geschrieben als lc(f)
\stress\(D5)\normal\ Der Exponentvektor eines Monoms sei bezeichnet mit lp(m)
Jetzt kommt der eigentlich wichtige Teil des Artikels, der Divisionssatz selber. Damit man diesen besser verstehen kann, möchte ich zunächst ein Beispiel durchrechnen und erst dann den Satz und den Algorithmus einführen.
3.1. Beispiel
Als Beispiel__ wollen wir das Polynom f=x*y^2+1 durch die Polynome
f_1=x*y+1 und f_2=y+1 dividieren. Als Termordnung soll die
lexikographische Ordnung zu Grunde liegen.
Dieses Beispiel ist besonders schön, da der Leitterm von f sowohl vom Leitterm von f_1 als auch vom Leitterm von f_2 geteilt wird. Da f_1 vorne steht, fang ich mal mit diesem Polynom an, und bilde:
f-lt(f)/lt(f_1)*f_1=(x*y^2+1)-y*(x*y+1)=-y+1 := f_3.
Das wiederholen wir jetzt mit f_3, wobei wir nun f_2 nutzen müssen um f_3 zu reduzieren, da der Leitterm von f_1 den Leitterm von f_3 nicht mehr teilt. Gebildet wird wieder:
f_3-lt(f_3)/lt(f_2)*f_2=(-y+1)-(-1)*(y+1)=2 := f_4
Da der Leitterm von f_4 weder vom Leitterm von f_1 noch vom Leitterm von f_2 geteilt wird, ist man fertig. Der Rest__ ist also f_4=2. Wir können f=x*y^2+1 jetzt also in der Form:
x*y^2+1=y*(x*y+1)+(-1)*(y+1)+2 schreiben.
3.2 Der Divisionssatz
Jetzt ist es an der Zeit, den Divisionssatz zu formulieren:
\light\stress\(Divisionssatz)\normal\ Sei > eine Monomordnung auf \IN^n und sei F=(f_1 , ... , f_s) ein geordnetes s-Tupel von Polynomen aus \IK\[x_1 , ... , x_n ]. Dann hat jedes f\el\IK_n eine Darstellung f=a_1*f_1+ ... + a_s*f_s + r, wobei a_i , r\el\IK_n. Entweder ist r=0, oder r ist eine Linearkombination mit Koeffizienten aus \IK und Monomen aus \IK_n, wobei kein Monom von einem Leitterm der f_i geteilt wird. r heißt der Rest__ der Division von f durch F.
3.3 Algorithmus für den Divisionssatz
Ich werde hier den Algorithmus angeben, der den Divisionssatz beschreibt. Ein Beweis der Korrektheit folgt in 3.4.
\sourceon
Input: f1, ... , fs, f
Output: a1, ... , as, r
a1 := 0; ... ; as := 0; r := 0;
p := f;
WHILE p != 0 DO
i := 1
divisionoccurred := false
WHILE i <= s AND divisionoccured = false DO
IF LT(fi) divides LT(p) THEN
ai := ai + LT(p)/LT(fi)
p := p-(LT(p)/LT(fi))*fi
divisionoccured := true
ELSE
i := i+1
IF divisionoccured = false THEN
r := r+LT(p)
p := p-LT(p)
\sourceoff
3.4 Beweis des Divisionssatzes
Es wird gezeigt, das der in 3.3 gegebene Algorithmus endlich ist.
\stress\(Beweis)\normal Bei jedem Schritt des Algorithmus wird dem Leitterm von f etwas ab substrahiert, was den Grad verkleinert. Man erhält eine Folge f_1 , f_2 , ...der f's im Algorithmus, wobei man p_(i+1) erhält, indem man h_i den Leitterm lt(f_i) und eventuell kleinere Terme substrahiert:
p_(i+1)=p_i-(lt(p_i)+ niedrigere Terme). Das ist so, weil man p_(i+1) mit h_i berechnet, indem man lt(p_i)/lt(f_j)*f_j=(lt(p_i)+niedrigere Terme) ((falls lp(f_j) teilt lp(p_i))) oder lt(p_i) (falls kein lp(f_j) teilt lp(p_i)) substrahiert.
Deshalb gilt jetzt für alle i: lp(p_(i+1)) eine Monomordnung, und somit wohlgeordnet ist, folgt mit dem Lemma, das die Anzahl der p_i endlich ist.
Es bleibt die Frage, ob der Divisionssatz für n Unbestimmte die gleichen schönen Eigenschaften hat, wie die Version für 1 Unbestimmte. Die Antwort ist leider nein.
In \IK\[x] ist der Rest der Polynomdivision eindeutig bestimmt, in \IK_n ist dies nicht der Fall, was man leicht an einigen Beispielen nachprüft. Es kommt unter anderem auf die Reihenfolge__ der f_i an, welcher Rest bei der Division heraus kommt. Eine einfache Umordnung des s-Tupels
(f_1 , ... , f_s ) verändert sowohl die Koeffizienten, die a_i , als auch den Rest r.
Die gewählte Monomordnung beeinflusst das Ergebnis ebenfalls, aber das ist eine andere Geschichte.
Aber der Divisionssatz wurde ja eingeführt, um mögliche Lösungsansätze für die Ausgangsprobleme zu geben. Zum Problem \stress\(1)\normal\, dem "Ideal Membership Problem":
Im Falle einer Variable ist die Aussage f \el \II=span(f_1 , ... , f_s) äquivalent dazu, das bei der Division von f durch die f_i der Rest r=0 ist.
Im Falle von beliebig vielen Variablen ist dies jedoch nur eine hinreichende__, keine notwendige Bedingung!
Der Divisionsalgorithmus ist also bei weitem nicht perfekt, und es stellt sich die Frage, wann er seine volle Stärke entfalten kann. Die Antwort auf diese Frage wird sein, dass man sich ein "gutes" Erzeugendensystem für das Ideal \II wählen muss, sodass die Aussagen f\el\II=span(f_1 , ... , f_s) und r=0 äquivalent sind.
Ein Erzeugendensystem, welches diese "guten" Eigenschaften hat, nennt man eine array(\stress\Gröbner-Basis)__ \normal\ des Ideals \II.
Über die Probleme (2) und (3) schreibe ich vielleicht ein anderes Mal! :)
Vielen Dank für die Aufmerksamkeit
Gonzbert
Eine Einfuehrung in die Theorie der Standardbasen (Gröbner-Basen) von Idealen in Polynomringen.
Der Divisionssatz als Verallgemeinerung des euklidischen Algorithmus und der Polynomdivision. Das Ziel ist es, darzustellen, dass der Algorithmus nicht immer einwandfrei funktioniert, um die Gröbner-Basen eines Ringideals zu motivieren.
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Ich möchte heute etwas über den Divisionssatz schreiben, welcher den euklidischen Algorithmus und die Polynomdivision verallgemeinert. Das Ziel ist es, darzustellen dass der Algorithmus nicht immer einwandfrei funktioniert, um die Gröbner-Basen eines Ringideals zu motivieren.
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
