From 4764f8b481629a2f733c6025ec66a34a31d50222 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 16 Jun 2022 20:01:13 +0200 Subject: more on polynomials --- buch/chapters/010-potenzen/polynome.tex | 61 ++++++++++++++++++++++++++++++++- 1 file changed, 60 insertions(+), 1 deletion(-) (limited to 'buch/chapters/010-potenzen/polynome.tex') diff --git a/buch/chapters/010-potenzen/polynome.tex b/buch/chapters/010-potenzen/polynome.tex index 981e444..2086078 100644 --- a/buch/chapters/010-potenzen/polynome.tex +++ b/buch/chapters/010-potenzen/polynome.tex @@ -24,6 +24,7 @@ $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}% @@ -82,32 +83,47 @@ ebenfalls als Approximationen dienen können. Weitere Möglichkeiten liefern Interpolationsmethoden der numerischen Mathematik. +% +% 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)$ +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,6 +160,9 @@ 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} Die Konstruktion der Folgen $a_n(x)$ und $b_n(x)$ kann in Matrixform kompakter geschrieben werden als @@ -265,10 +284,50 @@ g(x) = c(x)a(x)+d(x)b(x) gilt. \end{satz} +% +% Faktorisierung und Nullstellen +% \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. +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 -- cgit v1.2.1 From 07724dd7774994996b3dc1b2955ef9a30cb59a44 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 16 Jun 2022 21:47:35 +0200 Subject: more complete chapter 1 --- buch/chapters/010-potenzen/polynome.tex | 93 ++++++++++++++++++++++++++++++++- 1 file changed, 92 insertions(+), 1 deletion(-) (limited to 'buch/chapters/010-potenzen/polynome.tex') diff --git a/buch/chapters/010-potenzen/polynome.tex b/buch/chapters/010-potenzen/polynome.tex index 2086078..9edb012 100644 --- a/buch/chapters/010-potenzen/polynome.tex +++ b/buch/chapters/010-potenzen/polynome.tex @@ -83,6 +83,22 @@ 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 % @@ -287,7 +303,8 @@ gilt. % % Faktorisierung und Nullstellen % -\subsection{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$. @@ -318,6 +335,21 @@ 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 @@ -331,7 +363,66 @@ gemeinsame Nullstellen von $a(x)$ und $b(x)$. \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: + +\begin{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$. -- cgit v1.2.1 From 931871e8c8e9b266b9b626d816a803bbd2c56653 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Fri, 1 Jul 2022 20:55:53 +0200 Subject: more index stuff --- buch/chapters/010-potenzen/polynome.tex | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'buch/chapters/010-potenzen/polynome.tex') diff --git a/buch/chapters/010-potenzen/polynome.tex b/buch/chapters/010-potenzen/polynome.tex index 9edb012..ce5e521 100644 --- a/buch/chapters/010-potenzen/polynome.tex +++ b/buch/chapters/010-potenzen/polynome.tex @@ -19,6 +19,7 @@ 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} @@ -65,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)$ @@ -74,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 @@ -127,6 +132,7 @@ Ein gemeinsamer Teiler zweier Polynome $a(x)$ und $b(x)$ 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}% +\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. @@ -180,6 +186,9 @@ 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 \[ @@ -401,8 +410,11 @@ p_n 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. @@ -436,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 -- cgit v1.2.1