aboutsummaryrefslogtreecommitdiffstats
path: root/buch
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-02-26 09:36:30 +0100
committerAndreas Müller <andreas.mueller@ost.ch>2021-02-26 09:36:30 +0100
commitd0a6b498dcebb27ea8647ca35f4908a7974e83ec (patch)
treed528d1c60f1ad6cd7ace8a5e732f42c9ae1a68dd /buch
parentMathSemMSE slides session1 (diff)
downloadSeminarMatrizen-d0a6b498dcebb27ea8647ca35f4908a7974e83ec.tar.gz
SeminarMatrizen-d0a6b498dcebb27ea8647ca35f4908a7974e83ec.zip
Poylnomdivision
Diffstat (limited to 'buch')
-rw-r--r--buch/chapters/20-polynome/definitionen.tex113
1 files changed, 109 insertions, 4 deletions
diff --git a/buch/chapters/20-polynome/definitionen.tex b/buch/chapters/20-polynome/definitionen.tex
index b80769f..135ebf6 100644
--- a/buch/chapters/20-polynome/definitionen.tex
+++ b/buch/chapters/20-polynome/definitionen.tex
@@ -378,13 +378,118 @@ R^{(k+l)}[X].
%
\subsection{Teilbarkeit
\label{buch:subsection:polynome:teilbarkeit}}
-XXX Beispiel für Polynomdivision?
+Im Ring der ganzen Zahlen sind nicht alle Divisionen ohne Rest
+ausführbar, so entsteht das Konzept der Teilbarkeit.
+Der Divisionsalgorithmus, den man in der Schule lernt, liefert
+zu beliebigen ganzen Zahlen $a,b\in\mathbb{Z}$ den Quotienten
+$q$ und den Rest $r$ derart, dass $a=qb+r$.
+Der Algorithmus basiert auf der Zehnersystemdarstellung
+\begin{align*}
+a &= a_n10^{n} + a_{n-1}10^{n-1} + \dots + a_110^{1} + a_0
+\\
+b &= b_m10^{n} + b_{m-1}10^{n-1} + \dots + b_110^{1} + b_0
+\end{align*}
+und ermittelt den Quotienten, indem er mit den einzelnen Stellen
+$a_k$ und $b_k$ arbeitet.
+Er ist also eigentlich ein Algorithmus für die Polynome
+\begin{align*}
+a &= a_nX^{n} + a_{n-1}X^{n-1} + \dots + a_1X^{1} + a_0
+\\
+b &= b_mX^{n} + b_{m-1}X^{n-1} + \dots + b_1X^{1} + b_0,
+\end{align*}
+mit dem einzigen Unterschied, dass statt $X$ mit der festen Zahl $X=10$
+gearbeitet wird.
+Der Teilungsalgorithmus für Polynome lässt sich aber leicht
+rekonstruieren.
+
+\subsubsection{Polynomdivision}
+Wir zeigen den Polynomdivisionsalgorithmus an einem konkreten Beispiel.
+Gesucht sind Quotient $q\in \mathbb{Z}[X]$ und Rest $r\in\mathbb{Z}[X]$
+der beiden Polynome
+\begin{equation}
+\begin{aligned}
+a(X) &= X^4 - X^3 -7X^2 + X + 6\\
+b(X) &= X^2+X+1,
+\end{aligned}
+\label{buch:polynome:eqn:divisionsaufgabe}
+\end{equation}
+für die also gilt $a=bq+r$.
+Die Division ergibt
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcrcrcrcrcrcrcr}
+X^4&-& X^3&-&7X^2&+& X&+&6&:&X^2&+&X&+&1&=&X^2&-&2X&-&6=q\\
+\llap{$-($}X^4&+& X^3&+& X^2\rlap{$)$}& & & & & & & & & & & & & & & & \\ \cline{1-5}
+ &-&2X^3&-&8X^2&+& X& & & & & & & & & & & & & & \\
+ &\llap{$-($}-&2X^3&-&2X^2&-&2X\rlap{$)$}& & & & & & & & & & & & & & \\ \cline{2-7}
+ & & &-&6X^2&+&3X&+&6& & & & & & & & & & & & \\
+ & & &\llap{$-($}-&6X^2&-&6X&-&6\rlap{$)$}& & & & & & & & & & & & \\ \cline{4-9}
+ & & & & & &9X&+&12\rlap{$\mathstrut=r$}& & & & & & & & & & & & \\ \cline{7-9}
+\end{array}
+\]
+Durch nachrechnen kann man überprüfen, dass tatsächlich
+\begin{align*}
+bq
+&=
+X^4-X^3-7X^2-8X-6
+\\
+bq+r&=
+X^4-X^3-7X^2+X+6 = a
+\end{align*}
+gilt.
+
+Das Beispiel~\eqref{buch:polynome:eqn:divisionsaufgabe} war besonders
+einfach, weil der führende Koeffizient des Divisorpolynomes $1$ war.
+Für $b=2X^2+X+1$ funktioniert der Algorithmus dagegen nicht mehr.
+Jedes für $q$ in Frage kommende Polynom vom Grad $2$ muss von der
+Form $q=q_2X^2+q_1X+q_0$ sein.
+Multipliziert man mit $b$, erhält man $bq=2q_2X^4 + (2q_1+q_2)X^3+\dots$.
+Insbesondere ist es nicht möglich mit ganzzahligen Quotienten
+$q_k\in\mathbb{Z}$ auch nur der ersten Koeffizienten von $a$ zu
+erhalten.
+Dazu müsste nämlich $a_n = 1 = 2q_2$ oder $q_2 = \frac12\not\in\mathbb{Z}$
+sein.
+Der Divisionsalgorithmus funktioniert also nur dann, wenn die
+Division durch den führenden Koeffizienten des Divisorpolynomes $b$
+immer ausführbar ist.
+Im Beispiel~\eqref{buch:polynome:eqn:divisionsaufgabe} war das der
+Fall, weil der führende Koeffizient $1$ war.
+Für beliebige Polynome $b\in R[X]$ ist das aber nur der Fall,
+wenn die Koeffizienten in Tat und Wahrheit einem Körper entstammen.
+
+Im Folgenden betrachten wir daher nur noch Polynomringe mit Koeffizienten
+in einem Körper $\Bbbk$.
+In $\mathbb{Q}[X]$ ist die Division $a:b$ für die Polynome
+\begin{equation}
+\begin{aligned}
+a(X) &= X^4 - X^3 -7X^2 + X + 6\\
+b(X) &= X^2+X+1,
+\end{aligned}
+\label{buch:polynome:eqn:divisionsaufgabe}
+\end{equation}
+problemlos durchführbar:
+\[
+\arraycolsep=1.4pt
+\renewcommand{\arraystretch}{1.2}
+\begin{array}{rcrcrcrcrcrcrcrcrcrcr}
+X^4&-& X^3&-& 7X^2&+& X&+& 6&:&2X^2&+&X&+&1&=&\frac12X^2&-&\frac34X&-\frac{27}{8} = q\\
+\llap{$-($}X^4&+&\frac12X^3&+& \frac12X^2\rlap{$)$}& & & & & & & & & & & & & & & \\ \cline{1-5}
+ &-&\frac32X^3&-&\frac{15}2X^2&+& X& & & & & & & & & & & & & \\
+ &\llap{$-($}-&\frac32X^3&-&\frac{ 3}4X^2&-&\frac{ 3}4X\rlap{$)$}& & & & & & & & & & & & & \\\cline{2-7}
+ & & &-&\frac{27}4X^2&+&\frac{ 7}4X&+& 6& & & & & & & & & & & \\
+ & & &\llap{$-($}-&\frac{27}4X^2&-&\frac{27}8X&-&\frac{27}{8}\rlap{$)$}& & & & & & & & & & & \\\cline{4-9}
+ & & & & & &\frac{41}8X&+&\frac{75}{8}\rlap{$\mathstrut=r$}& & & & & & & & & & & \\
+\end{array}
+\]
+Der Algorithmus funktioniert selbstverständlich genauso in $\mathbb{R}[X]$
+oder $\mathbb{C}[X]$, und ebenso in den in
+Kapitel~\ref{buch:chapter:endliche-koerper} studierten endlichen Körpern.
\subsubsection{Euklidische Ringe und Faktorzerlegung}
-Der Polynomring $R[X]$ hat noch eine weitere Eigenschaft, die ihn
+Der Polynomring $\Bbbk[X]$ hat noch eine weitere Eigenschaft, die ihn
von einem gewöhnlichen Ring unterschiedet.
-Der Polynomdivisionsalgorithmus findet zu zwei Polynomen $f,g\in R[X]$
-den Quotienten $q\in R[X]$ und den Rest $r\in R[X]$ mit
+Der Polynomdivisionsalgorithmus findet zu zwei Polynomen $f,g\in\Bbbk[X]$
+den Quotienten $q\in\Bbbk[X]$ und den Rest $r\in\Bbbk[X]$ mit
$f=qg+r$, wobei ausserdem $\deg r<\deg g$ ist.
\begin{definition}