Polynomdivision

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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, wobei der Grad von r kleiner als der von q sein soll. Die Situation ist analog zur Division mit Rest bei ganzen Zahlen.

Inhaltsverzeichnis

1 Anwendungen
2 Berechnung
- 2.1 Manueller Ablauf
- 2.2 Algorithmus
3 Pseudo-Division
- 3.1 Beispiel
- 3.2 Algorithmus
4 Siehe auch
5 Weblinks

[Bearbeiten] Anwendungen

Eine Anwendung ist das 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 Näherungskurven 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.

[Bearbeiten] Berechnung

[Bearbeiten] 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 $4 x 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.

[Bearbeiten] 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.

[Bearbeiten] Pseudo-Division

Die oben beschriebene Methode zur Polynomdivision ist nur dann anwendbar, wenn der Leitkoeffizient des Divisors $q (x)$ eine Einheit im Grundring ist. Über allgemeinen Grundringen muss das jedoch nicht immer der Fall sein. Deswegen wird eine sogenannte Pseudo-Division definiert, die über allen Integritätsringen funktioniert. Gelöst wird dabei nicht die obige Gleichung, sondern die leicht variierte Gleichung

$\alpha p(x) = s(x) q(x) + r(x), \!$

wobei die Polynome $p$ und $q$ vorgegeben sind und eine Konstante $α$ sowie Polynome $s$ und $r$ gesucht werden. Auch hier soll wieder der Grad von $r$ kleiner als derjenige von $q$ sein.

Das Vorgehen ist ähnlich der normalen Polynomdivision. Allerdings werden im Divisionsschritt das Polynom nicht nur $q$ sondern auch $p$ mit geeigneten Faktoren multipliziert, um zu erreichen, dass die Leitkoeffizienten sich gegenseitig herauslöschen.

[Bearbeiten] Beispiel

Als Beispiel soll eine Pseudo-Division im Polynomring $\Z[x]$ über den ganzen Zahlen durchgeführt werden. Seien

$p(x) = 2x^2 + 1 \quad\hbox{und}\quad q(x) = 5x + 5.$

Eine normale Polynomdivision ist hier nicht möglich, da $5$ , der Leitkoeffizienten von $q$ , in $\Z$ nicht invertierbar ist. Wir können aber $p$ mit $5$ multiplizieren. Nun kann man $q$ mit $2 x$ multipliziert abziehen und erhält.

5 p (x) - 2 x q (x) = 10 x 2 + 5 - 10 x 2 - 10 x = - 10 x + 5.

Der Grad von $- 10 x + 5$ ist dabei kleiner als derjenige von $p$ aber noch nicht kleiner als der von $q$ . Ziehen wir nun von diesem Zwischenergebnis $- 2$ -mal $q$ ab, erhalten wir

- 10 x + 5 - ( - 2) q (x) = - 10 x + 5 + 10 x + 10 = 15.

Da $15$ als konstantes Polynom einen kleineren Grad als $q$ besitzt, sind wir hier fertig. Rückwärts einsetzen ergibt

15 = (5 p (x) - 2 x q (x)) - ( - 2) q = 5 p (x) - (2 x - 2) q (x)

oder umgeformt

5 p (x) = (2 x - 2) q (x) + 15.

Eine Probe bestätigt dies.

[Bearbeiten] Algorithmus

Das Vorgehen soll nun noch durch den Algorithmus illustriert werden. Dieser rekursive Algorithmus hat als Argumente zwei Polynome $p$ und $q$ , wobei $q$ nicht das Nullpolynom sein darf, sowie die Variable $x$ , bezüglich der die Pseudodivision zu erfolgen hat. Das Ergebnis ist ein Tripel $(c, s, r)$ bestehend aus Polynomen $s$ und $r$ sowie einer Konstanten $c$ , so dass $c p = s q + r$ und $\operatorname{grad}(r) < \operatorname{grad}(q)$ gelten.

   pseudoDivision(p, q, x) =
     if d < 0
     then (1, 0, p)
     else (c * a, c * t + s, r) where
       d       = grad(p, x) - grad(q, x)
       a       = lcoeff(q, x)
       b       = lcoeff(p, x)
       t       = b*x^d
       (c,q,r) = pseudoDivision(a*p - t*q, q, x)

Hierbei liefert $\operatorname{grad}(f, x)$ den Grad sowie $\operatorname{lcoeff}(f, x)$ den Leitkoeffizienten eines Polynomes. Man kann noch weitere Verbesserungen am Algorithmus vornehmen, indem man etwa wie im Beispiel die Multiplikation mit a unterlässt, wenn sie nicht notwendig ist.