Beispiel einer Polynomdivision

Wir betrachten ein Beispiel in

ℙ (ℝ)

. Dabei erhalten wir einen schreibtechnischen Vorteil, wenn wir Polynomfunktionen, anders als bisher, mit dem Leitkoeffizient-Summanden beginnen lassen. Also z.B.

2 X^{3} - X^{2} + 4

statt

4 - X^{2} + 2 X^{3}

Für $p = (4,0, - 1,2,0, \dots)$ und $q = (0,1,1,0, \dots)$ , also $f_{p} = 2 X^{3} - X^{2} + 4$ und $f_{q} = X^{2} + X$ , ist

\begin{array}{l} n = g r a d p = 3 \\ m = g r a d q = 2 \\ k = m - n = 1 \end{array}

Es sind also die Polynome $p_{0}, p_{1}, p_{2}$ zu bilden und zwar mit Hilfe der Rekursion

c_{i + 1, j} ≔ {\begin{array}{l} c_{i, j} für j \leq k - i - 1 \\ c_{i, j} - c_{i, n - i} \cdot b_{j - k + i} für j > k - i - 1 \end{array}

\begin{array}{l} p_{0} & = p = (c_{0}) = (4,0, - 1, \underset{c_{0,3}}{\underset{︸}{2}},0, \dots) \\ i = 0 p_{1} & = (c_{0,0}, c_{0,1} - c_{0,3} \cdot b_{0}, c_{0,2} - c_{0,3} \cdot b_{1}, c_{0,3} - c_{0,3} \cdot b_{2}, c_{0,4} - c_{0,3} \cdot b_{3}, \dots) \\ = (4,0 - 2 \cdot 0, - 1 - 2 \cdot 1,2 - 2 \cdot 1,0 - 2 \cdot 0, \dots) \\ = (4,0, \underset{c_{1,2}}{\underset{︸}{- 3}},0, \dots) \\ i = 1 p_{2} & = (c_{1,0} - c_{1,2} \cdot b_{0}, c_{1,1} - c_{1,2} \cdot b_{1}, c_{1,2} - c_{1,2} \cdot b_{2}, c_{1,3} - c_{1,2} \cdot b_{3}, \dots) \\ = (4 - (- 3) \cdot 0,0 - (- 3) \cdot 1, - 3 - (- 3) \cdot 1,0 - (- 3) \cdot 0, \dots) \\ = (4,3,0, \dots) \end{array}

Damit haben wir insbesondere die Polynomfunktion $f_{p_{2}} = 3 X + 4$ und können nun die gesuchte Darstellung

f_{p} = (\sum_{j = 0}^{k} c_{j, n - j} X^{k - j}) \cdot f_{q} + f_{p_{k + 1}}

für $k = 1$ also $f_{p} = (c_{0,3} X + c_{1,2}) f_{q} + f_{p_{2}}$ , angeben:

2 X^{3} - X^{2} + 4 = (2 X - 3) (X^{2} + X) + 3 X + 4

Es ist unverkennbar, dass Ermittlung der Koeffizienten $c_{i, j}$ , und damit der gesuchten Zerlegung, recht mühsam ist. Zum Glück gibt es eine alternative Rekursionsroutine, die an das schriftliche Dividieren aus der Schulzeit erinnert. Dabei wird die Darstellung

f_{p_{i + 1}} = f_{p_{i}} - c_{i, n - i} X^{k - i} \cdot f_{q}

direkt errechnet. Beachtet man, dass

c_{i, n - i} X^{k - i} = c_{i, n - i} X^{n - i - m} = (c_{i, n - i} X^{n - i}) : X^{m}

, so lässt sich die Berechnung von

f_{p_{i + 1}}

durch drei Schritte mechanisieren:

Teile den Leitkoeffizient-Summanden von $f_{p_{i}}$ durch Leitkoeffizient-Summanden von $f_{q}$ .
Multipliziere dieses Teilergebnis mit $f_{q}$ .
Subtrahiere dieses Produkt von $f_{p_{i}}$ .

In unserem Beispiel mit

f_{p} = 2 X^{3} - X^{2} + 4

und

f_{q} = X^{2} + X

, berechnet man etwa

f_{p_{1}}

aus

f_{p_{0}} = f_{p}

wie folgt:

$2 X^{3} : X^{2} = 2 X$ .
$(X^{2} + X) \cdot 2 X = 2 X^{3} + 2 X^{2}$ .
$(2 X^{3} - X^{2} + 4) - (2 X^{3} + 2 X^{2}) = - 3 X^{2} + 4$ .

Diesen dreistufigen Rekusionsschritt wiederholt man nun so oft bis $p_{i + 1}$ einen geringeren Grad hat als $q$ . Im Beispiel ist dies bereits im zweiten Schritt erreicht.

Den vollständigen Prozess notieren wir in der klassischen Schreibweise für eine schriftliche Division:

\begin{array}{l} (2 X^{3} - X^{2} + 4) : (X^{2} + X) = 2 X - 3 \\ - (2 X^{3} + 2 X^{2}) \\ - 3 X^{2} + 4 \leftarrow f_{p_{1}} \\ - (- 3 X^{2} - 3 X) \\ 3 X + 4 \leftarrow f_{p_{2}} \end{array}

und lesen schließlich die gewonnene Zerlegung ab:

2 X^{3} - X^{2} + 4 = (2 X - 3) (X^{2} + X) + 3 X + 4

Das folgende Formular berechnet Polynomdivisionen automatisch. Man wählt zunächst den Ring R aus, wobei im Fall $ℤ_{n}$ auch die gewünschte Primzahl einzutragen ist:

ℝ

ℤ= {0,...,n-1}

ℂ

Bei der Eingabe der Koeffizienten von $p = (a_{0}, a_{1}, \dots, a_{n})$ und $q = (b_{0}, \dots, b_{m - 1}, 1)$ muss das Komma als Trenner benutzt werden. Dezimalzahlen werden mit Dezimalpunkt notiert und auf vier Stellen gerundet. Komplexe Zahlen haben die übliche Form a+bi. Man beachte außerdem die Reihenfolge der Koeffizienten. Nach Eingabe der Daten

p = (

)

q = (

)

ruft man jetzt die Zerlegung von $f_{p}$ ab: Los!