Polynomdivision

Die Polynomdivision, auch Partialdivision genannt, ist ein mathematisches Verfahren zur Lösung der Gleichung

p(x)=s(x)q(x)+r(x)\!

bei gegebenen Polynomen p und q über einem Polynomring, also der Bestimmung der Polynome s und r. Die Situation ist analog zur Division mit Rest bei ganzen Zahlen. Die Polynomdivison war zu Zeiten Caesars auch als dreispaltiger Grottenschlund bekannt.

Anwendungen

Eine Anwendung ist das näherungsweise numerische Lösen von Gleichungen höheren Grades. Wenn eine Lösung x_n z. B. durch Intervallschachtelung gefunden wurde, findet die Polynomdivision Anwendung, um den Grad der Gleichung um Eins zu senken.

Eine weitere Anwendung findet die Polynomdivision bei der Bestimmung der Asymptoten einer rationalen Funktion (siehe Kurvendiskussion).

Bei der Berechnung von Prüfsummen findet die Polynomdivision über dem Ring der ganzen Zahlen modulo 2 Anwendung. Siehe CRC-Polynom.

Berechnung

Manueller Ablauf

Das Verfahren funktioniert genau so wie die schriftliche Division ganzer Zahlen und kann mit dem gleichen Schema gelöst werden. Hier sind die einzelnen Schritte erläutert:

So lösen Sie die Aufgabe

{\frac {p(x)}{q(x)}}={\frac {4\cdot x^{5}-x^{4}+2\cdot x^{3}+x^{2}-1}{x^{2}+1}}

Wie bei der Division ganzer Zahlen kümmern wir uns zuerst nur darum, den höchsten Anteil des Polynoms zu eliminieren. Dazu müssten wir q mit $4x^{3}$ multiplizieren, denn die höchste Potenz von q ist $x^{2}$ und es gilt $4x^{5}=x^{2}\cdot 4x^{3}$ .

{\begin{matrix}(4x^{5}&-x^{4}&+2x^{3}&+x^{2}&-1)&:&(x^{2}&+1)&=&4x^{3}\dots \\{\underline {-4x^{5}}}&&{\underline {-4x^{3}}}&&&&&&&\\&-x^{4}&-2x^{3}&&&&&&&\end{matrix}}

Man eliminiert jetzt immer weiter die jeweils höchste Potenz, bis man einen Rest erhält, der nicht mehr weiter eliminiert werden kann, weil der Grad des Rests kleiner als der Grad von q ist.

{\begin{matrix}(4x^{5}&-x^{4}&+2x^{3}&+x^{2}&-1)&:&(x^{2}&+1)&=&4x^{3}-x^{2}-2x+2+{\frac {2x-3}{x^{2}+1}}\\{\underline {-4x^{5}}}&&{\underline {-4x^{3}}}&&&&&&&\\&-x^{4}&-2x^{3}&&&&&&&\\&{\underline {+x^{4}}}&&{\underline {+x^{2}}}&&&&&&\\&&-2x^{3}&+2x^{2}&&&&&&\\&&{\underline {+2x^{3}}}&&{\underline {+2x}}&&&&&\\&&&2x^{2}&+2x&-1&&&&\\&&&{\underline {-2x^{2}}}&&{\underline {-2}}&&&\\&&&&2x&-3&&&&\end{matrix}}

Ein mögliches Verständnisproblem beim „Herausdividieren einer Nullstelle“ besteht darin, dass man vermeintlich durch 0 dividiert. Dies ist jedoch nicht der Fall, da man nicht Zahlen dividiert, sondern Polynome. Da das Polynom $x^{2}+1$ nicht das Nullpolynom ist, kann man (mit Rest) durch dieses Polynom dividieren.

Algorithmus

Das folgende Code-Fragment in BASIC zeigt den Kern der Berechnung:

   For i = GradZ - GradN To 0 Step -1
       Quotient(i) = Zähler(i + GradN) / Nenner(GradN)
       For j = GradN To 0 Step -1
           Zähler(i + j) = Zähler(i + j) - Nenner(j) * Quotient(i)
       Next j
   Next i
   For j = GradN - 1 To 0 Step -1
       Rest(j) = Zähler(j)
   Next j

Die Variable Zähler() ist ein Feld (Array), welches die Koeffizienten des Zählerpolynoms enthält, so dass Zähler(i) den Koeffizienten der Potenz $x^{i}$ enthält. Sinngemäß ist Nenner() ein weiteres Feld, welches in gleicher Art die Koeffizienten des Nennerpolynoms enthält. Das Ergebnis ist ein Polynom, welches in Quotient() und Rest() ausgegeben wird. Die Variablen GradN und GradZ enthalten den jeweiligen Polynomgrad von Zähler und Nenner.

In einem optimierten Programm würde man die innere Schleife von 0 bis (GradN-1) laufen lassen und die Ergebnisse in Zähler() zurückschreiben, so dass die Variablen Quotient() und Rest() entfallen würden. Der Einfachheit halber wurde hier darauf verzichtet.

Siehe auch

Partialbruchzerlegung

Weblinks