imported>FerdiBf: Änderung 252155959 von Lebsj rückgängig gemacht; Der Link auf "Division mit Rest" ist hier nicht hilfreich.

2025-02-26T15:17:41Z

Änderung 252155959 von Lebsj rückgängig gemacht; Der Link auf "Division mit Rest" ist hier nicht hilfreich.

Neue Seite

Eine '''Polynomrestfolge''' entsteht durch wiederholte Division mit Rest zweier [[Polynom]]e. Falls es sich um Polynome mit Koeffizienten aus einem [[Körper (Algebra)|Körper]] handelt, liefert zum Beispiel der [[Euklidischer Algorithmus|euklidische Algorithmus]] eine solche Folge. Im allgemeineren Fall von Polynomen mit Koeffizienten aus einem [[Faktorieller Ring|faktoriellen Ring]] muss jedoch der Dividend mit einer geeigneten Konstante multipliziert werden, um die Division mit Rest durchführen zu können ([[Pseudodivision]]).

Polynomrestfolgen werden in der Computeralgebra zur Berechnung eines [[größter gemeinsamer Teiler|größten gemeinsamen Teilers]] zweier Polynome eingesetzt. Das dort auftretende Problem, dass die Koeffizienten der Polynome exponentiell anwachsen, wird durch das Subresultantenverfahren gelöst.

== Definition ==

Für zwei Polynome <math>f,g \in R[x]</math>, <math>g \not = 0</math>, mit Koeffizienten aus einem faktoriellen Ring <math>R</math> ist gibt es stets Polynome <math>q, r\in R[x]</math>, so dass

:<math> \mathrm{lc}(g)^{\mathrm{deg}(f)-\mathrm{deg}(g)+1}f \,=\, qg + br</math> und <math>\mathrm{deg}(r) \,<\, \mathrm{deg}(g)</math>

gilt; dabei bezeichnet <math>\mathrm{lc}(g)</math> den Leitkoeffizienten von <math>g</math>. Dabei wird <math>r</math> als ''Pseudorest'' und <math>q</math> als ''Pseudoquotient'' bezeichnet (''Pseudodivision'', s. [[Donald Knuth]], Abschnitt 4.6.1), und wir schreiben

:<math>r = \mathrm{prem}(f,g)</math>.

Polynome <math>f</math> und <math>g</math> heißen ''ähnlich'', in Zeichen <math>f \sim g</math>, falls es <math>a,b\in R</math> gibt mit

:<math>af = bg.</math>

Eine Folge <math>p_0, p_1,\ldots,p_n</math> von Polynomen heißt ''Polynomrestfolge'', falls

:<math>p_{i+2} \ \sim \ \mathrm{prem}(p_i, p_{i+1})</math>

für <math>k = 0,\ldots,n-2</math> sowie

:<math>\mathrm{prem}(p_{n-1},p_n) = 0</math>

gelten.

== Spezielle Restfolgen ==

=== Pseudo-Polynomrestfolge ===

Zu Polynomen <math>p_0, p_1</math> liefert

:<math>p_{k+2} := \mathrm{prem}(p_k,p_{k+1})</math>

eine Polynomrestfolge, die ''Pseudo-Polynomrestfolge'' genannt wird. In der Praxis hat sie den Nachteil, dass die Koeffizienten der Polynome <math>p_k</math> exponentiell anwachsen.

=== Primitive Polynomrestfolge ===

Dividiert man ein Polynom durch seinen [[Inhalt (Polynom)|Inhalt]], so erhält man ein Polynom, dessen Koeffizienten teilerfremd sind (primitiver Anteil des Polynoms, ppart). Dies führt zur Folge

:<math>p_{k+2} := \mathrm{ppart}(\mathrm{prem}(p_k,p_{k+1})),</math>

die ''primitive Polynomrestfolge'' genannt wird. Um diese Folge zu berechnen, sind allerdings ggT-Berechnungen im Koeffizientenring <math>R</math> erforderlich, die in der Praxis viel Rechenzeit in Anspruch nehmen.

=== Subresultantenfolge ===

In der Praxis wird üblicherweise die durch

:<math>p_{k+2} := \frac{\mathrm{prem}(p_k,p_{k+1})}{g_k \cdot h_k^{\delta_k}}</math>

definierte Folge eingesetzt. Dabei ist

:<math>\delta_k := \mathrm{deg}(p_k) - \mathrm{deg}(p_{k+1})</math>

und <math>g_k</math> und <math>h_k</math> sind durch

:<math>h_0, g_0 := 1</math>
:<math>g_{k+1} := \mathrm{lc}(p_{k+1})</math>
:<math>h_{k+1} := h_k^{1-\delta_k}g_{k+1}^{\delta_k}</math>

definiert. Alle dabei vorkommenden Divisionen gehen auf, und die Koeffizienten der so definierten Polynome wachsen wesentlich langsamer als bei der Pseudo-Polynomrestfolge.

== Eigenschaften ==

Das letzte Glied <math>p_n</math> einer Polynomrestfolge ist ähnlich zum [[größter gemeinsamer Teiler|größten gemeinsamen Teiler]] der Polynome <math>p_0</math> und <math>p_1</math>:

:<math>p_n \ \sim \ \mathrm{ggT}(p_0, p_1).</math>

Polynomrestfolgen können daher zur ggT-Berechnung in [[Polynomring]]en eingesetzt werden.

== Literatur ==

* {{Literatur
|Autor=W. S. Brown, [[Joseph F. Traub]]
|Titel=On Euclid’s Algorithm and the Theory of Subresultants
|Sammelwerk=Journal of the ACM
|Band=18-4
|Datum=1971-10
|Seiten=505–514}}
* {{Literatur
|Autor=[[Donald E. Knuth]]
|Titel=The Art of Computer Programming
|Band=Vol. II: Seminumerical Algorithms
|Auflage=3.
|Verlag=Addison-Wesley
|Datum=1998}}
* {{Literatur
|Autor=Rüdiger Loos
|Hrsg=[[Bruno Buchberger]], G. E. Collins, Rüdiger Loos
|Titel=Generalized Polynomial Remainder Sequences
|Sammelwerk=Computer Algebra
|Verlag=Springer
|Datum=1982}}
* {{Literatur
|Autor=Attila Pethő
|Hrsg=[[Michael Pohst]]
|Titel=Algebraische Algorithmen
|Verlag=Vieweg
|Datum=1999
|ISBN=978-3-528-06598-0}}
* {{Literatur
|Autor=Michael Kaplan
|Titel=Computeralgebra
|Verlag=Springer
|Datum=2005
|ISBN=3-540-21379-1}}

[[Kategorie:Theorie der Polynome]]

Polynomrestfolge - Versionsgeschichte

imported>FerdiBf: Änderung 252155959 von Lebsj rückgängig gemacht; Der Link auf "Division mit Rest" ist hier nicht hilfreich.