Polynomdivision

Die Polynomdivision, auch Partialdivision genannt, ist ein mathematisches Rechenverfahren, bei dem ein Polynom durch ein anderes dividiert wird. Das Ergebnis ist ein „Ganzteil“-Polynom und evtl. ein Restpolynom. Das Verfahren verläuft analog zur üblichen und in der Schule gelehrten Division von Zahlen mit Rest. Während dort vorübergehend kleinere Dezimalstellen ignoriert werden und die nächste Ziffer des Ergebnisses ggf. erraten wird, ist hier der nächste Koeffizient durch Division der verbliebenen höchsten Koeffizienten exakt bestimmt.

Allgemein

Informell

Im Folgenden seien Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} natürliche Zahlen einschließlich Null (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n,m \in \N_0} ) und der Einfachheit halber die Größen $a_{i}\ (0\leq i\leq n)$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j\ (0 \le j \le m)} stets ganze Zahlen, also Elemente von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb Z} . Hat man nun zwei Polynome, etwa

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 \ne 0}

und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 \ne 0,}

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} , das sich nicht mehr weiter durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} teilen lässt und das dem Rest in der Zahlendivision entspricht:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x) = q(x) s(x) + r(x)}

oder in Analogie zur Schulschreibweise

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x) : q(x) = s(x) \text{ Rest } r(x).}

Das Verfahren zum Auffinden dieser Lösung, bestehend aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s(x)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} , ist die Polynomdivision.

Dass sich hiernach $r(x)$ nicht weiter durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} teilen lässt, ist gleichbedeutend damit, dass der Polynomgrad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} kleiner ist als der von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_m} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} eines Polynomringes $R[x]$ gegeben, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} ein kommutativer Ring mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \ne 0} und der Leitkoeffizient von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} eine Einheit in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} ist, und es wird die Gleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x) = s(x) q(x) + r(x),}

nach den gesuchten Polynomen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s(x)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} gelöst, und zwar so, dass der Grad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} kleiner als der von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} ist.

Anmerkungen

Wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{grad}\,r(x) < \operatorname{grad}\,q(x)} sind die Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s(x)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} in $R[x]$ eindeutig bestimmt.
Die Polynomdivision ist im Allgemeinen keine innere Verknüpfung auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R[x]} , da sich als Ergebnis der Division zweier Polynome im Allgemeinen nicht ein einzelnes, sondern zwei Polynome in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R[x]} ergeben und sich somit keine Zuordnung der Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R[x] \times R[x] \rightarrow R[x]} machen lässt. Ist das jedoch im Einzelfall möglich, so wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R[x]} zu einem Körper mit der Polynomdivision als Umkehrung der Polynommultiplikation.
Ist die Polynomdivision für jedes beliebige Paar von zwei Polynomen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R[x]} möglich, so wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R[x]} zu einem euklidischen Ring bzgl. der Polynomgrad-Funktion. Das ist genau dann der Fall, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} ein Körper ist.

Anwendungen

Eine Anwendung ist das Lösen von Gleichungen höheren Grades. Wenn eine Lösung (Nullstelle) $x_{n}$ bekannt ist, findet die Polynomdivision Anwendung, um den Grad der Gleichung um Eins zu senken. Diese Vorgehensweise wird „Abspalten einer Nullstelle“ genannt.
Eine weitere Anwendung findet die Polynomdivision bei der Kurvendiskussion mit der Bestimmung der Näherungskurven einer rationalen Funktion.
Bei der Partialbruchzerlegung rationaler Funktionen wird die Polynomdivision ebenfalls benötigt.
Bei der Berechnung von Prüfsummen findet die Polynomdivision über dem Ring der ganzen Zahlen modulo 2 Anwendung, siehe CRC-Polynom.
Nach erfolgter Polynomdivision kann man dasselbe Verfahren auf Divisor und Rest erneut anwenden und so einen weiteren Rest berechnen, und so weiter. Man erhält dann eine sogenannte Polynomrestfolge.

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 (Verfahren, Vorgehensweise) gelöst werden. Hier werden die einzelnen Schritte am Beispiel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{p(x)}{q(x)} = \frac{4 \cdot x^5 - x^4 + 2 \cdot x^3 + x^2 - 1} {x^2 + 1} }

