Polynomdivision

Grundidee und formale Voraussetzungen

Die Polynomdivision ist ein Rechenverfahren, bei dem ein Polynom p(x) durch ein anderes Polynom q(x) dividiert wird. Das Ergebnis besteht aus dem Quotientenpolynom s(x) und dem Restpolynom r(x):

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

Wie bei der Division ganzer Zahlen wird so lange weitergerechnet, bis der Rest nicht mehr durch den Divisor teilbar ist. Die entsprechende Abbruchbedingung lautet

grad r(x) < grad q(x).

Dadurch sind s(x) und r(x) eindeutig bestimmt. Formal liegen p(x) und q(x) im gemeinsamen Polynomring R[x], wobei R ein kommutativer Ring mit 1 ≠ 0 ist. Der Leitkoeffizient von q(x), also der Koeffizient seines Terms höchsten Grades, muss eine Einheit in R sein. Eine Einheit ist ein Ringelement, das ein multiplikatives Inverses besitzt. Ist R ein Körper, ist diese Voraussetzung immer erfüllt.

Im Allgemeinen liefert die Division zweier Polynome nicht ein einzelnes Polynom, sondern ein Paar aus Quotient und Rest. Ist die Division für jedes Polynom-Paar in R[x] möglich, ist R[x] bezüglich der Polynomgrad-Funktion ein euklidischer Ring; dies ist genau dann der Fall, wenn R ein Körper ist.

Manueller Ablauf und Beispiel

Die Rechnung erfolgt ähnlich wie die schriftliche Division von Zahlen. In jedem Schritt wird der Term höchsten Grades des aktuellen Restes beseitigt. Dazu teilt man seinen Leitkoeffizienten samt Potenz durch den entsprechenden Term des Divisors, multipliziert den Divisor mit dem erhaltenen Term und subtrahiert.

Für

p(x) = 4x⁵ − x⁴ + 2x³ + x² − 1 und q(x) = x² + 1

ist der erste Quotiententerm 4x⁵/x² = 4x³. Nach der Subtraktion bleibt zunächst −x⁴ − 2x³ + x² − 1. Durch weitere Schritte werden die Terme höchsten Grades beseitigt. Der endgültige Quotient und Rest sind

p(x) : q(x) = 4x³ − x² − 2x + 2 Rest (2x − 3),

also

p(x) = (x² + 1)(4x³ − x² − 2x + 2) + (2x − 3).

In einem Algorithmus können die Koeffizienten des Zähler- und Nennerpolynoms in Feldern Zähler() und Nenner() gespeichert werden. GradZ und GradN bezeichnen die jeweiligen Grade. Für jeden möglichen Quotientengrad i von GradZ − GradN bis 0 wird der Quotientkoeffizient durch Division der führenden verbleibenden Koeffizienten bestimmt; anschließend werden die Koeffizienten des Divisors mit diesem Wert multipliziert und vom Zählerfeld abgezogen. Die verbleibenden Koeffizienten mit Grad kleiner als GradN bilden das Restpolynom.

Anwendungen und besondere Folgerungen

Eine wichtige Anwendung ist das Lösen von Gleichungen höheren Grades. Ist eine Nullstelle x₁ bekannt, kann man den Linearfaktor (x − x₁) abspalten und dadurch den Grad der Gleichung um Eins verringern. Außerdem wird die Polynomdivision bei der Bestimmung von Näherungskurven rationaler Funktionen, bei der Partialbruchzerlegung rationaler Funktionen, bei Prüfsummen über dem Ring der ganzen Zahlen modulo 2 sowie bei der Bildung von Polynomrestfolgen verwendet.

Für ein Polynom

aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ⋯ + a₁x + a₀ = 0 mit aₙ ≠ 0 und eine bekannte Lösung x₁ hat das um ein Grad reduzierte Polynom die Koeffizienten

bₙ₋₁ = aₙ,

bₙ₋₂ = aₙ₋₁ + aₙx₁,

bₙ₋₃ = aₙ₋₂ + aₙ₋₁x₁ + aₙx₁²,

bis hin zu

b₀ = a₁ + a₂x₁ + a₃x₁² + ⋯ + aₙx₁ⁿ⁻¹.

Die Aussagen „a ist Nullstelle von p(x)“, „bei der Division durch x − a ist der Rest null“ und „p(x) ist durch x − a teilbar“ sind äquivalent. Ist a eine Nullstelle eines Polynoms in einem Integritätsring, gibt es ein eindeutig bestimmtes maximales m mit p(x) = (x − a)ᵐp₀(x) und p₀(a) ≠ 0. m heißt Ordnung der Nullstelle; m = 1 bezeichnet eine einfache, m = 2 eine doppelte Nullstelle. Die Anzahl der Nullstellen in R kann den Grad deg p(x) nicht überschreiten.

Linearfaktor und Horner-Schema

Als Beispiel besitzt die Gleichung

2x⁵ − 4x⁴ + 4x³ + 3x² + 1,5x + 0,75 = 0

die Lösung x₁ = −0,4841657. Nach dem Abspalten des Linearfaktors erhält man das Restpolynom

2x⁴ − 4,968331x³ + 6,405496x² − 0,101321x + 1,549056 = 0.

Seine Koeffizienten sind b₄ = 2, b₃ = −4,968331, b₂ = 6,405496, b₁ = −0,101321 und b₀ = 1,549056.

Bei Leitkoeffizient 1 kann das Horner-Schema die Berechnung beschleunigen. Umgekehrt kann die Polynomdivision auch zur Berechnung eines Funktionswertes dienen. Für p(x) = x³ − 2x + 1 gilt p(3) = 22. Die Division ergibt

(x³ − 2x + 1) : (x − 3) = x² + 3x + 7 + 22/(x − 3).

Nach Multiplikation mit x − 3 erkennt man, dass der Rest 22 genau dem Funktionswert p(3) entspricht.

Pseudo-Division und mehrvariable Polynome

Ist der Leitkoeffizient des Divisors im Grundring keine Einheit, kann die normale Polynomdivision scheitern. Für Integritätsringe verwendet man dann die Pseudo-Division. Gesucht werden eine Konstante α sowie s(x) und r(x) mit

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

grad r(x) < grad q(x).

Dabei werden im Divisionsschritt sowohl q(x) als auch p(x) mit geeigneten Faktoren multipliziert, damit sich die Leitkoeffizienten aufheben.

Im Polynomring Z[x] seien p(x) = 2x² + 1 und q(x) = 5x + 5. Eine normale Division ist nicht möglich, weil 5 in Z nicht invertierbar ist. Die Pseudo-Division liefert zunächst 5p(x) − 2xq(x) = −10x + 5 und anschließend den konstanten Rest 15. Rückwärts eingesetzt ergibt sich

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

Der rekursive Algorithmus pseudoDivision(p, q, x) gibt ein Tripel (c, s, r) zurück, sodass cp = sq + r und grad(r) < grad(q) gilt. Dabei werden Grad und Leitkoeffizient der Polynome bezüglich x verwendet.

Für multivariable Polynomringe K[x₁, x₂, …, xₙ] mit einem Körper K existiert ebenfalls eine verallgemeinerte Polynomdivision. Dabei müssen jedoch Einschränkungen, insbesondere der mögliche Verlust der Eindeutigkeit, in Kauf genommen werden. Der Nichtnullstellensatz lässt sich außerdem auf mehrere Variablen erweitern: Hat ein Polynom in xᵢ jeweils Grad dᵢ und enthält jede Menge Aᵢ genau dᵢ + 1 paarweise verschiedene Elemente, so verschwindet das Polynom nicht auf dem gesamten Produkt A₁ × A₂ × … × Aₙ.