This is documentation for Mathematica 4, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

 Documentation /  Mathematica /  Das Mathematica Buch /  Höhere Mathematik in Mathematica /  Algebraische Manipulation /

Strukturoperationen auf rationalen AusdrückenPolynome modulo Primzahlen

3.3.4 Algebraische Operationen auf Polynomen

Bei den meisten praktischen Berechnungen werden die einzigen Operationen, die man auf Polynome anwenden muß, die strukturellen Operationen sein, die in den vorangegangenen Abschnitten erörtert worden sind.

Betreibt man jedoch fortgeschrittenere Algebra mit Polynomen, so müssen die in diesem Abschnitt behandelten algebraischen Operationen verwendet werden.

Man sollte bedenken, daß die meisten der in diesem Abschnitt beschriebenen Operationen nur mit gewöhnlichen Polynomen funktionieren, bei denen jeder Term ganzzahlige Exponenten und rationale Koeffizienten hat.

Reduzierung von Polynomen

Für zwei gegebene Polynome und kann man immer eindeutig schreiben, wobei der Grad von kleiner als der Grad von ist. PolynomialQuotient ergibt den Quotienten und PolynomialRemainder den Rest .

Dies ergibt den Rest bei der Division von durch .

In[1]:= PolynomialRemainder[x^2, x+1, x]

Out[1]=

Hier ist der Quotient von und , wobei der Rest weggelassen wird.

In[2]:= PolynomialQuotient[x^2, x+1, x]

Out[2]=

Dies liefert den ursprünglichen Ausdruck zurück.

In[3]:= Simplify[ (x+1) % + %% ]

Out[3]=

Hier hängt das Ergebnis davon ab, ob die Polynome als solche in x oder in y angesehen werden.

In[4]:= {PolynomialRemainder[x+y, x-y, x],
PolynomialRemainder[x+y, x-y, y]}

Out[4]=

PolynomialGCD[, ] bestimmt das Polynom mit dem höchsten Grad, das die jeweils ohne Rest teilt. Diese Funktion für Polynome entspricht der Funktion GCD für ganze Zahlen.

PolynomialGCD ergibt den größten gemeinsamen Teiler der beiden Polynome.

In[5]:= PolynomialGCD[ (1-x)^2 (1+x) (2+x), (1-x) (2+x) (3+x) ]

Out[5]=

PolynomialMod ist für Polynome im wesentlichen das Analogon zur Funktion Mod für ganze Zahlen. Ist der Modul m eine ganze Zahl, reduziert PolynomialMod[poly, m] einfach jeden Koeffizienten in poly modulo der ganzen Zahl m. Ist m ein Polynom, so versucht PolynomialMod[poly, m] im Grunde ein Polynom möglichst kleinen Grades zu erhalten, indem von poly geeignete Vielfache von m subtrahiert werden. Der Faktor q kann selbst ein Polynom sein, dessen Grad jedoch immer kleiner als der Grad von poly ist. PolynomialMod liefert als Ergebnis ein Polynom, dessen Grad und dessen führender Koeffizient beide so klein wie möglich sind.

Dies reduziert modulo . Das Ergebnis ist einfach der Rest bei der Polynomdivision.

In[6]:= PolynomialMod[x^2, x+1]

Out[6]=

In diesem Fall ergeben PolynomialMod und PolynomialRemainder nicht das gleiche Ergebnis.

In[7]:= {PolynomialMod[x^2, 2x+1],
PolynomialRemainder[x^2, 2x+1, x]}

Out[7]=

Der Hauptunterschied zwischen PolynomialMod und PolynomialRemainder ist der, daß das erste einfach mit Multiplikation und Subtraktion von Polynomen arbeitet, während das zweite die Division zum Bestimmen von Ergebnissen benutzt. Zusätzlich erlaubt PolynomialMod die gleichzeitige Reduktion nach mehreren Moduli. Ein typischer Fall ist die Reduktion sowohl modulo einem Polynom als auch modulo einer ganzen Zahl.

Dies reduziert das Polynom sowohl modulo als auch .

In[8]:= PolynomialMod[x^2 + 1, {x + 1, 2}]

Out[8]=

