Quadratfreies Polynom – Wikipedia
Polynom ohne wiederholte Wurzel
In der Mathematik a quadratfreies Polynom ist ein Polynom, das über ein Feld (oder allgemeiner eine eindeutige Faktorisierungsdomäne) definiert ist, das kein Quadrat eines Nicht-Einheitsfaktors als Faktor hat. Im wichtigen Fall von univariaten Polynomen über einem Feld k, Dies bedeutet, dass
ist genau dann quadratfrei, wenn
für jedes Polynom
von positivem Grad.[1] In Anwendungen in Physik und Technik wird ein quadratfreies Polynom üblicherweise als a bezeichnet Polynom ohne wiederholte Wurzeln. Solche Polynome werden trennbar genannt, aber über einem perfekten Feld ist trennbar dasselbe wie quadratfrei.
EIN quadratfreie Zersetzung oder quadratfreie Faktorisierung eines Polynoms ist eine Faktorisierung in Potenzen quadratfreier Faktoren
wo die der eink die nicht gleich 1 sind, sind paarweise quadratische Coprime-Polynome.[1] Jedes Nicht-Null-Polynom mit Koeffizienten in einem Feld lässt eine quadratfreie Faktorisierung zu, die bis zur Multiplikation der Faktoren mit Nicht-Null-Konstanten eindeutig ist. Die quadratfreie Faktorisierung ist viel einfacher zu berechnen als die vollständige Faktorisierung in irreduzible Faktoren und wird daher häufig bevorzugt, wenn die vollständige Faktorisierung nicht wirklich benötigt wird, wie für die partielle Bruchzerlegung und die symbolische Integration rationaler Brüche. Die quadratfreie Faktorisierung ist der erste Schritt der Polynomfaktorisierungsalgorithmen, die in Computeralgebrasystemen implementiert sind. Daher ist der Algorithmus der quadratfreien Faktorisierung in der Computeralgebra grundlegend.
Im Fall von univariaten Polynomen über einem Feld führt jeder Mehrfachfaktor eines Polynoms einen nichttrivialen gemeinsamen Faktor von ein f und seine formale Ableitung f ‘, Also eine ausreichende Bedingung für f quadratfrei zu sein ist, dass der größte gemeinsame Teiler von f und f ‘Ist 1. Diese Bedingung ist auch über ein Feld der Charakteristik 0 oder allgemeiner über ein perfektes Feld notwendig, da über ein solches Feld jedes irreduzible Polynom trennbar ist und somit mit seiner Ableitung koprimiert.
Über einem Feld der Charakteristik 0 ist der Quotient von
durch seine GCD mit seinem Derivat ist das Produkt der
in der obigen quadratfreien Zersetzung. Über ein perfektes Feld mit einer Charakteristik ungleich Null pist dieser Quotient das Produkt der
so dass ich ist kein Vielfaches von p. Weitere GCD-Berechnungen und exakte Teilungen ermöglichen die Berechnung der quadratfreien Faktorisierung (siehe quadratfreie Faktorisierung über ein endliches Feld). In der Charakteristik Null ist ein besserer Algorithmus bekannt, der Yun-Algorithmus, der nachstehend beschrieben wird.[1] Seine rechnerische Komplexität ist höchstens doppelt so hoch wie die der GCD-Berechnung des Eingabepolynoms und seiner Ableitung. Genauer gesagt, wenn
ist die Zeit, die benötigt wird, um die GCD von zwei Gradpolynomen zu berechnen
und dann den Quotienten dieses Polynoms durch die GCD
ist eine Obergrenze für die Zeit, die zur Berechnung der quadratfreien Zerlegung benötigt wird.
Es sind auch Algorithmen zur Berechnung der quadratfreien Zerlegung multivariater Polynome bekannt.[2]
Yuns Algorithmus[edit]
Dieser Abschnitt beschreibt den Yun-Algorithmus für die quadratfreie Zerlegung univariater Polynome über ein Feld der Charakteristik 0.[1] Es erfolgt durch eine Abfolge von GCD-Berechnungen und genauen Unterteilungen.
Die Eingabe ist somit ein Polynom ungleich Null fund der erste Schritt des Algorithmus besteht darin, die GCD zu berechnen ein0 von f und seine formale Ableitung f ‘.
Wenn
ist die gewünschte Faktorisierung, die wir also haben
und
Wenn wir setzen
,
und
Das verstehen wir
und
Iterieren Sie diesen Prozess bis
wir finden alle
Dies wird wie folgt in einen Algorithmus formalisiert:
wiederholen
bis um
Ausgabe
Der Grad von
und
ist eins weniger als der Grad von
Wie
ist das Produkt der
die Summe der Grade der
ist der Grad von
Da die Komplexität von GCD-Berechnungen und -Divisionen mehr als linear mit dem Grad zunimmt, folgt, dass die Gesamtlaufzeit der “Wiederholungs” -Schleife geringer ist als die Laufzeit der ersten Zeile des Algorithmus und dass die Gesamtlaufzeit von Yuns Algorithmus ist durch die doppelte Zeit begrenzt, die zur Berechnung der GCD von benötigt wird
und
und der Quotient von
und
durch ihre GCD.
Quadratwurzel[edit]
Im Allgemeinen hat ein Polynom keine Quadratwurzel. Genauer gesagt können die meisten Polynome nicht als Quadrat eines anderen Polynoms geschrieben werden.
Ein Polynom hat genau dann eine Quadratwurzel, wenn alle Exponenten der quadratfreien Zerlegung gerade sind. In diesem Fall wird die Quadratwurzel erhalten, indem diese Exponenten durch 2 geteilt werden.
Das Problem der Entscheidung, ob ein Polynom eine Quadratwurzel hat, und der Berechnung, ob es existiert, ist daher ein Sonderfall der quadratfreien Faktorisierung.
Verweise[edit]
Recent Comments