1 files changed, 165 insertions, 2 deletions

diff --git a/buch/chapters/010-potenzen/polynome.tex b/buch/chapters/010-potenzen/polynome.tex
index 981e444..ce5e521 100644
--- a/buch/chapters/010-potenzen/polynome.tex
+++ b/buch/chapters/010-potenzen/polynome.tex
@@ -19,11 +19,13 @@ wobei $a_n\ne 0$ sein muss.
 Das Polynom heisst {\em normiert}, wenn $a_n=1$ ist.
 \index{normiert}%
 \index{Grad eines Polynoms}%
+\index{Polynom!Grad}%
 Die Menge aller Polynome mit Koeffizienten in der Menge $K$ wird mit
 $K[x]$ bezeichnet.
 \end{definition}
 
 Die Menge $K[x]$ ist heisst auch der {\em Polynomring}, weil $K[x]$
+\index{Polynomring}%
 mit der Addition, Subtraktion und Multiplikation von Polynomen eine
 algebraische Struktur bildet, die man einen Ring mit $1$ nennt.
 \index{Ring}%
@@ -64,6 +66,8 @@ Berechnungsverfahren für die speziellen Funktionen zu konstruieren.
 Dank des folgenden Satzes kann dies immer mit Polynomen geschehen.
 
 \begin{satz}[Weierstrass]
+\index{Satz!Weierstrass}%
+\index{Weierstrasse, Karl}%
 \label{buch:potenzen:satz:weierstrass}
 \index{Weierstrass, Satz von}%
 Eine auf einem kompakten Intervall $[a,b]$ stetige Funktion $f(x)$
@@ -73,7 +77,9 @@ approximieren.
 
 Der Satz sagt in dieser Form nichts darüber aus, wie die
 Approximationspolynome konstruiert werden sollen.
+\index{Approximationspolynom}%
 Von Bernstein gibt es konstruktive Beweise dieses Satzes,
+\index{Bernstein-Polynom}%
 welche auch explizit eine Folge von Approximationspolynomen
 konstruieren.
 In der späteren Entwicklung werden wir für die meisten
@@ -82,32 +88,64 @@ ebenfalls als Approximationen dienen können.
 Weitere Möglichkeiten liefern Interpolationsmethoden der
 numerischen Mathematik.
 
+Diese Betrachtungsweise von Polynomen als Funktionen trägt
+aber den zusätzlichen algebraischen Eigenschaften des Polynomringes
+nicht ausreichend Rechnung.
+Zum Beispiel bedeutet Gleichheit von zwei reellen Funktion $f(x)$ und
+$g(x)$, dass man $f(x)=g(x)$ für alle $x\in\mathbb{R}$ nachprüfen
+muss.
+Für Polynome reicht es jedoch, die Funktionswerte in nur wenigen
+Punkten zu vergleichen.
+Dies äussert sich zum Beispiel auch im Prinzip des
+Koeffizientenvergleichs von
+Satz~\ref{buch:polynome:satz:koeffizientenvergleich}.
+Im Gegensatz zu beliebigen Funktionen kann man daher Aussagen
+über Polynomen immer mit endlich Algorithmen entscheiden.
+Die nächsten Abschnitte sollen diese algebraischen Eigenschaften
+zusammenfassen.
+
+%
+% Polynomdivision, Teilbarkeit und ggT
+%
 \subsection{Polynomdivision, Teilbarkeit und grösster gemeinsamer Teiler}
 Der schriftliche Divisionsalgorithmus für Zahlen funktioniert 
 auch für die Division von Polynomen.
+\index{Polynome!Divisionsalgorithmus}%
 Zu zwei beliebigen Polynomen $p(x)$ und $q(x)$ lassen sich also
 immer zwei Polynome $a(x)$ und $r(x)$ finden derart, dass
 $p(x) = a(x) q(x) + r(x)$.
 Das Polynom $a(x)$ heisst der {\em Quotient}, $r(x)$ der {\em Rest}
 der Division.
 Das Polynom $p(x)$ heisst {\em teilbar} durch $q(x)$, geschrieben
+\index{teilbar}%
+\index{Polynome!teilbar}%
 $q(x)\mid p(x)$, wenn $r(x)=0$ ist.
 
+%
+% Grösster gemeinsamer Teiler
+%
 \subsubsection{Grösster gemeinsamer Teiler}
 Mit dem Begriff der Teilbarkeit geht auch die Idee des grössten
 gemeinsamen Teilers einher.
 Ein gemeinsamer Teiler zweier Polynome $a(x)$ und $b(x)$ 
