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.
Sei
ein Körper,
der Polynomring in
ü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:
Nun wollen wir das Konzept des Kopfterms bei univariaten Polynomen auf den multivariaten Fall verallgemeinern. Da auf
keine natürliche Ordnung zur Verfügung steht, benötigen wir folgende Konstruktion:
Definition: Sei
eine Halbordnung auf
.
wird als Termordnung bezeichnet, wenn die folgenden Axiome zusätzlich erfüllt sind:
- (1)
(0 ist das kleinste Element)
- (2)
(Monotonie der Addition)
- (3)
(vollständige Ordnung)
Der Initialterm eines Polynoms
bezüglich einer Termordnung
ist nun wie folgt definiert:
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/419ad69aa861d02575e3ebe472ac1afcc32a699d)
Hierbei bleiben vom univariaten Fall bekannte Strukturen, wie z.B.
erhalten. Dies ermöglicht uns die Definition einer multivariaten Division:
Satz: Für alle Poylnome
existieren Polynome
, sodass
mit
und keiner der Terme in r von irgendeinem
geteilt wird.
Statt eines Beweises geben wir folgenden Divisionsalgorithmus an (Der Beweis folgt dann unmittelbar):
Algorithmus: Multivariate Division
- Eingabe:
![{\displaystyle f,f_{1},\ldots ,f_{m}\in K[x_{1},\ldots ,x_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27984eb366cfc5c671d5045c0f00ae646a729e3f)
- Ausgabe:
![{\displaystyle r,a_{1},\ldots ,a_{m}\in K[x_{1},\ldots ,x_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df597eeee58436da208566afceecf95d7575ca9f)
- Initialisierung:
![{\displaystyle s:=f,a_{1},\ldots ,a_{m}:=0,r:=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/324ffa8a5be99c5b1af97b2d873b903dc831ca4b)
- while
- for
- if
then
![{\displaystyle a_{i}:=a_{i}+{\frac {in_{\leq }(s)}{in_{\leq }(f_{i})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd927982c0f47d717a220c30793a839ba79af6ad)
![{\displaystyle s:=s-{\frac {in_{\leq }(s)}{in_{\leq }(f_{i})}}f_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f0b67c32b0a4421025c4f264ff5e1394cef4b0c)
- break
- else if i=m
![{\displaystyle r:=r+in_{\leq }(s)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a7a926962d50add4658ca2f5e49cadb44200484)
![{\displaystyle s:=s-in_{\leq }(s)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/378a08207ced299a3770cef582d1d3604c4ed085)
- end if
- end for
- end while