diff options
Diffstat (limited to 'buch/chapters/20-polynome')
| -rw-r--r-- | buch/chapters/20-polynome/chapter.tex | 6 | ||||
| -rw-r--r-- | buch/chapters/20-polynome/definitionen.tex | 120 | ||||
| -rw-r--r-- | buch/chapters/20-polynome/vektoren.tex | 133 |
3 files changed, 150 insertions, 109 deletions
diff --git a/buch/chapters/20-polynome/chapter.tex b/buch/chapters/20-polynome/chapter.tex index c7fc9e9..fd72a59 100644 --- a/buch/chapters/20-polynome/chapter.tex +++ b/buch/chapters/20-polynome/chapter.tex @@ -38,7 +38,7 @@ verwendet werden, warum also diese Beschränkung. Für die nachfolgenden Betrachtungen stellen wir uns $X$ daher nicht mehr einfach als einen Platzhalter für eine Zahl vor, sondern als ein neues algebraisches Objekt, für das man die Rechenregeln erst noch definieren muss. -In diesem Kapteil sollen die Regeln zum Beispiel sicherstellen, +In diesem Kapitel sollen die Regeln zum Beispiel sicherstellen, dass man mit Polynomen so rechnen kann, wie wenn $X$ eine Zahl wäre. Es sollen also zum Beispiel die Regeln \begin{align} @@ -120,7 +120,7 @@ Elemente einer Algebra sind. \input{chapters/20-polynome/definitionen.tex} \input{chapters/20-polynome/vektoren.tex} -\input{chapters/20-polynome/matrizen.tex} -\input{chapters/20-polynome/minimalpolynom.tex} +%\input{chapters/20-polynome/matrizen.tex} +%\input{chapters/20-polynome/minimalpolynom.tex} diff --git a/buch/chapters/20-polynome/definitionen.tex b/buch/chapters/20-polynome/definitionen.tex index 135ebf6..3c541d8 100644 --- a/buch/chapters/20-polynome/definitionen.tex +++ b/buch/chapters/20-polynome/definitionen.tex @@ -12,8 +12,8 @@ Rechnen mit Polynomen zusammen. % % Skalare % -\subsection{Skalare -\label{buch:subsection:polynome:skalare}} +\subsection{Polynome +\label{buch:subsection:polynome:polynome}} Wie schon in der Einleitung angedeutet sind Polynome nur dann sinnvoll, wenn man mit den Koeffizienten gewisse Rechenoperationen durchführen kann. Wir brauchen mindestens die Möglichkeit, Koeffizienten zu addieren. @@ -31,7 +31,7 @@ in das Polynom einsetzen kann, dann muss es möglich sein, in $R$ zu Multiplizieren und zu Addieren, und es müssen die üblichen Rechenregeln der Algebra gelten, $R$ muss also ein Ring sein. \index{Ring}% -Wir werden im folgenden meistens voraussetzen, dass $R$ sogar kommutativ +Wir werden im folgenden zusätzlich voraussetzen, dass $R$ sogar kommutativ ist und eine $1$ hat. \begin{definition} @@ -85,6 +85,7 @@ X^n + \frac{a_{n-1}}{a_n}X^{n-1} + \dots + \frac{a_0}{a_n} \] machen. Man sagt auch, das Polynom $p(X)$ wurde normiert. +Wenn $R$ ein Körper ist, ist die Normierung immer möglich. Die Tatsache, dass zwei Polynome nicht gleich viele von $0$ verschiedene Koeffizienten haben müssen, verkompliziert die Beschreibung der Rechenoperationen ein wenig. @@ -109,42 +110,10 @@ dass nur über diejenigen Indizes $k$ summiert wird, für die $a_k$ definiert ist. \label{summenzeichenkonvention} -% -% Abschnitt über Polynomring Definition -% -\subsection{Der Polynomring -\label{buch:subsection:polynome:ring}} -Die Menge $R[X]$ aller Polynome über $R$ wird zu einem Ring, wenn man die -Rechenoperationen Addition und Multiplikation so definiert, wie man das -in der Schule gelernt hat. -Die Summe von zwei Polynomen -\begin{align*} -p(X) &= a_nX^n + a_{n-1}X^{n-1} + \dots + a_1X + a_0\\ -q(X) &= b_mX^m + b_{m-1}X^{m-1} + \dots + b_1X + b_0 -\end{align*} -ist -\[ -p(X)+q(X) -= -\sum_{k} (a_k+b_k)X^k, -\] -wobei die Summe wieder so zu interpretieren ist, über alle Terme -summiert wird, für die mindestens einer der Summanden von $0$ -verschieden ist. - -Für das Produkt verwenden wir die Definition -\[ -p(X)q(X) -= -\sum_{k}\sum_{l} a_kb_l X^{k+l}, -\] -die natürlich mit Formel~\eqref{buch:eqn:polynome:faltung} -gleichbedeutend ist. -Die Polynom-Multiplikation und Addition sind nur eine natürliche -Erweiterung der Rechenregeln, die man schon in der Schule lernt, -es ist daher nicht überraschend, dass die bekannten Rechenregeln -auch für Polynome gelten. +Die Menge $R[X]$ aller Polynome über $R$ mit den beschriebenen +Operationen ist ein Ring. Das Distributivgesetz +\index{Distributivgesetz}% \[ p(X)(u(X)+v(X)) = p(X)u(X) + p(X)v(X) \qquad @@ -152,6 +121,7 @@ p(X)(u(X)+v(X)) = p(X)u(X) + p(X)v(X) \] zum Beispiel sagt ja nichts anderes, als dass man ausmultiplizieren kann. +\index{ausmultiplizieren}% Oder die Assoziativgesetze \begin{align*} p(X)+q(X)+r(X) @@ -178,6 +148,7 @@ Reihenfolge man die Additionen oder Multiplikationen ausführt. \begin{definition} Der {\em Grad} eines Polynoms $p(X)$ ist die höchste Potenz von $X$, die im Polynom vorkommt. +\index{Grad eines Polynoms}% Das Polynom \[ p(X) = a_nX^n + a_{n-1}X^{n-1}+\dots a_1X + a_0 @@ -219,10 +190,12 @@ $\deg(\lambda p) \le \deg\lambda + \deg p$. \begin{proof}[Beweis] Wir schreiben die Polynome wieder in der Form -\begin{align*} +\[ +\begin{aligned} p(X) &= a_nX^n + a_{n-1}X^{n-1} + \dots + a_1X + a_0&&\Rightarrow&\deg p&=n\\ q(X) &= b_mX^m + b_{m-1}X^{m-1} + \dots + b_1X + b_0&&\Rightarrow&\deg q&=m. -\end{align*} +\end{aligned} +\] Dann kann der höchste Koeffizient in der Summe $p+q$ nicht weiter oben sein als die grössere von den beiden Zahlen $n$ und $m$ angibt, dies beweist \eqref{buch:eqn:polynome:gradsumme}. @@ -230,48 +203,15 @@ Ebenso kann der höchste Koeffizient im Produkt nach der Formel~\eqref{buch:eqn:polynome:faltung} nicht weiter oben als bei $n+m$ liegen, dies beweist beweist \eqref{buch:eqn:polynome:gradprodukt}. -Es könnte aber passieren, dass $a_nb_m=0$ ist, d.~h.~es ist durchaus möglich, +In einem Ring mit Nullteilern +(Siehe Definition~\ref{buch:grundlagen:def:nullteiler}) +könnte es passieren, dass $a_nb_m=0$ ist, d.~h.~es ist durchaus möglich, dass der Grad kleiner ist. Schliesslich kann der höchsten Koeffizient von $\lambda p(X)$ nicht grösser als der höchste Koeffizient von $p(X)$ sein, was \eqref{buch:eqn:polynome:gradskalar} beweist. \end{proof} -Etwas enttäuschend an diesen Rechenregeln ist, dass der Grad eines -Produktes nicht exakt die Summe der Grade hat. -Der Grund ist natürlich, dass es in gewissen Ringen $R$ passieren kann, -dass das Produkt $a_n\cdot b_m=0$ ist. -Zum Beispiel ist im Ring der $2\times 2$ Matrizen das Produkt der Elemente -\begin{equation} -a_n = \begin{pmatrix}1&0\\0&0\end{pmatrix} -\quad\text{und}\quad -b_m = \begin{pmatrix}0&0\\0&1\end{pmatrix} -\qquad\Rightarrow\qquad -a_nb_m = \begin{pmatrix}0&0\\0&0\end{pmatrix}. -\label{buch:eqn:definitionen:nullteilerbeispiel} -\end{equation} -Diese unangehme Situation tritt immer ein, wenn es von Null verschiedene -Elemente gibt, deren Produkt $0$ ist. -In Matrizenringen ist das der Normalfall, man kann diesen Fall also nicht -einfach ausschliessen. -In den Zahlenmengen wie $\mathbb{Z}$, $\mathbb{Q}$ und $\mathbb{R}$ passiert -das natürlich nie. - -\begin{definition} -Ein Ring $R$ heisst {\em nullteilerfrei}, wenn für zwei Elemente -$a,b\in R$ aus $ab=0$ immer geschlossen werden kann, dass -$a=0$ oder $b=0$. -Ein von $0$ verschiedenes Element $a\in R$ heisst Nullteiler, -wenn es eine $b\in R$ mit $b\ne 0$ gibt derart dass $ab=0$. -\index{Nullteiler} -\index{nullteilerfrei} -\end{definition} - -Die beiden Matrizen in -\eqref{buch:eqn:definitionen:nullteilerbeispiel} -sind Nullteiler im Ring $M_2(\mathbb{Z})$ der $2\times 2$-Matrizen. -Der Matrizenring $M_2(\mathbb{Z})$ ist also nicht nullteilerfrei. - In einem nullteilerfreien Ring gelten die Rechenregeln für den Grad jetzt exakt: @@ -381,6 +321,7 @@ R^{(k+l)}[X]. 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 +\index{Divisionsalgorithmus}% 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 @@ -399,11 +340,12 @@ 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 +Der Divisionsalgorithmus für Polynome lässt sich aber leicht rekonstruieren. \subsubsection{Polynomdivision} Wir zeigen den Polynomdivisionsalgorithmus an einem konkreten Beispiel. +\index{Polynomdivision}% Gesucht sind Quotient $q\in \mathbb{Z}[X]$ und Rest $r\in\mathbb{Z}[X]$ der beiden Polynome \begin{equation} @@ -427,7 +369,7 @@ X^4&-& X^3&-&7X^2&+& X&+&6&:&X^2&+&X&+&1&=&X^2&-&2X&-&6=q\\ & & & & & &9X&+&12\rlap{$\mathstrut=r$}& & & & & & & & & & & & \\ \cline{7-9} \end{array} \] -Durch nachrechnen kann man überprüfen, dass tatsächlich +Durch Nachrechnen kann man überprüfen, dass tatsächlich \begin{align*} bq &= @@ -445,7 +387,7 @@ 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 +$q_k\in\mathbb{Z}$ auch nur den 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. @@ -454,7 +396,7 @@ 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, +Für beliebige Polynome $b\in R[X]$ ist dies aber nur dann immer der Fall, wenn die Koeffizienten in Tat und Wahrheit einem Körper entstammen. Im Folgenden betrachten wir daher nur noch Polynomringe mit Koeffizienten @@ -494,6 +436,7 @@ $f=qg+r$, wobei ausserdem $\deg r<\deg g$ ist. \begin{definition} Ein {\em euklidischer Ring} $R$ ist ein nullteilerfreier Ring mit einer +\index{euklischer Ring}% Gradfunktion $\deg\colon R\setminus\{0\}\to\mathbb{N}$ mit folgenden Eigenschaften \begin{enumerate} @@ -520,10 +463,12 @@ zerlegt werden. \subsubsection{Irreduzible Polynome} Das Konzept der Primzahl lässt sich wie folgt in den Polynomring übertragen. +\index{Primzahl}% \begin{definition} -Ein Polynom $f\in R[X]$ heisst irreduzibel, es keine Faktorisierung $f=gh$ -in Faktoren $g,h\in R[X]$ mit $\deg(g)>0$ und $\deg(h) >0$. +Ein Polynom $f\in R[X]$ heisst irreduzibel, wenn es keine Faktorisierung $f=gh$ +in Faktoren $g,h\in R[X]$ mit $\deg(g)>0$ und $\deg(h) >0$ gibt. +\index{irreduzibles Polynom}% \end{definition} \begin{beispiel} @@ -540,7 +485,7 @@ x_i = -\frac{b}2\pm\sqrt{\frac{b^2}{4}-c} \] gefunden werden. Die Faktorisierung ist also genau dann möglich, wenn $b^2/4-c$ ein -Quadrat in $\mathbb{Q}$. +Quadrat in $\mathbb{Q}$ ist. In $\mathbb{R}$ ist das Polynom faktorisierbar, wenn $b^2-4c\ge 0$ ist. In $\mathbb{C}$ gibt es keine Einschränkung, die Wurzel zu ziehen, in $\mathbb{C}$ gibt es also keine irreduziblen Polynome im Grad $2$. @@ -572,12 +517,3 @@ eindeutig sind. \end{satz} -% -% Abschnitt über formale Potenzreihen -% -\subsection{Formale Potenzreihen -\label{buch:subsection:polynome:potenzreihen}} -XXX TODO - - - diff --git a/buch/chapters/20-polynome/vektoren.tex b/buch/chapters/20-polynome/vektoren.tex index 408587d..0743592 100644 --- a/buch/chapters/20-polynome/vektoren.tex +++ b/buch/chapters/20-polynome/vektoren.tex @@ -25,14 +25,14 @@ a_{n-1}\\ a_{n} \end{pmatrix} \in -R^n. +R^{n+1}. \] Diese Darstellung eines Polynoms gibt auch die Addition von Polynomen und die Multiplikation von Polynomen mit Skalaren aus $R$ korrekt wieder. Die Abbildung von Vektoren auf Polynome \[ \varphi -\colon R^n \to R[X] +\colon R^{n+1} \to R[X] : \begin{pmatrix}a_0\\\vdots\\a_n\end{pmatrix} \mapsto @@ -52,7 +52,7 @@ Die Abbildung $\varphi$ ist also ein Isomorphismus \varphi \colon \{p\in R[X]\;|\; \deg(p) \le n\} -\overset{\equiv}{\to} +\overset{\cong}{\to} R^{n+1} \] zwischen der Menge @@ -93,7 +93,7 @@ mit der Eigenschaft, dass die Komponenten mit Indizes $m+1,\dots n$ verschwinden. Polynome vom Grad $m<n$ bilden einen Unterraum der Polynome vom Grad $n$. Wir können auch die $m+1$-dimensionalen Vektoren in den $n+1$-dimensionalen -Vektoren einbetten, indem wir die Vektoren durch ``auffüllen'' mit Nullen +Vektoren einbetten, indem wir die Vektoren durch ``Auffüllen'' mit Nullen auf die richtige Länge bringen. Es gibt also eine lineare Abbildung \[ @@ -108,25 +108,25 @@ b_0\\b_1\\\vdots\\b_m\\0\\\vdots \end{pmatrix} . \] -Die Moduln $R^{k}$ sind also alle ineinandergeschachtelt, können aber +Die Moduln $R^{k+1}$ sind also alle ineinandergeschachtelt, können aber alle auf konsistente Weise mit der Abbildung $\varphi$ in den Polynomring $R[X]$ abgebildet werden. \begin{center} -\begin{tikzcd} -\{0\}\ar[r] %\arrow[d,"\varphi"] - &R \ar[r] %\arrow[d, "\varphi"] - &R^2 \ar[r] %\arrow[d, "\varphi"] +\begin{tikzcd}[>=latex] +R \ar[r] \arrow[d, "\varphi"] + &R^2 \ar[r] \arrow[d, "\varphi"] + &R^3 \ar[r] \arrow[d, "\varphi"] &\dots \ar[r] - &R^k \ar[r] %\arrow[d, "\varphi"] - &R^{k+1} \ar[r] %\arrow[d, "\varphi"] + &R^k \ar[r] \arrow[d, "\varphi"] + &R^{k+1} \ar[r] \arrow[d, "\varphi"] &\dots \\ R^{(0)}[X]\arrow[r,hook] \arrow[drrr,hook] &R^{(1)}[X]\arrow[r,hook] \arrow[drr,hook] &R^{(2)}[X]\arrow[r,hook] \arrow[dr,hook] &\dots\arrow[r,hook] - &R^{(k)}[X]\arrow[r,hook] \arrow[dl,hook] - &R^{(k+1)}[X]\arrow[r,hook] \arrow[dll,hook] + &R^{(k-1)}[X]\arrow[r,hook] \arrow[dl,hook] + &R^{(k)}[X]\arrow[r,hook] \arrow[dll,hook] &\dots \\ & @@ -137,10 +137,115 @@ R^{(0)}[X]\arrow[r,hook] \arrow[drrr,hook] & \end{tikzcd} \end{center} +In diesem Sinne können wir $R^m$ für $m<n$ als Teilmenge von $R^n$ betrachten +und $R^\infty$ als deren Vereinigung definieren. +Polynome in $R[X]$ sind also Vektoren beliebiger Länge mit Kompoenten +in $R$. + \subsection{Multiplikative Struktur \label{buch:subsection:polynome:multiplikativestruktur}} +Den Polynomring $R[X]$ aus den Vektoren $R^{k}$ aufzubauen, bedeutet, +dass wir die multiplikative Struktur ignorieren. +Augrund der Rechenregeln für das Symbol $X$ können wir $X$ als einen +Multiplikationsoperator +\[ +{X\cdot} +\colon R^{m} \to R^{n} +: +\begin{pmatrix}a_0\\a_1\\a_2\\\vdots\end{pmatrix} +\mapsto +\begin{pmatrix}0\\a_0\\a_1\\\vdots\end{pmatrix} +\] +betrachten. +Diese Operatoren setzen sich zusammen zu einem Operator +\[ +{X\cdot} \colon R^\infty \to \infty, +\] +der die Multiplikation mit $X$ beschreibt. +Ist $p(X)$ ein Polynom, dann lässt sich die Multiplikation +in von Polynome mit $R[X]$ ebenfalls als Operator schreiben. +Die Potenz $X^k$ wird durch $k$-fache Iteration des Operators +$X\cdot$. +Das Polynom $p(X)$ wird durch Linearkombination, entspricht +also dem Operator, den man durch Einsetzen von $X\cdot$ +in das Polynom erhalten kann: +\[ +p(X\cdot) += +a_n(X\cdot)^n + a_{n-1}(X\cdot)^{n+1} + \dots + a_1(X\cdot) + a_0 +\colon +R^\infty \to R^\infty +: +q(X) +\mapsto +p(X)q(X). +\] +Man kann den Operator $X\cdot$ oder den iterierten Operator +$(X\cdot)^k$ auch in Matrixform darstellen: +\begin{align*} +{X\cdot} +&= +\begin{pmatrix} +0&0&0&0&\dots\\ +1&0&0&0&\dots\\ +0&1&0&0&\dots\\ +0&0&1&0&\dots\\ +\vdots&\vdots&\vdots&\ddots&\ddots +\end{pmatrix} +& +(X\cdot)^k +&= +\begin{pmatrix} + 0 & 0 & 0 & 0 &\dots\\ +\vdots&\vdots&\vdots&\vdots& \\ + 0 & 0 & 0 & 0 &\dots\\ + 1 & 0 & 0 & 0 &\dots\\ + 0 & 1 & 0 & 0 &\dots\\ + 0 & 0 & 1 & 0 &\dots\\ +\vdots&\vdots&\vdots&\ddots&\ddots +\end{pmatrix}. +\end{align*} +In der Matrix für $(X\cdot)^k$ steht die erste $1$ auf der +$k+1$-ten Zeile. +Der zum Polynom $p(X)$ gehörige Operator $p(X\cdot)$ bekommt +damit die Matrix +\[ +p(X\cdot) += +\begin{pmatrix} +a_0 & 0 & 0 & 0 & 0 & \dots \\ +a_1 &a_0 & 0 & 0 & 0 & \dots \\ +a_2 &a_1 & a_0 & 0 & 0 & \dots \\ +a_3 &a_2 & a_1 & a_0 & 0 & \dots \\ +a_4 &a_3 & a_2 & a_1 & a_0 & \dots \\ +\vdots &\vdots &\vdots&\vdots&\vdots&\ddots +\end{pmatrix}. +\] +Da die Matrix-Operation als Produkt +$\text{Zeile}\times\text{Spalte}$ ausgeführt wird, +kann man erkennen, dass das Polynomprodukt auch auf +eine Faltung hinausläuft. +Die wichtigste Lehre aus obigen Ausführungen aber ist +die Beobachtung, dass sich eine ganz allgemeine Algebra +wie die der Polynome auf sehr direkte Art und Weise auf +abbilden lässt in eine Algebra von Matrizen auf einem +geeigneten Vektorraum. +Im vorliegenden Fall sind das zwar ``undendliche'' +Matrizen, in zukünftigen Beispielen werden wir das +selbe Prinzip jedoch in Aktion sehen in Situationen, +wo eine Operation auf einem endlichen Vektorraum +und ``gewöhnliche'' Matrizen entstehen. +Die Möglichkeit, beliebige Polynome solcher Operatoren +zu berechnen, erlaubt uns, mehr über den Operator +herauszufinden - +Dies eröffnet vielfältige Möglichkeiten, auf einfachere +Art mit den Operatoren zu rechnen. +In Kapitel~\ref{buch:chapter:eigenwerte-und-eigenvektoren} +wird sich daraus eine Reihe von Normalformen einer Matrix +ergeben sowie die Möglichkeit, für viele Matrizen $A$ +die Matrix $f(A)$ für eine grosse Zahl von praktisch +interessanten Funktionen $f(z)$ zu berechnen. |