Benutzer:Ap86/Artikelwerkstatt

Einleitung

Der Buchberger-Algorithmus ist ein 1965 von Bruno Buchberger entwickeltes Verfahren zur Berechnung einer Gröbnerbasis zu einem Ideal in einem Polynomring über einen Körper. Mithilfe des Buchberger-Algorithmus lässt sich z.B. die Lösung polynomialer Gleichungsysteme in mehreren Veränderlichen auf die Lösung einer Sequenz univariater Gleichungen reduzieren, welche nun wiederum algebraisch oder numerisch erfolgen kann.

Grundlagen

Sei $K$ ein Körper, $K[x_{1},\ldots ,x_{n}]$ der Polynomring in $x_{1},\ldots ,x_{n}$ über K. Diese können wir als die Menge aller Abbildungen der n-ten kartesischen Potenz der Menge der natürlichen Zahlen auf K, wobei nur endlich viele Elemente der Urbildmenge nicht auf das Nullelement abgebildet werden, auffassen, also: $K[x_{1},\ldots ,x_{n}]=K[\mathbb {N} ^{n}]=\lbrace f:\mathbb {N} \rightarrow K\vert \exists l\in \mathbb {N} :\vert \lbrace v\vert f(v)\neq 0\rbrace \vert =l\rbrace$

Nun wollen wir das Konzept des Kopfterms bei univariaten Polynomen auf den multivariaten Fall verallgemeinern. Da auf $\mathbb {N} ^{n}$ keine natürliche Ordnung zur Verfügung steht, benötigen wir folgende Konstruktion:

Definition: Sei $\leq$ eine Halbordnung auf $\mathbb {N} ^{n}$. $\leq$ wird als Termordnung bezeichnet, wenn die folgenden Axiome zusätzlich erfüllt sind:

(1)$\forall a\in \mathbb {N} ^{n}:0\leq a$ (0 ist das kleinste Element)

(2)$\forall a,b,c\in \mathbb {N} ^{n}:a\leq b\Rightarrow a+c\leq b+c$ (Monotonie der Addition)

(3)$\forall a,b\in \mathbb {N} ^{n}:a\leq b\lor b\leq a$ (vollständige Ordnung)

Der Initialterm eines Polynoms $P\in K[x_{1}\ldots x_{n}]$ bezüglich einer Termordnung $\leq$ ist nun wie folgt definiert:

$in_{\leq }(p)=aX^{v},a\in K,v\in \mathbb {N} ^{n}\Leftrightarrow f(v)=a\land \forall w\in \mathbb {N} ^{n}:v<w\Rightarrow f(v)=0$

Hierbei bleiben vom univariaten Fall bekannte Strukturen, wie z.B. $in_{\leq }(pq)=in_{\leq }(p)in_{\leq }(q)$ erhalten. Dies ermöglicht uns die Definition einer multivariaten Division:

Satz: Für alle Poylnome $f,f_{1},\ldots ,f_{m}\in K[x_{1},\ldots ,x_{n}]$ existieren Polynome $r,a_{1},\ldots ,a_{m}\in K[x_{1},\ldots ,x_{n}]$, sodass

$f=\sum _{i=1}^{m}a_{i}f_{i}+r$ mit $\forall 1\leq i\leq m:in_{\leq }(a_{i}f_{i})\leq in_{\leq }(f)$ und keiner der Terme in r von irgendeinem $in_{\leq }(f_{i}),1\leq i\leq m$ geteilt wird.

Statt eines Beweises geben wir folgenden Divisionsalgorithmus an (Der Beweis folgt dann unmittelbar):
Algorithmus: Multivariate Division

Eingabe: $f,f_{1},\ldots ,f_{m}\in K[x_{1},\ldots ,x_{n}]$

Ausgabe: $r,a_{1},\ldots ,a_{m}\in K[x_{1},\ldots ,x_{n}]$

Initialisierung: $s:=f,a_{1},\ldots ,a_{m}:=0,r:=0$

while $s\neq 0$

for $1\leq i\leq m$

if $(in_{\leq }(f_{i})\vert in_{\leq }(s))$ then

$a_{i}:=a_{i}+{\frac {in_{\leq }(s)}{in_{\leq }(f_{i})}}$

$s:=s-{\frac {in_{\leq }(s)}{in_{\leq }(f_{i})}}f_{i}$

break

else if i=m

$r:=r+in_{\leq }(s)$

$s:=s-in_{\leq }(s)$

end if

end for

end while