+\index{gemeinsamer Teiler}%
 ist ein Polynom $g(x)$, welches beide Polynome teilt, also
 $g(x)\mid a(x)$ und $g(x)\mid b(x)$.
 \index{grösster gemeinsamer Teiler}%
-Ein Polynome $g(x)$ heisst grösster gemeinsamer Teiler von $a(x)$
+\index{Polynome!grösster gemeinsamer Teiler}%
+Ein Polynom $g(x)$ heisst {\em grösster gemeinsamer Teiler} von $a(x)$
 und $b(x)$, wenn jeder andere gemeinsame Teiler $f(x)$ von $a(x)$
 und $b(x)$ auch ein Teiler von $g(x)$ ist.
 Man beachte, dass die skalaren Vielfachen eines grössten gemeinsamen
 Teilers ebenfalls grösste gemeinsame Teiler sind, der grösste gemeinsame
 Teiler ist also nicht eindeutig bestimmt.
 
+%
+% Der euklidische Algorithmus
+%
 \subsubsection{Der euklidische Algorithmus}
+\index{Algorithmus!euklidisch}%
+\index{euklidischer Algorithmus}%
 Zur Berechnung eines grössten gemeinsamen Teilers steht wie bei den
 ganzen Zahlen der euklidische Algorithmus zur Verfügung.
 Dazu bildet man die Folgen von Polynomen
@@ -144,7 +182,13 @@ a_m(x)&=b_m(x)q_m(x).&&
 Der Index $m$ ist der Index, bei dem zum ersten Mal $r_m(x)=0$ ist.
 Dann ist $g(x)=r_{m-1}(x)$ ein grösster gemeinsamer Teiler.
 
+%
+% Der erweiterte euklidische Algorithmus
+%
 \subsubsection{Der erweiterte euklidische Algorithmus}
