Mathematik: Der Divisionssatz
Released by matroid on Do. 16. Juni 2005 21:04:41 [Statistics]
Written by Gonzbert - 5174 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Der Divisionssatz

BildIch 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.
  1. Problemstellung
  2. Vorbereitungen 2.1 Termordnungen 2.2 einige Definitionen
  3. Der Divisionssatz 3.1 Beispiele 3.2 Der Divisionssatz 3.3 Algorithmus 3.4 Beweis
  4. Probleme und Lösungsansätze


1. Problemstellung

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.

2. Vorbereitungen

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)

3. Der Divisionssatz

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.

4. Probleme und Lösungsansätze

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
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Primzahlen :: Zahlentheorie :: Idealtheorie :: Gröbner-Basen :: Ringe :: euklidischer Algorithmus :: Polynome :: Standardbasis :: Buchberger-Algorithmus :
Der Divisionssatz [von 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.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5174
 
Aufrufstatistik des Artikels
Insgesamt 368 externe Seitenaufrufe zwischen 2012.01 und 2021.09 [Anzeigen]
DomainAnzahlProz
https://google.com174.6%4.6 %
http://google.de23363.3%63.3 %
https://google.de308.2%8.2 %
http://images.google.de154.1%4.1 %
http://google.ru246.5%6.5 %
http://google.it51.4%1.4 %
http://google.dk41.1%1.1 %
http://extern.peoplecheck.de30.8%0.8 %
https://www.bing.com30.8%0.8 %
http://google.at41.1%1.1 %
https://www.ecosia.org30.8%0.8 %
http://www.bing.com92.4%2.4 %
http://www.buzzdock.com10.3%0.3 %
http://google.co.in10.3%0.3 %
http://google.com20.5%0.5 %
http://192.168.0.250:191010.3%0.3 %
http://google.ba10.3%0.3 %
http://ecosia.org10.3%0.3 %
http://10.0.1.9:191020.5%0.5 %
http://search.conduit.com10.3%0.3 %
http://suche.t-online.de10.3%0.3 %
http://de.images.search.yahoo.com10.3%0.3 %
http://images.google.fr10.3%0.3 %
https://duckduckgo.com10.3%0.3 %
http://google.co.jp10.3%0.3 %
http://alicesuche.aol.de10.3%0.3 %
http://de.search.yahoo.com10.3%0.3 %
https://google.at10.3%0.3 %

Häufige Aufrufer in früheren Monaten
Insgesamt 316 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2017 (71x)http://google.de/url?sa=t&rct=j&q=
201203-03 (31x)http://google.de/url?sa=t&rct=j&q=n = qm r divisionssatz
201211-11 (22x)http://google.de/url?sa=t&rct=j&q=divisionssatz formulierung
2012-2013 (20x)http://google.de/url?sa=t&rct=j&q=divisionssatz
201303-03 (17x)http://google.de/url?sa=t&rct=j&q=inverse lexikographische Ordnung von Monome...
202005-07 (15x)https://google.de
2020-2021 (15x)https://google.de/
2016-2017 (15x)http://images.google.de/url?sa=t&rct=j&q=
201202-02 (14x)http://google.ru/url?sa=t&rct=j&q=was ist divisionssätze mathe
2020-2021 (13x)https://google.com/
201301-01 (11x)http://google.de/url?sa=t&rct=j&q=monomordnung echt absteigende folge
201407-07 (10x)http://google.ru/url?sa=t&rct=j&q=
2014-2017 (9x)http://google.de/
201205-05 (9x)http://google.de/url?sa=t&rct=j&q=i j ideale unbestimmte k x_1 x_n
2012-2017 (9x)http://google.de/url?sa=t&rct=j&q=divisionssatz von euklid
2017-2018 (8x)http://google.de/url?sa=i&rct=j&q=
201401-01 (5x)http://google.de/url?sa=t&rct=j&q=divisionssatz , polynomdivision mit rest
201306-06 (5x)http://google.de/url?sa=t&rct=j&q=beweis divisionssatz polynome
201206-06 (5x)http://google.it/url?sa=t&rct=j&q=normale form eines monoms
201208-08 (4x)http://google.de/url?sa=t&rct=j&q=monomordnung invers lexikographish
201209-09 (4x)http://google.de/url?sa=t&rct=j&q=polynome divisionssatz
2016-2017 (4x)http://google.dk/url?sa=i&rct=j&q=

[Top of page]

"Mathematik: Der Divisionssatz" | 2 Comments
The authors of the comments are responsible for the content.

Re: Der Divisionssatz
von: FlorianM am: Do. 16. Juni 2005 21:20:59
\(\begingroup\)Sehr schöne Darstellung. Gefällt mir wieder mal sehr gut, wie dein anderer Artikel! :)\(\endgroup\)
 

Re: Der Divisionssatz
von: Hans-im-Pech am: Di. 21. Juni 2005 11:04:12
\(\begingroup\)Sehr schöner Artikel! Verständlich und doch ausführlich! Viele Grüße, HiP\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]