Polynomdivision

Die Polynomdivision, auch Partialdivision genannt, ist ein mathematisches Rechenverfahren. Das Verfahren verläuft analog zur üblichen und in der Schule gelehrten Division von Zahlen mit Rest, nur dass hier statt zweier Zahlen zwei Polynome durch einander dividiert werden und als Ergebnis wieder zwei Polynome – der „Ganzteil“ und der Rest der Division – stehen.

Allgemein

Informell

Im Folgenden seien n und m natürliche Zahlen einschließlich Null (n,m\in \mathbb {N} _{0}) und der Einfachheit halber die Größen a_{i}\ (0\leq i\leq n) und b_{j}\ (0\leq j\leq m) stets ganze Zahlen, also Elemente von \mathbb {Z} . Hat man nun zwei Polynome, etwa

p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}\quad {\text{mit}}\ a_{n}\neq 0

und

q(x)=b_{m}x^{m}+b_{m-1}x^{m-1}+\cdots +b_{2}x^{2}+b_{1}x+b_{0}\quad {\text{mit}}\ b_{m}\neq 0,

so kann man sie unter gewissen formalen Voraussetzungen ähnlich wie ganze Zahlen durcheinander dividieren, also die Rechenaufgabe

p(x):q(x)=\;?

lösen. Im Ergebnis finden sich dann zwei Polynome: Ein Polynom s(x), das dem Ganzzahlquotienten in der Zahlendivision mit Rest entspricht, und ein Polynom r(x), das sich nicht mehr weiter durch q(x) teilen lässt und das dem Rest in der Zahlendivision entspricht:

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

oder in Analogie zur Schulschreibweise

p(x):q(x)=s(x){\text{ Rest }}r(x).

Das Verfahren zum Auffinden dieser Lösung, bestehend aus s(x) und r(x), ist die Polynomdivision.

Dass sich hiernach r(x) nicht weiter durch q(x) teilen lässt, ist gleichbedeutend damit, dass der Polynomgrad von r(x) kleiner ist als der von q(x), weshalb dies in der formalen Definition der Rechenvorschrift (Algorithmus) auch als Abbruchbedingung gefordert wird. In der Zahlendivision mit Rest wird stattdessen gefordert, dass der Rest kleiner als der Divisor ist. Beide Nebenbedingungen sorgen im jeweiligen Verfahren dafür, dass der Rest eindeutig bestimmt ist.

Bei der formalen Definition des Verfahrens werden einige zusätzliche Bedingungen beachtet. Das kommt daher, dass man Polynome im Allgemeinen viel weitläufiger definieren kann, als es hier zur einfacheren Erklärung geschehen ist oder man es zum Beispiel aus der Schule kennt. Die Koeffizienten eines Polynoms etwa können dann aus beliebigen Ringen stammen. Dann dürfen aber wiederum die Koeffizienten der beiden Polynome nicht aus verschiedenen Ringen stammen. Daher definiert man, dass die Polynome in einem gemeinsamen Polynomring liegen müssen. Auch reicht es nicht mehr zu fordern, dass der „höchste“ Koeffizient (Leitkoeffizient) b_{m} von q(x) nur ungleich Null sein müsse. Vielmehr muss man fordern, dass er zudem eine Einheit des Ringes sein muss. Oder es wird das unten beschriebene Verfahren der Pseudo-Division angewendet.

Formal

Bei der Polynomdivision sind zwei Polynome p(x) und q(x) eines Polynomringes R[x] gegeben, wobei R ein kommutativer Ring mit 1\neq 0 und der Leitkoeffizient von q(x) eine Einheit in R ist, und es wird die Gleichung

p(x)=s(x)q(x)+r(x),

nach den gesuchten Polynomen s(x) und r(x) gelöst, und zwar so, dass der Grad von r(x) kleiner als der von q(x) ist.

Anmerkungen

Anwendungen

Berechnung

Manueller Ablauf

Das Verfahren funktioniert für Polynome mit ganzzahligen Koeffizienten genau so wie die schriftliche Division ganzer Zahlen mit Rest und kann mit dem gleichen Schema gelöst werden. Hier werden die einzelnen Schritte am Beispiel

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

erläutert:

{\begin{matrix}(4x^{5}&-x^{4}&+2x^{3}&+x^{2}&-1)&:&(x^{2}&+1)&=&4x^{3}+\dotsb \\{\underline {-4x^{5}}}&&{\underline {-4x^{3}}}&&&&&&&\\&-x^{4}&-2x^{3}&&&&&&&\end{matrix}}
Es bleibt der Rest -x^{4}-2x^{3}+x^{2}-1.
{\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}}

Pseudo-Division

Die oben beschriebene Methode zur Polynomdivision ist nur dann anwendbar, wenn der Leitkoeffizient des Divisors q(x) eine Einheit im Grundring ist. Das ist immer der Fall, wenn der Grundring gleichzeitig auch ein Körper 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(x) und q(x) vorgegeben sind und eine Konstante \alpha sowie Polynome s(x) und r(x) gesucht werden. Auch hier soll wieder der Grad von r(x) kleiner als derjenige von q(x) sein.

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

Beispiel

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

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

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

5p(x)-2xq(x)=10x^{2}+5-10x^{2}-10x=-10x+5.

Der Grad von -10x+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

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

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

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

oder umgeformt

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

Eine Probe bestätigt dies.

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 cp=sq+r und \operatorname {grad} (r)<\operatorname {grad} (q) gilt.

   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*xd
       (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 x unterlässt, wenn sie nicht notwendig ist.

Horner-Schema

Häufig muss eine Polynomdivision durch einen Linearfaktor (x-a) mit Leitkoeffizient 1 erfolgen. Dies kann schneller mit Horner-Schema (zur Funktionswert-Berechnung eines Polynoms) erfolgen. Interessant ist die Umkehrung: man kann mit der Polynomdivision auch Funktionswerte bestimmen. Beispiel: p(x)=x^{3}-2x+1 mit p(3)=22

Polynomdivision liefert: \left(x^{3}-2x+1\right)\colon \left(x-3\right)=x^{2}+3x+7+{\frac {22}{x-3}}

Nach Multiplikation mit (x-3) sieht man, dass der Rest 22 der Funktionswert p(3) ist.

Trenner
Basierend auf einem Artikel in: externer Link Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 24.02. 2020