Die Funktion Resultant[, , x] wird in einer Reihe von klassischen algebraischen Algorithmen benötigt. Die Resultante der beiden Polynome und , beide mit führendem Koeffizienten Eins, ist durch das Produkt aller Differenzen zwischen den Polynom-Wurzeln gegeben. Es stellt sich heraus, daß für jedes Polynompaar die Resultante immer ein Polynom in ihren Koeffizienten ist. Durch Betrachtung der Nullstellen der Resultante läßt sich feststellen, für welche Werte ihrer Parameter zwei Polynome eine gemeinsame Wurzel haben. Zwei Polynome mit Eins als führendem Koeffizienten haben gemeinsame Wurzeln, wenn genau die ersten Elemente in der Liste Subresultants[, , x] Null sind.

Hier ist die Resultante bezüglich für die beiden Polynome in und . Die ursprünglichen Polynome haben eine gemeinsame Wurzel in nur für Werte von , an denen die Resultante verschwindet.

In[9]:= Resultant[(x-y)^2-2, y^2-3, y]

Out[9]=

Gröbner-Basen tauchen in vielen modernen algebraischen Algorithmen und Anwendungen auf. Die Funktion GroebnerBasis[, , ... , , , ... ] akzeptiert einen Satz Polynome und reduziert diesen Satz in eine kanonische Form, der viele Eigenschaften leicht zu entnehmen sind. Eine wichtige Eigenschaft ist, daß der durch GroebnerBasis produzierte Polynom-Satz immer genau dieselbe Menge gemeinsamer Wurzeln wie der ursprüngliche Satz hat.

ist im Grunde redundant und erscheint deshalb nicht in der Gröbner-Basis.

In[10]:= GroebnerBasis[{(x+y), (x+y)^2}, {x, y}]

Out[10]=

Das Polynom 1 hat keine Wurzeln; die ursprünglichen Polynome haben also auch keine gemeinsamen Wurzeln.

In[11]:= GroebnerBasis[{x+y,x^2-1,y^2-2x}, {x, y}]

Out[11]=

Die Polynome werden hier im Grunde entwirrt, und es können hier genau fünf gemeinsame Wurzeln identifiziert werden.

In[12]:= GroebnerBasis[{x y^2+2 x y+x^2+1, x y+y^2+1}, {x, y}]

Out[12]=

PolynomialReduce[poly, , , ... , , , ... ] liefert eine Liste , , ... , b mit Polynomen mit der Eigenschaft, daß b minimal und + + ... + b genau gleich poly ist.

Dies schreibt in Termen mit und , wobei ein Rest bleibt, der nur von abhängt.

In[13]:= PolynomialReduce[x^2 + y^2, {x - y, y + a}, {x, y}]

Out[13]=

Funktionen zur Faktorisierung von Polynomen

Factor, FactorTerms und FactorSquareFree führen verschiedene Stufen der Faktorzerlegung bei Polynomen durch. Factor führt vollständige Faktorisierung über den ganzen Zahlen durch. FactorTerms extrahiert den „Inhalt" des Polynoms. FactorSquareFree zieht alle auftretenden Mehrfachfaktoren heraus.

Hier ist ein Polynom in ausmultiplizierter Form.

In[14]:= t = Expand[ 2 (1 + x)^2 (2 + x) (3 + x) ]

Out[14]=

FactorTerms zieht nur den Faktor 2 heraus, der nicht von x abhängt.

In[15]:= FactorTerms[t, x]

Out[15]=

FactorSquareFree klammert den Term 2 und den Term (1 + x)^2 aus, läßt aber den Rest unfaktorisiert.

In[16]:= FactorSquareFree[t]

Out[16]=

Factor bewirkt die vollständige Faktorzerlegung und stellt dabei die ursprüngliche Form wieder her.

In[17]:= Factor[t]

Out[17]=

Besonders dann, wenn Sie Programme schreiben, die mit Polynomen arbeiten, werden Sie es nützlich finden, wenn Sie Teile von Polynomen in einer Standardform auswählen können. Die Funktion FactorList liefert eine Liste mit allen Faktoren eines Polynoms, zusammen mit ihren Exponenten. Das erste Element der Liste ist immer der gemeinsame numerische Faktor des Polynoms.

