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

${ displaystyle f in k[X]}}$

ist genau dann quadratfrei, wenn

${ displaystyle b ^ {2} nmid f}$

für jedes Polynom

${ displaystyle b in k[X]}}$

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

${ displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} cdots a_ {n} ^ {n} = prod _ {k = 1} ^ {n} a_ { k} ^ {k} ,}$

wo die der ein_k 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

${ displaystyle f}$

durch seine GCD mit seinem Derivat ist das Produkt der

${ displaystyle a_ {i}}$

in der obigen quadratfreien Zersetzung. Über ein perfektes Feld mit einer Charakteristik ungleich Null pist dieser Quotient das Produkt der

${ displaystyle a_ {i}}$

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

${ displaystyle T_ {n}}$

ist die Zeit, die benötigt wird, um die GCD von zwei Gradpolynomen zu berechnen

${ displaystyle n}$

und dann den Quotienten dieses Polynoms durch die GCD

${ displaystyle 2T_ {n}}$

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 ein₀ von f und seine formale Ableitung f ‘.

Wenn

${ displaystyle f = a_ {1} a_ {2} ^ {2} a_ {3} ^ {3} cdots a_ {k} ^ {k}}$

ist die gewünschte Faktorisierung, die wir also haben

${ displaystyle a_ {0} = a_ {2} ^ {1} a_ {3} ^ {2} cdots a_ {k} ^ {k-1},}$

${ displaystyle f / a_ {0} = a_ {1} a_ {2} a_ {3} cdots a_ {k}}$

und

${ displaystyle f ‘/ a_ {0} = sum _ {i = 1} ^ {k} ia_ {i}’ a_ {1} cdots a_ {i-1} a_ {i + 1} cdots a_ { k}.}$

Wenn wir setzen

${ displaystyle b_ {1} = f / a_ {0}}$

,

${ displaystyle c_ {1} = f ‘/ a_ {0}}$

und

${ displaystyle d_ {1} = c_ {1} -b_ {1} ‘}$

Das verstehen wir

${ displaystyle gcd (b_ {1}, d_ {1}) = a_ {1},}$

${ displaystyle b_ {2} = b_ {1} / a_ {1} = a_ {2} a_ {3} cdots a_ {n},}$

und

${ displaystyle c_ {2} = d_ {1} / a_ {1} = sum _ {i = 2} ^ {k} (i-1) a_ {i} ‘a_ {2} cdots a_ {i- 1} a_ {i + 1} cdots a_ {k}.}$

Iterieren Sie diesen Prozess bis

${ displaystyle b_ {k + 1} = 1}$

wir finden alle

${ displaystyle a_ {i}.}$

Dies wird wie folgt in einen Algorithmus formalisiert:

${ displaystyle a_ {0}: = gcd (f, f ‘); quad b_ {1}: = f / a_ {0}; quad c_ {1}: = f’ / a_ {0}; quad d_ {1}: = c_ {1} -b_ {1} ‘; quad i: = 1;}$

wiederholen

${ displaystyle a_ {i}: = gcd (b_ {i}, d_ {i}); quad b_ {i + 1}: = b_ {i} / a_ {i}; quad c_ {i + 1 }: = d_ {i} / a_ {i}; quad i: = i + 1; quad d_ {i}: = c_ {i} -b_ {i} ‘;}$

bis um

${ displaystyle b = 1;}$

Ausgabe

${ displaystyle a_ {1}, ldots, a_ {i-1}.}$

Der Grad von

${ displaystyle c_ {i}}$

und

${ displaystyle d_ {i}}$

ist eins weniger als der Grad von

${ displaystyle b_ {i}.}$

Wie

${ displaystyle f}$

ist das Produkt der

${ displaystyle b_ {i},}$

die Summe der Grade der

${ displaystyle b_ {i}}$

ist der Grad von

${ displaystyle f.}$

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

${ displaystyle f}$

und

${ displaystyle f ‘}$

und der Quotient von

${ displaystyle f}$

und

${ displaystyle f ‘}$

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]