+\index{Polynome!erweiterter euklidischer Algorithmus}%
+\index{erweiterter euklidischer Algorithmus}%
+\index{euklidischer Algorithmus!erweitert}%
 Die Konstruktion der Folgen $a_n(x)$ und $b_n(x)$ kann in Matrixform
 kompakter geschrieben werden als
 \[
@@ -265,14 +309,132 @@ g(x) = c(x)a(x)+d(x)b(x)
 gilt.
 \end{satz}
 
-\subsection{Faktorisierung und Nullstellen}
+%
+% Faktorisierung und Nullstellen
+%
+\subsection{Faktorisierung und Nullstellen
+\label{buch:polynome:subsection:faktorisierung-und-nullstellen}}
 % wird später gebraucht um bei der Definition der hypergeometrischen Reihe
 % die Zaehler- und Nenner-Polynome als Pochhammer-Symbole zu entwickeln
+Ist $\alpha$ eine Nullstelle des Polynoms $a(x)$, also $a(\alpha)=0$.
+Der Divisionsalgorithmus mit für die Polynome $a(x)$ und $b(x)=x-\alpha$
+liefert zwei Polynome $q(x)$ für den Quotienten und $r(x)$ für den Rest
+mit den Eigenschaften
+\[
+a(x)
+=
+q(x) b(x)
++r(x)
+=
+q(x)(x-\alpha)+r(x)
+\qquad\text{mit}\qquad
+\deg r < \deg b(x)=1.
+\]
+Der Rest $r(x)$ ist somit eine Konstante. 
+Setzt man $x=\alpha$ ein, folgt
+\[
+0
+=
+a(\alpha)
+=
+q(\alpha)(\alpha-\alpha)+r(\alpha)
+=
+r(\alpha),
+\]
+der Rest $r(x)$ muss also verschwinden.
+Für eine Nullstelle $\alpha$ von $a(x)$ ist $a(x)$ durch $(x-\alpha)$
+teilbar.
+Daraus folgt auch, dass ein Polynom $a(x)$ vom Grad $n=\deg a(x)$ höchstens
+$n$ verschiedene Nullstellen haben kann.
+
+Sind $\alpha_1,\dots,\alpha_k$ alle Nullstellen von $a(x)$, dann lässt
+sich $a(x)$ zerlegen in Faktoren
+\[
+a(x)
+=
+(x-\alpha_1)^{m_1}
+(x-\alpha_2)^{m_2}
+\cdots
+(x-\alpha_k)^{m_k}
+b(x).
+\]
+Das Polynom $b(x)\in K[x]$ hat keine Nullstellen in $K$.
 
+Wenn zwei Polynome $a(x)$ und $b(x)$ eine gemeinsame Nullstelle $\alpha$
+haben, dann ist $(x-\alpha)$ ein Teiler beider Polynome und somit auch
+ein Teiler eines grössten gemeinsamer Teiler.
+Insbesondere sind die Nullstellen des grössten gemeinsamen Teilers
+gemeinsame Nullstellen von $a(x)$ und $b(x)$.
+
+%
+% Koeffizienten-Vergleich
+%
 \subsection{Koeffizienten-Vergleich}
 % Wird gebraucht für die Potenzreihen-Methode
 % Muss später ausgedehnt werden auf Potenzreihen
+Wenn zwei Polynome $a(x)$ und $b(x)$ vom Grad $\le n$ die gleichen
+Koeffizienten haben, dann sind sie selbstverständlich gleich.
+Weniger klar ist, ob zwei Polynome, die die gleichen Werte für beliebige
+$x$ haben, auch die gleichen Koeffizienten haben.
+Wir nehmen also an, dass $a(x)=b(x)$ gilt für jedes $x\in K$ und
+wollen daraus ableiten, dass die Koeffizienten übereinstimmen müssen.
+Seien $x_1,\dots,x_n$ verschiedene Elemente in $K$, dann
+hat das Polynom $p(x)=a(x)-b(x)$, welches Grad $\le n$ hat,
+die $n$ Nullstellen $x_k$ für $k=1,\dots,n$.
+$p(x)$ ist also durch alle Polynome $x-x_k$ teilbar.
+Weil $\deg p\le n$ ist, muss 
+\[
+0
+=
+a(x)-b(x)
+=
+p(x)
+=
+p_n
+(x-x_1)(x-x_2)\cdots (x-x_n)
+\]
+sein.
+Ist $y\in K$ verschieden von den Nullstellen $x_i$, dann ist 
+in $y-x_i\ne 0$ für alle $i$.
+Für das Produkt gilt dann
+\[
+0
+=
+p(y) 
+=
+p_n
+(\underbrace{x-x_1}_{\displaystyle \ne 0})
+\cdots
+(\underbrace{x-x_n}_{\displaystyle \ne 0}),
+\]
+so dass $p_n=0$ sein muss, was schliesslich dazu führt, dass alle
+Koeffizienten von $a(x)-b(x)$ verschwinden.
+Daraus folgt das Prinzip des Koeffizientenvergleichs:
+\index{Koeffizientenvergleich}%
+\index{Polynome!Koeffizientenvergleich}%
+
+\begin{satz}[Koeffizientenvergleich]
+\index{Satz!Koeffizientenvergleich}%
+\label{buch:polynome:satz:koeffizientenvergleich}
+Zwei Polynome $a(x)$ und $b(x)$ stimmen genau dann überein, wenn
+sie die gleichen Koeffizienten haben.
+\end{satz}
 
+Man beachte, dass dieses Prinzip nur funktioniert, wenn es genügend
+viele verschiedene Elemente in $K$ gibt.
+Für die endlichen Körper $\mathbb{F}_p$ gilt dies nicht, denn es gilt
+\[
+a(x)
+=
+x^p-x\equiv 0\mod p
+\]
+für jede Zahl $x\in\mathbb{F}_p$, das Polynom $a(x)$ mit Grad $p$
+hat also genau $p$ Nullstellen, es gibt aber keine weitere Nullstelle,
+mit der man wie oben schliessen könnte, dass $a(x)$ das Nullpolynom ist.
+
+%
+% Berechnung von Polynom-Werten
+%
 \subsection{Berechnung von Polynom-Werten}
 Die naive Berechnung der Werte eines Polynoms $p(x)$ vom Grad $n$
 beginnt mit der Berechnung der Potenzen von $x$.
@@ -286,6 +448,7 @@ und $n$ Additionen.
 Die Anzahl nötiger Multiplikationen kann mit dem folgenden Vorgehen
 reduziert werden, welches auch als das {\em Horner-Schema} bekannt ist.
 \index{Horner-Schema}%
+\index{Polynome!Horner-Schema}%
 Statt erst am Schluss alle Terme zu addieren, addiert man so früh
 wie möglich.
 Zum Beispiel multipliziert man $(a_nx+a_{n-1})$ mit $x$, was auf