Die von FactorList zurückgegebene Form ist das Analogon für Polynome zur von FactorInteger erzeugten Form für ganze Zahlen.

Hier ist eine Liste mit Faktoren des Polynoms im vorigen Satz von Beispielen. Jedes Element der Liste liefert den Faktor zusammen mit seinem Exponenten.

In[18]:= FactorList[t]

Out[18]=

Faktorisierung von Polynomen mit komplexen Koeffizienten

Factor und verwandte Funktionen verarbeiten normalerweise nur Polynome mit ganzen oder rationalen Zahlen als Koeffizienten. Wenn Sie jedoch die Option GaussianIntegers -> True setzen, wird Factor Polynome zulassen, deren Koeffizienten komplexe Zahlen mit rationalen Real- und Imaginärteilen sind. Dadurch wird oft eine weitergehende Faktorzerlegung ermöglicht.

Dieses Polynom ist irreduzibel, wenn nur ganze Zahlen erlaubt sind.

In[19]:= Factor[1 + x^2]

Out[19]=

Wenn ganze Gaußsche Zahlen als Koeffizienten zugelassen werden, läßt sich das Polynom faktorisieren.

In[20]:= Factor[1 + x^2, GaussianIntegers -> True]

Out[20]=

Kreisteilungspolynome

Kreisteilungspolynome erscheinen als „elementare Polynome" in diversen algebraischen Algorithmen. Die Kreisteilungspolynome sind definiert durch , wobei die positiven ganzen Zahlen kleiner als durchläuft, die teilerfremd zu sind.

Dies ist das Kreisteilungspolynom .

In[21]:= Cyclotomic[6, x]

Out[21]=

erscheint in den Faktoren von .

In[22]:= Factor[x^6 - 1]

Out[22]=

Zerlegung von Polynomen

Faktorisierung ist eine wichtige Methode, Polynome in einfachere Teile zu zerlegen. Eine andere, davon ziemlich verschiedene Methode ist die Zerlegung. Wenn man ein Polynom faktorisiert, schreibt man es als Produkt der Polynome . Die Zerlegung eines Polynoms besteht darin, es als Komposition von Polynomen der Form zu schreiben.

Hier ist ein einfaches Beispiel von Decompose. Das ursprüngliche Polynom kann als das Polynom geschrieben werden, wobei das Polynom bedeutet.

In[23]:= Decompose[x^4 + x^2 + 1, x]

Out[23]=

Hier sind zwei Polynomfunktionen.

In[24]:= ( q1[x_] = 1 - 2x + x^4 ;
q2[x_] = 5x + x^3 ; )

Dies ergibt die Komposition der beiden Funktionen.

In[25]:= Expand[ q1[ q2[ x ] ] ]

Out[25]=

Decompose stellt die ursprünglichen Funktionen wieder her.

In[26]:= Decompose[%, x]

Out[26]=

Decompose[poly, x] ist so angelegt, daß es eine Liste von Polynomen in x liefert, die das ursprüngliche Polynom wiederherstellen, wenn sie miteinander verknüpft werden. Das ursprüngliche Polynom kann andere Variablen als x enthalten, aber die von Decompose erzeugte Folge von Polynomen werden nach Voraussetzung alle als Funktionen von x angesehen.

Im Unterschied zur Faktorisierung ist die Zerlegung von Polynomen nicht vollkommen eindeutig. Zum Beispiel ergeben die beiden Sätze von Polynomen und , verknüpft durch und , das gleiche Ergebnis bei der Komposition, so daß gilt. Mathematica folgt der Konvention, daß alle konstanten Terme vom ersten Polynom in der von Decompose aufgestellten Liste absorbiert werden.

Erzeugen von Interpolationspolynomen

Dies ergibt ein quadratisches Polynom, das durch die spezifizierten drei Punkte verläuft.

In[27]:= InterpolatingPolynomial[{{-1, 4}, {0, 2}, {1, 6}}, x]

Out[27]=

Wenn x gleich 0 ist, hat das Polynom den Wert 2.

In[28]:= % /. x -> 0

Out[28]=

Strukturoperationen auf rationalen AusdrückenPolynome modulo Primzahlen