erläutert:

Wie bei der Division ganzer Zahlen wird zuerst der Summand höchsten Grades des Polynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} eliminiert. Dazu wird zunächst der Summand höchsten Grades von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} durch den Summanden höchsten Grades von $q$ dividiert. Das Ergebnis ist ${\frac {4x^{5}}{x^{2}}}=4x^{3}$ . Danach wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4x^3} multipliziert und von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} subtrahiert.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} ( 4x^5 & -x^4 & +2x^3 & + x^2 & -1 ) & : & ( x^2 & +1 ) & = & 4x^3 + \frac{-x^4 -2x^3+x^2-1}{x^2 + 1} \\ \underline{-4x^5} & & \underline{-4x^3} \\ & -x^4 & -2x^3 \end{matrix} }

Es bleibt der Rest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -x^4 -2x^3+x^2-1} . Sein Grad ist nicht kleiner als der des Divisors.

Im nächsten Schritt wird von diesem Rest der Summand höchsten Grades eliminiert, bis in mehreren solchen Schritten ein Rest entsteht (hier: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2x - 3} ), der nicht mehr eliminiert werden kann, weil sein Grad kleiner als der Grad des Divisors $q$ ist.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{array}{rrrrl} (-x^4 & -2x^3 & + x^2 && -1) & : & (x^2 && +1) = - x^2 & -2x & +2 & + \frac{2x - 3}{x^2 + 1}\\ \underline{+x^4} & & \underline{+x^2} \\ & -2x^3 & +2x^2 \\ & \underline{+2x^3} & & \underline{+2x} \\ & & +2x^2 & +2x \\ & & \underline{-2x^2} & & \underline{- 2} \\ & & & +2x & - 3 \end{array} }

Weitere Beispiele

Polynomdivision 3.svg

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.

Pseudo-Division

Die oben beschriebene Methode zur Polynomdivision ist nur dann anwendbar, wenn der Leitkoeffizient des Divisors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} eine Einheit im Grundring ist. Das ist immer der Fall, wenn der Grundring 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha p(x) = s(x) q(x) + r(x),}

wobei die Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} vorgegeben sind und eine Konstante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha} sowie Polynome $s(x)$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} gesucht werden. Auch hier soll wieder der Grad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} kleiner als derjenige von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} sein.

Das Vorgehen ist ähnlich der normalen Polynomdivision. Allerdings werden im Divisionsschritt nicht nur das Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} , sondern auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z[x]} über den ganzen Zahlen durchgeführt werden. Seien

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} , in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z} nicht invertierbar ist. Wir können aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 5} multiplizieren. Nun kann man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2x} multipliziert abziehen und erhält

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

Der Grad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -10x + 5} ist dabei kleiner als derjenige von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} aber noch nicht kleiner als der von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} . Ziehen wir nun von diesem Zwischenergebnis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -2} -mal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} ab, erhalten wir

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -10x + 5 - (-2)q(x) = -10x + 5 + 10x + 10 = 15. }

Da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 15} als konstantes Polynom einen kleineren Grad als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} besitzt, sind wir hier fertig. Rückwärts einsetzen ergibt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 15 = (5p(x) - 2xq(x)) - (-2)q = 5p(x) - (2x - 2) q(x) }

oder umgeformt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 5 p(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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} und $q$ , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} nicht das Nullpolynom sein darf, sowie die Variable $x$ , bezüglich der die Pseudodivision zu erfolgen hat. Das Ergebnis ist ein Tripel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (c,s,r)} bestehend aus Polynomen $s$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} sowie einer Konstanten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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*x^d
       (c,q,r) = pseudoDivision(a*p - t*q, q, x)

Hierbei liefert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{grad}(f, x)} den Grad sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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.

Division durch Linearfaktor

Will man bei einer Gleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_n x^n + a_{n-1} x^{n-1} + \cdots +a_2 x^2 + a_1 x + a_0 = 0 \quad\text{mit}\ a_n \ne 0}

den Linearfaktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x-x_1)} einer Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_1} abspalten, so ergibt sich das um ein Grad reduzierte Polynom

b_{n-1}x^{n-1}+b_{n-2}x^{n-2}\cdots +b_{2}x^{2}+b_{1}x+b_{0}=0

mit den Koeffizienten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{n-1} = a_n}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{n-2} = a_{n-1} + a_n \cdot x_1}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{n-3} = a_{n-2} + a_{n-1} \cdot x_1 + a_n \cdot {x_1}^2}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \cdots}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{0} = a_1 + a_2 \cdot x_1 + a_3 \cdot {x_1}^2 \cdots + a_n \cdot {x_1}^{n-1}}

Beispiel:

Die Polynomgleichung

2x^{5}-4x^{4}+4x^{3}+3x^{2}+1,5x+0,75=0

hat die Lösung

x_{1}=-0,4841657

Das Restpolynom hat also die Koeffizienten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_4 = a_5 = 2}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_3 = a_4 + a_5 \cdot x_1 = -4,968331}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_2 = a_3 + a_4 \cdot x_1 + a_5 \cdot {x_1}^2 = 6,405496}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_1 = a_2 + a_3 \cdot x_1 + a_4 \cdot {x_1}^2 + a_5 \cdot {x_1}^3 = -0,101321}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_0 = a_1 + a_2 \cdot x_1 + a_3 \cdot {x_1}^2 + a_4 \cdot {x_1}^3 + a_5 \cdot {x_1}^4 = 1,549056}

und lautet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 x^4 -4,968331 x^3 + 6,405496 x^2 -0,101321 x + 1,549056 = 0}

Horner-Schema

Mit Leitkoeffizient 1 kann schneller mit dem Horner-Schema (zur Funktionswert-Berechnung eines Polynoms) gearbeitet werden. Interessant ist die Umkehrung: man kann mit der Polynomdivision auch Funktionswerte bestimmen. Beispiel: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x) = x^3-2x+1} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(3)=22}

Polynomdivision liefert: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(x^3-2x+1\right)\colon\left(x-3\right) = x^2+3x+7 + \frac{22}{x-3}}

Nach Multiplikation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x-3)} sieht man, dass der Rest 22 der Funktionswert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(3)} ist.

Verallgemeinerung auf Polynomringe in mehreren Unbestimmten

Es existiert eine verallgemeinerte Polynomdivision in multivariablen Polynomringen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K[x_1, x_2, \ldots, x_n]} , wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} ein Körper ist. Dabei werden einige Abstriche in Kauf genommen, wie beispielsweise die Eindeutigkeit.

Literatur

Peter Hartmann: Mathematik für Informatiker. Vieweg+Teubner, 2006, ISBN 3-8348-0096-1, S. 88–90 (Auszug in der Google-Buchsuche)
Schülerduden Mathematik II. Dudenverlag, 2004, ISBN 3-411-04275-3, S. 327–328
Charles D. Miller, Margaret L. Lial, David I. Schneider: Fundamentals of College Algebra. 3. überarbeitete Auflage. Scott & Foresman / Little & Brown Higher Education, 1990, ISBN 0-673-38638-4, S. 24–26

Weblinks

Anonym

Suche

Polynomdivision

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Allgemein

Informell

Formal

Anmerkungen

Anwendungen

Berechnung

Manueller Ablauf

Algorithmus

Pseudo-Division

Beispiel

Algorithmus

Division durch Linearfaktor

Horner-Schema

Verallgemeinerung auf Polynomringe in mehreren Unbestimmten

Literatur

Weblinks

Navigation

Navigation

Mitmachen

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

Polynomdivision

Allgemein

Informell

Formal

Anmerkungen

Anwendungen

Berechnung

Manueller Ablauf

Algorithmus

Pseudo-Division

Beispiel

Algorithmus

Division durch Linearfaktor

Horner-Schema

Verallgemeinerung auf Polynomringe in mehreren Unbestimmten

Literatur

Weblinks

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien