Polynomdivision - Direkte Berechnung beliebiger Koeffizienten
Von: easymathematics
Datum: Mo. 16. August 2021 18:59:39
Thema: Mathematik
\(\newcommand{\ggT}{\mathbb{ggT}}\)
In diesem Artikel möchte ich ein Verfahren vorstellen, welches mathematisch gesehen gewisse Ästhetik hat. Gegeben seien zwei Polynome \( a(x)=\sum \limits_{i=0}^{n} a_i x^i \) und \( b(x)=b_1 x + b_0\). Dann gibt es bekanntlich zwei eindeutige Polynome \( q(x)=\sum \limits_{i=0}^{n-1} q_i x^i \) und \(r(x) = r\), s. d. \[a(x) = q(x)b(x) + r(x)\] gilt. Die Koeffizienten \(q_i\) können mit Stift und Papier nach und nach mittels Polynomdivision berechnet werden. Problem: Um einen Koeffizienten \(q_i\) zu berechnen, müssen die vorherigen \( q_{i+1}, ..., q_{n-1}\) bekannt sein. Wie wäre es mittels einer Matrix eine direkte Formel anzugeben? "Direkt" heißt hier: Ohne Kenntnis der vorherigen Koeffizienten. Ist es möglich? Falls nein, warum nicht? Und falls doch... wie sieht \[ q_{i} = f(a_{i}, b_{i}) \] aus? Ich habe mit auf die Suche begeben und das Resultat gibt es hier: \[ q_{n-1-i} = \sum \limits_{t=0}^{i} (-1)^{i+t} \quad b_{1}^{t-i-1} \quad b_{0}^{i-t} \quad a_{n-t}, \quad i=0, ..., n \] und speziell gilt \( q_{-1} = \frac{r}{b_1} \), welcher mit dem Koeffizienten der Laurent-Reihe an der Indexstelle -1 übereinstimmt. Hübsch, oder? Wir diskutieren in diesem Artikel den Beweis.Lemma: Sei \(n > 0\) natürlich, seien \( a(x)=\sum \limits_{i=0}^{n} a_i x^i \) und \( b(x) = b_1 x + b_0\) zwei reelle Polynome. Sei weiter \( M \) eine reelle \( (n+1)x(n+1) \)-Matrix mit Einträgen \(m_{ij}\) gegeben durch \[ m_{ij}=\left\{\begin{array}{ll} 0, & n \geq j \gt i \geq 0\\ (-1)^{i+j} \quad b_1^{j-i-1} \quad b_0^{i-j}, & 0 \leq j \leq i \leq n \end{array}\right. . \] Sei \( \vec{a} = \begin{pmatrix} a_{n} \\ a_{n-1} \\ ... \\ a_0\end{pmatrix} \) der "Koeffizientenvektor" des Polynoms \( a(x) \). Dann erfüllt der Koeffizientenvektor \( \vec{q} := M \vec{a} = \begin{pmatrix} q_{n-1} \\ q_{n-2} \\ ... \\ q_0 \\ q_{-1}\end{pmatrix} \) die Polynomdivision \[ a(x) = q(x)b(x) + r(x),\] mit \( q(x)=\sum \limits_{i=0}^{n-1} q_i x^i \) und \(r(x) = q_{-1}b_1\).
 
Beweis: Wir starten bei \( q(x)b(x) + r(x) \), verwenden die Definitionen von \(q(x) \) und \( r(x) \) und zeigen, dass wir schließlich bei \( a(x) \) landen. \[ q(x)b(x) + r(x) \\ = ( \sum \limits_{i=0}^{n-1} q_{n-1-i} x^{n-1-i} ) (b_1x + b_0) + q_{-1}b_1 \\ \overset{\text{nach Potenzen sortieren}}{=} b_1 q_{n-1}x^n + \sum \limits_{i=1}^{n-1} (b_1 q_{n_1-i} + b_0 q_{n-i}) x^{n-i} + b_0 q_0 + q_{-1}b_1 \\ \overset{\text{Def. von } q_{k}}{=} \sum \limits_{i=0}^{n} a_i x^i \\ \overset{\text{Definition}}{=} a(x)\] \( \blacksquare \)
 
Übung: Man zeige, dass \( q_{-1} \) der Koeffizient der Laurent-Reihe an der Indexstelle -1 ist.
 
Abschließende Worte: Wie habe ich die Matrix konstruiert? Ich habe mit schriftlicher Multiplikation von Polynomen und Faltungen herum gespielt. Zwei Polynome mittels einer Matrix zu multiplizieren ist keine große Schwierigkeit. Dabei entstehen, falls man ein Polynom p(x) mit einem q(x) vom Grad m multipliziert Matrizen mit m gefüllten Diagonalen. Für lineare Faktoren ist die Berechnung der Inversen noch im Rahmen. Dabei habe ich beobachtet, dass dadurch die Polynomdivision eine sehr kompakte Form bekommt und man die Koeffizienten unabhängig voneinander berechnen kann. Ich will diese Beobachtung mit Euch teilen und deshalb dieser kurze, nette Artikel. Liebe Grüße, easymathematics
 


Dieser Artikel kommt von Matroids Matheplanet
https://matheplanet.de

Die Url für diesen Artikel ist:
https://matheplanet.de/default3.html?article=1940