Größter gemeinsamer Teiler von Polynomen
Dieser Rechner erstellt den ggT (größten gemeinsamer Teiler) von zwei Polynomen.
Dieser Online-Rechner ermittelt den größten gemeinsamen Teiler eines Polynoms mit dem euklidischen Algorithmus und der Polynomdivision. Die Polynom-Koeffizienten sind Ganzzahlen, Brüche oder komplexe Zahlen mit Ganzzahlen oder Brüche von realen oder imaginären Teilen. Das Ergebnis ist ein Polynom, welches zwei eingebebene Polynome ohne Reste teilt, oder mit 1, falls es solch ein Polynom nicht gibt.
Größter gemeinsamer Teiler von Polynomen
Das Phänomen des explosiven Koeffizientenwachstum.
Für die Berechnung des ggT von Polynomen größeren Grades, wachsen die Reste-Koeffizienten extrem an. Selbst in diesem Rechner kann man dies and den Standardeingabedaten sehen; die Restesequenz beinhaltet große Brüche. Um diese Brüche zu eliminieren und die Ganzzahlkoeffizienten reduzieren, kann man eine Pseudo-Division mit einem Reduktionsalgorithmus für den Restekoeffizient. In dem Rechner stehen 3 Algorithmen für die Resteberechnung zur Verfügung, ohne die Pseudo-Division ohne Koeffizient Reduktion mitzuzählen.
Die beste Koeffizient-Reduktion bekommt man mit der Reduktionsmethode, in der alle Terme mit dem ggT der Koeffizienten geteilt wird. Aber die Berechnungskosten für diese Methode sind inakzeptabel hoch für Polynome mit hohen Graden mit komplexen Koeffizienten, da der euklidische Algorithmus für jeder Iteration für jegliche Koeffizienten angewandt wird.
Als Kompromissvariante für die Kontrolle des Koeffizientenwachstum werden Algorithmen genutzt, die auf sich ergebenden PRS basiert sind. Der Rechner nutzt zwei von denen (Algorithmus 1 und Algorithmus 3), die von W.S. Brown im Artikel „The Subresultant PRS Algorithm1“ beschrieben wurden
Der Rechner erstellt eine Pseudo-Reste Tabelle mit Polynominhalt für jeden Rest, um die Algorithmus-Effektivität zu schätzen. Je geringer der Inhalt ist, desto höher die Algorithmus-Effektivität.
-
W.S. Brown, Bell Laboratories. ACM Transactions on Mathematical Software, Vol 4, No 3, September 1978, p.p. 237-249
tical Software, Vol 4, No 3, September 1978, p.p. 237-249 ↩
Kommentare