diff options
Diffstat (limited to 'buch')
84 files changed, 1763 insertions, 823 deletions
diff --git a/buch/chapters/10-vektorenmatrizen/ringe.tex b/buch/chapters/10-vektorenmatrizen/ringe.tex index 1149e29..433f1e9 100644 --- a/buch/chapters/10-vektorenmatrizen/ringe.tex +++ b/buch/chapters/10-vektorenmatrizen/ringe.tex @@ -57,7 +57,7 @@ in denen die Multiplikation nicht kommutativ ist, die Multiplikation kein neutrales Element hat oder beides. \begin{definition} -\index{Ring mit Eins}% +\index{Ring!mit Eins}% Ein Ring $R$ heisst ein {\em Ring mit Eins}, wenn die Multiplikation ein neutrales Element hat. \index{Ring mit Eins}% diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index b066969..e3731d5 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -164,7 +164,7 @@ X^2+8X+15 X^2+X+1\mod 7. \] Das Polynom $X^2+X+1$ ist daher über $\mathbb{F}_7$ reduzibel und -das Polynom $X^3-1\in\mathbb{F}_7$ zerfällt daher in Linearfaktoren +das Polynom $X^3-1\in\mathbb{F}_7$ zerfällt in Linearfaktoren $X^3-1=(X+6)(X+3)(X+5)$. \end{beispiel} diff --git a/buch/chapters/40-eigenwerte/eigenwerte.tex b/buch/chapters/40-eigenwerte/eigenwerte.tex index 563b58a..1af91f8 100644 --- a/buch/chapters/40-eigenwerte/eigenwerte.tex +++ b/buch/chapters/40-eigenwerte/eigenwerte.tex @@ -19,7 +19,7 @@ Eigenschaften der Matrix $A$ abzuleiten. \label{buch:eigenwerte:def:spektrum} Ein Vektor $v\in V$ heisst {\em Eigenvektor} von $A$ zum {\em Eigenwert} \index{Eigenwert}% -\index{Eigenvekor}% +\index{Eigenvektor}% $\lambda\in\Bbbk$, wenn $v\ne 0$ und $Av=\lambda v$ gilt. Die Menge \[ diff --git a/buch/chapters/40-eigenwerte/grundlagen.tex b/buch/chapters/40-eigenwerte/grundlagen.tex index 91294f1..b41da1d 100644 --- a/buch/chapters/40-eigenwerte/grundlagen.tex +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -27,7 +27,7 @@ bereits eine Normalform für nilpotente Matrizen. \caption{Iterierte Kerne und Bilder einer $3\times 3$-Matrix mit Rang~2. Die abnehmend geschachtelten iterierten Bilder $\mathcal{J}^1(A) \subset \mathcal{J}^2(A)$ -sind links dargestellt, die zunehmen geschachtelten iterierten Kerne +sind links dargestellt, die zunehmend geschachtelten iterierten Kerne $\mathcal{K}^1(A) \subset \mathcal{K}^2(A)$ rechts. \label{buch:eigenwerte:img:kernbild}} \end{figure} @@ -387,7 +387,7 @@ $A^k=0$. \begin{beispiel} Obere (oder untere) Dreiecksmatrizen mit Nullen auf der Diagonalen sind nilpotent. -\index{Dreicksmatrix}% +\index{Dreiecksmatrix}% Wir rechnen dies wie folgt nach. Die Matrix $A$ mit Einträgen $a_{i\!j}$ \[ diff --git a/buch/chapters/60-gruppen/Makefile.inc b/buch/chapters/60-gruppen/Makefile.inc index 8b3d974..fe327a9 100644 --- a/buch/chapters/60-gruppen/Makefile.inc +++ b/buch/chapters/60-gruppen/Makefile.inc @@ -9,4 +9,7 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/60-gruppen/lie-gruppen.tex \ chapters/60-gruppen/lie-algebren.tex \ chapters/60-gruppen/homogen.tex \ + chapters/60-gruppen/uebungsaufgaben/6001.tex \ + chapters/60-gruppen/uebungsaufgaben/6002.tex \ + chapters/60-gruppen/uebungsaufgaben/6003.tex \ chapters/60-gruppen/chapter.tex diff --git a/buch/chapters/60-gruppen/chapter.tex b/buch/chapters/60-gruppen/chapter.tex index 3b1abc1..4f2fb5a 100644 --- a/buch/chapters/60-gruppen/chapter.tex +++ b/buch/chapters/60-gruppen/chapter.tex @@ -9,22 +9,40 @@ \rhead{} Matrizen können dazu verwendet werden, Symmetrien von geometrischen oder physikalischen Systemen zu beschreiben. +\index{Symmetrie}% +\index{physikalisches System}% Neben diskreten Symmetrien wie zum Beispiel Spiegelungen gehören dazu +\index{diskrete Symmetrie}% +\index{Symmetrie!diskret}% +\index{Spiegelung}% auch kontinuierliche Symmetrien wie Translationen oder Invarianz einer -phyisikalischen Grösse über die Zeit. +\index{kontinuierliche Symmetrie}% +\index{Symmetrie!kontinuierlich}% +\index{Translation}% +physikalischen Grösse über die Zeit. Solche Symmetrien müssen durch Matrizen beschrieben werden können, die auf stetige oder sogar differenzierbare Art von der Zeit abhängen. Die Menge der Matrizen, die zur Beschreibung solcher Symmetrien benutzt werden, muss also eine zusätzliche Struktur haben, die ermöglicht, sinnvoll über Stetigkeit und Differenzierbarkeit bei Matrizen +\index{Stetigkeit}% +\index{Differenzierbarkeit}% zu sprechen. Die Menge der Matrizen bilden zunächst eine Gruppe, -die zusätzliche differenziarbare Struktur macht daraus +die zusätzliche differenzierbare Struktur macht daraus eine sogenannte Lie-Gruppe. -Die Ableitungen nach einem Parameter liegen in der sogenannten -Lie-Algebra, einer Matrizen-Algebra mit dem antisymmetrischen +\index{Lie-Gruppe}% +Die Ableitungen nach einem Parameter sind nicht mehr Gruppenelemente, +wie man nach allem, was man in der Analysis-Grundvorlesung +gelernt hat, vielleicht erwarten würde. +Sie liegen in der sogenannten Lie-Algebra, +einer Matrizen-Algebra mit dem antisymmetrischen +\index{Lie-Algebra}% +\index{antisymmetrisch}% Lie-Klammer-Produkt $[A,B]=AB-BA$, auch Kommutator genannt. +\index{Lie-Klammer}% +\index{Kommutator}% Lie-Gruppe und Lie-Algebra sind eng miteinander verknüpft, so eng, dass sich die meisten Eigenschaften der Gruppe aus den Eigenschaften der Lie-Gruppe aus der Lie-Algebra ableiten lassen. @@ -43,5 +61,6 @@ Zusammenhangs darzustellen. \begin{uebungsaufgaben} \uebungsaufgabe{6002} \uebungsaufgabe{6001} +\uebungsaufgabe{6003} \end{uebungsaufgaben} diff --git a/buch/chapters/60-gruppen/images/Makefile b/buch/chapters/60-gruppen/images/Makefile index 3ed39e5..294ecfa 100644 --- a/buch/chapters/60-gruppen/images/Makefile +++ b/buch/chapters/60-gruppen/images/Makefile @@ -3,7 +3,8 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: phasenraum.pdf kartenkreis.pdf karten.pdf sl2.pdf scherungen.pdf +all: phasenraum.pdf kartenkreis.pdf karten.pdf sl2.pdf scherungen.pdf \ + rodriguez.pdf nichtkomm.pdf phasenraum.pdf: phasenraum.tex pdflatex phasenraum.tex @@ -23,3 +24,8 @@ sl2.pdf: sl2.tex scherungen.pdf: scherungen.tex pdflatex scherungen.tex +rodriguez.pdf: rodriguez.tex rodriguez.jpg + pdflatex rodriguez.tex + +nichtkomm.pdf: nichtkomm.tex c60.jpg + pdflatex nichtkomm.tex diff --git a/buch/chapters/60-gruppen/images/c60.jpg b/buch/chapters/60-gruppen/images/c60.jpg Binary files differnew file mode 100644 index 0000000..2bc77e7 --- /dev/null +++ b/buch/chapters/60-gruppen/images/c60.jpg diff --git a/buch/chapters/60-gruppen/images/nichtkomm.pdf b/buch/chapters/60-gruppen/images/nichtkomm.pdf Binary files differnew file mode 100644 index 0000000..8b66ea3 --- /dev/null +++ b/buch/chapters/60-gruppen/images/nichtkomm.pdf diff --git a/buch/chapters/60-gruppen/images/nichtkomm.tex b/buch/chapters/60-gruppen/images/nichtkomm.tex new file mode 100644 index 0000000..53cf87a --- /dev/null +++ b/buch/chapters/60-gruppen/images/nichtkomm.tex @@ -0,0 +1,68 @@ +% +% nichtkomm.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{times} +\usepackage{amsmath} +\usepackage{txfonts} +\usepackage[utf8]{inputenc} +\usepackage{graphics} +\usetikzlibrary{arrows,intersections,math} +\usepackage{ifthen} +\begin{document} + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\breite{7} +\def\hoehe{4} + +\begin{tikzpicture}[>=latex,thick] + +% Povray Bild +\node at (0,0) {\includegraphics[width=14cm]{c60.jpg}}; + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\coordinate (A) at (-0.3,3); +\coordinate (B) at (-1.1,2); +\coordinate (C) at (-2.1,-1.2); +\draw[->,color=red,line width=1.4pt] + (A) + to[out=-143,in=60] + (B) + to[out=-120,in=80] + (C); +%\fill[color=red] (B) circle[radius=0.08]; +\node[color=red] at (-1.2,1.5) [above left] {$R_{x_1,\alpha}$}; +\coordinate (D) at (0.3,3.2); +\coordinate (E) at (1.8,2.8); +\coordinate (F) at (5.2,-0.3); +\draw[->,color=blue,line width=1.4pt] + (D) + to[out=-10,in=157] + (E) + to[out=-23,in=120] + (F); +%\fill[color=blue] (E) circle[radius=0.08]; +\node[color=blue] at (2.4,2.4) [above right] {$R_{x_2,\beta}$}; +\draw[->,color=darkgreen,line width=1.4pt] + (0.7,-3.1) to[out=1,in=-160] (3.9,-2.6); +\node[color=darkgreen] at (2.5,-3.4) {$R_{x_3,\gamma}$}; + +\node at (6.4,-2.9) {$x_1$}; +\node at (-0.2,3.8) {$x_3$}; + +\end{tikzpicture} + +\end{document} + diff --git a/buch/chapters/60-gruppen/images/rodriguez.jpg b/buch/chapters/60-gruppen/images/rodriguez.jpg Binary files differnew file mode 100644 index 0000000..5c49700 --- /dev/null +++ b/buch/chapters/60-gruppen/images/rodriguez.jpg diff --git a/buch/chapters/60-gruppen/images/rodriguez.pdf b/buch/chapters/60-gruppen/images/rodriguez.pdf Binary files differnew file mode 100644 index 0000000..d947fe1 --- /dev/null +++ b/buch/chapters/60-gruppen/images/rodriguez.pdf diff --git a/buch/chapters/60-gruppen/images/rodriguez.tex b/buch/chapters/60-gruppen/images/rodriguez.tex new file mode 100644 index 0000000..8544739 --- /dev/null +++ b/buch/chapters/60-gruppen/images/rodriguez.tex @@ -0,0 +1,45 @@ +% +% 3dimagetemplate.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{times} +\usepackage{amsmath} +\usepackage{txfonts} +\usepackage[utf8]{inputenc} +\usepackage{graphics} +\usetikzlibrary{arrows,intersections,math} +\usepackage{ifthen} +\begin{document} + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\breite{7} +\def\hoehe{4} + +\begin{tikzpicture}[>=latex,thick] + +% Povray Bild +\node at (0,0) {\includegraphics[width=10cm]{rodriguez.jpg}}; + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\node[color=blue] at (0.6,3.0) {$\vec{k}\mathstrut$}; +\node[color=red] at (1.8,-1.0) [below right] {$\vec{x}\mathstrut$}; +\node[color=darkgreen] at (-4.5,1.0) [below left] + {$\vec{x}\times\vec{k}\mathstrut$}; +\node[color=yellow] at (1.9,-0.5) [right] {$\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}$}; + +\end{tikzpicture} + +\end{document} + diff --git a/buch/chapters/60-gruppen/lie-algebren.tex b/buch/chapters/60-gruppen/lie-algebren.tex index cee8510..0f6429f 100644 --- a/buch/chapters/60-gruppen/lie-algebren.tex +++ b/buch/chapters/60-gruppen/lie-algebren.tex @@ -8,7 +8,7 @@ \rhead{Lie-Algebren} Im vorangegangenen Abschnitt wurde gezeigt, dass alle beschriebenen Matrizengruppen als Untermannigfaltigkeiten im $n^2$-dimensionalen -Vektorraum $M_n(\mathbb{R}9$ betrachtet werden können. +Vektorraum $M_n(\mathbb{R})$ betrachtet werden können. Die Gruppen haben damit nicht nur die algebraische Struktur einer Matrixgruppe, sie haben auch die geometrische Struktur einer Mannigfaltigkeit. @@ -27,6 +27,7 @@ Insbesondere werden wir sehen, wie die Gruppen $\operatorname{SO}(3)$ und $\operatorname{SU}(2)$ die gleich Lie-Algebra haben und dass die Lie-Algebra von $\operatorname{SO}(3)$ mit dem Vektorprodukt in $\mathbb{R}^3$ übereinstimmt. +\index{Vektorprodukt}% % % Die Lie-Algebra einer Matrizengruppe @@ -78,12 +79,12 @@ I+(B+A)t + \biggl(\frac{B^2}{2!}+BA+\frac{A^2}{2!}\biggr)t^2 +\dots \intertext{% Die beiden Kurven $e^{At}e^{Bt}$ und $e^{Bt}e^{At}$ haben zwar den gleichen Tangentialvektor für $t=0$, sie unterscheiden -sich aber untereinander, und sie unterscheiden sich von der -Einparameteruntergruppe von $A+B$} +sich aber für $t>0$ und sie unterscheiden sich von der +Einparameteruntergruppe} e^{(A+B)t} &= I + (A+B)t + \frac{t^2}{2}(A^2 + AB + BA + B^2) + \ldots -\intertext{Für die Unterschiede finden wir} +\intertext{von $A+B$. Für die Unterschiede finden wir} e^{At}e^{Bt} - e^{(A+B)t} &= \biggl(AB-\frac{AB+BA}2\biggr)t^2 @@ -110,15 +111,19 @@ e^{At}e^{Bt}-e^{Bt}e^{At} = \phantom{-}[A,B]t^2+\ldots \end{align*} -wobei mit $[A,B]=AB-BA$ abgekürzt wird. +wobei $[A,B]=AB-BA$ abgekürzt wird. \begin{definition} \label{buch:gruppen:def:kommutator} -Der Kommutator zweier Matrizen $A,B\in M_n(\mathbb{R})$ ist die Matrix +Der {\em Kommutator} zweier Matrizen $A,B\in M_n(\mathbb{R})$ ist die Matrix $[A,B]=AB-BA$. +\index{Kommutator}% +\index{Lie-Klammer}% \end{definition} Der Kommutator ist bilinear und antisymmetrisch, da +\index{bilinear}% +\index{antisymmetrisch}% \begin{align*} [\lambda A+\mu B,C] &= @@ -139,11 +144,13 @@ AB-BA = -(BA-AB) = -[B,A]. Aus der letzten Bedingung folgt insbesodnere $[A,A]=0$ Der Kommutator $[A,B]$ misst in niedrigster Ordnung den Unterschied -zwischen den $e^{At}$ und $e^{Bt}$. +zwischen den +$ e^{At} e^{Bt} $ +und +$ e^{Bt} e^{At} $. Der Kommutator der Tangentialvektoren $A$ und $B$ bildet also die Nichtkommutativität der Matrizen $e^{At}$ und $e^{Bt}$ ab. - \subsubsection{Die Jacobi-Identität} Der Kommutator hat die folgende zusätzliche algebraische Eigenschaft: \begin{align*} @@ -182,6 +189,7 @@ Identität. \label{buch:gruppen:def:jacobi} Ein bilineares Produkt $[\;,\;]\colon V\times V\to V$ auf dem Vektorraum erfüllt die {\em Jacobi-Identität}, wenn +\index{Jacobi-Identität}% \[ [u,[v,w]] + [v,[w,u]] + [w,[u,v]]=0 \] @@ -199,23 +207,26 @@ Ein Vektorraum $V$ mit einem bilinearen, Produkt \] welches zusätzlich die Jacobi-Identität~\ref{buch:gruppen:def:jacobi} erfüllt, heisst eine {\em Lie-Algebra}. +\index{Lie-Algebra}% \end{definition} Die Lie-Algebra einer Lie-Gruppe $G$ wird mit $LG$ bezeichnet. $LG$ besteht aus den Tangentialvektoren im Punkt $I$. -Die Exponentialabbildung $\exp\colon LG\to G:A\mapsto e^A$ +Die {\em Exponentialabbildung} $\exp\colon LG\to G:A\mapsto e^A$ +\index{Exponentialabbildung}% ist eine differenzierbare Abbildung von $LG$ in die Gruppe $G$. Insbesondere kann die Inverse der Exponentialabbildung als eine Karte in einer Umgebung von $I$ verwendet werden. Für die Lie-Algebren der Matrizengruppen, die früher definiert worden -sind, verwenden wir die als Notationskonvention, dass der Name der +sind, verwenden wir die Notationskonvention, dass der Name der Lie-Algebra der mit kleinen Buchstaben geschrieben Name der Lie-Gruppe ist. Die Lie-Algebra von $\operatorname{SO}(n)$ ist also -$L\operatorname{SO}(n) = \operatorname{os}(n)$, +$L\operatorname{SO}(n) = \operatorname{so}(n)$, +\index{so(n)@$\operatorname{so}(n)$}% die Lie-Algebra von $\operatorname{SL}_n(\mathbb{R})$ ist $L\operatorname{SL}_n(\mathbb{R})=\operatorname{sl}_n(\mathbb{R})$. - +\index{sln(r)@$\operatorname{sl}_n(\mathbb{R})$}% % % Die Lie-Algebra von SO(3) @@ -229,34 +240,126 @@ Solche Matrizen haben die Form \Omega = \begin{pmatrix} - 0 & \omega_3&-\omega_2\\ --\omega_3& 0 & \omega_1\\ - \omega_2&-\omega_1& 0 + 0 &-\omega_3& \omega_2\\ + \omega_3& 0 &-\omega_1\\ +-\omega_2& \omega_1& 0 \end{pmatrix} \] +Die antisymmetrischen Matrizen +\[ +\omega_{23} += +\begin{pmatrix} 0&0&0\\0&0&-1\\0&1&0\end{pmatrix}, +\quad +\omega_{31} += +\begin{pmatrix} 0&0&1\\0&0&0\\-1&0&0\end{pmatrix}, +\quad +\omega_{12} += +\begin{pmatrix} 0&1&0\\-1&0&0\\0&0&0\end{pmatrix} +\] +bilden eine Basis für $\operatorname{so}(3)$, man kann +\[ +\Omega += +\omega_1\omega_{23} ++ +\omega_2\omega_{31} ++ +\omega_3\omega_{12} +\] +schreiben. Der Vektorraum $\operatorname{so}(3)$ ist also dreidimensional. -Die Wirkung von $I+t\Omega$ auf einem Vektor $x$ ist +Die Kommutatoren der Basisvektoren sind +\begin{equation} +\setlength\arraycolsep{4pt} +\begin{aligned} +[\omega_{23},\omega_{31}] +&= +\begin{pmatrix} +0&-1&0\\ +1&0&0\\ +0&0&0 +\end{pmatrix} += +\omega_{12}, +%\\ +& +[\omega_{31},\omega_{12}] +&= +\begin{pmatrix} +0&0&0\\ +0&0&-1\\ +0&1&0 +\end{pmatrix} += +\omega_{23}, +%\\ +& +[\omega_{12},\omega_{23}] +&= +\begin{pmatrix} +0&0&1\\ +0&0&0\\ +-1&0&0 +\end{pmatrix} += +\omega_{31}, +\end{aligned} +\label{buch:gruppen:eqn:so3-kommutatoren} +\end{equation} +wie man durch direkte Rechnung bestätigt. +Diese Regeln stimmen mit den Vektorprodukten der Standardbasisvektoren +in $\mathbb{R}^3$ überein. + +\begin{figure} +\centering +\includegraphics{chapters/60-gruppen/images/nichtkomm.pdf} +\caption{Der Kommutator zweier Drehungen um die $x_1$ und $x_2$ +Achse ist eine Drehung um die $x_3$-Achse. +\label{buch:lie:fig:kommutator}} +\end{figure} +Abbildung~\ref{buch:lie:fig:kommutator} illustriert, wie der +Kommutator die Nichtkommutativität der Gruppe $\operatorname{SO}(3)$ +wiedergibt. +Die Matrix $\omega_{23}$ erzeugt eine Drehung $R_{x_1,\alpha}$ +um die $x_1$-Achse, +die Matrix $\omega_{31}$ eine Drehung $R_{x_2,\beta}$ um die $x_2$ Achse. +Der Kommutator $[\omega_{23},\omega_{31}]=\omega_{12}$ beschreibt in +niedrigster Ordnung den Unterschied, der entsteht, wenn man die +beiden Drehungen in verschiedenen Reihenfolgen ausführt. +Dies ist eine Drehung $R_{x_3,\gamma}$ um die $x_3$-Achse. + +Aus der Rodriguez-Formel~\ref{buch:lie:eqn:rodrigues} wissen wir +bereits, dass die Ableitung der Drehung das Vektorprodukt +$\vec{\omega}\times\vec{x}$ ist. +Dieses kann jedoch auch als +$\Omega\vec{x} = \vec{omega}\times\vec{x}$ +ausgedrückt werden. + +Die Wirkung von $I+t\Omega$ auf einem Vektor $\vec{x}$ ist \[ (I+t\Omega) \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix} - 1 & t\omega_3&-t\omega_2\\ --t\omega_3& 1 & t\omega_1\\ - t\omega_2&-t\omega_1& 1 + 1 &-t\omega_3& t\omega_2\\ + t\omega_3& 1 &-t\omega_1\\ +-t\omega_2& t\omega_1& 1 \end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix} -x_1-t(-\omega_3x_2+\omega_2x_3)\\ -x_2-t( \omega_3x_1-\omega_1x_3)\\ -x_3-t(-\omega_2x_1+\omega_1x_2) +x_1+t(-\omega_3x_2+\omega_2x_3)\\ +x_2+t( \omega_3x_1-\omega_1x_3)\\ +x_3+t(-\omega_2x_1+\omega_1x_2) \end{pmatrix} = -x- t\begin{pmatrix}\omega_1\\\omega_2\\\omega_3\end{pmatrix}\times x +\vec{x}+ t\begin{pmatrix}\omega_1\\\omega_2\\\omega_3\end{pmatrix}\times x = -x+ tx\times \omega. +\vec{x}+ t\vec{\omega}\times \vec{x}. \] Die Matrix $\Omega$ ist als die infinitesimale Version einer Drehung um die Achse $\omega$. @@ -271,9 +374,9 @@ mit Hilfe der Abbildung \begin{pmatrix}v_1\\v_2\\v_3\end{pmatrix} \mapsto \begin{pmatrix} - 0 & v_3&-v_1\\ --v_3& 0 & v_2\\ - v_1&-v_2& 0 + 0 &-v_3& v_2\\ + v_3& 0 &-v_1\\ +-v_2& v_1& 0 \end{pmatrix}. \] Der Kommutator von zwei so aus Vektoren $\vec u$ und $\vec v$ @@ -285,56 +388,56 @@ UV-VU \\ &= \begin{pmatrix} - 0 & u_3&-u_1\\ --u_3& 0 & u_2\\ - u_1&-u_2& 0 + 0 &-u_3& u_2\\ + u_3& 0 &-u_1\\ +-u_2& u_1& 0 \end{pmatrix} \begin{pmatrix} - 0 & v_3&-v_1\\ --v_3& 0 & v_2\\ - v_1&-v_2& 0 + 0 &-v_3& v_2\\ + v_3& 0 &-v_1\\ +-v_2& v_1& 0 \end{pmatrix} - \begin{pmatrix} - 0 & v_3&-v_1\\ --v_3& 0 & v_2\\ - v_1&-v_2& 0 + 0 &-v_3& v_2\\ + v_3& 0 &-v_1\\ +-v_2& v_1& 0 \end{pmatrix} \begin{pmatrix} - 0 & u_3&-u_1\\ --u_3& 0 & u_2\\ - u_1&-u_2& 0 + 0 &-u_3& u_2\\ + u_3& 0 &-u_1\\ +-u_2& u_1& 0 \end{pmatrix} \\ &= \begin{pmatrix} -u_3v_3+u_1v_1 - u_3v_3 - u_1v_1 - & u_1v_2 - u_2v_1 - & u_3v_2 - u_2v_3 -\\ -u_2v_1 - u_1v_2 - & -u_3v_3-u_2v_2 + u_3v_3+u_2v_2 +-u_3v_3-u_2v_2 + u_3v_3 + u_2v_2 + & u_2v_1 - u_1v_2 & u_3v_1 - u_1v_3 \\ -u_2v_3 - u_3v_2 - & u_1v_3 - u_3v_1 - &-u_1v_1-u_2v_2 u_1v_1+u_2v_2 +u_1v_2 - u_2v_1 + & -u_3v_3-u_1v_1 + u_3v_3+u_1v_1 + & u_3v_2 - u_2v_3 +\\ +u_1v_3 - u_3v_1 + & u_2v_3 - u_3v_2 + &-u_2v_2-u_1v_1+ u_2v_2+u_1v_1 \end{pmatrix} \\ &= \begin{pmatrix} 0 - & u_1v_2 - u_2v_1 - &-(u_2v_3-u_3v_2) + &-(u_1v_2 - u_2v_1) + &u_3v_1-u_1v_3 \\ --( u_1v_2 - u_2v_1) +u_1v_2 - u_2v_1 & 0 - & u_3v_1 - u_1v_3 + &-(u_2v_3 - u_3v_2) \\ -u_2v_3 - u_3v_2 - &-( u_3v_1 - u_1v_3) +-(u_3v_1 - u_1v_3) + & u_3v_2 - u_2v_3 & 0 -\end{pmatrix} +\end{pmatrix}. \end{align*} Die Matrix $[U,V]$ gehört zum Vektor $\vec u\times\vec v$. Damit können wir aus der Jacobi-Identität jetzt folgern, dass @@ -349,10 +452,10 @@ Damit können wir aus der Jacobi-Identität jetzt folgern, dass für drei beliebige Vektoren $\vec u$, $\vec v$ und $\vec w$ ist. Dies bedeutet, dass der dreidimensionale Vektorraum $\mathbb R^3$ mit dem Vektorprodukt zu einer Lie-Algebra wird. -In der Tat verwenden einige Bücher statt der vertrauten Notation +In der Tat verwenden einige Lehrbücher statt der vertrauten Notation $\vec u\times \vec v$ für das Vektorprodukt die aus der Theorie der Lie-Algebren entlehnte Notation $[\vec u,\vec v]$, zum Beispiel -das Lehrbuch der Theoretischen Physik \cite{skript:landaulifschitz1} +auch das Lehrbuch der Theoretischen Physik \cite{skript:landaulifschitz1} von Landau und Lifschitz. Die Lie-Algebren sind vollständig klassifiziert worden, es gibt @@ -361,56 +464,6 @@ Unser dreidimensionaler Raum ist also auch in dieser Hinsicht speziell: es ist der kleinste Vektorraum, in dem eine nichttriviale Lie-Algebra-Struktur möglich ist. -Die antisymmetrischen Matrizen -\[ -\omega_{23} -= -\begin{pmatrix} 0&1&0\\-1&0&0\\0&0&0\end{pmatrix} -\quad -\omega_{31} -= -\begin{pmatrix} 0&0&-1\\0&0&0\\1&0&0\end{pmatrix} -\quad -\omega_{12} -= -\begin{pmatrix} 0&0&0\\0&0&1\\0&-1&0\end{pmatrix} -\] -haben die Kommutatoren -\begin{equation} -\begin{aligned} -[\omega_{23},\omega_{31}] -&= -\begin{pmatrix} -0&0&0\\ -0&0&1\\ -0&-1&0 -\end{pmatrix} -= -\omega_{12} -\\ -[\omega_{31},\omega_{12}] -&= -\begin{pmatrix} -0&1&0\\ --1&0&0\\ -0&0&0 -\end{pmatrix} -= -\omega_{23} -\\ -[\omega_{12},\omega_{23}] -&= -\begin{pmatrix} -0&0&-1\\ -0&0&0\\ -1&0&0 -\end{pmatrix} -= -\omega_{31} -\end{aligned} -\label{buch:gruppen:eqn:so3-kommutatoren} -\end{equation} - \subsection{Die Lie-Algebra von $\operatorname{SL}_n(\mathbb{R})$} Die Lie-Algebra von $\operatorname{SL}_n(\mathbb{R})$ besteht aus den spurlosen Matrizen in $M_n(\mathbb{R})$. @@ -448,13 +501,16 @@ A\in M_n(\mathbb{C} AA^*=I \} \] +\index{unitäre Gruppe}% +\index{Gruppe, unitär}% +\index{U(n)@$\operatorname{U}(n)$}% heisst die unitäre Gruppe, sie besteht aus den Matrizen, die das sesquilineare Standardskalarprodukt auf dem komplexen Vektorraum $\mathbb{C}^n$ invariant lassen. Sei eine $\gamma(t)$ ein differenzierbare Kurve in $\operatorname{U}(n)$ derart, dass $\gamma(0)=I$. Die Ableitung der Identität $AA^*=I$ führt dann auf -\begin{align*} +\begin{equation*} 0 = \frac{d}{dt} @@ -469,14 +525,17 @@ Die Ableitung der Identität $AA^*=I$ führt dann auf + \dot{\gamma}(0)^* \quad\Rightarrow\quad -\dot{\gamma}(0)&=-\dot{\gamma}(0)^*. -A&=-A^* -\end{align*} +\dot{\gamma}(0)=-\dot{\gamma}(0)^* +\quad\Rightarrow\quad +A=-A^* +\end{equation*} Die Lie-Algebra $\operatorname{u}(n)$ besteht daher aus den antihermiteschen Matrizen. +\index{u(n)@$\operatorname{u}(n)$}% Wir sollten noch verifizieren, dass der Kommutator zweier antihermiteschen Matrizen wieder anithermitesch ist: +\index{antihermitesch}% \begin{align*} [A,B]^* &= @@ -489,7 +548,7 @@ BA - AB -[B,A]. \end{align*} -Eine antihermitesche Matrix erfüllt $a_{ij}=-\overline{a}_{ji}$, +Eine antihermitesche Matrix erfüllt $a_{i\!j}=-\overline{a}_{ji}$, für die Diagonalelemente folgt daher $a_{ii} = -\overline{a}_{ii}$ oder $\overline{a}_{ii}=-a_{ii}$. Der Realteil von $a_{ii}$ ist @@ -510,6 +569,7 @@ imaginär. \subsection{Die Lie-Algebra von $\operatorname{SU}(2)$} Die Lie-Algebra $\operatorname{su}(n)$ besteht aus den spurlosen antihermiteschen Matrizen. +\index{su(n)@$\operatorname{su}(n)$}% Sie erfüllen daher die folgenden Bedingungen: \[ A=\begin{pmatrix}a&b\\c&d\end{pmatrix} @@ -557,6 +617,7 @@ iu\underbrace{\begin{pmatrix}0&-i\\i&0\end{pmatrix}}_{\displaystyle=\sigma_2} is\underbrace{\begin{pmatrix}1&0\\0&-1\end{pmatrix}}_{\displaystyle=\sigma_3} \end{align*} Diese Matrizen heissen die {\em Pauli-Matrizen}, sie haben die Kommutatoren +\index{Pauli-Matriizen}% \begin{align*} [\sigma_1,\sigma_2] &= @@ -623,7 +684,7 @@ Die Matrizen $-\frac12i\sigma_j$ haben die Kommutatorprodukte = -{\textstyle\frac14}\cdot 2i\sigma_2 = --{\textstyle\frac12}i\sigma_2 +-{\textstyle\frac12}i\sigma_2. \end{align*} Die lineare Abbildung, die \begin{align*} @@ -631,7 +692,7 @@ Die lineare Abbildung, die \omega_{31}&\mapsto -{\textstyle\frac12}i\sigma_2\\ \omega_{12}&\mapsto -{\textstyle\frac12}i\sigma_3 \end{align*} -abbildet ist daher ein Isomorphismus der Lie-Algebra $\operatorname{so}(3)$ +abbildet, ist daher ein Isomorphismus der Lie-Algebra $\operatorname{so}(3)$ auf die Lie-Algebra $\operatorname{su}(2)$. Die Lie-Gruppen $\operatorname{SO}(3)$ und $\operatorname{SU}(2)$ haben also die gleiche Lie-Algebra. diff --git a/buch/chapters/60-gruppen/lie-gruppen.tex b/buch/chapters/60-gruppen/lie-gruppen.tex index e92c254..94df38e 100644 --- a/buch/chapters/60-gruppen/lie-gruppen.tex +++ b/buch/chapters/60-gruppen/lie-gruppen.tex @@ -16,11 +16,13 @@ Die Gruppe \] besteht aus den Matrizen, deren Determinante nicht $0$ ist. Da die Menge der Matrizen mit $\det A=0$ eine abgeschlossene Menge -in $M_n(\mathbb{R}) \simeq \mathbb{R}^{n^2}$ ist, ist +in $M_n(\mathbb{R}) \cong \mathbb{R}^{n^2}$ ist, ist $\operatorname{GL}_n(\mathbb{R})$ eine offene Teilmenge in $\mathbb{R}^{n^2}$, sie besitzt also automatisch die Struktur einer $n^2$-Mannigfaltigkeit. -Dies gilt jedoch auch für alle anderen Matrizengruppen, die in diesem -Abschnitt genauer untersucht werden sollen. +Doch auch alle anderen Matrizengruppen, +die in diesem Abschnitt genauer untersucht werden sollen, +stellens ich als Untermannigfaltigkeiten von +$\operatorname{GL}_n(\mathbb{R})$ heraus. \subsection{Mannigfaltigkeitsstruktur der Matrizengruppen \label{buch:subsection:mannigfaltigkeitsstruktur-der-matrizengruppen}} @@ -74,8 +76,9 @@ Die Abbildung $l_{g_1^{-1}g_2}$ ist aber nur die Multiplikation mit einer Matrix, also eine lineare Abbildung, so dass der Kartenwechsel nichts anderes ist als die Darstellung der Matrix der Linksmultiplikation $l_{g_1^{-1}g_2}$ im Koordinatensystem der Karte $U_e$ ist. -Differenzierbarkeit der Kartenwechsel ist damit sichergestellt, -die Matrizengruppen sind automatisch differenzierbare Mannigfaltigkeiten. +Differenzierbarkeit der Kartenwechsel ist damit sichergestellt. +Somit sind +die Matrizengruppen automatisch differenzierbare Mannigfaltigkeiten. Die Konstruktion aller Karten aus einer einzigen Karte für eine Umgebung des neutralen Elements zeigt auch, dass es für die Matrizengruppen @@ -115,7 +118,7 @@ enthalten. Diffferenzierbare Kurven $\gamma(t)$ in $\operatorname{GL}_n(\mathbb{R})$ haben daher in jedem Punkt Tangentialvektoren, die als Matrizen in $M_n(\mathbb{R})$ betrachtet werden können. -Wenn $\gamma(t)$ die Matrixelemente $\gamma_{ij}(t)$ hat, dann ist der +Wenn $\gamma(t)$ die Matrixelemente $\gamma_{i\!j}(t)$ hat, dann ist der Tangentialvektor im Punkt $\gamma(t)$ durch \[ \frac{d}{dt} @@ -152,7 +155,8 @@ Eine solche Kurve muss die Differentialgleichung erfüllen, wobei $A\in M_n(\mathbb{R})$ der gegebene Tangentialvektor in $e=I$ ist. -Die Matrixexponentialfunktion +Die {\em Matrixexponentialfunktion} +\index{Matrixexponentialfunktion}% \[ e^{At} = @@ -183,49 +187,53 @@ beschrieben werden kann. $\operatorname{SO}(2)\subset \operatorname{GL}_2(\mathbb{R})$} Drehungen der Ebene können in einer orthonormierten Basis durch Matrizen der Form -\[ -D_{\alpha} +\begin{equation} +R_{\alpha} = \begin{pmatrix} \cos\alpha&-\sin\alpha\\ \sin\alpha& \cos\alpha \end{pmatrix} -\] +\label{buch:lie:eqn:ralphadefinition} +\end{equation} dargestellt werden. Wir bezeichnen die Menge der Drehmatrizen in der Ebene mit $\operatorname{SO}(2)\subset\operatorname{GL}_2(\mathbb{R})$. Die Abbildung \[ -D_{\bullet} +R_{\bullet} \colon \mathbb{R}\to \operatorname{SO}(2) : -\alpha \mapsto D_{\alpha} +\alpha \mapsto R_{\alpha} \] hat die Eigenschaften -\begin{align*} -D_{\alpha+\beta}&= D_{\alpha}D_{\beta} +\begin{equation} +\begin{aligned} +R_{\alpha+\beta}&= R_{\alpha}R_{\beta} \\ -D_0&=I +R_0&=I \\ -D_{2k\pi}&=I\qquad \forall k\in\mathbb{Z}. -\end{align*} -Daraus folgt zum Beispiel, dass $D_{\bullet}$ eine $2\pi$-periodische +R_{2k\pi}&=I\qquad \forall k\in\mathbb{Z}. +\end{aligned} +\label{buch:lie:so2matrizen} +\end{equation} +Daraus folgt zum Beispiel, dass $R_{\bullet}$ eine $2\pi$-periodische Funktion ist. -$D_{\bullet}$ bildet die Menge der Winkel $[0,2\pi)$ bijektiv auf +$R_{\bullet}$ bildet die Menge der Winkel $[0,2\pi)$ bijektiv auf die Menge der Drehmatrizen in der Ebene ab. Für jedes Intervall $(a,b)\subset\mathbb{R}$ mit Länge -$b-a < 2\pi$ ist die Abbildung $\alpha\mapsto D_{\alpha}$ umkehrbar, +$b-a < 2\pi$ ist die Abbildung $\alpha\mapsto R_{\alpha}$ umkehrbar, die Umkehrung kann als Karte verwendet werden. Zwei verschiedene Karten $\alpha_1\colon U_1\to\mathbb{R}$ und $\alpha_2\colon U_2\to\mathbb{R}$ bilden die Elemente $g\in U_1\cap U_2$ in Winkel $\alpha_1(g)$ und $\alpha_2(g)$ ab, für die -$D_{\alpha_1(g)}=D_{\alpha_2(g)}$ gilt. +$R_{\alpha_1(g)}=R_{\alpha_2(g)}$ gilt. Dies ist gleichbedeutend damit, dass $\alpha_1(g)=\alpha_2(g)+2\pi k$ mit $k\in \mathbb{Z}$. In einem Intervall in $U_1\cap U_2$ muss $k$ konstant sein. -Die Kartenwechselabblidung ist also nur die Addition eines Vielfachen +Die Kartenwechselabbildung ist also nur die Addition eines Vielfachen von $2\pi$, mit der identischen Abbildung als Ableitung. Diese Karten führen also auf besonders einfache Kartenwechselabbildungen. @@ -239,22 +247,27 @@ Die Zahlen der Form $e^{i\alpha}$ haben den Betrag $1$ und die Abbildung f\colon \mathbb{R}\to \mathbb{C}:\alpha \mapsto e^{i\alpha} \] hat die Eigenschaften -\begin{align*} +\begin{equation} +\begin{aligned} f(\alpha+\beta) &= f(\alpha)f(\beta) \\ f(0)&=1 \\ f(2\pi k)&=1\qquad\forall k\in\mathbb{Z}, -\end{align*} -die zu den Eigenschaften der Abbildung $\alpha\mapsto D_{\alpha}$ +\end{aligned} +\label{buch:lie:so2komplex} +\end{equation} +die zu den Eigenschaften +\eqref{buch:lie:so2matrizen} der Abbildung $\alpha\mapsto R_{\alpha}$ analog sind. Jede komplexe Zahl $z$ vom Betrag $1$ kann geschrieben werden in der Form -$z=e^{i\alpha}$, die Abbildung $f$ ist also eine Parametrisierung des +$z=e^{i\alpha}$. +Die Abbildung $f$ ist also eine Parametrisierung des Einheitskreises in der Ebene. Wir bezeichen $S^1=\{z\in\mathbb{C}\;|\; |z|=1\}$ die komplexen Zahlen vom Betrag $1$. -$S^1$ ist eine Gruppe bezüglich der Multiplikation, da für jede Zahl +$S^1$ ist eine Gruppe bezüglich der Multiplikation, da für alle Zahlen $z,w\in S^1$ gilt $|z^{-1}|=1$ und $|zw|=1$ und damit $z^{-1}\in S^1$ und $zw\in S^1$. @@ -266,32 +279,32 @@ Damit kann man jetzt die Abbildung \colon S^1\to \operatorname{SO}(2) : -z\mapsto D_{\alpha(z)} +z\mapsto R_{\alpha(z)} \] konstruieren. -Da $D_{\alpha}$ $2\pi$-periodisch ist, geben um Vielfache +Da $R_{\alpha}$ $2\pi$-periodisch ist, geben um Vielfache von $2\pi$ verschiedene Wahlen von $\alpha(z)$ die gleiche -Matrix $D_{\alpha(z)}$, die Abbildung $\varphi$ ist daher +Matrix $R_{\alpha(z)}$, die Abbildung $\varphi$ ist daher wohldefiniert. $\varphi$ erfüllt ausserdem die Bedingungen \begin{align*} \varphi(z_1z_2) &= -D_{\alpha(z_1z_2)} +R_{\alpha(z_1z_2)} = -D_{\alpha(z_1)+\alpha(z_2)} +R_{\alpha(z_1)+\alpha(z_2)} = -D_{\alpha(z_1)}D_{\alpha(z_2)} +R_{\alpha(z_1)}R_{\alpha(z_2)} = -\varphi(z_1)\varphi(z_2) +\varphi(z_1)\varphi(z_2), \\ \varphi(1) &= -D_{\alpha(1)} +R_{\alpha(1)} = -D_0 +R_0 = -I +I. \end{align*} Die Abbildung $\varphi$ ist ein Homomorphismus der Gruppe $S^1$ in die Gruppe $\operatorname{SO}(2)$. @@ -301,7 +314,7 @@ in der komplexen Ebene identifiziert werden. \subsubsection{Tangentialvektoren von $\operatorname{SO}(2)$} Da die Gruppe $\operatorname{SO}(2)$ eine eindimensionale Gruppe ist, kann jede Kurve $\gamma(t)$ durch den Drehwinkel $\alpha(t)$ -mit $\gamma(t) = D_{\alpha(t)}$ beschrieben werden. +mit $\gamma(t) = R_{\alpha(t)}$ beschrieben werden. Die Ableitung in $M_2(\mathbb{R})$ ist \begin{align*} \frac{d}{dt} \gamma(t) @@ -334,24 +347,27 @@ Die Ableitung in $M_2(\mathbb{R})$ ist \cdot \dot{\alpha}(t) = -D_{\alpha(t)}J\cdot\dot{\alpha}(t). +R_{\alpha(t)}J\cdot\dot{\alpha}(t). \end{align*} -Alle Tangentialvektoren von $\operatorname{SO}(2)$ im Punkt $D_\alpha$ -entstehen aus $J$ durch Drehung mit der Matrix $D_\alpha$ und Skalierung -mit $\dot{\alpha}(t)$. +Alle Tangentialvektoren von $\operatorname{SO}(2)$ im Punkt $R_\alpha$ +entstehen aus $J$ durch Drehung mit der Matrix $R_\alpha$ und Skalierung +mit der Winkelgeschwindigkeit $\dot{\alpha}(t)$. +\index{Winkelgeschwindigkeit}% % % Isometrien von R^n % \subsection{Isometrien von $\mathbb{R}^n$ \label{buch:gruppen:isometrien}} +Isometrien von $\mathbb{R}^n$ führen automatisch auf eine interessante +Lie-Gruppe. \subsubsection{Skalarprodukt} Lineare Abbildungen des Raumes $\mathbb{R}^n$ können durch $n\times n$-Matrizen beschrieben werden. Die Matrizen, die das Standardskalarprodukt $\mathbb{R}^n$ erhalten, bilden eine Gruppe, die in diesem Abschnitt genauer untersucht werden soll. -Eine Matrix $A\in M_{n}(\mathbb{R})$ ändert das Skalarprodukt, wenn +Eine Matrix $A\in M_{n}(\mathbb{R})$ ändert das Skalarprodukt nicht, wenn für jedes beliebige Paar $x,y$ von Vektoren gilt $\langle Ax,Ay\rangle = \langle x,y\rangle$. Das Standardskalarprodukt kann mit dem Matrixprodukt ausgedrückt werden: @@ -372,17 +388,20 @@ Mit dem Skalarprodukt kann man auch die Matrixelemente einer Matrix einer Abbildung $f$ in der Standardbasis bestimmen. Das Skalarprodukt $\langle e_i, v\rangle$ ist die Länge der Projektion des Vektors $v$ auf die Richtung $e_i$. -Die Komponenten von $Ae_j$ sind daher $a_{ij}=\langle e_i,f(e_j)\rangle$. -Die Matrix $A$ der Abbildung $f$ hat also die Matrixelemente -$a_{ij}=e_i^tAe_j$. +Die Komponenten von $Ae_j$ sind daher $a_{i\!j}=\langle e_i,f(e_j)\rangle$. +Die Matrix $A$ der Abbildung $f$ hat folglich die Matrixelemente +$a_{i\!j}=e_i^tAe_j$. \subsubsection{Die orthogonale Gruppe $\operatorname{O}(n)$} Die Matrixelemente von $A^tA$ sind -$\langle A^tAe_i, e_j\rangle =\langle e_i,e_j\rangle = \delta_{ij}$ -sind diejenigen der Einheitsmatrix, -die Matrix $A$ erfüllt $AA^t=I$ oder $A^{-1}=A^t$. +$\langle A^tAe_i, e_j\rangle =\langle e_i,e_j\rangle = \delta_{i\!j}$ +also die der Einheitsmatrix. +Die Matrix $A$ erfüllt $AA^t=I$ oder $A^{-1}=A^t$. Dies sind die {\em orthogonalen} Matrizen. -Die Menge $\operatorname{O}(n)$ der isometrischen Abbildungen besteht +\index{orthogonale Matrix}% +Die Menge $\operatorname{O}(n)$ der isometrischen Abbildungen +\index{O(n)@$\operatorname{O}(n)$}% +von $\mathbb{R}^n$ besteht daher aus den Matrizen \[ \operatorname{O}(n) @@ -401,7 +420,7 @@ n^2 - \frac{n(n+1)}{2} = \frac{n(n-1)}2. \] -Im Spezialfall $n=2$ ist die Gruppe $O(2)$ eindimensional. +Im Spezialfall $n=2$ ist die Gruppe $\operatorname{O}(2)$ eindimensional. \subsubsection{Tangentialvektoren} Die orthogonalen Matrizen bilden eine abgeschlossene Untermannigfaltigkeit @@ -440,16 +459,17 @@ A^t&=-A \] Die Tangentialvektoren von $\operatorname{O}(n)$ sind also genau die antisymmetrischen Matrizen. +\index{antisymmetrisch}% Für $n=2$ sind alle antisymmetrischen Matrizen Vielfache der Matrix $J$, wie in Abschnitt~\ref{buch:gruppen:drehungen2d} gezeigt wurde. -Für jedes Paar $i<j$ ist die Matrix $A_{ij}$ mit den Matrixelementen -$(A_{ij})_{ij}=-1$ und $(A_{ij})_{ji}=1$ +Für jedes Paar $i<j$ ist die Matrix $A_{i\!j}$ mit den Matrixelementen +$(A_{i\!j})_{i\!j}=-1$ und $(A_{i\!j})_{ji}=1$ antisymmetrisch. Für $n=2$ ist $A_{12}=J$. -Die $n(n-1)/2$ Matrizen $A_{ij}$ bilden eine Basis des +Die $n(n-1)/2$ Matrizen $A_{i\!j}$ bilden eine Basis des $n(n-1)/2$-dimensionale Tangentialraumes von $\operatorname{O}(n)$. Tangentialvektoren in einem anderen Punkt $g\in\operatorname{O}(n)$ @@ -464,6 +484,7 @@ Wegen $\det (AA^t)=\det A\det A^t = (\det A)^2=1$ kann die Determinante einer orthogonalen Matrix nur $\pm 1$ sein. Orientierungserhaltende Isometrien haben Determinante $1$. +\begin{definition} Die Gruppe \[ \operatorname{SO}(n) @@ -471,7 +492,13 @@ Die Gruppe \{A\in\operatorname{O}(n)\;|\; \det A=1\} \] heisst die {\em spezielle orthogonale Gruppe}. -Die Dimension der Gruppe $\operatorname{O}(n)$ ist $n(n-1)/2$. +\index{spezielle orthogonale Gruppe}% +\index{orthogonale Gruppe, speziell}% +\index{Gruppe, spezielle orthogonale}% +\index{SO(n)@$\operatorname{SO}(n)$}% +\end{definition} + +%Die Dimension der Gruppe $\operatorname{SO}(n)$ ist $n(n-1)/2$. \subsubsection{Die Gruppe $\operatorname{SO}(3)$} Die Gruppe $\operatorname{SO}(3)$ der Drehungen des dreidimensionalen @@ -485,7 +512,7 @@ Der Drehwinkel ist der dritte Parameter. Drehungen mit kleinen Drehwinkeln können zusammengesetzt werden aus den Matrizen \begin{align*} -D_{x,\alpha} +R_{x,\alpha} &= \begin{pmatrix} 1&0&0\\ @@ -493,7 +520,7 @@ D_{x,\alpha} 0&\sin\alpha& \cos\alpha \end{pmatrix}, & -D_{y,\beta} +R_{y,\beta} &= \begin{pmatrix} \cos\beta&0&\sin\beta\\ @@ -501,7 +528,7 @@ D_{y,\beta} -\sin\beta&0&\cos\beta \end{pmatrix}, & -D_{z,\gamma} +R_{z,\gamma} &= \begin{pmatrix} \cos\gamma&-\sin\gamma&0\\ @@ -524,16 +551,73 @@ Auch die Winkel $\alpha$, $\beta$ und $\gamma$ können als die drei Koordinaten der Mannigkfaltigkeit $\operatorname{SO}(3)$ angesehen werden. +\begin{figure} +\centering +\includegraphics{chapters/60-gruppen/images/rodriguez.pdf} +\caption{Herleitung der Rodrigues-Formel~\eqref{buch:lie:eqn:rodrigues} +für die Beschreibung einer +Drehung mit Drehachse $\vec{k}$. +\label{buch:lie:fig:rodrigues}} +\end{figure} +Die Drehung des Vektors $\vec{x}$ um die Achse mit Richtung $\vec{k}$, +$|\vec{k}|=1$, kann man mit dem Vektorprodukt und dem Skalarprodukt +beschreiben. +Die Vektoren $\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}$, $-\vec{x}\times\vec{k}$ +und $\vec{k}$ bilden ein Rechtssystem im Punkt $\vec{x}$, dessen zweite +Achse tangential an die Bahn von $\vec{x}$ unter der Drehung ist. + +Die Komponente $(\vec{k}\cdot\vec{x})\vec{k}$ parallel zu $\vec{k}$ +ändert sich bei der Drehung nicht. +In der Ebene mit der orthogonalen Basis aus den Vektoren +$\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}$ und $-\vec{x}\times\vec{k}$ +kann man die Drehung $R_\alpha$ um den Winkel $\alpha$ mit den +trigonometrischen Funktionen beschreiben +(siehe Abbildung~\ref{buch:lie:fig:rodrigues}): +\begin{align} +\vec{x} +\mapsto +R_\alpha\vec{x} +&= +(\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}) +\cos\alpha +- +\vec{x}\times\vec{k} +\sin\alpha ++ +(\vec{k}\cdot\vec{x})\vec{k} +\notag +\\ +&= +\vec{x}\cos\alpha ++ +(1-\cos\alpha)(\vec{x}\cdot\vec{k})\vec{k} ++ +\vec{k}\times\vec{x}\sin\alpha. +\label{buch:lie:eqn:rodrigues} +\end{align} +Dies ist bekannt als die {\em Formel von Rodrigues} +\index{Formel von Rodrigues}% +\index{Rodrigues-Formel}% +Wir halten noch fest, dass die Ableitung an der Stelle $\alpha=0$ +der Tangentialvektor +\begin{equation} +\frac{d}{d\alpha}R_\alpha\vec{x}\,\bigg|_{\alpha=0} += +\vec{k}\times\vec{x} +\label{buch:lie:eqn:so3tangentialvektor} +\end{equation} +ist. + % % Spezielle lineare Gruppe % \subsection{Volumenerhaltende Abbildungen und die Gruppe $\operatorname{SL}_n(\mathbb{R})$ \label{buch:gruppen:sl}} -Die Elemente der Gruppe $SO(n)$ erhalten Längen, Winkel und die +Die Elemente der Gruppe $\operatorname{SO}(n)$ erhalten Längen, Winkel und die Orientierung, also auch das Volumen. Es gibt aber volumenerhaltende Abbildungen, die Längen oder Winkel -nicht notwendigerweise erhalten. +nicht notwendigerweise erhalten, zum Beispiel Scherungen. Matrizen $A\in M_n(\mathbb{R})$, die das Volumen erhalten, haben die Determinante $\det A=1$. Wegen $\det(AB)=\det A\det B$ ist das Produkt zweier Matrizen mit @@ -541,6 +625,7 @@ Determinante $1$ wieder eine solche, sie bilden daher eine Gruppe. \begin{definition} Die volumenerhaltenden Abbildungen bilden die Gruppe +\index{volumenerhaltend}% \[ \operatorname{SL}_n(\mathbb{R}) = @@ -551,6 +636,9 @@ A\in M_n(\mathbb{R}) \} \] sie heisst die {\em spezielle lineare Gruppe}. +\index{spezielle lineare Gruppe}% +\index{Gruppe, spezielle lineare}% +\index{SLn(R)@$\operatorname{SL}_n(\mathbb{R})$}% \end{definition} Wir wollen jetzt die Tangentialvektoren von $\operatorname{SL}_n(\mathbb{R})$ @@ -576,6 +664,10 @@ c(t)&d(t) \frac{d}{dt} \det A(t)\bigg|_{t=0} &= +\frac{d}{dt}\bigl(a(t)d(t)-b(t)c(t)\bigr)\bigg|_{t=0} +\\ +&&&& +&= \dot{a}(0) d(0)+a(0)\dot{d}(0) - \dot{b}(0) c(0)-b(0)\dot{c}(0) @@ -592,7 +684,7 @@ Dies gilt nicht nur im Falle $n=2$, sondern ganz allgemein für beliebige $n\times n$-Matrizen. \begin{satz} -Ist $A(t)$ eine differenzierbare Kurve in $\operatorname{SL}_n(\mathbb{B})$ +Ist $A(t)$ eine differenzierbare Kurve in $\operatorname{SL}_n(\mathbb{R})$ mit $A(0)=I$, dann ist $\operatorname{Spur}\dot{A}(0)=0$. \end{satz} @@ -626,8 +718,8 @@ jenes für $i=1$, somit ist die Ableitung von $\det A(t)$ \frac{d}{dt}\det A_{11}(t). \label{buch:gruppen:eqn:detspur} \end{equation} -Die Beziehung \eqref{buch:gruppen:eqn:detspur} kann für einen Beweis mit -vollständiger Induktion verwendet werden. +Die Beziehung \eqref{buch:gruppen:eqn:detspur} kann wie folgt +für einen Beweis mit vollständiger Induktion verwendet werden. Die Induktionsverankerung für $n=1$ besagt, dass $\det A(t)=a_{11}(t)$ genau dann konstant $=1$ ist, wenn $\dot{a}_{11}(0)=\operatorname{Spur}A(0)$ @@ -668,6 +760,19 @@ A=\begin{pmatrix}a&b\\c&d\end{pmatrix} A=\begin{pmatrix}a&b\\c&-a\end{pmatrix}. \] Der Tangentialraum ist also dreidimensional. +\begin{figure} +\centering +\includegraphics{chapters/60-gruppen/images/sl2.pdf} +\caption{Tangentialvektoren und die davon erzeugen Einparameteruntergruppen +für die Lie-Gruppe $\operatorname{SL}_2(\mathbb{R})$ der flächenerhaltenden +linearen Abbildungen von $\mathbb{R}^2$. +In allen drei Fällen wird das blaue Quadrat mit den Ecken in den +Standardbasisvektoren von einer Matrix der Einparameteruntergruppe zu +zum roten Viereck verzerrt, der Flächeninhalt bleibt aber erhalten. +In den beiden Fällen $B$ und $C$ stellen die grünen Kurven die Bahnen +der Bilder der Standardbasisvektoren dar. +\label{buch:gruppen:fig:sl2}} +\end{figure}% Als Basis könnte man die folgenden Vektoren verwenden: \begin{align*} A @@ -714,8 +819,10 @@ I\cosh t + C \sinh t \end{align*} wobei in der Auswertung der Potenzreihe für $e^{Ct}$ verwendet wurde, dass $C^2=I$. +Die von $A$, $B$ und $C$ erzeugten Einparameteruntergruppen sind in +Abbildung~\ref{buch:gruppen:fig:sl2} visualisiert. -Die Matrizen $e^{At}$ Streckungen der einen Koordinatenachse und +Die Matrizen $e^{At}$ sind Streckungen der einen Koordinatenachse und Stauchungen der anderen derart, dass das Volumen erhalten bleibt. Die Matrizen $e^{Bt}$ sind Drehmatrizen, die Längen und Winkel und damit erst recht den Flächeninhalt erhalten. @@ -764,25 +871,26 @@ Dies ist die gegenüber $e^{At}$ um $45^\circ$ verdrehte Situation, auch diese Matrizen sind flächenerhaltend. \begin{figure} \centering -\includegraphics{chapters/60-gruppen/images/sl2.pdf} -\caption{Tangentialvektoren und die davon erzeugen Einparameteruntergruppen -für die Lie-Gruppe $\operatorname{SL}_2(\mathbb{R})$ der flächenerhaltenden -linearen Abbildungen von $\mathbb{R}^2$. -In allen drei Fällen wird ein blauer Rhombus mit den Ecken in den -Standardbasisvektoren von einer Matrix der Einparameteruntergruppe zu -zum roten Viereck verzerrt, der Flächeninhalt bleibt aber erhalten. -In den beiden Fällen $B$ und $C$ stellen die grünen Kurven die Bahnen -der Bilder der Standardbasisvektoren dar. -\label{buch:gruppen:fig:sl2}} -\end{figure}% -\begin{figure} -\centering \includegraphics{chapters/60-gruppen/images/scherungen.pdf} -\caption{Weitere Matrizen mit Spur $0$ und ihre Wirkung -Die inken beiden Beispiele $M$ und $N$ sind nilpotente Matrizen, -die zugehörigen Einparameter-Untergruppen beschreiben Schwerungen. +\caption{Weitere Matrizen mit Spur $0$ und ihre Wirkung. +Die linken beiden Beispiele $M$ und $N$ sind nilpotente Matrizen, +die zugehörigen Einparameteruntergruppen beschreiben Scherungen. \label{buch:gruppen:fig:scherungen}} \end{figure} + +Die Gruppe $\operatorname{SL}_2(\mathbb{R})$ hat aber auch die +Tangentialvektoren +\begin{align*} +M&=\begin{pmatrix}0&1\\0&0\end{pmatrix}=\frac12(B+C) +&&\text{und}& +N&=\begin{pmatrix}0&0\\1&0\end{pmatrix}=\frac12(-B+C), +\intertext{die die Scherungen} +e^{Mt}&= \begin{pmatrix}1&0\\t&0\end{pmatrix} +&& +e^{NT}&=\begin{pmatrix}1&t\\0&1\end{pmatrix} +\end{align*} +als Einparameteruntergruppen haben. +Diese sind in Abbildung~\ref{buch:gruppen:fig:scherungen} dargestellt. \end{beispiel} % @@ -802,9 +910,20 @@ a,b,c,d\in\mathbb{C},\det(A)=1, AA^*=I \right\} \] heisst die {\em spezielle unitäre Gruppe}. +\index{spezielle unitäre Gruppe}% +\index{unitäre Gruppe, speziell}% +\index{Gruppe, speziell unitäre}% +\index{SU(n)@$\operatorname{SU}(n)$}% Wegen $\det(AB)=\det(A)\det(B)=1$ und $(AB)^*AB=B^*A^*AB=B^*B=I$ ist $\operatorname{SU}(2)$ eine Untergruppe von $\operatorname{GL}_2(\mathbb{C})$. -Die Bedingungen $\det A=1$ und $AA^*=I$ schränken die möglichen Werte +Die Bedingungen +\begin{equation} +\det A=1 +\qquad\text{und}\qquad +AA^*=I +\label{buch:lie:eqn:su2bed} +\end{equation} +schränken die möglichen Werte von $a$ und $b$ weiter ein. Aus \[ @@ -815,7 +934,7 @@ A^* \overline{b}&\overline{d} \end{pmatrix} \] -und den Bedingungen führen die Gleichungen +und den Bedingungen~\eqref{buch:lie:eqn:su2bed} folgen die Gleichungen \[ \begin{aligned} a\overline{a}+b\overline{b}&=1 @@ -831,7 +950,7 @@ c\overline{a}+d\overline{b}&=0 \\ c\overline{c}+d\overline{d}&=1&&\Rightarrow&|c|^2+|d|^2&=1 \\ -ad-bc&=1 +ad-bc&=1. \end{aligned} \] Aus der zweiten Gleichung kann man ableiten, dass es eine Zahl $t\in\mathbb{C}$ @@ -846,7 +965,7 @@ t(|a|^2+|b|^2) = t, \] -also muss die Matrix $A$ die Form haben +also muss die Matrix $A$ die Form \[ A = @@ -854,10 +973,11 @@ A a&b\\ -\overline{b}&\overline{a} \end{pmatrix} -\qquad\text{mit}\quad |a|^2+|b|^2=1. +\qquad\text{mit}\quad |a|^2+|b|^2=1 \] +haben. Schreibt man $a=a_1+ia_2$ und $b=b_1+ib_2$ mit rellen $a_i$ und $b_i$, -dann besteht $SU(2)$ aus den Matrizen der Form +dann besteht $\operatorname{SU}(2)$ aus den Matrizen der Form \[ A= \begin{pmatrix} diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex index aee3b41..252fdca 100644 --- a/buch/chapters/60-gruppen/symmetrien.tex +++ b/buch/chapters/60-gruppen/symmetrien.tex @@ -15,7 +15,7 @@ bedeutet. Spiegelsymmetrische Objekte zeichnen sich zum Beispiel dadurch aus, dass Messungen von Strecken die gleichen Werte ergeben wie die Messungen der entsprechenden gespiegelten Strecken (siehe auch -Abbildung~\ref{buch:lie:bild:castlehoward}, was die Herkunft des +Abbildung~\ref{buch:lie:bild:castlehoward}), was die Herkunft des Begriffs verständlich macht. \begin{figure} \centering @@ -31,8 +31,8 @@ In der Physik wird dem Begriff der Symmetrie daher auch eine erweiterte Bedeutung gegeben. Jede Transformation eines Systems, welche bestimmte Grössen nicht verändert, wird als Symmetrie bezeichnet. -Die Gesetze der Physik sind typischerweise unabhängig davon, wo man den -den Nullpunkt der Zeit oder das räumlichen Koordinatensystems ansetzt, +Die Gesetze der Physik sind typischerweise unabhängig davon, wo man +den Nullpunkt der Zeit oder des räumlichen Koordinatensystems ansetzt, eine Transformation des Zeitnullpunktes oder des Ursprungs des Koordinatensystems ändert daher die Bewegungsgleichungen nicht, sie ist eine Symmetrie des Systems. @@ -52,8 +52,8 @@ zusätzliche geometrische Struktur, man nennt sie eine differenzierbare Mannigfaltigkeit. Dieser Begriff wird im Abschnitt~\ref{buch:subsection:mannigfaltigkeit} eingeführt. -Es wird sich zum Beispiel zeigen, dass die Menge der Drehungen der -Ebene mit den Punkten eines Kreises parametrisieren lassen, +Es wird sich zum Beispiel zeigen, dass sich die Menge der Drehungen der +Ebene mit den Punkten eines Kreises parametrisieren lässt, die Lösungen der Gleichung $x^2+y^2=1$ sind. Eine Lie-Gruppe ist eine Gruppe, die gleichzeitig eine differenzierbare @@ -94,10 +94,10 @@ Die folgenden Beispiele sollen zeigen, wie solche Symmetriedefinitionen auf algebraische Bedingungen an die Matrixelemente führen. Zu jeder Abbildung $f\colon\mathbb{R}^n\to\mathbb{R}^n$, unter der -ein geometrisches Objekt in $\mathbb{R}^n$ symmetrisch ist, können wir +ein geometrisches Objekt in $\mathbb{R}^n$ unveränder bleibt, können wir sofort weitere Abbildungen angeben, die ebenfalls Symmetrien sind. Zum Beispiel sind die iterierten Abbildungen $f\circ f$, $f\circ f\circ f$ -u.~s.~w., die wir auch $f^n$ mit $n\in\mathbb{N}$ schreiben werden, +usw., die wir auch $f^n$ mit $n\in\mathbb{N}$ schreiben werden, ebenfalls Symmetrien. Wenn die Symmetrie auch umkehrbar ist, dann gilt dies sogar für alle $n\in\mathbb{Z}$. @@ -105,7 +105,9 @@ Wir erhalten so eine Abbildung $\varphi\colon \mathbb{Z}\to \operatorname{GL}_n(\mathbb{R}):n\mapsto f^n$ mit den Eigenschaften $\varphi(0)=f^0 = I$ und $\varphi(n+m)=f^{n+m}=f^n\circ f^m = \varphi(n)\circ\varphi(m)$. -$\varphi$ ist ein Homomorphismus der Gruppe $\mathbb{Z}$ in die Gruppe +$\varphi$ ist ein Homomorphismus (siehe +Definition~\ref{buch:gruppen:def:homomorphismus}) +der Gruppe $\mathbb{Z}$ in die Gruppe $\operatorname{GL}_n(\mathbb{R})$. Wir nennen dies eine {\em diskrete Symmetrie}. @@ -114,10 +116,10 @@ Wir nennen dies eine {\em diskrete Symmetrie}. Von besonderem Interesse sind kontinuierliche Symmetrien. Dies sind Abbildungen eines Systems, die von einem Parameter abhängen. -Zum Beispiel können wir Drehungen der Ebene $\mathbb{R}^2$ um den -Winkel $\alpha$ durch Matrizen +Zum Beispiel können Drehungen der Ebene $\mathbb{R}^2$ um den +Winkel $\alpha$ durch die Matrizen \[ -D_{\alpha} +R_{\alpha} = \begin{pmatrix} \cos\alpha&-\sin\alpha\\ @@ -126,18 +128,20 @@ D_{\alpha} \] beschrieben werden. Ein Kreis um den Nullpunkt bleibt unter jeder dieser Drehungen invariant. -Im Gegensatz dazu sind alle $3n$-Ecke mit Schwerpunkt $0$ nur invariant -unter der einen Drehung $D_{\frac{2\pi}3}$ invariant. -Die kleinste Menge, die einen vorgegebenen Punkt enthält und unter -allen Drehungen $D_\alpha$ invariant ist, ist immer ein Kreis um +Im Gegensatz dazu sind alle gleichseitigen Dreiecke mit Schwerpunkt $0$ +nur unter der einen Drehung $R_{\frac{2\pi}3}$ invariant. +Eine minimale Menge, die einen vorgegebenen Punkt enthält und unter +allen Drehungen $R_\alpha$ invariant ist, ist immer ein Kreis um den Nullpunkt. \begin{definition} +\label{buch:lie:def:einparameteruntergruppe} Ein Homomorphismus $\varphi\colon\mathbb{R}\to\operatorname{GL}_n(\mathbb{R})$ von der additiven Gruppe $\mathbb{R}$ in die allgemeine lineare Gruppe -heisst eine {\em Einparameter-Untergruppe} von +heisst eine {\em Einparameteruntergruppe} von $\operatorname{GL}_n(\mathbb{R})$. \end{definition} +\index{Einparameteruntergruppe} Die Abbildung \[ @@ -146,16 +150,18 @@ Die Abbildung \mathbb{R}\to\operatorname{GL}_n(\mathbb{R}) : \alpha \mapsto -D_{\alpha} +R_{\alpha} = \begin{pmatrix} \cos\alpha&-\sin\alpha\\ \sin\alpha& \cos\alpha \end{pmatrix} \] -ist also eine Einparameter-Untergruppe von $\operatorname{GL}_2(\mathbb{R})$. +ist also eine Einparameteruntergruppe von $\operatorname{GL}_2(\mathbb{R})$. \subsubsection{Der harmonische Oszillator} +\index{harmonischer Oszillator}% +\index{Oszillator}% \begin{figure} \centering \includegraphics{chapters/60-gruppen/images/phasenraum.pdf} @@ -165,17 +171,21 @@ im Phasenraum sind Ellipsen mit Halbachsenverhältnis $\omega^{-1}$. \label{chapter:gruppen:fig:phasenraum}} \end{figure} Eine Masse $m$ verbunden mit einer Feder mit der Federkonstanten $K$ +\index{Federkonstante}% schwingt um die Ruhelage $x=0$ entsprechend der Differentialgleichung \[ m\frac{d^2}{dt^2} x(t) = -Kx(t). \] Die Kreisfrequenz der Schwingung ist +\index{Kreisfrequenz}% +\index{Schwingung}% \[ \omega = \sqrt{\frac{K}{m}}. \] Das System kann als zweidimensionales System im Phasenraum mit den Koordinaten $x_1=x$ und $x_2=p=m\dot{x}$ beschrieben werden. Die zweidimensionale Differentialgleichung ist +\index{zweidimensionale Differentialgleichung}% \begin{equation} \left. \begin{aligned} @@ -230,7 +240,7 @@ p(t) \label{buch:gruppen:eqn:phi} \end{equation} schreiben. -Die Matrizen $\Phi_t$ bilden eine Einparameter-Untergruppe von +Die Matrizen $\Phi_t$ bilden eine Einparameteruntergruppe von $\operatorname{GL}_n(\mathbb{R})$, da \begin{align*} \Phi_s\Phi_t @@ -265,11 +275,13 @@ gilt. Die Lösungen der Differentialgleichung~\eqref{chapter:gruppen:eqn:phasenraumdgl} sind in Abbildung~\ref{chapter:gruppen:fig:phasenraum} +dargestellt. Die Matrizen $\Phi_t$ beschreiben eine kontinuierliche Symmetrie des Differentialgleichungssystems, welches den harmonischen Oszillator beschreibt. \subsubsection{Fluss einer Differentialgleichung} +\index{Fluss}% Die Abbildungen $\Phi_t$ von \eqref{buch:gruppen:eqn:phi} sind jeweils Matrizen in $\operatorname{GL}_n(\mathbb{R})$. Der Grund dafür ist, dass die @@ -333,9 +345,10 @@ Die Abbildung \[ \Phi\colon \mathbb{R}\times\mathbb{R}^n\to\mathbb{R}^n : -(t,x_0) \mapsto \Phi_t(x_0) = x(t,x_0) +(t,x_0) \mapsto \Phi_t(x_0) := x(t,x_0) \] heisst der {\em Fluss} der Differentialgleichung +\index{Fluss}% \eqref{buch:gruppen:eqn:dgl}, wenn für jedes $x_0\in\mathbb{R}^n$ die Kurve $t\mapsto \Phi_t(x_0)$ eine Lösung der Differentialgleichung ist mit Anfangsbedingung $x_0$. @@ -358,10 +371,10 @@ Das funktioniert auch, weil $f(t_0,x_0)$ selbst ein Vektor von $\mathbb{R}^n$ ist, in dem die Bahnkurve verläuft. Diese Idee funktioniert nicht mehr zum Beispiel für eine -Differentialgleichung auf einer Kugeloberfläche, weil alle Punkte +Differentialgleichung auf einer Kugel\-oberfläche, weil alle Punkte $x(t_0)+hf(t_0,x_0)$ für alle $h\ne 0$ nicht mehr auf der Kugeloberfläche liegen. -Physikalisch äussert sich das ein einer zusätzlichen Kraft, die nötig +Physikalisch äussert sich das in einer zusätzlichen Kraft, die nötig ist, die Bahn auf der Kugeloberfläche zu halten. Diese Kraft stellt zum Beispiel sicher, dass die Vektoren $f(t,x)$ für Punkte $x$ auf der Kugeloberfläche immer tangential an die Kugel sind. @@ -370,12 +383,13 @@ nicht mehr ein Objekt, welches als Teil der Kugeloberfläche definiert werden kann, er kann nur definiert werden, wenn man sich die Kugel als in einen höherdimensionalen Raum eingebettet vorstellen kann. -Um die Idee der Differentialgleichung auf einer beliebigen Fläche -konsistent zu machen ist daher notwendig, die Idee einer Tagentialrichtung +Um die Idee einer Differentialgleichung auf einer beliebigen Fläche +konsistent zu machen, ist daher notwendig, die Idee einer Tagentialrichtung auf eine Art zu definieren, die nicht von der Einbettung der Fläche in den $n$-dimensionalen Raum abhängig ist. Das in diesem Abschnitt entwickelte Konzept der {\em Mannigfaltigkeit} löst dieses Problem. +\index{Mannigfaltigkeit}% \subsubsection{Karten} Die Navigation auf der Erdoberfläche verwendet das Koordinatensystem @@ -385,6 +399,11 @@ den geographischen Polen befindet, denn deren Koordinaten sind nicht mehr eindeutig. Alle Punkte mit geographischer Breite $90^\circ$ und beliebiger geographischer Länge beschreiben den Nordpol. +\index{geographische Länge}% +\index{geographische Breite}% +\index{Nordpol}% +\index{Länge, geographisch}% +\index{Breite, geographisch}% Auch die Ableitung funktioniert dort nicht mehr. Bewegt man sich mit konstanter Geschwindigkeit über den Nordpol, springt die Ableitung der geographischen Breite von einem positiven @@ -412,6 +431,7 @@ verschiedenen Koordinatensystemen versehen werden kann. Ein Koordinatensystem ist eine umkehrbare Abbildung einer offenen Teilmenge $U\subset M$ in den Raum $\mathbb{R}^n$. Die Komponenten dieser Abbildung heissen die {\em Koordinaten}. +\index{Koordinaten}% \begin{figure} \centering @@ -429,12 +449,13 @@ entstehen soll. \end{figure} \begin{definition} -Eine Karte auf $M$ ist eine umkehrbare Abbildung -$\varphi\colon U\to \mathbb{R}^n$ (siehe auch -Abbildung~\ref{buch:gruppen:fig:karten}). -Ein differenzierbarer Atlas ist eine Familie von Karten $\varphi_\alpha$ +\index{Karte}% +Eine {\em Karte} auf $M$ ist eine umkehrbare Abbildung +$\varphi\colon U\to \mathbb{R}^n$ einer offenen Menge $U_\alpha\subset M$ +(siehe auch Abbildung~\ref{buch:gruppen:fig:karten}). +Ein {\em differenzierbarer Atlas} ist eine Familie von Karten $\varphi_\alpha$ derart, dass die Definitionsgebiete $U_\alpha$ die ganze Menge $M$ -überdecken, und dass die Kartenwechsel Abbildungen +überdecken, und dass die Kartenwechselabbildungen \[ \varphi_{\beta\alpha}=\varphi_\beta\circ\varphi_\alpha^{-1} \colon @@ -444,8 +465,9 @@ derart, dass die Definitionsgebiete $U_\alpha$ die ganze Menge $M$ \] als Abbildung von offenen Teilmengen von $\mathbb{R}^n$ differenzierbar ist. -Eine {$n$-dimensionale differenzierbare Mannigfaltigkeit} ist eine +Eine {\em $n$-dimensionale differenzierbare Mannigfaltigkeit} ist eine Menge $M$ mit einem differenzierbaren Atlas. +\index{Atlas}% \end{definition} Karten und Atlanten regeln also nur, wie sich verschiedene lokale @@ -569,7 +591,7 @@ konstruieren, der $S^n$ zu einer $n$-dimensionalen Mannigfaltigkeit macht. \subsubsection{Tangentialraum} Mit Hilfe einer Karte $\varphi_\alpha\colon U_\alpha\to\mathbb{R}^n$ kann das Geschehen in einer Mannigfaltigkeit in den vertrauten -$n$-dimensionalen Raum $\mathbb{B}^n$ transportiert werden. +$n$-dimensionalen Raum $\mathbb{R}^n$ transportiert werden. Eine Kurve $\gamma\colon \mathbb{R}\to M$, die so parametrisiert sein soll, dass $\gamma(t)\in U_\alpha$ für $t$ in einer Umgebung $I$ von $0$ ist, wird von der Karte in eine Kurve @@ -606,7 +628,8 @@ Aus = \varphi_{\beta\alpha}\circ\gamma_\alpha \] -folgt durch Ableitung nach dem Kurvenparameter $t$, dass +folgt durch Ableitung nach dem Kurvenparameter $t$ mit Hilfe der +Kettenregel, dass \[ \frac{d}{dt}\gamma_\beta(t) = @@ -624,7 +647,7 @@ $\varphi_{\beta\alpha}$ stellt also nur sicher, dass die Beschreibung eines Systemes mit Differentialgleichungen in verschiedenen Koordinatensystemen auf die gleichen Lösungskurven in der Mannigfaltigkeit führt. -Insbesondere ist die Verwendung von Karten ist also nur ein Werkzeug, +Insbesondere ist die Verwendung von Karten also nur ein Werkzeug, mit dem die Unmöglichkeit einer globalen Besschreibung einer Mannigfaltigkeit $M$ mit einem einzigen globalen Koordinatensystem ohne Singularitäten umgangen werden kann. @@ -658,9 +681,9 @@ Die Koordinatenumrechnung ist gegeben durch \dot{x}(t) = D\varphi_{31}(\gamma(t)) -\dot{y}(t) +\dot{y}(t). \] -wird für die spezielle Kurve $\gamma(t)=(\cos t,\sin t)$ wird dies zu +Für die spezielle Kurve $\gamma(t)=(\cos t,\sin t)$ wird dies zu \[ D\varphi_{31}(\gamma(t)) \cdot @@ -690,7 +713,7 @@ Darüber hinweg hilft auch die Tatsache nicht, dass die Kreislinie in den Vektorraum $\mathbb{R}^2$ eingebettet sind, wo sich Vektoren durch Translation miteinander vergleichen lassen. Ein nichtverschwindender Tangentialvektor im Punkt $(1,0)$ hat, -betrachtet als Vektor in $\mathbb{R}^2$ verschwindende $x$-Komponente, +betrachtet als Vektor in $\mathbb{R}^2$, verschwindende $x$-Komponente, für Tangentialvektoren im Inneren eines Quadranten ist dies nicht der Fall. @@ -701,18 +724,25 @@ Dies ist möglich, weil die Kreislinie eine kontinuierliche Symmetrie, nämlich die Drehung um den Winkel $t$ hat, die es erlaubt, den Punkt $(1,0)$ in den Punkt $(\cos t,\sin t)$ abzubilden. Erst diese Symmetrie ermöglicht den Vergleich. -Dieser Ansatz ist für alle Matrizen erfolgreich, wie wir später sehen werden. +Dieser Ansatz ist für alle Matrizengruppen erfolgreich, +wie wir später sehen werden. Ein weiterer Ansatz, Tangentialvektoren zu vergleichen, ist die Idee, einen sogenannten Zusammenhang zu definieren, eine Vorschrift, wie +\index{Zusammenhang}% +\index{Paralleltransport}% Tangentialvektoren infinitesimal entlang von Kurven in der Mannigfaltigkeit transportiert werden können. Auf einer sogenannten {\em Riemannschen Mannigfaltigkeit} ist zusätzlich zur Mannigfaltigkeitsstruktur die Längenmessung definiert. +\index{Riemannsche Mannigfaltigkeit}% +\index{Mannigfaltigkeit!Riemannsche}% Sie kann dazu verwendet werden, den Transport von Vektoren entlang einer Kurve so zu definieren, dass dabei Längen und Winkel erhalten bleiben. +\index{Längenmessung}% Dieser Ansatz ist die Basis der Theorie der Krümmung sogenannter Riemannscher Mannigfaltigkeiten. +\index{Krümmung}% %\subsection{Der Satz von Noether %\label{buch:subsection:noether}} diff --git a/buch/chapters/60-gruppen/uebungsaufgaben/6003.tex b/buch/chapters/60-gruppen/uebungsaufgaben/6003.tex new file mode 100644 index 0000000..663b1a0 --- /dev/null +++ b/buch/chapters/60-gruppen/uebungsaufgaben/6003.tex @@ -0,0 +1,134 @@ +Für die Lie-Algebra $\operatorname{sl}_2(\mathbb{R})$ wurde die Basis +\[ +A=\begin{pmatrix} 1&0\\0&-1 \end{pmatrix}, +\qquad +N=\begin{pmatrix} 0&1\\0&0\end{pmatrix}, +\qquad +N=\begin{pmatrix} 0&0\\1&0\end{pmatrix} +\] +gefunden. +Dies bedeutet, dass die Elemente +der Gruppe $\operatorname{SL}_2(\mathbb{R})$ nahe der Einheitsmatrix +als ein Produkt von Matrizen der Form +\[ +D=e^{At}=\begin{pmatrix}e^t&0\\0&e^{-1}\end{pmatrix}, +\quad +S=e^{Ns} = \begin{pmatrix}1&s\\0&1\end{pmatrix}, +\quad +T=e^{Mt} = \begin{pmatrix}1&0\\t&1\end{pmatrix} +\] +geschrieben werden können. +\begin{teilaufgaben} +\item +Finden Sie zur Drehung $R_\alpha\in\operatorname{SO}(2)$ +aus \eqref{buch:lie:eqn:ralphadefinition} eine solche Zerlegung +$R_\alpha=DST$. +\item +Schreiben Sie die Matrix +\[ +A=\begin{pmatrix} +\frac12&-\frac{\sqrt{3}}2\\ +\frac{\sqrt{3}}2&\frac12 +\end{pmatrix} +\] +als Produkt $A=DST$. +\end{teilaufgaben} + +\begin{loesung} +\begin{teilaufgaben} +\item +Zunächst schreiben wir etwas einfacher +\[ +D=\begin{pmatrix}c&0\\0&c^{-1}\end{pmatrix}. +\] +Dann multiplizeren wir +\begin{align*} +DST +&= +\begin{pmatrix}c&0\\0&c^{-1}\end{pmatrix} +\begin{pmatrix}1&s\\0&1\end{pmatrix} +\begin{pmatrix}1&0\\t&1\end{pmatrix} +\\ +&= +\begin{pmatrix}c&0\\0&c^{-1}\end{pmatrix} +\begin{pmatrix}1+st&s\\t&1\end{pmatrix} +\\ +&= +\begin{pmatrix} +(1+st)c&sc\\ +c^{-1}t&c^{-1} +\end{pmatrix}. +\end{align*} +Der Vergleich mit +\[ +R_\alpha += +\begin{pmatrix} +\cos\alpha&-\sin\alpha\\ +\sin\alpha& \cos\alpha +\end{pmatrix} += +\begin{pmatrix} +(1+st)c&sc\\ +c^{-1}t&c^{-1} +\end{pmatrix} +\] +erlaubt jetzt, die Parameter, $c$, $s$ und $t$ abzulesen. +Zunächst folgt aus dem Eintrag rechts unten, dass +\[ +c=\frac{1}{\cos\alpha} +\] +sein muss. +Aus dem Eintrag links unten in der Matrix folgt dann +\[ +c^{-1}t = t\cos\alpha = \sin\alpha +\quad\Rightarrow\quad +t=\frac{\sin\alpha}{\cos\alpha}=\tan\alpha. +\] +Der Eintrag rechts oben führt schliesslich auf die Gleichung +\[ +sc=\frac{s}{\cos\alpha}=-\sin\alpha +\quad\Rightarrow\quad +s=-\sin\alpha\cos\alpha +\] +für $s$. +Damit sind zwar die Parameter bestimmt, es ist aber noch nachzuprüfen, +dass sich damit auch der korrekte Eintrag oben links in der Matrix +ergibt. +Es ist +\[ +(1+st)c += +\frac{1-\sin\alpha\cos\alpha\tan\alpha}{\cos\alpha} += +\frac{1-\sin^2\alpha}{\cos\alpha} += +\frac{\cos^2\alpha}{\cos\alpha}=\cos\alpha, +\] +somit ist +\[ +c=\frac{1}{\cos\alpha},\; t=\tan\alpha,\; s=-\sin\alpha\cos\alpha=-\frac12\sin2\alpha +\] +tatsächlich die gesuchte Lösung. +\item +Die Matrix $A$ ist die Drehung $A=R_{60^\circ}$, daher können wir nach +a) folgern: +\begin{align*} +c&=\frac{1}{\cos 60^\circ}= 2\\ +s&=-\frac12\sin120^\circ =-\frac{\sqrt{3}}4\\ +t&=\tan 60^\circ = \sqrt{3}. +\end{align*} +Daher gilt +\[ +DST += +\begin{pmatrix}2&0\\0&\frac12\end{pmatrix} +\begin{pmatrix}1&-\frac{\sqrt{3}}4\\0&1\end{pmatrix} +\begin{pmatrix}1&0\\ \sqrt{3}&1\end{pmatrix} += +A, +\] +wie man mit einem Computeralgebraprogramm leicht nachprüfen kann. +\qedhere +\end{teilaufgaben} +\end{loesung} diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index a0f46da..918594d 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -6,16 +6,21 @@ \section{Beschreibung von Graphen mit Matrizen \label{buch:section:beschreibung-von-graphen-mit-matrizen}} \rhead{Beschreibung mit Matrizen} -Ein Graph ist eine Menge von Knoten, die untereinander mit Kanten -verbunden sind. -Graphen können zum Beispiel verwendet werden um Netzwerke zu beschreiben, -aber auch viele andere Datenstrukturen. -Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben -dann Beziehungen zwischen diesen Objekten. +Als universelles kombinatorisches Modell sind Graphen für eine +Vielzahl von Problemlösungen interessant. +Zum Beispiel zeigt Kapitel~\ref{chapter:munkres}, wie man +ein Zuordnungsproblem als Graphenproblem formulieren kann. +Die Lösung erfolgt dann allerdings zweckmässigerweise unter +Verwendung einer Matrix. +Ziel dieses Abschnitts ist, Graphen und ihre zugehörige Matrizen +zu definieren und erste Eigenschaften des Graphen mit algebraischen +Mitteln abzuleiten. +Die Präsentation ist allerdings nur ein erster Einstieg, tiefer +gehende Information kann in \cite{skript:brualdi} gefunden werden. \subsection{Definition von Graphen \label{subsection:definition-von-graphen}} -In der Einleitung zu diesem Abschnitt wurde bereits eine informelle +In der Einleitung wurde bereits eine informelle Beschreibung des Konzeptes eines Graphen gegeben. Um zu einer Beschreibung mit Hilfe von Matrizen zu kommen, wird eine exakte Definition benötigt. @@ -25,7 +30,7 @@ sind und sich in Unterschieden in der Definition der zugehörigen Matrix \subsubsection{Ungerichtete Graphen} Die Grundlage für alle Arten von Graphen ist eine Menge $V$ von {\em Knoten}, -auch {\em Vertices} genannt. +auch {\em Vertizes} genannt. \index{Knoten}% \index{Vertex}% Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten @@ -35,7 +40,7 @@ verbunden werden. Bei einen ungerichteten Graphen sind die beiden Endpunkte einer Kante gleichwertig, es gibt keine bevorzugte Reihenfolge oder Richtung der Kante. -Eine Kante wird daher vollständig spezifiziert, wenn wir die +Eine Kante ist daher vollständig spezifiziert, wenn wir die Menge der Endpunkte kennen. Dies führt auf die folgende Definition eines ungerichteten Graphen. @@ -48,14 +53,16 @@ und eine Menge $E$ von zweielementigen Teilmengen \[ E \subset \{\, \{a,b\}\subset V\,|\, a\ne b\}. \] -Die Elemente von $E$ heissen {\em Kanten} ({\em edges}). +Die Elemente von $E$ heissen {\em Kanten} (edges). \end{definition} Man beachte, dass es keine Kante gibt, die einen Knoten $a\in V$ mit sich selbst verbindet, da die zugehörige Menge $\{a,a\}=\{a\}$ nicht aus zwei verschiedenen Elementen besteht, wie die Definition~\ref{buch:def:ungerichteter-graph} dies verlangt. +Es gibt also keine Schleifen an einem Knoten. +\begin{beispiel} Ein elektrisches Netzwerk von ohmschen Widerständen kann mit Hilfe eines ungerichteten Graphen beschrieben werden. Ohmsche Widerstände hängen nicht von der Richtung des Stromflusses @@ -67,6 +74,7 @@ Die Endpunkte solcher Widerstände wären immer auf dem gleichen Potential. Folglich würde kein Strom fliessen und sie hätten keinen Einfluss auf das Verhalten des Netzwerkes. Sie können einfach weggelassen werden. +\end{beispiel} \subsubsection{Gerichtete Graphen} In vielen Anwendungen sind die Endpunkte einer Kante nicht austauschbar. @@ -95,15 +103,15 @@ Der Knoten $a(k)$ heisst der {\em Anfangspunkt} der Kante $k\in E$, $e(k)$ heisst der {\em Endpunkt}. \end{definition} -In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung -und die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll +In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung. +Die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll geworden. Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom -Knoten $a$ wieder zu $a$ zurückführt. +Knoten $a$ wieder zu $a$ zurück führt. Man kann einen ungerichteten Graphen in einen gerichteten Graphen -verwandeln, indem wir jede Kante $\{a,b\}$ durch zwei Kanten -$(a,b)$ und $(b,a)$ ersetzen. +verwandeln, indem jede Kante $\{a,b\}$ durch zwei Kanten +$(a,b)$ und $(b,a)$ ersetzt wird. Aus dem ungerichteten Graphen $(V,E)$ mit Knotenmenge $V$ und Kantenmenge $E$ wird so der gerichtete Graph $(V,E')$ mit der Kantenmenge @@ -130,12 +138,12 @@ Dies bedeutet, dass der Endpunkt jeder Kante mit dem Anfangspunkt der nachfolgenden Kante übereinstimmt. Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$. -\subsubsection{Adjazenzmatrix} +\subsection{Adjazenzmatrix} \begin{figure} \centering \includegraphics{chapters/70-graphen/images/adjazenzu.pdf} \caption{Adjazenz-, Inzidenz- und Gradmatrix eines ungerichteten -Graphen mit $5$ Knoten und $7$ Kanten. +Graphen mit fünf Knoten und sieben Kanten. \label{buch:graphen:fig:adjazenzu}} \end{figure} Eine naheliegende Beschreibung eines Graphen mit Hilfe einer @@ -146,13 +154,13 @@ Diese Zahlen werden dann als Zeilen- uns Spaltenindizes interpretiert. Die zum Graphen gehörige sogenannte {\em Adjazenzmatrix} $A(G)$ enthält die Einträge \begin{equation} -a_{ij} +a_{i\!j} = \begin{cases} 1&\qquad \{j,i\} \in E\\ 0&\qquad \text{sonst.} \end{cases} -\label{buch:graphen:eqn:linkmatrix} +\label{buch:graphen:eqn:adjazenzmatrix} \end{equation} Die Matrix hat also genau dann einen von Null verschiedenen Eintrag in Zeile $i$ und Spalte $j$, wenn die beiden Knoten $i$ und $j$ @@ -165,24 +173,27 @@ dargestellt. \centering \includegraphics{chapters/70-graphen/images/adjazenzd.pdf} \caption{Adjazenz-, Inzidenz- und Gradmatrix eines gerichteten -Graphen mit $5$ Knoten und $7$ Kanten. +Graphen mit fünf Knoten und sieben Kanten. +Die roten Einträge in der Adjazenzmatrix $A(G)$ heben die +Unterschiede zur Adjazenzmatrix des gerichteten Graphen +von Abbildung~\ref{buch:graphen:fig:adjazenzu} hervor. \label{buch:graphen:fig:adjazenzd}} \end{figure} Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert -werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzu} +werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzd} illustriert ist. Ihre Einträge sind in diesem Fall definiert mit Hilfe der gerichteten Kanten als \begin{equation} -A(G)_{ij} +A(G)_{i\!j} = -a_{ij} +a_{i\!j} = \begin{cases} 1&\qquad (j,i) \in E\\ 0&\qquad \text{sonst.} \end{cases} -\label{buch:graphen:eqn:linkmatrix} +\label{buch:graphen:eqn:adjazenzmatrix} \end{equation} Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung @@ -192,31 +203,36 @@ von Knoten $j$ zu Knoten $i$ gibt. \subsubsection{Adjazenzmatrix und die Anzahl der Pfade} Die Beschreibung des Graphen mit der Adjazenzmatrix $A=A(G)$ nach -\eqref{buch:graphen:eqn:linkmatrix} ermöglicht bereits, eine interessante -Aufgabe zu lösen. +\eqref{buch:graphen:eqn:adjazenzmatrix} ermöglicht bereits, eine +interessante Aufgabe zu lösen. \begin{satz} \label{buch:graphen:pfade-der-laenge-n} Der gerichtete Graph $G=([n],E)$ werde beschrieben durch die Adjazenzmatrix $A=A(G)$. -Dann gibt das Element in Zeile $j$ und Spalte $i$ von $A^n$ die Anzahl -der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen. -Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:linkmatrix} +Dann gibt das Element $(A^n)_{ji}$ in Zeile $j$ und Spalte $i$ von $A^n$ +die Anzahl der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen. +Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:adjazenzmatrix} formulieren als: In Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl der Pfade der Länge $1$, die $i$ mit $j$ verbinden. \end{satz} +\index{Anzahl der Pfade}% \begin{proof}[Beweis] -Es ist klar, dass $A^1$ die genannte Eigenschaft hat. -Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von -vollständiger Induktion. -Zur Unterscheidung schreiben wir $A^{(n)}$ für die Matrix, die in Zeile +Zur Unterscheidung der Matrix der Wegzahlen von $A^n$ schreiben wir +$A^{(n)}$ für die Matrix, die in Zeile $j$ und Spalte $i$ die Anzahl der Pfade der Länge $n$ von $i$ nach $j$ enhält. Die zugehörigen Matrixelemente schreiben wir $a_{ji}^{n}$ bzw.~$a_{ji}^{(n)}$. Wir haben also zu zeigen, dass $A^n = A^{(n)}$. -Wir nehmen daher an, dass bereits bewiesen ist, dass das Element in Zeile +Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von +vollständiger Induktion. +Es ist klar, dass $A^1$ die genannte Eigenschaft hat. +Der Fall $A^1$ dient daher als Induktionsverankerung. + +Wir nehmen daher im Sinne einer Induktionsannahme an, dass bereits +bewiesen ist, dass das Element in Zeile $j$ und Spalte $i$ von $A^{n-1}$ die Anzahl der Pfade der Länge $n-1$ zählt, dass also $A^{n-1}=A^{(n-1)}$. Dies ist die Induktionsannahme. @@ -225,16 +241,16 @@ Wir bilden jetzt alle Pfade der Länge $n$ von $i$ nach $k$. Ein Pfad der Länge besteht aus einem Pfad der Länge $n-1$, der von $i$ zu einem beliebigen Knoten $j$ führt, gefolgt von einer einzelnen Kante, die von $j$ nach $k$ führt. -Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{kj}$ an. +Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{k\!j}$ an. Das Element in Zeile $j$ und Spalte $i$ der Matrix $A^{(n-1)}$ gibt die Anzahl der Wege von $i$ nach $j$ an. -Es gibt also $a_{kj}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ +Es gibt also $a_{k\!j}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ nach $k$ führen, aber als zweitletzten Knoten über den Knoten $j$ führen. Die Gesamtzahl der Wege der Länge $n$ von $i$ nach $k$ ist daher \[ a_{ki}^{(n)} = -\sum_{j=1}^n a_{kj} a_{ji}^{(n-1)}. +\sum_{j=1}^n a_{k\!j} a_{ji}^{(n-1)}. \] In Matrixschreibweise bedeutet dies \[ @@ -248,8 +264,13 @@ A^n. \] Beim zweiten Gleichheitszeichen haben wir die Induktionsannahme verwendet. +Damit ist der Induktionsschritt vollzogen und der Satz bewiesen. \end{proof} +Speziell geben die Diagonalelemente von $A^n$ die Zahl der geschlossenen +Pfade an. +$(A^n)_{ii}$ ist die Anzahl der geschlossenen Pfade, die $i$ enthalten. + Der Satz~\ref{buch:graphen:pfade-der-laenge-n} ermöglicht auch, einen Algorithmus für den sogenannten Durchmesser eines Graphen zu formulieren. @@ -291,7 +312,7 @@ G 0& 0& 1& 0& 0& 0& 1& 0& 1& 0\\ % 8 0& 0& 0& 1& 0& 0& 0& 1& 0& 1\\ % 9 0& 0& 0& 0& 1& 1& 0& 0& 1& 0 % 10 -\end{pmatrix} +\end{pmatrix}. \] Durch Nachrechnen kann man bestätigen, dass $G^3$ keine Ausserdiagonalelemente $0$ enthält: @@ -310,13 +331,15 @@ G^3 2& 2& 2& 5& 2& 2& 2& 5& 0& 5\\ 2& 2& 2& 2& 5& 5& 2& 2& 5& 0 \end{pmatrix} += +2(U-I) + 3G. \] Daraus kann man jetzt ablesen, dass der Durchmesser des Petersongraphen -$d=5$ ist. -Man kann aber auch mehr ablesen: +$d=3$ ist. +Man kann aber noch mehr ablesen: \begin{itemize} \item -Es gibt keine geschlossenen Pfade der Länge $\le 3$. +Es gibt keine geschlossenen Pfade der Länge $3$. \item Zwischen benachbarten Knoten gibt es jeweils $5$ Pfade der Länge $3$, zwischen nicht benachbarten Knoten gibt es genau $2$ Pfade der Länge $3$. @@ -332,18 +355,6 @@ Für den Peterson-Graphen können die gefundenen Aussagen über die Anzahl von Pfaden durch Ausnützung der Symmetrien des Graphen leichter direkt gefunden werden. -\subsubsection{Beschriftete Graphen} -Bei der Beschreibung eines elektrischen Netzwerkes mit Hilfe eines -ungerichteten Graphen muss jeder Kante zusätzlich ein Widerstandswert -zugeordnet werden. -Dies ist, was eine Beschriftung einer Kante bewerkstelligt. - -\begin{definition} -Eine Beschriftung mit Elementen der Menge $L$ -eines gerichteten oder ungerichteten Graphen $G=(V,E)$ -ist eine Abbildung $l\colon E\to L$. -\index{Beschriftung}% -\end{definition} \subsection{Inzidenzmatrix} Die Adjazenzmatrix kann zusätzliche Information, die möglicherweise @@ -352,27 +363,27 @@ Dies tritt zum Beispiel in der Informatik bei der Beschreibung endlicher Automaten auf, wo zu jeder gerichteten Kante auch noch Buchstaben gehören, für die der Übergang entlang dieser Kante möglich ist. - -Die {\em Inzidenzmatrix} löst dieses Problem. -\index{Inzidenzmatrix}% -Dazu werden zunächst die Kanten numeriert $1,\dots,m$ -numeriert. -Die Matrixeinträge -\[ -a_{ij} = \begin{cases} -1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$} -\\ -0\qquad&\text{sonst} -\end{cases} -\] -stellen die Beziehung zwischen Kanten und Knoten her. +Oder in der Elektrotechnik, wo jedes Bauteil in einem elektrischen +Netzwerk eine Impedanz hat. \subsubsection{Beschriftete Graphen} -Die Inzidenzmatrix kann auch einen erweiterten Graphenbegriff abbilden, -in dem zwischen zwei Kanten mehrere Verbindungen möglich sind. -Graphen mit beschrifteten Kanten gehören dazu. +Ein beschrifteter Graph löst dieses Problem. \begin{definition} +Eine {\em Beschriftung} +eines gerichteten oder ungerichteten Graphen $G=(V,E)$ +mit Elementen der Menge $L$, den Labels, +ist eine Abbildung $l\colon E\to L$. +\index{Beschriftung}% +\end{definition} + +Einen gerichteten, beschrifteten Graphen können wir gleichwertig +statt mit einer Beschriftungsabbildung $l$ auch dadurch erhalten, +dass wir Kanten als Tripel betrachten, die ausser den Knoten auch +noch den Wert der Beschriftung enthalten. + +\begin{definition} +\label{buch:graphen:def:beschriftetergraphgerichtet} Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von Knoten und eine Menge von beschrifteten Kanten der Form \[ @@ -381,63 +392,104 @@ E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt vo Die Menge $L$ enthält die möglichen Beschriftungen der Kanten. \end{definition} +Diese Definition gestattet, dass zwischen zwei Knoten $a$ und $e$ +mehrere Kanten vorhanden sind, die sich durch die Beschriftung +unterscheiden. + +\subsubsection{Inzidenzmatrix} +Die Adjazenzmatrix bildet nur die Nachbarschaftsbeziehung ab, +sie sagt nichts aus über die ``Qualität'' der Verbindung, die durch +die Beschriftung einer Kante angezeigt wird. +Nach Definition~\ref{buch:graphen:def:beschriftetergraphgerichtet} +ist es auch möglich, dass mehrere Kanten von $a$ nach $e$ führen, +die Adjazenzmatrix kann diese ebenfalls nicht unterscheiden. +Die {\em Inzidenzmatrix} +löst dieses Problem. +\index{Inzidenzmatrix}% +Dazu werden zunächst zusätzlich die Kanten $1,\dots,m$ +numeriert, wobei Kanten mit verschiedenen Beschriftungen separat +gezählt werden. +Die Matrixeinträge +\[ +b_{i\!j} = \begin{cases} +1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$} +\\ +0\qquad&\text{sonst} +\end{cases} +\] +der Inzidenzmatrix $B(G)$ +stellen die Beziehung zwischen Kanten und Knoten her. Für einen gerichteten Graphen wird in der Inzidenzmatrix für den Anfangspunkt einer Kante $-1$ eingetragen und für den Endpunkt $+1$. -% XXX Beispiel +Die Inzidenzmatrizen $B(G)$ für die Graphen der beiden Beispiele +in den Abbildungen~\ref{buch:graphen:fig:adjazenzu} und +\ref{buch:graphen:fig:adjazenzd} ist ebendort angegeben. \subsubsection{Inzidenzmatrix und Adjazenzmatrix} -Sei $B(G)$ die Inzidenzmatrix eines Graphen $G$. +Sei $B(G)$ die Inzidenzmatrix eines ungerichteten Graphen $G$. Die Spalten von $B(G)$ sind mit den Kanten des Graphen indiziert. Die Matrix $B(G)B(G)^t$ ist eine quadratische Matrix, deren Zeilen und Spalten mit den Knoten des Graphen indiziert sind. -In dieser Matrix geht die Informatione über die individuellen +In dieser Matrix geht die Information über die individuellen Kanten wieder verloren. Sie hat für $i\ne j$ die Einträge \begin{align*} -(B(G)B(G)^t)_{ij} +(B(G)B(G)^t)_{i\!j} &= \sum_{\text{$k$ Kante}} b_{ik}b_{jk} \\ &=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden} \\ -&=a_{ij}. +&=a_{i\!j}. \end{align*} Die Adjazenzmatrix eines Graphen lässt sich also aus der Inzidenzmatrix berechnen. \subsubsection{Gradmatrix} \index{Gradmatrix}% -Die Diagonale von $B(G)B(G)^t$ enthält die Werte -\begin{align*} +Die Diagonale von $B(G)B(G)^t$ eines ungerichteten Graphen $G$ +enthält die Werte +\begin{align} (B(G)B(G)^t)_{ii} &= \sum_{\text{$k$ Kante}} b_{ik}^2 = \text{Anzahl Kanten, die im Knoten $i$ enden} -\end{align*} +\label{buch:graphen:eqn:gradmatrix} +\end{align} Der {\em Grad} eines Knoten eines Graphen ist die Anzahl der \index{Grad eines Knotens}% Kanten, die in diesem Knoten enden. -Die Diagonalmatrix die aus den Graden der Knoten besteht, heisst die +Die Diagonalmatrix, die aus den Graden der Knoten besteht, heisst die Gradmatrix $D(G)$ des Graphen. Es gilt daher $B(G)B(G)^t = A(G) + D(G)$. +Für Beispiele siehe die Abbildungen~\ref{buch:graphen:fig:adjazenzu} und +\ref{buch:graphen:fig:adjazenzd}. \subsubsection{Gerichtete Graphen} Für einen gerichteten Graphen ändert sich an der Diagonalen der Matrix $B(G)B(G)^t$ nichts. -Da es in einem gerichteten Graphen nur eine einzige Kante $k$ gibt, die zwei -Knoten $i$ und $j$ verbinden kann, muss das zugehörige -Ausserdiagonalelement -\[ -a_{ij} -=b_{ik}b_{jk} +Sei $k$ die Kante, die vom Knoten $j$ zum Knoten $i$ führt. +Die Einträge in der Inzidenzmatrix sind daher $b_{ik}=1$ und $b_{jk}=-1$. +Da es nur eine solche Kante gibt (der Graph ist nicht beschriftet), +ist $b_{ik}b_{jk}$ der einzige Term in der Summe, mit der das +Matrixelement +\begin{equation} +a_{i\!j} += +(B(G)B(G)^t)_{i\!j} += +\sum_{\kappa} b_{i\kappa}b_{j\kappa} += +b_{ik}b_{jk} = -1 -\] -sein. +\label{buch:graphen:eqn:ausserdiagonal} +\end{equation} +berechnet wird. Für einen gerichteten Graphen sind daher alle Ausserdiagonalelemente -negativ und es gilt $B(G)B(G)^t = D(G)-A(G)$. +negativ. \subsubsection{Anwendung: Netlist} Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen @@ -451,52 +503,61 @@ welchen Nets verbunden werden müssen. Die Informationen in der Inzidenzmatrix werden also in einer Applikation zum Schaltungsentwurf in ganz natürlicher Weise erhoben. -\subsection{Die Adjazenzmatrix und Laplace-Matrix -\label{subsection:adjazenz-und-laplace-matrix}} -Die Beschreibung mit der Matrix~\eqref{buch:graphen:eqn:linkmatrix} -``vergisst'' den ``Namen'' der Kante, die eine Verbindung zwischen zwei -Knoten herstellt. -Damit ist sie keine geeignete Grundlage, um beschriftete Graphen einer -Matrixbeschreibung zuzuführen. -Eine solche muss eine Matrix verwenden, die nicht nur das Vorhandensein einer -Verbindung wiedergibt, sondern ausdrückt, welche Kante welche beiden -Knoten miteinander verbindet. -Dies führt zur sogenannten Adjazenzmatrix. +\subsection{Die Laplace-Matrix +\label{subsection:laplace-matrix}} +Will man ein elektrisches Netzwerk modellieren oder den Transport +von Wärme durch eine Gitterstruktur berechnen, dann muss man zwar den +Kanten des Netzwerks eine ``Stromrichtung'' geben um ausdrücken zu können, +in welche Richtung der Strom oder die Wärmeenergie fliesst. +Trotzdem gestattet man natürlich auch den Stromfluss in Gegenrichtung. + +Wir gehen also aus von einem ungerichteten Graphen $G$, aus dem +wir einen gerichteten Graphen $G'$ machen. +Zu jeder Kante $\{a,b\}$ von $G$ wählen wir genau eine der möglichen +Orientierungen $(a,b)$ oder $(b,a)$ im Graphen $G'$. +Aus der Inzidenzmatrix $B(G')$ lässt sich jetzt ein Operator konstruieren, +der für die Anwendungen besonders gut geeignet ist. \begin{definition} -\label{buch:def:adjazenz-matrix} -Ist $G=(V,E)$ ein gerichteter Graph mit $n=|G|$ Vertizes und $m=|E|$ Kanten, -dann ist die zugehörige {\em Adjazenzmatrix} $A=A(G)$ eine $n\times m$-Matrix. -In der Spalte $k$ wird der Anfangspunkt der Kante $k$ mit $-1$, der Endpunkt -mit $+1$ angezeigt, die übrigen Einträge sind $0$. -$A$ hat also die Matrixelemente +\label{buch:graphen:def:laplace-matrix} +Die {\em Laplace-Matrix} des Graphen $G$ ist +\[ +L(G) = B(G')B(G')^t, +\] +wobei $G'$ ein wie oben konstruierter gerichteter Graph ist. +\end{definition} + +Wir müssen uns davon überzeugen, dass diese Definition sinnvoll ist +und nicht etwa von der Wahl von $G'$ abhängt. +Diese klärt der folgende Satz. + +\begin{satz} +Die Laplace-Matrix eines ungerichteten Graphen $G$ ist \begin{equation} -a_{ik} -= -\begin{cases} --1&\qquad i=a(k)\\ -+1&\qquad i=e(k)\\ -\phantom{+}0&\qquad\text{sonst} -\end{cases} -\label{buch:eqn:ajazenz-matrix} +L(G) = D(G) - A(G) +\label{buch:graphen:eqn:laplace-definition} \end{equation} -\end{definition} +und somit insbesondere unabhängig von der Wahl des Graphen $G'$, +der für die Definition von $L(G)$ verwendet wurde. +\end{satz} -Der wesentliche Unterschied dieser Definition von der Matrix $G$ -liegt in der Bedeutung der Einträge. -Für $G$ drückt ein nicht verschwindendes Matrixelement das Vorhandensein -einer Kante aus, in $A$ ist es die Tatsache, dass in diesem Knoten -eine Kante beginnt oder endet. - -Es ist natürlich möglich, aus der Adjazenzmatrix auch die Link-Matrix -zu rekonstruieren. -Dazu muss für jedes Paar $(j,i)$ von Knoten festgestellt werden, -ob die Adjazenzmatrix eine entsprechende Verbindung enthält, also ob der -Vektor -\[ -k_{ji} = e_i - e_j -\] -als Spaltenvektor vorkommt, wobei die $e_i$ die $n$-dimensionalen -Standardbasisvektoren sind. +\begin{proof}[Beweis] +Aufgrund der Konstruktion des Graphen $G'$ sind die Diagonalelemente +der Laplace-Matrix +$L(G)=B(G')B(G')^t$ nach \eqref{buch:graphen:eqn:gradmatrix} genau +die Elemente der Gradmatrix $D(G)$. +Die ausserdiagonalen Elemente sind nach +\eqref{buch:graphen:eqn:ausserdiagonal} +genau dann, wenn es in $G$ eine Verbindung zwischen den beiden Knoten +gibt. +Dies sind die Elemente von $-A(G)$. +Damit ist die Formel +\eqref{buch:graphen:eqn:laplace-definition} +nachgewiesen. +\end{proof} +Die Laplace-Matrix tritt zum Beispiel als Diskretisation des Laplace-Operators +in partiellen Differentialgleichungen auf. +Sie ist die Basis für die Untersuchungen der spektralen Graphentheorie +in Abschnitt~\ref{buch:section:spektrale-graphentheorie}. diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex index 530d96c..1fb61b6 100644 --- a/buch/chapters/70-graphen/chapter.tex +++ b/buch/chapters/70-graphen/chapter.tex @@ -9,41 +9,44 @@ \rhead{} Ein Graph ist eine Menge von Knoten, die untereinander mit Kanten verbunden sind. -Graphen können zum Beispiel verwendet werden um Netzwerke zu beschreiben, +\index{Graph}% +Graphen können zum Beispiel verwendet werden, um Netzwerke zu beschreiben, aber auch viele andere Datenstrukturen. \index{Graph}% -Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben +Die Knoten können einzelne Objekte darstellen, die Kanten entsprechen dann Beziehungen zwischen diesen Objekten. Graphen haben zwar nur eine eindimensionale Geometrie, sie können aber auch als -erste Approximation dreidimensionaler Objekte dienen. +erste Approximation höherdimensionaler geometrischer Strukturen dienen. Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl -von Fragestellungen, die über Graphen gestellt, und der +von Fragestellungen, die über Graphen gestellt worden sind, und der zugehörigen Lösungsalgorithmen, die zu ihrer Beantwortung gefunden worden sind. Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes diskrete +\index{Komplexitätstheorie}% Problem in ein Graphenproblem umformulieren lässt. \index{Komplexitätstheorie}% Das Problem, einen Stundenplan zu finden, der sicherstellt, dass +\index{Stundenplan}% alle Studierenden jedes Fach besuchen können, für die sie sich angemeldet haben, lässt sich zum Beispiel wie folgt als ein Graphenproblem formulieren. Die Fächer betrachten wir als Knoten des Graphen. -Für jedes Paar von Fächern ziehen wir eine Kante des Graphen, wenn +Für jedes Paar von Fächern ziehen wir eine Kante, wenn sich mindestens ein Studierender für beide Fächer angemeldet hat. Die Kante drückt aus, dass die beiden Fächer nicht zur gleichen Zeit geplant werden dürfen. Das Problem, einen Stundenplan zu finden, besteht jetzt darin, für -jedes Fach ein Zeitintervall zu finden, während dem es durchgeführt +jedes Fach ein Zeit\-intervall zu finden, während dem es durchgeführt werden soll. -\index{Stundenplan}% -Natürlich steht nur eine beschränkte Anzahl Zeitintervalle zur Verfügung -und benachbarte Knoten dürfen nicht ins gleiche Zeitintervall geplant -werden. +Natürlich steht nur eine beschränkte Anzahl Zeitintervalle zur Verfügung. +Benachbarte, also mit einer Kante verbundene Knoten dürfen nicht +ins gleiche Zeitintervall geplant werden. Das zugehörige abstrakte Graphenproblem heisst das Färbeproblem: \index{Färbeproblem}% -ist es möglich, mit einer beschränkten Anzahl von Farben die Knoten +ist es möglich, mit einer beschränkten Anzahl von Farben, oder im +vorliegenden Fall Zeitintervalle, die Knoten des Graphen so einzufärben, dass benachbarte Knoten niemals die gleiche Farbe haben. diff --git a/buch/chapters/70-graphen/images/adjazenzd.pdf b/buch/chapters/70-graphen/images/adjazenzd.pdf Binary files differindex dc3dd8f..146856c 100644 --- a/buch/chapters/70-graphen/images/adjazenzd.pdf +++ b/buch/chapters/70-graphen/images/adjazenzd.pdf diff --git a/buch/chapters/70-graphen/images/adjazenzd.tex b/buch/chapters/70-graphen/images/adjazenzd.tex index 5cef18e..81801d3 100644 --- a/buch/chapters/70-graphen/images/adjazenzd.tex +++ b/buch/chapters/70-graphen/images/adjazenzd.tex @@ -10,12 +10,14 @@ \usepackage{txfonts} \usepackage{pgfplots} \usepackage{csvsimple} +\usepackage{color} \usetikzlibrary{arrows,intersections,math,calc} \begin{document} \def\skala{1} \begin{tikzpicture}[>=latex,thick,scale=\skala] \def\r{1.8} +\def\R{\bgroup\color{red}0\egroup} \begin{scope} \coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); @@ -71,15 +73,16 @@ B(G) \end{pmatrix*}$}; \end{scope} + \begin{scope}[xshift=3cm,yshift=1.1cm] \node at (0,0) [right] {$\displaystyle A(G) = \begin{pmatrix*}[r] - 0& 1& 1& 0& 1\\ - 1& 0& 1& 1& 0\\ - 1& 1& 0& 1& 0\\ - 0& 1& 1& 0& 1\\ + 0&\R&\R& 0&\R\\ + 1& 0&\R&\R& 0\\ + 1& 1& 0&\R& 0\\ + 0& 1& 1& 0&\R\\ 1& 0& 0& 1& 0 \end{pmatrix*}, \quad @@ -90,7 +93,7 @@ D(G) 0&3&0&0&0\\ 0&0&3&0&0\\ 0&0&0&3&0\\ -0&0&0&0&1 +0&0&0&0&2 \end{pmatrix*} $}; \end{scope} diff --git a/buch/chapters/70-graphen/images/adjazenzu.pdf b/buch/chapters/70-graphen/images/adjazenzu.pdf Binary files differindex d3f255e..6002cbf 100644 --- a/buch/chapters/70-graphen/images/adjazenzu.pdf +++ b/buch/chapters/70-graphen/images/adjazenzu.pdf diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex index 5fb3056..b718b65 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -6,7 +6,7 @@ \section{Spektrale Graphentheorie \label{buch:section:spektrale-graphentheorie}} \rhead{Spektrale Graphentheorie} -Die Adjazenz-Matrix, die Grad-Matrix und damit natürlich auch +Die Adjazenzmatrix, die Gradmatrix und damit natürlich auch die Laplace-Matrix codieren alle wesentliche Information eines ungerichteten Graphen. Sie operiert auf Vektoren, die für jeden Knoten des Graphen eine @@ -18,11 +18,11 @@ der chromatischen Zahl eines Graphen illustrieren. \subsection{Chromatische Zahl und Unabhängigkeitszahl \label{buch:subsection:chromatische-zahl}} -Der Grad eines Knotens ist ein mass dafür, wie stark ein Graph +Der Grad eines Knotens ist ein Mass dafür, wie stark ein Graph ``vernetzt'' ist. Je höher der Grad, desto mehr direkte Verbindungen zwischen Knoten gibt es. -Noch etwas präziser können diese Idee die beiden mit Hilfe der -chromatischen zahl und der Unabhängigkeitszahl erfasst werden. +Noch etwas präziser kann diese Idee die mit Hilfe der +chromatischen Zahl und der Unabhängigkeitszahl erfasst werden. \begin{definition} Die {\em chromatische Zahl} $\operatorname{chr}G$ eines Graphen $G$ ist @@ -39,9 +39,14 @@ ist die maximale Anzahl Knoten einer unabhängigen Menge. \index{Unabhängigkeitszahl} \end{definition} +\begin{beispiel} +Abbildung~\ref{buch:graphen:fig:chrindpeterson} bestimmt die chromatische +Zahl und die Unabhängigkeitszahl im Beispiel des Peterson-Graphen. +\end{beispiel} + Zwischen der chromatischen Zahl und der Unabhängigkeitszahl eines Graphen muss es einen Zusammenhang geben. -Je mehr Verbingungen es im Graphen gibt, desto grösser wird die chromatische +Je mehr Verbindungen es im Graphen gibt, desto grösser wird die chromatische Zahl. Gleichzeitig wird es schwieriger für Mengen von Knoten, unabhängig zu sein. @@ -53,7 +58,7 @@ $\operatorname{chr}G\cdot\operatorname{ind}G\ge n$. \begin{proof}[Beweis] Eine minimale Färbung des Graphen mit $\operatorname{chr}G$ Farben -teilt die Knoten in $\operatorname{chr}G$ Mengen $V_f$ von Knoten mit +teilt die Knoten in $\operatorname{chr}G$ disjunkte Mengen $V_f$ von Knoten mit gleicher Farbe $f$ ein. Da diese Mengen einfarbig sind, sind sie unabhängig, enthalten also höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt, @@ -109,16 +114,17 @@ der grossen Knoten, mit denen sie verbunden sind. \begin{beispiel} Der Peterson-Graph $P$ von Abbildung~\ref{buch:graphen:fig:chrindpeterson} -hat chromatische Zahl $\operatorname{chr}P=3$ und unabhängigkeitszahl +hat chromatische Zahl $\operatorname{chr}P=3$ und Unabhängigkeitszahl $\operatorname{ind}P=4$. Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar als Ungleichung: $\operatorname{chr}P\cdot\operatorname{ind}P=3\cdot 4=12>10=n$. \end{beispiel} -Nach Definition ist Unabhängigkeitszahl ein Mass für die Grösse einer +Nach Definition ist die Unabhängigkeitszahl ein Mass für die Grösse einer unabhängigen Menge von Punkten. Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die -chromatische Zahl als ein Mass dafür, wieviele solche anabhängige +chromatische Zahl als ein Mass dafür vorstellen kann, +wieviele solche unabhängige Mengen in einem Graphen untergebracht werden können. % @@ -133,11 +139,13 @@ Einfärbung des ganzen Graphen reichen. Genau dies garantiert jedoch der folgende Satz. \begin{definition} -Der maximale Grad +Der {\em maximale Grad} \( \max_{v\in V} \deg(v) \) +eines ungerichteten Graphen wird mit $d$ bezeichnet. +\index{maximaler Grad}% \end{definition} \begin{satz} @@ -153,11 +161,11 @@ Ein Graph mit nur einem Knoten hat keine Kanten, der maximale Grad ist daher $0$ und $d+1=1$ Farbe reicht auch tatsächlich zur Einfärbung des einen Knotens. -Wir nehmen jetzt an, die Behaupt sei für Graphen mit $n-1$ Knoten bereits +Wir nehmen jetzt an, die Behauptung sei für Graphen mit $n-1$ Knoten bereits bewiesen, ein Graph $G'$ mit $n-1$ Knoten und maximalem Grad $d'$ erfüllt also die Ungleichung $\operatorname{chr}G'\le d'+1$. -Wir wählen jetzt einen beleibigen Knoten $v$ des Graphen $G$ und bilden +Wir wählen jetzt einen beliebigen Knoten $v$ des Graphen $G$ und bilden den Graphen $G'$, der aus $G$ entsteht, indem man den Knoten $v$ entfernt: $G'=G\setminus\{v\}$. Der maximale Grad $d'$ von $G'$ kann dabei nicht grösser werden, es ist @@ -177,7 +185,7 @@ ist für alle Begriffe anwendbar, die sich bei der Bildung eines Untergraphen auf ``monotone'' Art ändern. Die chromatische Zahl eines Untergraphen ist höchstens so gross wie die des ganzen Graphen. -Dann kann man eine Ungleichung für grosse Graphen schrittweise aus +Daher kann man eine Ungleichung für grosse Graphen schrittweise aus entsprechenden Ungleichungen für die kleineren Teilgraphen gewinnen. Ziel der folgenden Abschnitte ist zu zeigen, dass sich eine Grösse mit ähnlichen Eigenschaften aus dem Eigenwertspektrum der Adjazenzmatrix @@ -210,7 +218,14 @@ Somit ist \frac{1}{n}(d_1+\dots+d_n) \label{buch:graphen:eqn:AUdavg} \end{equation} -der mittlere Grad, der mit $\overline{d}$ bezeichnet werden soll. +der {\em mittlere Grad}, der mit $\overline{d}$ bezeichnet werden soll. +Da die Kanten eines Graphen zusammen $2\cdot|E|$ Enden haben, kann +er kann auch als +\[ +\overline{d}=\frac{2\cdot|E|}{|V|} +\] +berechnet werden. +\index{mittlerer Grad}% Da $A(G)$ eine symmetrische Matrix ist, ist $A(G)$ diagonalisierbar, die Eigenwerte sind also alle reell. @@ -232,20 +247,23 @@ ist. In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} des nächsten Kapitels wird die Perron-Frobenius-Theorie positiver +\index{Perron-Frobenius-Theorie}% +\index{positive Matrix}% Matrizen vorgestellt, welche einer Reihe interessanter Aussagen über den betragsgrössten Eigenwert und den zugehörigen Eigenvektor macht. -Die Adjazenz-Matrix ist eine nichtnegative Matrix und $\alpha_{\text{max}}$ +Die Adjazenzmatrix ist eine nichtnegative Matrix und $\alpha_{\text{max}}$ ist der grösste Eigenwert, also genau die Grösse, auf die die Sätze~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} -und \label{buch:wahrscheinlichkeit:satz:perron-frobenius2} +und \ref{buch:wahrscheinlichkeit:satz:perron-frobenius2} anwendbar sind. Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend +\index{primitive Matrix}% ist damit, dass der Graph zusammenhängend ist. Im folgenden soll dies daher jeweils angenommen werden. \begin{satz} -Ist $G$ ein zusammenhänger Graph mit $n$ Knoten und maximalem Grad $d$, +Ist $G$ ein zusammenhängender Graph mit $n$ Knoten und maximalem Grad $d$, dann gilt \[ \frac1n\sum_{v\in V} \deg(v) @@ -266,8 +284,8 @@ ist $f$ ein positiver Vektor mit der Eigenschaft $A(G)f=\alpha_{\text{max}}f$. Der Eigenvektor $f$ ist eine Funktion auf den Knoten des Graphen, die $v$-Komponente des Vektors $f$ für einen Vertex $v\in V$ ist $f(v)$. Die Eigenvektoreigenschaft bedeutet $(A(G)f)(v)=\alpha_{\text{max}} f(v)$. -Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ Einsen genau für diejenigen -Knoten $u\in V$, die zu $v$ benachbart sind. +Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ genau für diejenigen +Knoten $u\in V$ Einsen, die zu $v$ benachbart sind. Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist \[ (A(G)f)(v) @@ -278,9 +296,10 @@ Die Summe der Komponenten $A(G)f$ kann man erhalten durch Multiplikation von $A(G)f$ mit einem Zeilenvektor $U^t$ aus lauter Einsen, also \begin{equation} \begin{aligned} -\sum_{v\in V}\sum_{u\sim v}f(v) +{\color{red} +\sum_{v\in V}}\sum_{u\sim v}f(v) &= -U^tA(G)f +{\color{red}U^t}A(G)f = (U^tA(G))f = @@ -356,7 +375,7 @@ f'(v)&\qquad v\in V'\\ \] konstruieren, der auf ganz $V$ definiert ist. -Die Vektoren $f'$ und $g$ haben die gleichen Komponenten, also ist auch +Die Vektoren $f'$ und $g$ haben auf $V'$ die gleichen Komponenten, also ist auch $\langle f',f'\rangle = \langle g,g\rangle$. Die Matrixelemente von $A(G')$ und $A(G)$ auf gemeinsamen Knoten $u,v\in V'$ erfüllen $A(G')_{uv}\le A(G)_{uv}$, da jede Kante von $G'$ auch in $G$ ist. @@ -385,6 +404,8 @@ $\langle A(G)h,h\rangle/\langle h,h\rangle$ für alle Vektoren $h\ne 0$ ist. % \subsection{Chromatische Zahl und $\alpha_{\text{max}}$: Der Satz von Wilf \label{buch:subsection:chr-und-alpha-max}} +\index{Satz von Wilf}% +\index{Wilf, Satz von}% Die in Satz~\ref{buch:graphen:satz:amaxuntergraph} beschriebene Eigenschaft von $\alpha_{\text{max}}$ beim Übergang zu einem Untergraphen ermöglich jetzt, eine besser Abschätzung für die chromatische Zahl @@ -407,13 +428,15 @@ bewiesen werden. Ein Graph mit nur einem Knoten hat die $0$-Matrix als Adjazenzmatrix, der maximale Eigenwert ist $\alpha_{\text{max}}=0$, und tatsächlich reicht $\alpha_{\text{max}}+1=1$ Farbe, um den einen Knoten einzufärben. +Dies ist die Induktionsverankerung. -Wir nehmen jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits +Im Sinne der Induktionsannahme +nehmen wir jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits beweisen. Wir müssen dann zeigen, dass der Satz dann auch für Graphen mit $n$ Knoten gilt. -Sei $v\in V$ ein Knoten minimalen Grades und $G'=G\setminus{v}$ der +Sei $v\in V$ ein Knoten minimalen Grades und $G'=G\setminus\{v\}$ der Untergraph, der entsteht, wenn der Knoten $v$ entfernt wird. Da $G'$ genau $n-1$ Knoten hat, gilt der Satz von Wilf für $G'$ und daher kann $G'$ mit höchstens @@ -443,7 +466,7 @@ maximale Grad. \end{figure} \begin{beispiel} -Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} 12 Kanten und 9 +Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} hat 12 Kanten und 9 Knoten, daher ist $\overline{d}\le \frac{24}{9}$. Der maximale Grad ist $4$ und durch explizite Rechnung mit Hilfe zum Beispiel von Octave ergibt, dass $\alpha_{\text{max}}\approx 2.9565$. diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index 8baa88c..2b9f29b 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -270,7 +270,7 @@ $\lambda_k$, $k=1,\dots,n$ h(\lambda_k) + \sum_ig(a_i\lambda_k)=1 \] gilt. -Für beleibige Funktionen $g$ und $h$ kann man nicht davon ausgehen, +Für beliebige Funktionen $g$ und $h$ kann man nicht davon ausgehen, aber man kann erwarten. Man muss daher zusätzlich verlangen, dass \[ diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index 977bf81..fb88d09 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -152,3 +152,13 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc language = {german}, } +@buch{skript:brualdi, + title = {The mutually beneficial relationships of graphs and matrices}, + author = {Richard A. Brualdi}, + series = {CBMS Regionals conference series in mathematics}, + number = {115}, + publisher = {American Mathematical Society}, + isbn = {978-0-8218-5315-3}, + year = 2011, + language = {english} +} diff --git a/buch/papers/clifford/0_ElevatorPitch.tex b/buch/papers/clifford/0_ElevatorPitch.tex index a68ac8f..3d04737 100644 --- a/buch/papers/clifford/0_ElevatorPitch.tex +++ b/buch/papers/clifford/0_ElevatorPitch.tex @@ -1,12 +1,12 @@ -Der Nutzen, welche die Clifford Algebra hat, lässt sich am besten mit den Worten des modernen Begründers derselben erläutern. -\index{Clifford Algebra}% +Der Nutzen, welche die geometrische Algebra hat, lässt sich am besten mit den Worten des modernen +Begründers derselben erläutern. \index{geometrische Algebra}% \begin{quote} -GA [Geometric Algebra i.~a.~W.~Clifford Algebra] +GA [Geometric Algebra] provides a unified language for the whole of physics and for much of mathematics and its applications that is conceptually and computationally superior to alternative mathematical systems in many application domains. \cite{clifford:hestenes_GA} \end{quote} -Im folgenden hoffen wir den Leser von der Nützlichkeit und der geometrischen Schönheit der Clifford Algebra zu überzeugen. +Im folgenden hoffen wir den Leser von der Nützlichkeit und der geometrischen Schönheit der geometrischen Algebra zu überzeugen. diff --git a/buch/papers/clifford/2_QuadratVektoren.tex b/buch/papers/clifford/2_QuadratVektoren.tex index 8916e15..d54b068 100644 --- a/buch/papers/clifford/2_QuadratVektoren.tex +++ b/buch/papers/clifford/2_QuadratVektoren.tex @@ -4,7 +4,7 @@ Was eine Addition von Vektoren bedeutet ist sehr intuitiv und auch leicht geometrisch darzustellen wie in Abbildung \ref{figure:addition}. Was allerdings das Produkt von Vektoren ergibt, mag anfänglich unintuitiv wirken. \begin{figure}[tb] \centering - \begin{tikzpicture} + \begin{tikzpicture}[>=latex] \draw[thin,gray!40] (0,0) grid (4,4); \draw[blue,thick,->] (0,0)--(3.5,2) node[midway,above,sloped] {$\textbf{a}$}; \draw[red,thick,->] (3.5,2)--(1.5,3.8) node[midway,above,sloped] {$\textbf{b}$}; diff --git a/buch/papers/clifford/6_PauliMatrizen.tex b/buch/papers/clifford/6_PauliMatrizen.tex index 70d28ad..c89ad02 100644 --- a/buch/papers/clifford/6_PauliMatrizen.tex +++ b/buch/papers/clifford/6_PauliMatrizen.tex @@ -4,10 +4,10 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Pauli-Matrizen} -\rhead{Pauli-Matrizen} \index{Pauli-Matrizen}% -Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in der Clifford-Algebra zu erstellen? Man könnte versuchen einen textuellen Rechner zu implementieren der für die Elemente $\mathbf{e}_i$ hartkodierte Vereinfachungen ausführt. +Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in der Clifford-Algebra zu erstellen? +Man könnte versuchen, einen textuellen Rechner zu implementieren, der für die Elemente $\mathbf{e}_i$ hartkodierte Vereinfachungen ausführt. \begin{beispiel} Der Algorithmus weiss, dass er $a\mathbf{e}_1\cdot b\mathbf{e}_1$ zu $ab\cdot1$ vereinfachen kann. Dies ermöglicht zum Beispiel die Vereinfachung \begin{equation*} @@ -15,6 +15,7 @@ Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in \qedhere \end{equation*} \end{beispiel} +\rhead{Pauli-Matrizen} Ein textueller Algorithmus ist aber sehr ineffizient. Die Pauli-Matrizen bilden eine elegante und schnellere Alternative, welche für die dreidimensionale Clifford-Algebra verwendet werden können und alle Operationen aus der Clifford-Algebra gleich wie die Matrixoperationen ausführen lassen. \begin{definition} \label{def:defPauli} diff --git a/buch/papers/clifford/7_Reflektion.tex b/buch/papers/clifford/7_Reflektion.tex index 549848c..d4f2c6f 100644 --- a/buch/papers/clifford/7_Reflektion.tex +++ b/buch/papers/clifford/7_Reflektion.tex @@ -9,7 +9,7 @@ Die Spiegelung ist eine grundlegende, geometrische Operation, aus welcher man weitere Operationen, wie beispielsweise die später beschriebene Rotation, ableiten kann. Da die geometrische Algebra für geometrische Anwendungen ausgelegt ist, sollte die Spiegelung auch eine einfache, praktische Formulierung besitzen. \begin{figure} \centering - \begin{tikzpicture} + \begin{tikzpicture}[>=latex] \draw[thin,gray!40] (-3,-1) grid (3,3); \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; \draw[<->] (0,-1)--(0,3) node[above]{$a_2$}; @@ -92,4 +92,4 @@ Verwendet man für $\mathbf{u}$ nur einen Einheitsvektor $\mathbf{\hat{u}}$, wel \begin{align} \mathbf{v'} = -\mathbf{\hat{u}v\hat{u}} \end{align} -vereinfacht. Im Gegensatz zu den Abbildungen in der linearen Algebra, welche in jeder anderen Dimension, durch andere Matrizen \eqref{Spiegelmatrizen} beschrieben werden müssen, ist es in der geometrischen Algebra immer der gleiche Vorgehensweise. Zudem ist diese kompakte Schreibweise in der linearen Algebra nicht möglich, da bis auf das Vektorprodukt in der dritten Dimension keine Multiplikation von Vektoren definiert ist.
\ No newline at end of file +vereinfacht. Im Gegensatz zu den Abbildungen in der linearen Algebra, welche in jeder anderen Dimension, durch andere Matrizen \eqref{Spiegelmatrizen} beschrieben werden müssen, ist es in der geometrischen Algebra immer der gleiche Vorgehensweise. Zudem ist diese kompakte Schreibweise in der linearen Algebra nicht möglich, da bis auf das Vektorprodukt in der dritten Dimension keine Multiplikation von Vektoren definiert ist. diff --git a/buch/papers/erdbeben/Erdbeben_Standardfall.PNG b/buch/papers/erdbeben/Erdbeben_Standardfall.PNG Binary files differnew file mode 100644 index 0000000..6aed433 --- /dev/null +++ b/buch/papers/erdbeben/Erdbeben_Standardfall.PNG diff --git a/buch/papers/erdbeben/Erdbeben_Standardfall_Zoom.PNG b/buch/papers/erdbeben/Erdbeben_Standardfall_Zoom.PNG Binary files differnew file mode 100644 index 0000000..e3a6286 --- /dev/null +++ b/buch/papers/erdbeben/Erdbeben_Standardfall_Zoom.PNG diff --git a/buch/papers/erdbeben/Messrauschen_geaendert.PNG b/buch/papers/erdbeben/Messrauschen_geaendert.PNG Binary files differnew file mode 100644 index 0000000..f46354d --- /dev/null +++ b/buch/papers/erdbeben/Messrauschen_geaendert.PNG diff --git a/buch/papers/erdbeben/Messrauschen_geaendert_zoom.PNG b/buch/papers/erdbeben/Messrauschen_geaendert_zoom.PNG Binary files differnew file mode 100644 index 0000000..971ee82 --- /dev/null +++ b/buch/papers/erdbeben/Messrauschen_geaendert_zoom.PNG diff --git a/buch/papers/erdbeben/Prozessrauschen_geaendert.PNG b/buch/papers/erdbeben/Prozessrauschen_geaendert.PNG Binary files differnew file mode 100644 index 0000000..aff9ed8 --- /dev/null +++ b/buch/papers/erdbeben/Prozessrauschen_geaendert.PNG diff --git a/buch/papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG b/buch/papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG Binary files differnew file mode 100644 index 0000000..f2c1d3b --- /dev/null +++ b/buch/papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG diff --git a/buch/papers/erdbeben/Standard_F-T.PNG b/buch/papers/erdbeben/Standard_F-T.PNG Binary files differnew file mode 100644 index 0000000..9da5f5e --- /dev/null +++ b/buch/papers/erdbeben/Standard_F-T.PNG diff --git a/buch/papers/erdbeben/Standard_V-T.PNG b/buch/papers/erdbeben/Standard_V-T.PNG Binary files differnew file mode 100644 index 0000000..b511ff4 --- /dev/null +++ b/buch/papers/erdbeben/Standard_V-T.PNG diff --git a/buch/papers/erdbeben/Standard_Zoom.PNG b/buch/papers/erdbeben/Standard_Zoom.PNG Binary files differnew file mode 100644 index 0000000..4f4e770 --- /dev/null +++ b/buch/papers/erdbeben/Standard_Zoom.PNG diff --git a/buch/papers/erdbeben/Standard_Zoom_leicht.PNG b/buch/papers/erdbeben/Standard_Zoom_leicht.PNG Binary files differnew file mode 100644 index 0000000..5885d77 --- /dev/null +++ b/buch/papers/erdbeben/Standard_Zoom_leicht.PNG diff --git a/buch/papers/erdbeben/Standard_alles.PNG b/buch/papers/erdbeben/Standard_alles.PNG Binary files differnew file mode 100644 index 0000000..a678df2 --- /dev/null +++ b/buch/papers/erdbeben/Standard_alles.PNG diff --git a/buch/papers/erdbeben/Systemparameter_geaendert.PNG b/buch/papers/erdbeben/Systemparameter_geaendert.PNG Binary files differnew file mode 100644 index 0000000..84249af --- /dev/null +++ b/buch/papers/erdbeben/Systemparameter_geaendert.PNG diff --git a/buch/papers/erdbeben/Systemparameter_geaendert_2.PNG b/buch/papers/erdbeben/Systemparameter_geaendert_2.PNG Binary files differnew file mode 100644 index 0000000..d4f530e --- /dev/null +++ b/buch/papers/erdbeben/Systemparameter_geaendert_2.PNG diff --git a/buch/papers/erdbeben/Teil_Fabio.tex b/buch/papers/erdbeben/Teil_Fabio.tex index 9f5d092..2ab6052 100644 --- a/buch/papers/erdbeben/Teil_Fabio.tex +++ b/buch/papers/erdbeben/Teil_Fabio.tex @@ -1,202 +1,197 @@ -\section{Kalman-Filter} -\subsection{Was ist ein Erdbeben?} -Für das Verständnis möchten wir zuerst erklären, was ein Erdbeben genau ist. -Das soll uns helfen, eine Verknüpfung zwischen dem Naturphänomen und der mathematischen Problemstellung herzustellen. - - -Unter einem Erdbeben verstehen wir eine Erschütterung des Erdkörpers. -Dabei reiben zwei tektonische Platten aneinander, welche sich durch die Gesteinsverzahnung gegenseitig blockieren. -Aufgrund dieser Haftreibung entstehen Spannungen, die sich immer mehr bis zum Tipping Point aufbauen. -Irgendwann ist der Punkt erreicht, in dem die Scherfestigkeit der Gesteine überwunden wird. -Wenn dies passiert, entlädt sich die aufgebaute Spannung und setzt enorme Energien frei, die wir als Erdbeben wahrnehmen. - -Ein Erdbeben breitet sich vom Erdbebenherd in allen Richtungen gleich aus. -Vergleichbar ist, wenn man einen Stein in einen Teich wirft und die Wellen beobachten kann, die sich ausbreiten. - -Wir möchten nun mittels Kalman-Filter die Erdbebenbeschleunigung herausfinden. -Die Erdbebenbeschleunigung ist in der Praxis zur Entwicklung von Erdbebengefährdungskarten, sowie der Ausarbeitung von Baunormen für erdbebengerechte Bauweise von Bedeutung. - +\section{Anwendung des Kalman-Filters} +\subsection{Ziel} +Bis jetzt haben wir gelesen, was das Kalman-Filter bewirkt und wie es funktioniert. +Nun möchten wir mit einem Beispiel herausfinden, +ob das Filter unsere gesuchte Grösse $f(t)$ bestimmen kann. \subsection{Künstliche Erdbebendaten} -Nun möchten wir anhand eines eigenen Beispiels das Kalman-Filter anwenden. -Da wir keine Rohdaten über vergangene Erdbeben zur Hand haben, müssen wir künstliche Daten erzeugen, um sie in das Filter einzugeben und somit den Prozess starten. -Dafür nehmen wir die Formel für harmonisch gedämpfte Schwingungen, die - +Da wir keine Rohdaten über vergangene Erdbeben zur Hand haben, müssen wir mittels Matlab künstliche Daten erzeugen und sie dann in das Filter eingeben. +Diese Vorgehensweise erlaubt uns das Erdbeben beliebig zu gestalten +und weil es digital simuliert wird, +haben wir keine Bauschäden zu beklagen. + +\subsection{Wahl der Schwingung} +Wir müssen uns überlegen, mit welcher Schwingung wir ein realitätsnahes Beben erzeugen können. +Mit einer ungedämpften harmonischen Schwingung können wir zwar die meisten Vorgänge in der Physik erklären. +Da aber unser Erdbeben irgendwann abklingen muss, wählen wir die gedämpfte harmonische Schwingung. +Die dazugehörige Schwingungsgleichung lautet \begin{equation} - y = A \sin(\omega t e^{-lambda t}) -\end{equation} - -lautet. - -A ist die Amplitude der Schwingung und beschreibt die Heftigkeit eines Erdbebens, die Magnitude. -Omega repräsentiert die Erdbebenfrequenz, die in der Realität zwischen 1 Hz und 30 Hz beträgt. -Wir wählen als Erwartungswert 15 Herz und für die Standardabweichung 1 Hz. -Lambda ist die Bodendämpfung, für die wir 0.2 wählen. -Wir haben diese Zahl aus der Literatur entnommen, denn sie ist für das Bauwesen bedeutend. -Lambda ist ein Materialparameter von Böden. - -Je grösser Lambda gewählt wird, desto stärker wirkt die Dämpfung der Massenschwingung. -Die Funktion ist zeitabhängig und wir lassen pro Sekunde zehn Messwerte generieren. - -Die Frequenz basiert auf einer random-Funktion, da wir das Erdbeben unberechenbar gestalten möchten. -Mit dem Golay-Filter können wir hohe Frequenz-Anteile in die Berechnung mit einfliessen lassen, anstatt sie abzuschneiden. -Die Bildung eines üblichen Mittelwerts wäre hier weniger geeignet. - -\begin{lstlisting} -freq = sgolayfilt(randn(size(Time)),0,11)*freqstd... -+freqmean; -\end{lstlisting} - -Mit der Frequenz erhalten wir die Winkelbeschleunigung und damit können wir die Amplitude berechnen. - - -\begin{lstlisting} -w = 2 * pi * freq; -a = Amplitude*sin(cumsum(w.*[0;diff(Time)])).*exp(-lambda*Time); -\end{lstlisting} - -Mit der Matlab-Funktion ode45 haben wir eine Funktion gefunden, um die Differentialgleichung aufzulösen. ode45 basiert auf dem Runge-Kutta-Verfahren, einem Einschrittverfahren, bei dem die Lösung ausgehend von einem gegebenen Anfangswert, in einer Näherung gesucht wird. - -\begin{lstlisting} -[T,Y] = ode45(@(t,x)ErzeugteSchwingung(t,x,m,k,d,a,Time),[0 tend], IC, SolverOptions); -\end{lstlisting} - -Grafik einfügen - -In der Grafik erkennen wir in den Sekunden 0 bis 10, dass die Sinuskurve gezackt ist. -Das deutet darauf hin, dass die Frequenz des Erdbebens einen hohen Einfluss auf die Masse des Seismographen hat. -Ab der 10. Sekunde bis zu tend, pendelt sich die Masse in ihre Eigenfrequenz ein und verhält sich unabhängiger vom Erdbeben. - -\subsection{Versuch (bin noch dran)} - -Um den Kalman-Filter auszuprobieren, setzen wir nun Werte ein. -Für die Systemparameter wählen wir m=1.0, D = 0.3 und k = 0.1 und fügen es in die Differentialgleichung - + y = A e^{-\lambda t} \sin(\omega t). +\end{equation} +Dabei ist $A=5$ die anfängliche Amplitude der Schwingung, +die uns die Heftigkeit des Erdebebens beschreibt. +Sie ist vergleichbar mit der Magnitude. +$\lambda$ bezeichnet die Bodendämpfung, für die wir $0.2$ wählen. +Sie ist dafür verantwortlich, dass unser Erdbeben abklingt +und kreiert die bei gedämpften Schwingungen typische Hüllkurve. +Wir nehmen an, dass $\lambda$ ein Materialparameter von geologischen Böden ist. +Die Kreisfrequenz $\omega$ ist durch \begin{equation} - m\ddot x + 2k \dot x + Dx = f -\end{equation} + \omega = 2 \pi f +\end{equation} +gegeben, +wobei die Momentanfrequenz $f = \mathcal N(\mu_f, \sigma_f) $ einer Normalverteilung mit +\begin{equation} + \mu_f = \SI{15}{\hertz} + \qquad \text{und} \qquad + \sigma_f = \SI{10}{\hertz} +\end{equation} +folgt. + +Zusätzlich haben wir $f$ mit einem Savitzky-Golay-Filter gefiltert. +Das Savitzky-Golay-Filter schaut sich immer eine definierte Anzahl von Datenpunkte an +und bildet darüber ein Polynom $n$-ter Ordnung. +In unserer Anwendung schaut sich das Filter, im Sinne eines verschiebbaren Fensters, +jeweils elf aufeinanderfolgende Datenpunkte an +und approximiert diese mit ein Polynom $0$-ter Ordnung, +also einer Konstanten. +Somit erhalten wir mit Matlab-Standardfunktionen einen gleitenden Mittelwert. + +\subsection{Versuch im Standardfall} +Im nächsten Schritt müssen wir sinnvolle Systemparameter für unseren Seismographen definieren. +Eine kurze Recherche zeigt, dass die Masse ein Gewicht von ca.\ \SI{100}{\gram} hat. +Zur Federkonstante D und Dämpfung k konnten wir leider keine brauchbaren Grössen finden und treffen die Annahme, dass $D = 1$ und $k = 0.01$. +Für die Masse definieren wir $m = 0.01$. + +Da unser Seismograph von der Umgebung durch Wind, Temperatur oder menschgemachten Vibrationen beeinflusst wird, müssen wir ein Prozessrauschen definieren. +Die dazugehörige Matrix $Q$ beinhaltet die Standardabweichung für die Position, Geschwindigkeit und äussere Kraft. +Wir nehmen an, dass -ein und erhalten +\begin{equation} + Q = \left( + \begin{array}{ccc} + {\sigma_x }^2& 0& 0 \\ + 0 & {\sigma_v }^2& 0\\ + 0 & 0& {\sigma_f }^2\\ + \end{array}\right)= \left( + \begin{array}{ccc} + {0.00001}^2& 0& 0 \\ + 0 & {0.00001}^2& 0\\ + 0 & 0& {1 }^2\\ + \end{array}\right). +\end{equation} + +Auch für die Messung setzen wir ein Rauschen voraus und definieren \begin{equation} - 1\ddot x + 0.1 \dot x + 0.3x = f -\end{equation} - -\subsection{Matlab Code} - - -\begin{lstlisting} - %% Initialisierte Werte - t0 = 0.00; % Anfangszeit - deltat = 0.01; % Zeitschritt - tend = 50.00; % Endzeit -\end{lstlisting} -Ein natürliches Erdbeben dauert zwischen wenigen Sekunden bis etwa eine Minute an. -50 Sekunden genügen für unsere Daten. -Pro Sekunde erhalten wir 100 Messpunkte, die für den Prozess des Filters eine präzise Anwendung ermöglichen. - -\begin{lstlisting} - % Standard-Abweichungen Prozess - sigmax = 0.05e-3; % Position - sigmav = 0.01e-3; % Geschwindigkeit - sigmaf = 1; % (Äussere) Kraft - - % Standard-Abweichung Messung - sigmam = 0.01e-3; -\end{lstlisting} - -Wir vertrauen dem System und geben kleine Standardabweichungen für die Position, Geschwindigkeit und Kraft ein. -Bei der Messung erwarten wir auch, dass die Sensoren genau funktionieren. -Jedoch hängt das vom Hersteller ab oder muss statistisch ermittelt werden. - - -\begin{lstlisting} - % Systemparameter -m = 1.00; % Masse -D = 0.30; % Federkonstante -k = 0.10; % Dämpfung -\end{lstlisting} -Hier werden die Spezifikationen des Seismographen definiert. - -\begin{lstlisting} -%% Kalmanfilter -% Initialisierung - -% Anfangszustand (Position, Geschwindigkeit, Kraft) -x0 = [0; 0; 0]; - -% Unsicherheit des Anfangszustand -P0 = [0, 0, 0; ... -0, 0, 0; ... -0, 0, 0]; - -% Systemmatrizen -A = [0, 1, 0;... % Dynamikmatrix --D/m, -2*k/m, 1;... -0, 0, 0]; % Ableitungen von f(t) unbekant. Annahme: 0 -A = expm(A * deltat); - -Q = [sigmax^2, 0, 0;... -0, sigmav^2, 0;... -0, 0, sigmaf^2]; % Prozessrauschen (Covarianz) - - -\begin{lstlisting} -% Messprozess -H = [1, 0, 0]; % Messmatrix -R = sigmam^2; % Messrauschen (Könnte durch Versuche bestimmt werden) -\end{lstlisting} -Tritt ein Erdbeben ein, wird die Position der Masse in die Messmatrix eingetragen. - - -I = eye(3); % Identity matrix (Einheitsmatrix) - -\begin{lstlisting} -% Filterprozess - -% Initialisieren der Variablen -N = length(t); % Anzahl Punkte im Einheitsvektor (= Anzahl Messwerte) -xhat = zeros(3, N); % Matrix mit geschätzten Zuständen - -% Index ':' bedeutet: 'alles' -% Index '(1, :)' bedeutet: 'alles aus der 1. Zeile' - -% Anfangszustand setzen -xhat(:, 1) = x0; -P = P0; -\end{lstlisting} - -\begin{lstlisting} - -% Kalman-Matrizen konvergiert. Vorab-Berechnung in 'genügenden' Iterationen -for idx = 1:100 -Ppred = A * P * A' + Q; % Prädizieren der Kovarianz -S = (H * Ppred * H' + R); % Innovationskovarianz -K = Ppred * H' / S; % Filter-Matrix (Kalman-Gain) -P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz -end -\end{lstlisting} - -In diesem Schritt wird die Kovarianz vorhergesagt, mit der Messung verglichen und nach jeder Berechnung aktualisiert. - -\begin{lstlisting} -% Anfangszustand gegeben -% Erster zu berechnender Wert ist der zweite -for idx = 2:N -% Vorhersage -xpred = A * xhat(:, idx-1); % Prädizierter Zustand aus Bisherigem und System -% Ppred = A * P * A' + Q; % Prädizieren der Kovarianz - -% Korrektur -y = xt(idx) - H * xpred; % Messungen/ Kraft aus System - Vohersage -% S = (H * Ppred * H' + R); % Innovationskovarianz -% K = Ppred * H' / S; - -xhat(:, idx) = xpred + K * y; % Aktualisieren des Systemzustands -% P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz -end -\end{lstlisting} - -\subsection{Resultate} -Grafik einfügen -Wir erkennen, dass wir mit dem Kalman-Filter eine gute Methode gefunden haben, die äussere Beschleunigung zu schätzen. Die Schätzung der nächsten Position der Federmasse liegt immer ziemlich nahe der tatsächlichen Messung. Man muss aber auch berücksichtigen, dass die Federschwingung ziemlich kontrolliert verläuft und das Kalman-Filter somit präzise Vorhersagen treffen kann. +R= ({\sigma_x}^2)= +({0.00001}^2). +\end{equation} + +Sind nun die benötigten Systemparameter und Varianzen definiert, +erzeugen wir ein Erdbeben mittels Simulation und schauen, +wie gut das Kalman-Filter die äussere Beschleunigung schätzen kann. + +\subsubsection{Ergebnis} + +Abbildung~\ref{erdbeben:fig:standard-alles} zeigt zuoberst unsere Messwerte, +also die Position der Masse relativ zum Seismografen. +Wir sehen, dass unsere vorher gewählten Parameter eine realistische Erdbebenaufzeichnung erzeugen. +Leiten wir die Position einmal ab, erhalten wir die Geschwindigkeit, +und die zweite Ableitung ergibt uns die Kraft, welche für unsere Aufgabenstellung relevant ist. +Sehr gut ersichtlich ist die typische Hüllkurve, wie wir sie bei einer gedämpften Schwingung erwarten. + +Die blaue Kurve ist die geschätzte äussere Kraft des Kalman-Filters. +Erst wenn wir näher zoomen, erkennen wir in Abbildung~\ref{erdbeben:fig:standard-zoom}, +wie nahe die Schätzung an der idealen Schwingung liegt. + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Standard_alles.PNG} + \caption{Das Position-Zeit-Diagramm zeigt uns die typische Aufzeichnung eines Seismographen während eines Erdbebens. Um die Geschwindigkeit zu erhalten müssen wir die Position einmal ableiten. Ein weiteres Ableiten erzeugt uns die Beschleunigung, respektive die Kraft.} + \label{erdbeben:fig:standard-alles} + \end{center} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Standard_Zoom.PNG} + \caption{Erst das Vergrössern an die Datenpunkte zeigt uns auf, wie gut die Schätzung des Kalman-Filters funktioniert.} + \label{erdbeben:fig:standard-zoom} + \end{center} +\end{figure} + +\subsection{Veränderung der Systemparameter} +Was wir nun testen möchten, sind die Auswirkungen wenn zum Beispiel der Seismograph andere Systemparameter aufweist. +Wir nehmen an, dass sich im Vergleich zum Standardfall die Masse erhöht, die Federkonstante schwächer und die Federdämpfung doppelt so stark wirkt. +Somit gilt neu +\[ +m = 0.05, +\qquad +D = 0.5 +\qquad \text{und} \qquad +k = 0.02. +\] + +Da wir mit dieser Anpassung die Trägheit des Seismogrammes erhöht haben, +erwarten wir eine langsamere Bewegung der Masse, +das heisst die Frequenz wird kleiner. + +Betrachten wir Abbildung~\ref{erdbeben:fig:systemparameter-geaendert}, +können wir diese Erwartung bestätigen. +Zudem bemerken wir eine grössere Auslenkung der Position, +die wir mir durch die höhere Energie der Masse und geringeren Rücklenkkraft der Feder erklären können. + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Systemparameter_geaendert_2.PNG} + \caption{Im Geschwindigkeits-Diagramm erkennen wir, dass sich im Vergleich zum Standardfall, die Auslenkung und Frequenz vergrössert hat. Dies wird mit der Erhöhung der Masse und somit der Trägheit begründet. Auch stellen wir fest, dass die Positionsmessung überwiegend die Eigenfrequenz misst.} + \label{erdbeben:fig:systemparameter-geaendert} + \end{center} +\end{figure} + + +\subsection{Verstärkung des Prozessrauschens} +Falls wir unseren Seismographen in der Nähe einer grösseren Stadt aufstellen, so müssen wir aufgrund der Vibrationen mit einem stärkeren Prozessrauschen rechnen. +Dieses Rauschen beeinflusst die Varianzen der Position und Geschwindigkeit in der Matrix $Q$. +Aus diesem Grund erhöhen wir die Standardabweichungen in der Matrix $Q$ um den Faktor $100$. +Die Auswertung in Abbildung~\ref{erdbeben:fig:prozessrauschen-geaendert} zeigt auf, dass das Kalman-Filter die Schätzung der Kraft nur gering an den Messwerten anpasst. + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Prozessrauschen_geaendert.PNG} + \caption{Mit dem Erhöhen des Prozessrauschens gehen wir von einer grösseren Unsicherheit der Systemmatrix aus. Aus diesem Grund folgt das Filter vor allem den Messwerten, was sichtbare Folgen für die Schätzkurve im Kraft-Zeit-Diagramm hat. Hier möchte das Filter auch den Messwerten folgen. Da wir aber für die Kraft keine Messwerte aufzeichnen, erhalten wir eine sehr schwache Kurve} + \label{erdbeben:fig:prozessrauschen-geaendert} + \end{center} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG} + \caption{Die Position kann immernoch präzise geschätzt werden und die Ableitung zur Geschwindigkeit ergibt gute Resultate. Jedoch ist die Schätzkurve der Kraft sehr weit von der idealen Kurve entfernt und nicht nutzbar.} + \label{erdbeben:fig:prozessrauschen-geaendert-zoom} + \end{center} +\end{figure} + +\subsection{Verstärkung des Messrauschens} +Als letztes verstärken wir das Messrauschen um den Faktor $100$ und belassen wieder den Rest wie im Standardfall. +Wie man eigentlich schon erwarten kann, zeigt uns die Abbildung~\ref{erdbeben:fig:messrauschen-geaendert}, dass das Signal des Messsensors vom Messrauschen gestört wird. +Weil die Messung somit ungenau wird, kann das Kalman-Filter nicht mehr genau arbeiten und produziert eine ungenaues Resultat. + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Messrauschen_geaendert.PNG} + \caption{Im Kraft-Zeit-Diagramm erhalten wir nur bis ca. $t = 10$ gute Schätzwerte. Von $t = 10$ bis $t = 30$ wirkt das Messrauschen zu stark und erhalten keine brauchbaren Werte mehr} + \label{erdbeben:fig:messrauschen-geaendert} + \end{center} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Messrauschen_geaendert_zoom.PNG} + \caption{Im Position-Zeit-Diagramm erhielten wir bis jetzt immer genaue Schätzungen. Mit einem starken Messrauschen fällt es nun dem Filter schwerer, präzise Werte zu generieren. Die Nahaufnahme im Kraft-Zeit-Diagramm bestätigt uns aber, dass die Messfehler zu gross sind, um ein klares Bild über die äussere Kraft zu erhalten.} + \label{erdbeben:fig:messrauschen-geaendert_zoom} + \end{center} +\end{figure} + +\subsection{Zusammenfassung} +Wir haben uns zum Ziel gesetzt, die äussere Beschleunigung $a(t)$, bzw. die Kraft $f(t)$ eines Erdbebens zu ermitteln. + +Mit der Software Matlab haben wir einen virtuellen Seismographen gebaut und ein künstliches Erdbeben erzeugt. +Der Seismograph war fähig die Position der Masse während der Einwirkung des Erdbebens aufzuzeichnen. +$a(t)$ kann zwar nicht mit Sensoren gemessen werden, jedoch erhalten wir $a(t)$ durch zweifaches Ableiten. +Da wir so aber die innere Beschleunigung erhalten, mussten wir das Kalman-Filter anwenden. +Das Kalman-Filter half uns die äussere Beschleunigung zu schätzen und lieferte erstaunlich genaue Werte. + +Schlussendlich haben wir aufgezeigt, das Veränderungen an den System- und Rauschparametern die Genauigkeit und Zuverlässigkeit des Kalman-Filters beeinträchtigen. + diff --git a/buch/papers/erdbeben/images/Makefile b/buch/papers/erdbeben/images/Makefile new file mode 100644 index 0000000..3c82cb7 --- /dev/null +++ b/buch/papers/erdbeben/images/Makefile @@ -0,0 +1,15 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +all: standard.pdf messrauschen_geaendert.pdf prozessrauschen_geaendert.pdf + +standard.pdf: standard.tex + pdflatex standard.tex + +messrauschen_geaendert.pdf: messrauschen_geaendert.tex + pdflatex messrauschen_geaendert.tex + +prozessrauschen_geaendert.pdf: prozessrauschen_geaendert.tex + pdflatex prozessrauschen_geaendert.tex diff --git a/buch/papers/erdbeben/images/messrauschen_geaendert.pdf b/buch/papers/erdbeben/images/messrauschen_geaendert.pdf Binary files differnew file mode 100644 index 0000000..5056dd0 --- /dev/null +++ b/buch/papers/erdbeben/images/messrauschen_geaendert.pdf diff --git a/buch/papers/erdbeben/images/messrauschen_geaendert.tex b/buch/papers/erdbeben/images/messrauschen_geaendert.tex new file mode 100644 index 0000000..a5a7509 --- /dev/null +++ b/buch/papers/erdbeben/images/messrauschen_geaendert.tex @@ -0,0 +1,61 @@ +% +% messrauschen_geaendert.tex -- Kombination der Messrauschen-Bilder +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\node at (0,0) {\includegraphics[width=14cm]{../Messrauschen_geaendert.PNG}}; + +\def\yten{-2.06} +\def\yfifteen{0.16} + +\def\links{12.2} +\def\rechts{14.2} + +\pgfmathparse{(\yfifteen-(\yten))/5} +\xdef\m{\pgfmathresult} +\xdef\b{\yten} + +\pgfmathparse{\m*(\links-10)+(\b)} +\xdef\Links{\pgfmathresult} + +\pgfmathparse{\m*(\rechts-10)+(\b)} +\xdef\Rechts{\pgfmathresult} + +\begin{scope}[yshift=-9cm] +\node at (0,0) {\includegraphics[width=14cm]{../Messrauschen_geaendert_zoom.PNG}}; +\end{scope} + +\def\breite{7} +\def\hoehe{2} + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\def\unten{-4.15} + +\draw[line width=0.7pt] (\Links,\unten) rectangle (\Rechts,4.15); +\draw[line width=0.7pt] (\Links,\unten) -- (\Links,{\unten-0.05}) + -- (-6.45,-4.6) -- (-6.45,-4.9); +\draw[line width=0.7pt] (\Rechts,\unten) -- (\Rechts,{\unten-0.05}) + -- (6.86,-4.6) -- (6.86,-4.9); +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/erdbeben/images/prozessrauschen_geaendert.pdf b/buch/papers/erdbeben/images/prozessrauschen_geaendert.pdf Binary files differnew file mode 100644 index 0000000..e0bf605 --- /dev/null +++ b/buch/papers/erdbeben/images/prozessrauschen_geaendert.pdf diff --git a/buch/papers/erdbeben/images/prozessrauschen_geaendert.tex b/buch/papers/erdbeben/images/prozessrauschen_geaendert.tex new file mode 100644 index 0000000..ad4dcf9 --- /dev/null +++ b/buch/papers/erdbeben/images/prozessrauschen_geaendert.tex @@ -0,0 +1,61 @@ +% +% prozessrauschen_geaendert.tex -- Kombination der Prozessrauschen-Bilder +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\node at (0,0) {\includegraphics[width=14cm]{../Prozessrauschen_geaendert.PNG}}; + +\def\yten{-2.1} +\def\yfifteen{0.12} + +\def\links{13.27} +\def\rechts{14.2} + +\pgfmathparse{(\yfifteen-(\yten))/5} +\xdef\m{\pgfmathresult} +\xdef\b{\yten} + +\pgfmathparse{\m*(\links-10)+(\b)} +\xdef\Links{\pgfmathresult} + +\pgfmathparse{\m*(\rechts-10)+(\b)} +\xdef\Rechts{\pgfmathresult} + +\begin{scope}[yshift=-9cm] +\node at (0,0) {\includegraphics[width=14cm]{../Prozessrauschen_geaendert_zoom.PNG}}; +\end{scope} + +% Gitter +\def\breite{7} +\def\hoehe{2} +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\def\unten{-4.15} + +\draw[line width=0.7pt] (\Links,\unten) rectangle (\Rechts,4.18); +\draw[line width=0.7pt] (\Links,\unten) -- (\Links,{\unten-0.05}) + -- (-6.62,-4.6) -- (-6.62,-4.9); +\draw[line width=0.7pt] (\Rechts,\unten) -- (\Rechts,{\unten-0.05}) + -- (6.80,-4.6) -- (6.80,-4.9); + +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/erdbeben/images/standard.pdf b/buch/papers/erdbeben/images/standard.pdf Binary files differnew file mode 100644 index 0000000..f2ca85e --- /dev/null +++ b/buch/papers/erdbeben/images/standard.pdf diff --git a/buch/papers/erdbeben/images/standard.tex b/buch/papers/erdbeben/images/standard.tex new file mode 100644 index 0000000..74ac7a1 --- /dev/null +++ b/buch/papers/erdbeben/images/standard.tex @@ -0,0 +1,64 @@ +% +% standard.tex -- Kombination der Standard-Bilder +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\node at (0,0) {\includegraphics[width=14cm]{../Standard_alles.PNG}}; + +\def\yten{-2.12} +\def\yfifteen{0.1} + +\def\links{12.5} +\def\rechts{13.4} + +\pgfmathparse{(\yfifteen-(\yten))/5} +\xdef\m{\pgfmathresult} +\xdef\b{\yten} + +%\node at (0,7) {$m=\m$}; \node at (0,8) {$b=\b$}; + +\pgfmathparse{\m*(\links-10)+(\b)} +\xdef\Links{\pgfmathresult} + +\pgfmathparse{\m*(\rechts-10)+(\b)} +\xdef\Rechts{\pgfmathresult} + +\begin{scope}[yshift=-9cm] +\node at (0,0) {\includegraphics[width=14cm]{../Standard_Zoom.PNG}}; +\end{scope} + +\def\breite{7} +\def\hoehe{2} + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\def\unten{-4.15} + +\draw[line width=0.7pt] (\Links,\unten) rectangle (\Rechts,4.18); +\draw[line width=0.7pt] (\Links,\unten) -- (\Links,{\unten-0.05}) + -- (-6.36,-4.6) -- (-6.36,-4.9); +\draw[line width=0.7pt] (\Rechts,\unten) -- (\Rechts,{\unten-0.05}) + -- (6.87,-4.6) -- (6.87,-4.9); + +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/ifs/teil0.tex b/buch/papers/ifs/teil0.tex index 2a803d6..c37c704 100644 --- a/buch/papers/ifs/teil0.tex +++ b/buch/papers/ifs/teil0.tex @@ -4,7 +4,7 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Einleitung \label{ifs:section:teil0}} -\rhead{Was ist ein Iteriertes Funktionsschema} +\rhead{Was ist ein Iteriertes Funktionsschema?} Mit der Hilfe von iterierten Funktionsschemata (IFS) können mit nur wenigen affinen Funktionen komplexe Bilder beschrieben werden. \index{iterierte Funktionsschemata}% \index{Funktionschemata, iterierte}% diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex index 360a2c0..042d765 100644 --- a/buch/papers/ifs/teil2.tex +++ b/buch/papers/ifs/teil2.tex @@ -5,7 +5,7 @@ % \section{Fraktale mit IFS \label{ifs:section:teil2}} -\rhead{Teil 2} +\rhead{Fraktale mit iterierten Funktionensystemen} Wollen wir nun eine bestimmte Art anschauen, wie man Fraktale erzeugen kann. Im Beispiel auf Seite \pageref{ifs:trinagle} haben wir ein Dreieck aus 4 skalierten Kopien zusammengefügt. Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sogenannten Sierpinski-Dreiecks in Abbildung \ref{ifs:sierpinski10}. diff --git a/buch/papers/mceliece/fazit.tex b/buch/papers/mceliece/fazit.tex index b53328f..3714d31 100644 --- a/buch/papers/mceliece/fazit.tex +++ b/buch/papers/mceliece/fazit.tex @@ -5,7 +5,6 @@ % \section{Fazit \label{mceliece:section:fazit}} -\rhead{Fazit} Ein kurzer Vergleich des McEliece-Systems mit dem oft verwendeten RSA-System soll zeigen, wo dessen Vor- und Nachteile liegen. @@ -16,6 +15,7 @@ wird Redundanz benötigt, weshalb dessen Kanalefizienz (Nutzbits/Übertragungsbits) sinkt. \index{Kanaleffizienz}% +\rhead{Fazit} Die Schlüsselgrösse des McEliece-Systems ist deshalb so riesig, weil es sich um eine zweidimensionale Matrix handelt, währenddem RSA mit nur zwei Skalaren auskommt. \index{Schlüsselgrösse}% Das McEliece-System benötigt dafür weniger Rechenaufwand beim Verschlüsseln/Entschlüsseln, diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 4d6c18d..3802820 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -86,8 +86,8 @@ Die Verschlüsselung soll mittels eines numerischen Beispiels demonstriert werde Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four} beschrieben. \begin{itemize} \item Daten- und Fehlervektor - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \[d_4= \begin{pmatrix} 1\\ @@ -107,11 +107,12 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 \end{pmatrix}. \] - \end{itemize} +% \end{itemize} \item Private Matrizen: - \begin{itemize} - \item[] - \[S_4= +\begin{gather*} +% \begin{itemize} +% \item[] + S_4= \begin{pmatrix} 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\\ @@ -125,9 +126,8 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ \end{pmatrix}, - \] - \item[] - \[ + \\ +% \item[] G_{7,4}= \begin{pmatrix} 1 & 0 & 0 & 0\\ @@ -138,9 +138,8 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{pmatrix}, - \] - \item[] - \[ + \\ +% \item[] P_7= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0\\ @@ -162,13 +161,14 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}. - \] - \end{itemize} + \\ +% \end{itemize} +\end{gather*} \item Öffentlicher Schlüssel: \index{Schlüssel, öffentlicher}% -\index{öffentlicher Schlüssel}% - \begin{itemize} - \item[] +\index{offentlicher Schlüssel@öffentlicher Schlüssel}% +% \begin{itemize} +% \item[] \begin{align*} K_{7,4}&=P_{7}\cdot G_{7,4}\cdot S_{4}=\\ \begin{pmatrix} %k @@ -209,10 +209,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \item Verschlüsselung: - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} c_7&=K_{7,4}\cdot d_4 + e_7=\\ \begin{pmatrix} %c @@ -253,10 +253,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \item Entschlüsselung (Permutation rückgängig machen): - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} c_{7}''&=P_7^{-1}\cdot c_7=\\ \begin{pmatrix} %c'' @@ -290,10 +290,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \item Entschlüsselung (Bitfehlerkorrektur mit Linearcode): - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} c_{7}'&=\text{Linear-Code-Decoder($c''_7$)}=\\ \begin{pmatrix} %c' @@ -315,10 +315,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \text{)} . \end{align*} - \end{itemize} +% \end{itemize} \item Entschlüsselung (Umkehrung des $S_4$-Matrix-Effekts): - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} d'_{4}&=S_{4}^{-1} \cdot c'_4 \,(= d_4)\\ \begin{pmatrix} @@ -343,7 +343,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \end{itemize} \subsection{7/4-Code @@ -368,7 +368,6 @@ Damit diese Multiplikation mit Matrizen ausgeführt werden kann, werden die Poly Auch das Datenpolynom wird mit einem Vektor dargestellt: $P_d = d_0 \cdot x^0 + d_1 \cdot x^1 + d_2 \cdot x^2 + d_3 \cdot x^3 \implies [d_0, d_1, d_2, d_3] = d_4$. Der Vektor $g_4$ wird nun in die sogenannte Generatormatrix $G_{7,4}$ gepackt, sodass die Polynommultiplikation mit $d_4$ mittels Matrixmultiplikation realisiert werden kann: - \[ c_7=G_{7,4} \cdot d_4= \begin{pmatrix} diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index 3ffc24c..7637854 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -17,7 +17,7 @@ C_{ij} = \sum_{k=1}^n A_{ik} B_{kj}. \label{multiplikation:eq:MM} \end{equation} Grafisch kann die Matrizenmultiplikation $\mathbf{AB}=\mathbf{C}$ wie in Abbildung \ref{multiplikation:fig:mm_viz} visualisiert werden. -\index{Matrizenmultiplikation}% +\index{Matrixmultiplikation}% \index{Multiplikation, Matrizen-}% Im Fall einer Matrizengr\"osse von $2\times 2$ kann die Matrixgleichung \begin{equation} diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 2531bbb..578833b 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -517,7 +517,6 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \end{figure} \section{Fazit} -\rhead{Fazit} Wie man im Abschnitt \ref{multiplikation:section:Implementation} sehen kann, sind die gezeigten Algorithmen trotz der theoretisch geringeren Zeitkomplexitäten den Implementationen der numerischen Bibliotheken klar unterlegen. Ein optimierter Speicherzugriff hat einen weitaus grösseren Einfluss auf die Laufzeit als die Zeitkomplexität des Algorithmus. @@ -528,3 +527,5 @@ Denke man an sehr kleine Mikrocontroller ohne Floatingpoint Recheneinheiten oder Der Overhead der gezeigten Algorithmen ist in allen Fällen grösser als bei der Standardmethode (z.B. sieben rekursive Aufrufe gegenüber drei \texttt{for}-Schleifen). Um diesem entgegenzuwirken muss der Laufzeitunterschied zwischen Addition und Multiplikation gross genug sein. Wenn dies gegeben ist und dazu noch grosse Matritzen multipliziert werden, kann die Verwendung der Algorithmen von Strassen oder Winograd zu einer Senkung der Laufzeit führen. + +\rhead{Fazit} diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex index e4e968a..9ad64b4 100644 --- a/buch/papers/munkres/teil2.tex +++ b/buch/papers/munkres/teil2.tex @@ -5,13 +5,13 @@ % \section{Schwierigkeit der Lösung \label{munkres:section:teil2}} -\rhead{Schwierigkeit der Lösung} Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. \index{Transversale einer Matrix}% Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. +\rhead{Schwierigkeit der Lösung} In einer $n\times n$-Matrix gibt es genau so viele Möglichkeiten, die Zeilen- bzw.~Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Ausser bei kleinen Matrizen ist es daher nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer $10\times 10$-Matrix gibt es nahezu 3.63 Millionen ($10!=3628800$) zu berücksichtigende Permutationen. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 500216a..8a0d2cb 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -5,7 +5,6 @@ % \section{Der Munkres-Algorithmus oder die ungarische Methode \label{munkres:section:teil3}} -\rhead{Ungarische Methode} Mit der ungarischen Methode können also Optimierungsprobleme gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. @@ -13,6 +12,8 @@ Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der Gesamtgewinn maximiert werden kann. +\rhead{Ungarische Methode} + \subsection{Geschichte \label{munkres:subsection:malorum}} Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht. @@ -20,7 +21,7 @@ Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker basierte: Dénes Kőnig und Jenő Egerváry. -\index{Kőnig, Dénes}% +\index{Konig, Denes@Kőnig, Dénes}% \index{Egerváry, Jenő}% \index{Munkres, James}% James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest, diff --git a/buch/papers/punktgruppen/crystals.tex b/buch/papers/punktgruppen/crystals.tex index 1ba5466..4def071 100644 --- a/buch/papers/punktgruppen/crystals.tex +++ b/buch/papers/punktgruppen/crystals.tex @@ -1,4 +1,5 @@ \section{Kristalle} +\rhead{Kristalle} \index{Kristalle}% Eine nicht allzu häufig gestellte Frage ist, wie ein Kristall definiert ist. Um zu klären, was ein Kristall mit Symmetrien zu tun hat, ist jedoch genau diese Frage äusserst relevant. diff --git a/buch/papers/punktgruppen/intro.tex b/buch/papers/punktgruppen/intro.tex index f11a346..c537f69 100644 --- a/buch/papers/punktgruppen/intro.tex +++ b/buch/papers/punktgruppen/intro.tex @@ -1,5 +1,5 @@ \section{Einleitung} - +\rhead{Einleitung} Es gibt viele Möglichkeiten sich in Kristallen zu verlieren. \index{Kristall}% Auch wenn man nur die mathematischen Betrachtungsweisen berücksichtigt, hat man noch viel zu viele Optionen, sich mit Kristallen zu beschäftigen. diff --git a/buch/papers/punktgruppen/piezo.tex b/buch/papers/punktgruppen/piezo.tex index cc4272b..eddd8a5 100644 --- a/buch/papers/punktgruppen/piezo.tex +++ b/buch/papers/punktgruppen/piezo.tex @@ -1,4 +1,5 @@ \section{Piezoelektrizität} +\rhead{Piezoelektrizität} \index{Piezoelektrizität}% Die Piezoelektrizität ist die spannende Eigenschaft, dass gewisse Kristalle eine elektrische Spannung erzeugen, wenn mechanischer Druck auf sie ausgeübt wird. \index{elektrische Spannung}% diff --git a/buch/papers/punktgruppen/symmetry.tex b/buch/papers/punktgruppen/symmetry.tex index ec06046..dd37ba9 100644 --- a/buch/papers/punktgruppen/symmetry.tex +++ b/buch/papers/punktgruppen/symmetry.tex @@ -1,4 +1,5 @@ \section{Symmetrie} +\rhead{Symmetrie} Das Wort Symmetrie ist sehr alt und hat sich seltsamerweise von seinem ursprünglichen griechischen Wort \(\mathrm{\Sigma\upsilon\mu\mu\varepsilon\tau\rho\iota\alpha}\)\footnote{\emph{Symmetr\'ia}: ein gemeinsames Mass habend, gleichmässig,verhältnismässig} fast nicht verändert. In der Alltagssprache mag es ein locker definierter Begriff sein, in der Mathematik hat Symmetrie jedoch eine sehr präzise Bedeutung. diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex index 9bb1d99..12bfe74 100644 --- a/buch/papers/reedsolomon/anwendungen.tex +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -5,18 +5,18 @@ % \section{Anwendungen des Reed-Solomon-Codes \label{reedsolomon:section:anwendung}} -\rhead{Anwendungen} In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie funktionieren. In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt. All diese Anwendungen teilen das gleiche Problem: Die Daten können nur durch einen höchstwahrscheinlich fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode, an diese Daten zu kommen, als über diesen Kanal. -In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpaketen diese einfach noch einmal innert wenigen Millisekunden angefordert werden können. +\rhead{Anwendungen} +In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverlusten oder beschädigt empfangenen Datenpaketen diese einfach noch einmal innert weniger Millisekunden angefordert werden können. \index{Paketverluste}% In der Raumfahrt ist dies nicht möglich, da aufgrund der beschränkten Speichermöglichkeit die gesammelten Daten so rasch wie möglich zur Erde gesendet werden. \index{Raumfahrt}% -Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen. +Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden, bis sie beim Empfänger ankommen. Fehlerhafte Daten können also auf Grund der Zeitverzögerung nicht mehr angefordert werden. Bei CDs oder DVDs gibt es zwar kein zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. @@ -26,7 +26,7 @@ Bei CDs oder DVDs gibt es zwar kein zeitliches Problem, jedoch erschweren Kratze \index{Digital Video Disk}% Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden, wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. -Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. +Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann, wenn der Code nicht mehr vollständig vorhanden ist. \index{QR-Code}% %Wie man sieht, eignen sich Reed-Solomon-Codes vor allem für Anwendungen, bei der die Informationen nicht auf einen Anderen Weg beschafft werden kann. @@ -39,11 +39,11 @@ Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch % da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. % -Obwohl alle diese Codes nach dem gleichen Prinzip arbeiten gibt es starke Unterschiede in deren Funktionsweise. -Dies kommt vor allem daher, da die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitstellt wird, auf denen die Codes implementiert wurden. -Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um möglichst effizient zu arbeiten. +Obwohl all diese Codes nach dem gleichen Prinzip arbeiten, gibt es starke Unterschiede in deren Funktionsweise. +Dies kommt vor allem daher, dass die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitgestellt werden, auf denen die Codes implementiert wurden. +Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen, um möglichst effizient zu arbeiten. -Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet man die Notation ($n$,$k$), wobei $n$ die Grösse des Nachrichtenblocks angibt und $k$ die Anzahl der Stellen, die für Nutzdaten gebraucht werden können. +Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben, verwendet man die Notation ($n$,$k$), wobei $n$ die Grösse des Nachrichtenblocks angibt und $k$ die Anzahl der Stellen, die für Nutzdaten gebraucht werden können. %Dies kommt vor allem daher, da diese Codes an ihre Hardware gebunden sind, auf denen sie implementiert worden sind. %Deshalb wurden diese Codes stark optimiert damit sie möglichst Effizient arbeiten können. @@ -78,20 +78,20 @@ Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet \begin{figure} \centering \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Voyager_Sonde} - \caption{Mit einer Entfernung von über 22.8 Milliarden Kilometer ist die Voyager 1 Raumsonde das am weitesten entfernte, von Menschen erschaffene Objekt. Obwohl ihre Schwestersonde Voyager 2 zuerst ins All gestartet wurde befindet Sie sich ``nur'' 19 Milliarden Kilometer weit weg von der Erde. Aufgrund abnehmender Batterieleistung werden die beiden Sonden ihre wissenschaftlichen Aktivitäten etwa 2025 einstellen, bleiben aber bis in die 2030er mit uns in Kontakt.} + \caption{Mit einer Entfernung von über 22.8 Milliarden Kilometer ist die Voyager 1 Raumsonde das am weitesten entfernte, von Menschen erschaffene Objekt. Obwohl ihre Schwestersonde Voyager 2 zuerst ins All gestartet wurde, befindet sie sich ``nur'' 19 Milliarden Kilometer weit weg von der Erde. Aufgrund abnehmender Batterieleistung werden die beiden Sonden ihre wissenschaftlichen Aktivitäten etwa 2025 einstellen, bleiben aber bis in die 2030er Jahre mit uns in Kontakt.} \index{Voyager 1 und 2}% \label{fig:voyager} \end{figure} \subsection{Raumfahrt} -Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden (siehe Abbildung \ref{fig:voyager}) werden mit einem ($255$,$233$)-Code +Obwohl Reed-Solomon-Codes bereits in den 1960er Jahren entwickelt wurden, fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden (siehe Abbildung \ref{fig:voyager}) werden mit einem ($255$,$233$)-Code \index{Voyager Raumsonde}% \index{NASA}% codiert. Der Nachrichtenblock hat somit eine Länge von $255$ Zahlen, wovon $233$ als Nutzlast zur Verfügung stehen. -Damit ist es möglich bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. +Damit ist es möglich, bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. Der codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut codiert und anschliessend gesendet. -Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, +Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage, Fehler zu korrigieren, codiert seine Information aber auf eine andere Weise. Aus jedem unterteilten Block wird vor dem Versenden ein Paritätsbit erzeugt und dem Block angehängt. Anhand dieses Paritätsbits überprüft der Empfänger, ob bei der Übertragung der Block beschädigt wurde. Ist dies der Fall, wird der Block bei der Decodierung nicht beachtet. Diese so entstandenen ``Lücken'' im Datenstrom werden wiederum vom Reed-Solomon-Code korrigiert. Dieses Zusammenspiel beider Codes garantiert so eine hohe Robustheit gegenüber Übertragungsfehler. \begin{figure} @@ -102,7 +102,7 @@ codiert seine Information aber auf eine andere Weise. Aus jedem unterteilten Blo \subfigure[]{ \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc_zoomed_in} } - \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das Einpressen oder Einbrennen von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} + \caption{CDs kamen 1982 auf den Markt. Sie funktionieren durch das Einpressen oder Einbrennen von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} \label{fig:cd} \end{figure} % @@ -122,11 +122,11 @@ codiert seine Information aber auf eine andere Weise. Aus jedem unterteilten Blo \subsection{CD/DVD} -Compact discs verwenden sogar zwei ineinander verschachtelte Reed-Solomon-Codes, einen (32,28)-Code und einen (28,24)-Code. +Compact Discs verwenden sogar zwei ineinander verschachtelte Reed-Solomon-Codes, einen (32,28)-Code und einen (28,24)-Code. Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle Zusammenspielen dieser beiden Codes wird auch Cross-interleaved Reed-Solomon-Code (CIRC) genannt. \index{CIRC}% \index{Cross-interleaved Reed-Solomon code}% -Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehlern oder Verschmutzung auf der Disc. Bei CDs sind diese in der Lage, bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5mm$) zu erkennen und zu korrigieren. +Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehlern oder Verschmutzung auf der Disc. Bei CDs sind diese in der Lage, bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5$mm) zu erkennen und zu korrigieren. Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeblöcken. Die DVD verwendet einen (208,192)-Code und einen (182,172)-Code. @@ -147,7 +147,7 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb % \subfigure[]{ % \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} % } - \caption{Anhand der grösse würde man darauf schliessen, dass bei (a) mehr Informationen codiert sind als bei (b). Tatsächlich aber beinhalten beide Codes die gleiche Information. Das liegt daran, da die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Der höchste Fehlerkorrektur-Level, der bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Der kleinste Level schafft etwa 7\%, der in (b) veranschaulicht wird. Da die Grösse also nichts über die Menge an Daten aussagt, könnte es sich bei (a) auch um einen Code mit viel Nutzdaten und kleinem Fehlerkorrektur-Level handeln. Der Unterschied ist von Auge nicht sichtbar.} + \caption{Anhand der Grösse würde man darauf schliessen, dass bei (a) mehr Informationen codiert sind als bei (b). Tatsächlich aber beinhalten beide Codes die gleiche Information. Das liegt daran, dass die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Das höchste Fehlerkorrektur-Level, das bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Das kleinste Level schafft etwa 7\%, das in (b) veranschaulicht wird. Da die Grösse also nichts über die Menge an Daten aussagt, könnte es sich bei (a) auch um einen Code mit viel Nutzdaten und kleinem Fehlerkorrektur-Level handeln. Der Unterschied ist von Auge nicht sichtbar.} \label{fig:qr} \end{figure} @@ -165,19 +165,19 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb \subfigure[]{ \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} } - \caption{Während (a) noch einen unveränderten QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich die Fehlerkorrekturfähigkeit je nach Grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} + \caption{Während (a) noch einen unveränderten QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt ein Teil des Codes durch ein Logo verdeckt wird, schränkt sich die Fehlerkorrekturfähigkeit je nach Grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage, etwa 9\% des Codes zu rekonstruieren.} \label{fig:designqr} \end{figure} \subsection{QR-Codes} \index{QR-Code}% -Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. +Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel die Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion}, nur der QR-Code in einem $\mathbb{F}_{256}$ Körper arbeitet. Die physische Grösse eines Codes ist stark abhängig von der Menge an codierten Daten sowie dem verwendeten Fehlerkorrektur-Level. -Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein QR-Code enthält. +Es ist so auf den ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein QR-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes zweckentfremdet werden. \index{Designed-QR-Code}% -Dabei wird z.~B.~das Firmenlogo oder einen Schriftzug über den QR-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist in Abbildung \ref{fig:designqr} zu finden. +Dabei wird z.~B.~das Firmenlogo oder ein Schriftzug über den QR-Code gelegt, ohne dass die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist in Abbildung \ref{fig:designqr} zu finden. % diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 02484e0..037fba7 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -5,14 +5,14 @@ % \section{Codierung eines Beispiels \label{reedsolomon:section:codebsp}} -\rhead{Codierung eines Beispiels} Um die Funktionsweise eines Reed-Solomon-Codes besser zu verstehen, werden wir die einzelnen Probleme und ihre Lösungen anhand eines Beispiels betrachten. Da wir in endlichen Körpern rechnen, werden wir zuerst solch einen Körper festlegen. Dabei müssen wir die Definition \ref{buch:endlichekoerper:def:galois-koerper} berücksichtigen, die besagt, dass nur Primzahlen für endliche Körper in Frage kommen. Wir legen für unser Beispiel den endlichen Körper $\mathbb{F}_{q}$ mit $q = 11$ fest. -Zur Hilfestellung zum Rechnen in $\mathbb{F}_{11}$ können die beiden Tabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} hinzugezogen werden. Diese Tabellen enthalten die Resultate der arithmetischen Operationen im Körper $\mathbb{F}_{11}$, die durchgeführt werden können. +Zur Hilfestellung beim Rechnen in $\mathbb{F}_{11}$ können die beiden Tabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} hinzugezogen werden. Diese Tabellen enthalten die Resultate der arithmetischen Operationen im Körper $\mathbb{F}_{11}$, die durchgeführt werden können. Aus der Definition der endlichen Körper (ersichtlich auch in den Tabellen) folgt, dass uns nur die Zahlen \[\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}\] zur Verfügung stehen und somit $11 = 0$ gelten muss. +\rhead{Codierung eines Beispiels} % OLD TEXT %Alle folgenden Berechnungen wurden mit den beiden Restetabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} durchgeführt. %Aus den Tabellen folgt auch, dass uns nur die Zahlen \[\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}\] zur Verfügung stehen. @@ -26,7 +26,7 @@ Der Nachrichtenblock im Beispiel besteht aus \[ n = q - 1 = 10 \text{ Zahlen}, \] -wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu codieren, so stellen wir fest, dass wir wieder Null an der gleichen Stelle erhalten und somit wäre die Codierung nicht eindeutig. +wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu codieren, stellen wir fest, dass wir wieder null an der gleichen Stelle erhalten und somit wäre die Codierung nicht eindeutig. % Notes %Da bei allen Codes, die codiert werden wird an der gleichen Stelle eine Nullstelle auftreten. @@ -37,28 +37,28 @@ wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu cod %n = q - 1 = 10 \text{ Zahlen}. %\] -Im nächsten Schritt bestimmen wir, wie viele Fehler $t$ maximal während der Übertragung auftreten dürfen, damit wir sie noch korrigieren können. +Im nächsten Schritt bestimmen wir, wie viele Fehler $t$ während der Übertragung maximal auftreten dürfen, damit wir sie noch korrigieren können. Unser Beispielcode sollte in der Lage sein \[ t = 2 \] Fehlerstellen korrigieren zu können. -Die Grösse des Nutzdatenteils hängt von der Grösse des Nachrichtenblocks sowie der Anzahl der Fehlerkorrekturstellen ab. Je robuster der Code sein muss, desto weniger Platz für Nutzdaten $k$ bleibt in der Nachricht übrig. -Bei maximal 2 Fehler können wir noch +Die Grösse des Nutzdatenteils hängt von der Grösse des Nachrichtenblocks sowie der Anzahl der Fehlerkorrekturstellen ab. Je robuster der Code sein muss, desto weniger Platz bleibt für Nutzdaten $k$ in der Nachricht übrig. +Bei maximal 2 Fehlern können wir noch \[ k = n - 2t = 6\text{ Zahlen} \] übertragen. -Zusammenfassend haben wir einen Nachrichtenblock mit der Länge von 10 Zahlen definiert, der 6 Zahlen als Nutzlast beinhaltet und in der Lage ist, aus 2 fehlerhafte Stellen im Block die ursprünglichen Nutzdaten zu rekonstruieren. Zudem werden wir im Weiteren feststellen, dass dieser Code maximal vier Fehlerstellen erkennen, diese aber nicht rekonstruieren kann. +Zusammenfassend haben wir einen Nachrichtenblock mit der Länge von 10 Zahlen definiert, der 6 Zahlen als Nutzlast beinhaltet und in der Lage ist, aus 2 fehlerhaften Stellen im Block die ursprünglichen Nutzdaten zu rekonstruieren. Zudem werden wir im Weiteren feststellen, dass dieser Code maximal vier Fehlerstellen erkennen, diese aber nicht rekonstruieren kann. Wir legen nun für das Beispiel die Nachricht \[ m = [0,0,0,0,4,7,2,5,8,1] \] fest, die wir gerne an einen Empfänger übertragen möchten, wobei die vorderen vier Stellen für die Fehlerkorrektur zuständig sind. -Solange diese Stellen vor dem Codieren und nach dem Decodieren den Wert null haben, so ist die Nachricht fehlerfrei übertragen worden. +Solange diese Stellen vor dem Codieren und nach dem Decodieren den Wert null haben, ist die Nachricht fehlerfrei übertragen worden. Da wir in den folgenden Abschnitten mit Polynomen arbeiten, stellen wir die Nachricht auch noch als Polynom \[ @@ -77,7 +77,7 @@ dar. \label{reedsolomon:subsection:diskFT}} Im vorherigen Abschnitt \ref{reedsolomon:section:dtf} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulersche Zahl $e$ in endlichen Körpern nicht existiert. -Wir wählen deshalb eine Zahl $a$, die die gleichen Aufgaben haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken. +Wir wählen deshalb eine Zahl $a$, die die gleiche Aufgabe haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken. Dazu ändern wir die Darstellung von \[ \mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\} @@ -119,17 +119,18 @@ in die von $a$ abhängige Schreibweise \index{Einheitswurzel, primitiv}% Wenn wir jetzt Zahlen von $\mathbb{F}_{11}$ an Stelle von $a$ einsetzen, erhalten wir \begin{center} -\begin{tabular}{c c c c c c c} -$a = 1$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 2$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 2, 4, 8, 5, 10, 9, 7, 3, 6\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 3$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 3, 9, 5, 4, 1, 3, 9, 5, 4\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 4$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 4, 5, 9, 3, 1, 4, 5, 9, 3\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 5$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 5, 3, 4, 9, 1, 5, 3, 4, 9\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 6$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 6, 3, 7, 9, 10, 5, 8, 4, 2\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 7$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 7, 5, 2, 3, 10, 4, 6, 9, 8\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 8$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 8, 9, 6, 4, 10, 3, 2, 5, 7\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 9$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 9, 4, 3, 5, 1, 9, 4, 3, 5\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$. \\ +\def\s{\phantom{0}} +\begin{tabular}{c c c c c c l} +$a = \s1$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s1,\s1,\s1,\s1,\s1,\s1,\s1,\s1,\s1\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s2$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s2,\s4,\s8,\s5,10,\s9,\s7,\s3,\s6\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s3$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s3,\s9,\s5,\s4,\s1,\s3,\s9,\s5,\s4\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s4$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s4,\s5,\s9,\s3,\s1,\s4,\s5,\s9,\s3\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s5$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s5,\s3,\s4,\s9,\s1,\s5,\s3,\s4,\s9\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s6$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s6,\s3,\s7,\s9, 10,\s5,\s8,\s4,\s2\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s7$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s7,\s5,\s2,\s3,10,\s4,\s6,\s9,\s8\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s8$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s8,\s9,\s6,\s4, 10,\s3,\s2,\s5,\s7\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s9$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s9,\s4,\s3,\s5,\s1,\s9,\s4,\s3,\s5\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10,\s1,10,\s1, 10,\s1, 10,\s1, 10\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$. \\ \end{tabular} \end{center} %\begin{center} @@ -147,15 +148,15 @@ $a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1 %$a = 10 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ %\end{tabular} %\end{center} -Es fällt auf, dass wir für $a$ die Zahlen $2,6,7,8$ Mengen erhalten, die tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em primitive Einheitswurzel \em genannt. -Wenden wir diese Vorgehensweise auch für andere endliche Körper an, so werden wir sehen, dass wir immer mindestens zwei solcher Einheitswurzel finden werden. Somit ist es uns überlassen, eine dieser Einheitswurzel auszuwählen, mit der wir weiter rechnen wollen. Für das Beispiel wählen wir die Zahl $a = 8$. +Es fällt auf, dass wir für $a$ die Zahlen $2,6,7,8$ Mengen erhalten, die tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em primitive Einheitswurzeln \em genannt. +Wenden wir diese Vorgehensweise auch für andere endliche Körper an, so werden wir sehen, dass wir immer mindestens zwei solcher Einheitswurzeln finden werden. Somit ist es uns überlassen, eine dieser Einheitswurzeln auszuwählen, mit der wir weiter rechnen wollen. Für das Beispiel wählen wir die Zahl $a = 8$. \subsubsection{Bildung einer Transformationsmatrix \label{reedsolomon:subsection:transMat}} \index{Transformationsmatrix}% -Mit der Wahl einer Einheitswurzel ist es uns jetzt möglich, unsere Nachricht zu Codieren. Daraus sollen wir dann einen Übertragungsvektor $v$ erhalten, den wir an den Empfänger schicken können. -Für die Codierung setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nacheinander in $m(X)$ ein. Da wir zuvor eine von $a$ abhängige Schreibweise gewählt haben setzen wir stattdessen $a^i$ ein mit $a = 8$ als die von uns gewählten primitiven Einheitswurzel. Daraus ergibt sich +Mit der Wahl einer Einheitswurzel ist es uns jetzt möglich, unsere Nachricht zu codieren. Daraus sollen wir dann einen Übertragungsvektor $v$ erhalten, den wir an den Empfänger schicken können. +Für die Codierung setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nacheinander in $m(X)$ ein. Da wir zuvor eine von $a$ abhängige Schreibweise gewählt haben, setzen wir stattdessen $a^i$ ein mit $a = 8$ als die von uns gewählten primitiven Einheitswurzel. Daraus ergibt sich %Für die Codierung müssen wir alle $a^i$ in das Polynom $m(X)$ einsetzen. Da wir $a^i = 8^i$ gewählt haben, ergibt sich daraus % %Damit wir unsere Nachricht codieren können, müssen wir $8^i$ in $m(X)$ einsetzen. @@ -164,7 +165,7 @@ Für die Codierung setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nac \begin{tabular}{c} $m(8^0) = 4 \cdot 1^5 + 7 \cdot 1^4 + 2 \cdot 1^3 + 5 \cdot 1^2 + 8 \cdot 1^1 + 1 = 5$ \\ $m(8^1) = 4 \cdot 8^5 + 7 \cdot 8^4 + 2 \cdot 8^3 + 5 \cdot 8^2 + 8 \cdot 8^1 + 1 = 3$ \\ - \vdots \\ + \vdots \\[5pt] $m(8^9) = 4 \cdot 7^5 + 7 \cdot 7^4 + 2 \cdot 7^3 + 5 \cdot 7^2 + 8 \cdot 7^1 + 1 = 4$ \end{tabular} \end{center} @@ -175,7 +176,7 @@ als unser Übertragungsvektor. \label{reedsolomon:subsection:algCod}} Um das Ganze noch ein wenig übersichtlicher zu gestalten, können wir die Polynome zu einer Matrix zusammenfassen, die unsere Transformationsmatrix $A$ bildet. -Für die allgemeine Codierung benötigen wir die Nachricht $m$, die codiert werden soll, sowie die Transformationsmatrix $A$. Daraus erhalten wir den Übertragungsvektor $v$. Setzen wir die Zahlen aus dem Beispiel ein erhalten wir folgende Darstellung: +Für die allgemeine Codierung benötigen wir die Nachricht $m$, die codiert werden soll sowie die Transformationsmatrix $A$. Daraus erhalten wir den Übertragungsvektor $v$. Setzen wir die Zahlen aus dem Beispiel ein, erhalten wir folgende Darstellung: \[ v = A \cdot m \qquad \Rightarrow \qquad v = \begin{pmatrix} 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0\\ diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex index 97694ae..6cea758 100644 --- a/buch/papers/reedsolomon/decmitfehler.tex +++ b/buch/papers/reedsolomon/decmitfehler.tex @@ -7,8 +7,8 @@ \label{reedsolomon:section:decmitfehler}} \rhead{Decodierung mit Fehler} Bisher haben wir die Decodierung unter der Bedingung durchgeführt, dass der Übertragungsvektor fehlerlos versendet und empfangen wurde. -In der realen Welt müssen wir uns jedoch damit abfinden, dass kein Übertragungskanal garantiert fehlerfrei ist und das wir früher oder später mit Fehlern rechnen müssen. -Genau für dieses Problem wurden Fehler korrigierende Codes, wie der Reed-Solomon-Code, entwickelt. +In der realen Welt müssen wir uns jedoch damit abfinden, dass kein Übertragungskanal garantiert fehlerfrei ist und dass wir früher oder später mit Fehlern rechnen müssen. +Genau für dieses Problem wurden Fehler korrigierende Codes wie der Reed-Solomon-Code entwickelt. In diesem Abschnitt betrachten wir somit die Idee der Fehlerkorrektur und wie wir diese auf unser Beispiel anwenden können. Der Übertragungskanal im Beispiel weist jetzt den Fehlervektor @@ -79,7 +79,7 @@ Wir stellen jedoch recht schnell fest, dass am decodierten Nachrichtenblock r = [\underbrace{5,7,4,10,}_{\displaystyle\text{Syndrom}}5,4,5,7,6,7] \] etwas nicht in Ordnung ist, denn die vorderen vier Fehlerkorrekturstellen haben nicht mehr den Wert null. -Der Nachrichtenblock weisst jetzt ein {\em Syndrom} auf, welches anzeigt, dass der Übertragungsvektor fehlerhaft empfangen wurde. +Der Nachrichtenblock weist jetzt ein {\em Syndrom} auf, welches anzeigt, dass der Übertragungsvektor fehlerhaft empfangen wurde. \index{Syndrom}% % Old Text %Wenn wir den Übertragungsvektor jetzt Rücktransformieren wie im vorherigen Kapitel erhalten wir @@ -92,7 +92,7 @@ Jetzt stellt sich natürlich die Frage, wie wir daraus den ursprünglich gesende \subsection{Das Fehlerstellenpolynom $d(X)$ \label{reedsolomon:subsection:fehlerpolynom}} Bevor wir unser Lokatorpolynom berechnen können, müssen wir zuerst eine Möglichkeit finden, die fehlerhaften von den korrekten Stellen im Übertragungsvektor unterscheiden zu können. -In einem ersten Versuch berechnen wir die Differenz $d$ des empfangenen und dem gesendeten Übertragungsvektor mit +In einem ersten Versuch berechnen wir die Differenz $d$ des empfangenen und des gesendeten Übertragungsvektors mit %Alle Stellen in $d$, die nicht null sind sind demnach fehler. % %In einem ersten Versuch könnten wir $d$ berechnen mit @@ -107,11 +107,11 @@ und nennen $d(X)$ unser {\em Fehlerstellenpolynom}. \index{Fehlerstellenpolynom}% Dieses Polynom soll uns sagen, welche Stellen korrekt und welche fehlerhaft sind. -Durch das Verwenden von $m(X)$ stossen wir auf weitere Probleme, da wir den Nachrichtenvektor auf der Empfängerseite nicht kennen (unser Ziel ist es ja genau diesen zu finden). Dieses Problem betrachten wir im Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} genauer. Um die Überlegungen in den folgenden Abschnitten besser zu verstehen sei $m(X)$ bekannt auf der Empfängerseite. +Durch das Verwenden von $m(X)$ stossen wir auf weitere Probleme, da wir den Nachrichtenvektor auf der Empfängerseite nicht kennen (unser Ziel ist es ja, genau diesen zu finden). Dieses Problem betrachten wir in Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} genauer. Um die Überlegungen in den folgenden Abschnitten besser zu verstehen, sei $m(X)$ bekannt auf der Empfängerseite. %Dies wird uns zwar andere sorgen wegen $m(X)$ bereiten, wir werden werden deshalb erst in Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} darauf zurückkommen. -Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein so erhalten wir +Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein, erhalten wir % Old Text %\begin{align} % m(X) & = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \\ @@ -130,10 +130,10 @@ Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein so erhalten wir \hline \end{tabular} \end{center} -und damit die Information, dass allen Stellen, die nicht Null sind, Fehler enthalten. -Aus der Tabelle lesen wir ab, das in unserem Beispiel die Fehler an der Stelle $3$ und $8$ zu finden sind. +und damit die Information, dass alle Stellen, die nicht null sind, Fehler enthalten. +Aus der Tabelle lesen wir ab, dass in unserem Beispiel die Fehler an der Stelle $3$ und $8$ zu finden sind. -Für das einfache Bestimmen von Hand mag dies ja noch ausreichen, jedoch können wir mit diesen Stellen nicht das Lokatorpolynom bestimmen, denn dafür bräuchten wir alle Nullstellen, an denen es Fehler gegeben hat (also sozusagen genau das umgekehrte). Um dies zu erreichen wenden wir eine andere Herangehensweise und nehmen uns den Satz von Fermat sowie den kleinsten gemeinsamen Teiler zur Hilfe. +Für das einfache Bestimmen von Hand mag dies ja noch ausreichen. Wir können jedoch mit diesen Stellen das Lokatorpolynom nicht bestimmen, denn dafür würden wir alle Nullstellen gebrauchen, an denen es Fehler gegeben hat (also sozusagen genau das Umgekehrte). Um dies zu erreichen, wenden wir eine andere Herangehensweise an und nehmen uns den Satz von Fermat sowie den kleinsten gemeinsamen Teiler zu Hilfe. \subsection{Mit dem grössten gemeinsamen Teiler auf Nullstellenjagd \label{reedsolomon:subsection:ggT}} @@ -158,7 +158,7 @@ Wir können jetzt auch $d(X)$ nach der gleichen Überlegung darstellen als d(X) = (X-a^0)(X-a^1)(X-a^2)\textcolor{gray!40}{(X-a^3)}(X-a^4)(X-a^5)(X-a^6)(X-a^7)\textcolor{gray!40}{(X-a^8)}(X-a^9) \cdot p(x), \] wobei diese Darstellung nicht mehr alle Nullstellen umfasst wie es noch in $f(X)$ der Fall war. -Dies liegt daran, dass wir ja zwei Fehlerstellen (grau markiert) haben, die nicht Null sind. Diese fassen wir zum Restpolynom $p(X)$ zusammen. +Dies liegt daran, dass wir ja zwei Fehlerstellen (grau markiert) haben, die nicht null sind. Diese fassen wir zum Restpolynom $p(X)$ zusammen. Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $d(X)$ berechnen, so erhalten wir mit \[ \operatorname{ggT}(f(X),d(X)) = (X-a^0)(X-a^1)(X-a^2)\textcolor{gray!40}{(X-a^3)}(X-a^4)(X-a^5)(X-a^6)(X-a^7)\textcolor{gray!40}{(X-a^8)}(X-a^9) @@ -172,7 +172,7 @@ Dies scheint zuerst nicht sehr hilfreich zu sein, da wir für das Lokatorpolynom \label{reedsolomon:subsection:kgV}} \index{kgV}% \index{kleinstes gemeinsames Vielfaches}% -Das kgV hat nämlich die Eigenschaft sämtliche Nullstellen zu finden, also nicht nur die fehlerhaften sondern auch die korrekten, was in +Das kgV hat nämlich die Eigenschaft, sämtliche Nullstellen zu finden, also nicht nur die fehlerhaften, sondern auch die korrekten, was in \[ \operatorname{kgV}(f(X),d(X)) = (X-a^0)(X-a^1)(X-a^2)(X-a^3)(X-a^4)(X-a^5)(X-a^6)(X-a^7)(X-a^8)(X-a^9) \cdot q(X). \] @@ -187,8 +187,8 @@ Somit ist l(X) = (X-a^3)(X-a^8) \] unser gesuchtes Lokatorpolynom. -Es scheint so als müssten wir nur noch an den besagten Stellen den Übertragungsvektor korrigieren und wir wären fertig mit der Fehlerkorrektur. -Jedoch haben wir noch ein grundlegendes Problem, dass zu Beginn aufgetaucht ist, wir aber beiseite geschoben haben. Die Rede ist natürlich vom Nachrichtenvektor $m(X)$, mit dem wir in erster Linie das wichtige Fehlerstellenpolynom $d(X)$ berechnet haben, auf der Empfängerseite aber nicht kennen. +Es scheint so als müssten wir nur noch den Übertragungsvektor an den besagten Stellen korrigieren und wir wären fertig mit der Fehlerkorrektur. +Jedoch haben wir noch ein grundlegendes Problem, das zu Beginn aufgetaucht ist, wir aber beiseite geschoben haben. Die Rede ist natürlich vom Nachrichtenvektor $m(X)$, mit dem wir in erster Linie das wichtige Fehlerstellenpolynom $d(X)$ berechnet haben, auf der Empfängerseite aber nicht kennen. \subsection{Der problematische Nachrichtenvektor $m(X)$ \label{reedsolomon:subsection:nachrichtenvektor}} @@ -198,8 +198,8 @@ In Abschnitt \ref{reedsolomon:section:decmitfehler} haben wir d(X) = r(X) - m(X) \] in Abhängigkeit von $m(X)$ berechnet. -Jedoch haben wir ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht verfügbar und somit gänzlich unbekannt ist. -Es scheint so als würde dieser Lösungsansatz, den wir bisher verfolgt haben, nicht funktioniert. +Wir haben jedoch ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht verfügbar und somit gänzlich unbekannt ist. +Es scheint so als würde dieser Lösungsansatz, den wir bisher verfolgt haben, nicht funktionieren. Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Nachrichtenvektor im Beispiel wissen. Wenn wir noch einmal den Vektor betrachten als @@ -211,7 +211,7 @@ Im Normalfall sollen diese nämlich den Wert $0$ haben und somit sind nur die le \[ m = [0,0,0,0,?,?,?,?,?,?]. \] -Nach der Definition des Reed-Solomon-Codes soll an genau diesen vier Stellen auch die Information befinden, wo die Fehlerstellen liegen. Daher reicht es auch aus +Nach der Definition des Reed-Solomon-Codes soll sich an genau diesen vier Stellen auch die Information befinden, wo die Fehlerstellen liegen. Daher reicht es auch aus % darum werden die stellen auch als fehlerkorrekturstellen bezeichnet \[ d(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X) @@ -221,7 +221,7 @@ so zu berechnen, dass wir die wichtigen vier Stellen kennen, der Rest des Polyno \subsection{Die Berechnung der Fehlerstellen \label{reedsolomon:subsection:nachrichtenvektor}} \index{Fehlerstellen}% -Um die Fehlerstellen zu berechnen wenden wir die gleiche Vorgehensweise wie zuvor an, also zuerst den ggT, danach berechnen wir das kgV um am Ende das Lokatorpolynom zu erhalten. +Um die Fehlerstellen zu berechnen wenden wir die gleiche Vorgehensweise wie zuvor an, also zuerst den ggT, danach berechnen wir das kgV, um am Ende das Lokatorpolynom zu erhalten. \subsubsection{Schritt 1: ggT} @@ -285,7 +285,7 @@ und erhalten \subsubsection{Schritt 2: kgV} -Mit dem Resultat das wir vom ggT erhalten haben können wir jetzt das kgV berechnen. Dazu können wir jetzt den erweiterten Euklidischen Algorithmus verwenden, den wir in Abschnitt \ref{buch:subsection:daskgv} kennengelernt haben. +Mit dem Resultat, das wir vom ggT erhalten haben, können wir jetzt das kgV berechnen. Dazu können wir jetzt den erweiterten Euklidischen Algorithmus verwenden, den wir in Abschnitt \ref{buch:subsection:daskgv} kennengelernt haben. % %Mit den Resultaten, die wir vom Rechenweg des grössten gemeinsamen Teiler erhalten haben können wir jetzt auch das kleinste Gemeinsame Vielfache berechnen. Eine detailliertere Vorgehensweise findet man in Kapitel ???. % @@ -314,14 +314,14 @@ Unser gesuchtes Lokatorpolynom hat also die Form l(X) = (X-a^i)(X-a^j). \] Also brauchen wir nur noch $i$ und $j$ zu berechnen und wir haben unsere gesuchten Fehlerstellen. -Diese bekommen wir recht einfach mit +Diese erhalten wir recht einfach mit \begin{equation*} \begin{aligned} a^i &= 5 &&\Rightarrow & i &= 3\\ a^j &= 6 &&\Rightarrow & j &= 8. \end{aligned} \end{equation*} -Schlussendlich erhalten wir +Schliesslich erhalten wir \[ d(X) = (X-a^3)(X-a^8) \] diff --git a/buch/papers/reedsolomon/decohnefehler.tex b/buch/papers/reedsolomon/decohnefehler.tex index 2c755f9..bb5656b 100644 --- a/buch/papers/reedsolomon/decohnefehler.tex +++ b/buch/papers/reedsolomon/decohnefehler.tex @@ -7,9 +7,9 @@ \label{reedsolomon:section:decohnefehler}} \rhead{Decodierung ohne Fehler} -In diesem Abschnitt betrachten wie die Überlegung, wie wir auf der Empfängerseite die Nachricht aus dem empfangenen Übertragungsvektor erhalten. Nach einer einfachen Überlegung müssen wir den Übertragungsvektor decodieren, was auf den ersten Blick nicht allzu kompliziert sein sollte, solange wir davon ausgehen können, dass es während der Übertragung keine Fehler gegeben hat. Wir betrachten deshalb den Übertragungskanal als fehlerfrei. +In diesem Abschnitt betrachten wir die Überlegung, wie wir auf der Empfängerseite die Nachricht aus dem empfangenen Übertragungsvektor erhalten. Nach einer einfachen Überlegung müssen wir den Übertragungsvektor decodieren, was auf den ersten Blick nicht allzu kompliziert sein sollte, solange wir davon ausgehen können, dass es während der Übertragung keine Fehler gegeben hat. Wir betrachten deshalb den Übertragungskanal als fehlerfrei. -Der Übertragungsvektor empfangen wir also als +Den Übertragungsvektor empfangen wir also als \[ v = [5,3,6,5,2,10,2,7,10,4]. \] @@ -27,13 +27,13 @@ Nach einem banalen Ansatz ist die Decodierung die Inverse der Codierung. Dank de v = A \cdot m \qquad \Rightarrow \qquad m = A^{-1} \cdot v \] Nur stellt sich jetzt die Frage, wie wir die Inverse von $A$ berechnen. -Dazu können wir wiederum den Ansatz der Fouriertransformation uns zur Hilfe nehmen, +Dazu können wir wiederum den Ansatz der Fouriertransformation zu Hilfe nehmen, jedoch betrachten wir jetzt deren Inverse. Definiert ist sie als \[ F(\omega) = \int_{-\infty}^{\infty} f(t) \mathrm{e}^{-j\omega t} dt \qquad \Rightarrow \qquad \mathfrak{F}^{-1}(F(\omega)) = f(t) = \frac{1}{2 \pi} \int_{-\infty}^{\infty} F(\omega) \mathrm{e}^{j \omega t} d\omega. \] -Im wesentlichen ändert sich bei der inversen diskreten Fouriertransformation $e^{j/2\pi}$ zu $e^{-j/2\pi}$. Zusätzlich benötigt die Inverse noch einen Korrekturfaktor $1/n$. Wir erwarten daher, dass wir auch im endlichen Körper $A$ die Zahl $a$ durch $a^{-1}$ ersetzen können. Mit der primitiven Einheitswurzel ergibt das +Im Wesentlichen ändert sich bei der inversen diskreten Fouriertransformation $e^{j/2\pi}$ zu $e^{-j/2\pi}$. Zusätzlich benötigt die Inverse noch einen Korrekturfaktor $1/n$. Wir erwarten daher, dass wir auch im endlichen Körper $A$ die Zahl $a$ durch $a^{-1}$ ersetzen können. Mit der primitiven Einheitswurzel ergibt das \index{Korrekturfaktor}% %Damit beschäftigen wir uns im Abschnitt \ref{reedsolomon:subsection:sfaktor} weiter, konkret suchen wir momentan aber eine Inverse für unsere primitive Einheitswurzel $a$. \[ @@ -47,13 +47,13 @@ Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:e \subsection{Inverse der primitiven Einheitswurzel \label{reedsolomon:subsection:invEinh}} \index{Inverse}% -Die Funktionsweise des euklidischen Algorithmus ist im Abschnitt \ref{buch:section:euklid} ausführlich beschrieben. +Die Funktionsweise des euklidischen Algorithmus ist in Abschnitt \ref{buch:section:euklid} ausführlich beschrieben. Für unsere Anwendung wählen wir die Parameter $a = 8$ und $b = 11$ ($\mathbb{F}_{11}$). Daraus erhalten wir \begin{center} -\begin{tabular}{| c | c c | c | r r |} +\begin{tabular}{| c | r r | c | r r |} \hline $k$ & $a_i$ & $b_i$ & $q_i$ & $c_i$ & $d_i$\\ \hline @@ -106,9 +106,9 @@ Die inverse Transformationsmatrix $A^{-1}$ bilden wir, indem wir jetzt die inver \subsection{Der Faktor $s$ \label{reedsolomon:subsection:sfaktor}} Die diskrete Fouriertransformation benötigt für die Inverse einen Vorfaktor von $\frac{1}{2\pi}$. -Wir müssen also damit rechnen, dass wir für die Inverse Transformationsmatrix ebenfalls einen solchen Vorfaktor benötigen. +Wir müssen also damit rechnen, dass wir für die inverse Transformationsmatrix ebenfalls einen solchen Vorfaktor benötigen. Nur stellt sich jetzt die Frage, wie wir diesen Vorfaktor in unserem Fall ermitteln können. -Dafür betrachten wir eine Regel aus der linearen Algebra, nämlich dass +Dafür betrachten wir eine Regel aus der linearen Algebra, nämlich, dass \[ A \cdot A^{-1} = E @@ -152,7 +152,7 @@ Aus der letzten Matrix folgt, dass wir \[ s = \dfrac{1}{10} \] -als unseren Vorfaktor setzen müssen um, die Gleichung \ref{reedsolomon:equation:sfaktor} zu erfüllen. Da wir in $\mathbb{F}_{11}$ nur mit ganzen Zahlen arbeiten, schreiben wir $\frac{1}{10}$ in $10^{-1}$ um und bestimmen diese Inverse erneut mit dem euklidischen Algorithmus. So erhalten wir $10^{-1} = 10$ als Vorfaktor in $\mathbb{F}_{11}$. +als unseren Vorfaktor setzen müssen, um die Gleichung \ref{reedsolomon:equation:sfaktor} zu erfüllen. Da wir in $\mathbb{F}_{11}$ nur mit ganzen Zahlen arbeiten, schreiben wir $\frac{1}{10}$ in $10^{-1}$ um und bestimmen diese Inverse erneut mit dem euklidischen Algorithmus. So erhalten wir $10^{-1} = 10$ als Vorfaktor in $\mathbb{F}_{11}$. % %erfüllt wird. Wir schreiben den Bruch um in $\frac{1}{10} = 10^{-1}$ und wenden darauf erneut den euklidischen Algorithmus an und erhalten somit den Vorfaktor $10^{-1} = 10 = s$ in $\mathbb{F}_{11}$. % diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index a50a134..587d36c 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -4,10 +4,10 @@ \section{Übertragung mit Hilfe der diskreten Fourier-Transformation \label{reedsolomon:section:dtf}} \rhead{Fehlerkorrektur mit diskreter Fourier-Transformation} -Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunktes -durch die Codierung auf viele übertragene Werte verteilt werden. +Die Grundidee eines fehlerkorrigierenden Codes ist, dass Informationen eines Datenpunktes +durch die Codierung auf viele übertragenen Werte verteilt werden. Die Decodierung ist in der Lage, den ursprünglichen Datenwert zu rekonstruieren, -sogar wenn einzelne wenige übertragene Werte beschädigt worden sind. +sogar wenn einzelne wenig übertragene Werte beschädigt worden sind. \par Die Fourier-Transformation transformiert einen einzelnen Wert, \index{Fourier-Transformation}% @@ -23,7 +23,7 @@ für Codierung und Decodierung zu verwenden. \subsection{Beispiel: Fehlerkorrektur mit Fourier-Transformation \label{reedsolomon:subsection:sendbsp}} Das folgende Beispiel soll zeigen, wie die Idee der Fehlerkorrektur umgesetzt wurde. -Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr Ähnlichen Prinzip. +Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr ähnlichen Prinzip. \index{Reed-Solomon-Code}% %Das folgende Beispiel soll zeigen, wie Fehlerkorrektur möglich ist. @@ -31,8 +31,8 @@ Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr Ähnlich %der später erklärt wird, analog ist. \par Der Auftrag besteht darin, 64 Datenwerte zu übertragen, 32 Fehler erkennen können und bis zu 16 Fehler zu rekonstruieren. -Mit Hilfe der Fourier-Transformation werden die \textcolor{blue}{blauen Datenpunkte} transformiert, -zu den \textcolor{darkgreen}{grünen Übertragungspunkten}. +Mit Hilfe der Fourier-Transformation werden die \textcolor{blue}{blauen Datenpunkte} +zu den \textcolor{darkgreen}{grünen Übertragungspunkten} transformiert. Durch eine Rücktransformation können die \textcolor{blue}{blauen Datenpunkte} wieder rekonstruiert werden. \begin{figure}%[!ht] @@ -45,17 +45,17 @@ Durch eine Rücktransformation können die \textcolor{blue}{blauen Datenpunkte} \label{fig:sendorder} \end{figure} In der Abbildung \ref{fig:sendorder} wird eine Übertragung Schritt für Schritt illustriert. -In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläutert: +In der folgenden Aufzählung werden diese einzelnen Schritte erklärt und erläutert: \begin{enumerate}[(1)] \item Das Signal besteht aus 64 zufälligen, ganzzahligen Datenwerten zwischen 0 und 10. - Für die Rekonstruktion werden zusätzliche Datenwerte benötigt, wir fügen deshalb 32 Werte hinzu. + Für die Rekonstruktion werden zusätzliche Datenwerte benötigt. Wir fügen deshalb 32 Werte hinzu. Diese setzen wir willkürlich alle auf Null und nennen sie {\em Fehlerkorrekturstellen}. \index{Fehlerkorrekturstellen}% Wir erhalten so einen erweiterten Signalvektor der Länge $N =96$. \index{Signalvektor}% \item Mit der Fourier-Transformation wird der ganze Signalvektor codiert. Dadurch wird jede Informationseinheit auf alle Punkte des Spektrums verteilt. - \item Wir dürfen annehmen, dass bei der Übertragung, nur einzelne übertragene + \item Wir dürfen annehmen, dass bei der Übertragung nur einzelne übertragene Werte durch Fehler verändert werden. \par Im Beispiel sind dies die Werte an den Stellen 6, 20 und 74 (\textcolor{red}{rote Kurve}), @@ -68,10 +68,10 @@ In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläut \par Sind Übertragungsfehler aufgetreten, werden an diesen Stellen die Werte von Null abweichen. Somit haben wir bereits Fehler erkannt. - \item Die Werte an den Fehlerkorrekturstellen 64--96, die nicht mehr Null sind, nennen wir das {\em Syndrom}. + \item Die Werte an den Fehlerkorrekturstellen 64--96, die nicht mehr null sind, nennen wir das {\em Syndrom}. \index{Syndrom}% Im Syndrom steckt nur Information über die Fehler, sie werden durch die inverse Fourier-Transformation erzeugt. - \item Um die Fehler zu rekonstruieren, kann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren. + \item Um die Fehler zu rekonstruieren kann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren. Da das Syndrom nur ein Teil der Fehlerinformation ist, liefert die Fourier-Transformation eine Approximation der Fehler. Diese Approximation der Fehler ist genau genug, um die Fehlerstellen zu lokalisieren. \end{enumerate} @@ -100,7 +100,7 @@ Die Analogie geht aber noch weiter. Schreibt man \( w = e^{-\frac{2\pi j}{N} k}\) - \label{reedsolomon:DFT_summand}, damit wird aus der Formel + \label{reedsolomon:DFT_summand}, wird aus der Formel \begin{equation} \hat{c}_{k} = \frac{1}{N} \sum_{n=0}^{N-1} @@ -121,12 +121,12 @@ Die Analogie geht aber noch weiter. \label{reedsolomon:DFT_polynom2} \end{equation} für verschiedene \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots ,N-1\) übermittelt. -Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$ (graue Koeffizenten). +Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$ (graue Koeffizienten). Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reellen Zahlen. Wenn die Approximation nicht mehr genügend gut ist, um die Fehler zu erkennen und zu rekonstruieren, dann brauchen wir andere Varianten. -Um dieser Approximation zu entkommen, verlassen wir die reellen Zahlen und gehen zu endlichen Körpern, auch Galois-Körper genannt. +Um dieser Approximation zu entkommen verlassen wir die reellen Zahlen und gehen zu endlichen Körper, auch Galois-Körper genannt. \index{endlicher Körper}% \index{Galois-Körper}% \index{Körper, endlich}% diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index cf46c27..c70f595 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -10,9 +10,10 @@ Der Reed-Solomon-Code wurde von den beiden Mathematikern Irving S. Reed und Gust \index{Reed, Irving S.}% \index{Solomon, Gustave}% Dabei haben sie das Problem der fehlerhaften Datenübertragung gelöst. -In diesem Kapitel wird möglichst verständlich die mathematische Abfolge und -Funktionsweise des Reed-Solomon-Code erklärt. -Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen, jedoch werden im Abschnitt \ref{reedsolomon:section:anwendung} einige Anwendungen des Reed-Solomon-Codes vorgestellt. +In diesem Kapitel wird die mathematische Abfolge und +Funktionsweise des Reed-Solomon-Code möglichst verständlich erklärt. +Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen. +In Abschnitt \ref{reedsolomon:section:anwendung} werden jedoch einige Anwendungen des Reed-Solomon-Codes vorgestellt. diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index 3019dd7..79c3c19 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -14,10 +14,10 @@ Zudem beschränken sich die arithmetischen Rechenoperationen auf das Addieren un Wir können also nur ganze Zahlen als Resultat erhalten. Dies erleichtert auch die Umsetzung auf ein digitales System, da Computer in der Regel lieber mit ganzen als mit gebrochenen oder komplexen Zahlen arbeiten. -Um jetzt eine Nachricht in einem endlichen Körpern zu konstruieren gehen, wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. +Um jetzt eine Nachricht in einem endlichen Körper zu konstruieren, gehen wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. Eine Nachricht besteht aus einem Nutzdatenteil und einem Fehlerkorrekturteil. Diese Nachricht wird codiert, übertragen und beim Empfänger wieder decodiert. -In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation zur Hilfe nehmen. +In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation zu Hilfe nehmen. Wir müssen also eine Alternative finden, welche die gleichen Eigenschaften wie die Fouriertransformation aufweist, aber im endlichen Körper verwendet werden kann. Auch beim Decodieren müssen wir uns etwas einfallen lassen, wenn die Vorgehensweise mit dem Lokator auch in endlichen Körpern funktionieren soll. Die folgenden Abschnitte widmen sich deshalb der genaueren Betrachtung eines Reed-Solomon-Codes und wie er in endlichen Körpern funktioniert. diff --git a/buch/papers/reedsolomon/hilfstabellen.tex b/buch/papers/reedsolomon/hilfstabellen.tex index 24fabdf..2c8585f 100644 --- a/buch/papers/reedsolomon/hilfstabellen.tex +++ b/buch/papers/reedsolomon/hilfstabellen.tex @@ -7,7 +7,7 @@ \label{reedsolomon:section:hilfstabellen}} \rhead{Hilfstabellen} -Um das rechnen zu erleichtern findet man in diesem Abschnitt die Resultate, die bei der Addition und der Multiplikation in $\mathbb{F}_{11}$ resultieren. +Um das Rechnen zu erleichtern findet man in diesem Abschnitt die Resultate, die bei der Addition und der Multiplikation in $\mathbb{F}_{11}$ resultieren. \subsection{Additionstabelle \label{reedsolomon:subsection:adtab}} diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index b1ab8f6..df8c30d 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -5,14 +5,14 @@ \label{reedsolomon:section:idee}} \rhead{Problemstellung} Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, -also den gleiche Wert immer zweimal. -Tritt ein Fehler ein wird sich dies in der Differenz der beiden Werte bemerkbar machen. +also den gleichen Wert immer zweimal. +Tritt ein Fehler ein, wird sich dies in der Differenz der beiden Werte bemerkbar machen. Aber wie erkennen wir, welcher nun der richtige ist? Die Lösung ist simpel: Wir übertragen den Wert einfach dreimal. Wenn jetzt ein Fehler auftritt, kann durch die beiden unveränderten Werte der richtige bestimmt werden. Doch was machen wir, wenn bei dieser Übertragung zwei Fehler auftreten? -Oder noch schlimmer: Was wenn zweimal derselbe Fehler auftritt? Die beiden fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. +Oder noch schlimmer: Was ist, wenn zweimal derselbe Fehler auftritt? Die beiden fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. Wir könnten dies noch steigern mit vier, fünf oder mehr gleichen übertragenen Werte. Dies erhöht zwar die Robustheit der gesendeten Daten, führt aber auch dazu, dass wir durch die Mehrfachübertragung nur sehr wenige Nutzdaten versenden können. -Gerade in unserer heutigen Zeit wäre dies ein enorm grosses Problem und aus diesem Grund wurden alternative Ansätze ausgearbeitet um dieses grundlegende Problem zu lösen. +Gerade in der heutigen Zeit wäre dies ein enorm grosses Problem und aus diesem Grund wurden alternative Ansätze ausgearbeitet, um dieses grundlegende Problem zu lösen. % % %Gerade in der heutigen modernen Zeit bei dem hohen bedarf an Daten würden unsere Kommunikationssysteme bei weitem nicht ausreichen um den einen einzigen Datenwert mehrfach zu übertragen @@ -60,7 +60,7 @@ Gerade in unserer heutigen Zeit wäre dies ein enorm grosses Problem und aus die \subsection{Polynom-Ansatz \label{reedsolomon:section:polynomansatz}} \rhead{Polynom-Ansatz} -Eine zentrale Idee des Reed-Solomon-Code ist, aus den Daten ein Polynom zu bilden. +Eine zentrale Idee des Reed-Solomon-Codes ist, aus den Daten ein Polynom zu bilden. Mit dieser Polynomfunktion wird dann eine Anzahl von Werten übertragen. \begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}, welche übertragen werden sollen. Daraus bilden wir das Polynom \begin{equation} @@ -71,17 +71,17 @@ p(x) \end{equation} Ein Polynom zweiten Grades ist durch drei Punkte eindeutig bestimmbar. -Bei einer fehlerlosen Übertragung können wir mit drei übertragenen Werten - das Polynom durch Polynominterpolation volständig rekonstruieren. +Bei einer fehlerlosen Übertragung können wir mit drei übertragenen Werte +das Polynom durch Polynominterpolation vollständig rekonstruieren. Wir brauchen Polynominterpolation als Methode, um aus den Punkten wieder ein Polynom zu bilden. -Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}. +Die Koeffizienten des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}. Wie können wir nun Fehler erkennen oder sogar korrigieren? Versuchen wir doch, mehr Werte zu übertragen, wie zum Beispiel sieben Werte. Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} - des \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3, \dots , 7. -In Abbildung \ref{fig:polynom} ist das zu den \textcolor{blue}{Datenpunkten} gehörige Polynom blau dargestellt, -die \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün, wobei diese Punkte aufgrund von Übertragungsfehler jetzt eine Parabel darstellen. + des \textcolor{blue}{blauen Polynoms} an den Stellen 1, 2, 3, \dots , 7. +In Abbildung \ref{fig:polynom} ist das zu den \textcolor{blue}{Datenpunkten} gehörende Polynom blau dargestellt, +die \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün, wobei diese Punkte aufgrund von Übertragungsfehlern jetzt eine Parabel darstellen. Die fehlerhaften Punkte lassen sich sehr einfach bestimmen, weil diese nicht auf der ursprünglichen Funktion liegen. Somit können die roten Punkte auf der Parabel durch die grauen ersetzt werden und sind damit korrigiert. @@ -97,14 +97,14 @@ Wir erhöhen dazu die Fehleranzahl Schritt für Schritt: \begin{itemize} \item[\textit{1 Fehler}:] Bei einem Fehler können konkurrenzierende, aber falsche Polynome zusammen mit zwei originalen Punkten entstehen. Dabei können aber maximal drei Punkte auf diesem Konkurrenzpolynom sein. - Da 6 > 3 ist haben wir unser originales Polynom gefunden. - \item[\textit{2 Fehler}:] Bei Zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. - Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbilbung \ref{fig:polynom} zu sehen ist. - Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{fünf} übereinstimmenden und ein konkurrenzierendes mit vier Punkten. + Da 6 > 3 ist, haben wir unser originales Polynom gefunden. + \item[\textit{2 Fehler}:] Bei zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. + Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbildung \ref{fig:polynom} zu sehen ist. + Nun haben wir ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{fünf} übereinstimmenden und ein konkurrenzierendes mit vier Punkten. Da fünf noch grösser als vier ist, können wir sagen, welches das Originalpolynom ist. - \item[\textit{3 Fehler}:] Bei drei kann genau wie bei ein oder zwei Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. + \item[\textit{3 Fehler}:] Bei drei kann genau wie bei ein oder zwei Fehlern ein konkurrenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. Auch hier sind die anderen Fehler frei wählbar und liegen auf dem Konkurrenzpolynom. - Nun ist es so das fünf Punkte auf diesem konkurenzierenden Polynom und vier Punkte auf dem originalen liegen. + Nun ist es so, dass fünf Punkte auf diesem konkurrenzierenden Polynom und vier Punkte auf dem originalen liegen. Das Originalpolynom kann nicht mehr gefunden werden. \item[\textit{4 Fehler}:] Bei vier kann noch erkannt werden, dass Fehler aufgetreten sind, da drei originale Punkte das ursprüngliche Polynom ergeben. Somit haben wir mindestens zwei verschiedene Polynome, was bedeutet, dass Fehler entstanden sind. @@ -120,10 +120,10 @@ Um zu bestimmen, wie viele zusätzliche \textcolor{darkgreen}{Übertragungspunkt muss man zuerst wissen, wie viele \textcolor{blue}{Datenwerte} gesendet und wie viele \textcolor{red}{Fehler} erkannt werden sollen. Die Anzahl Datenwerte ergibt die Anzahl \textcolor{blue}{$k$} -Polynomkoeffizenten +Polynomkoeffizienten und somit den Grad $k-1$ des Polynoms. Die Bestimmung der Anzahl \textcolor{red}{$t$} der Fehler, welche korrigiert werden können, braucht Redundanz. -Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich vielen Fehlern erkennt man allmählich ein Muster. +Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich vielen Fehlern, erkennt man allmählich ein Muster. \begin{table}%[!ht] \centering @@ -138,11 +138,11 @@ Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ \hline \end{tabular} - \caption{ Fehlerkorrekturstellen Bestimmung.} + \caption{Bestimmung der Anzahl Übertragungspunkte in Abhängigkeit von den Fehlern.} \label{tab:fehlerkorrekturstellen} \end{table} \par -Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden. +Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen als auf dem konkurrenzierenden. Somit braucht man für die Übertragung pro \textcolor{red}{Fehler} zwei Übertragungspunkte mehr. Wie in der Tabelle \ref{tab:fehlerkorrekturstellen} ersichtlich ist ergibt sich die Anzahl @@ -154,7 +154,7 @@ Anzahl von \textcolor{darkgreen}{Punkten} für die Übertragung. Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, die aber nicht korrigiert werden können. -Um die Polynomkoeffizenten nach der Übertragung zu rekonstruieren, haben wir jedes mal die Polynominterpolationsmethode angewendet. +Um die Polynomkoeffizienten nach der Übertragung zu rekonstruieren, haben wir jedes mal die Polynominterpolationsmethode angewendet. Diese Polynominterpolation ist leider schwierig zu berechnen und sehr fehleranfällig. Es wäre daher einfacher, wenn wir eine alternative Vorgehensweise finden könnten. diff --git a/buch/papers/reedsolomon/rekonstruktion.tex b/buch/papers/reedsolomon/rekonstruktion.tex index 4f7fd7b..b714225 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -5,7 +5,6 @@ % \section{Nachricht rekonstruieren \label{reedsolomon:section:rekonstruktion}} -\rhead{Rekonstruktion der Nachricht} Im letzten Abschnitt haben wir eine Möglichkeit gefunden, wie wir die fehlerhaften Stellen lokalisieren können. Mit diesen Stellen soll es uns nun möglich sein, aus dem fehlerhaften empfangenen Nachrichtenvektor wieder unsere Nachricht zu rekonstruieren. Das Lokatorpolynom @@ -17,9 +16,10 @@ markiert dabei diese fehlerhaften Stellen im Übertragungsvektor w = [5,3,6,8,2,10,2,7,1,4]. \] Als Ausgangslage verwenden wir die Matrix, mit der wir den Nachrichtenvektor ursprünglich codiert haben. -Unser Ziel ist es wie auch schon im Abschnitt \ref{reedsolomon:section:decohnefehler} eine Möglichkeit zu finden, wie wir den Übertragungsvektor decodieren können. -Aufgrund der Fehlerstellen müssen wir aber davon ausgehen, das wir nicht mehr den gleichen Weg verfolgen können wie wir im Abschnitt \ref{reedsolomon:section:decohnefehler} angewendet haben. +Unser Ziel ist es, wie auch schon im Abschnitt \ref{reedsolomon:section:decohnefehler}, eine Möglichkeit zu finden, wie wir den Übertragungsvektor decodieren können. +Aufgrund der Fehlerstellen müssen wir aber davon ausgehen, dass wir nicht mehr den gleichen Weg verfolgen können, wie wir ihn in Abschnitt \ref{reedsolomon:section:decohnefehler} angewandt haben. +\rhead{Rekonstruktion der Nachricht} Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen: \[ \textcolor{gray}{ @@ -49,9 +49,9 @@ Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen: \end{pmatrix} . \] -Die rot markierten Stellen im Übertragungsvektor enthalten Fehler und bringt uns daher keinen weiteren Nutzen. +Die rot markierten Stellen im Übertragungsvektor enthalten Fehler und bringen uns daher keinen weiteren Nutzen. Aus diesem Grund werden diese Stellen aus dem Vektor entfernt, was wir hier ohne Probleme machen können, da dieser Code ja über Fehlerkorrekturstellen verfügt, deren Aufgabe es ist, eine bestimmte Anzahl an Fehler kompensieren zu können. -Die dazugehörigen Zeilen in der Matrix werden ebenfalls entfernt, da die Matrix gleich viele Zeilen wie im Übertragungsvektor aufweisen muss, damit man ihn decodieren kann. +Die dazugehörenden Zeilen in der Matrix werden ebenfalls entfernt, da die Matrix gleich viele Zeilen wie im Übertragungsvektor aufweisen muss, damit man ihn decodieren kann. Daraus resultiert \[ @@ -76,8 +76,8 @@ Daraus resultiert . \] Die Matrix ist jedoch nicht mehr quadratisch, was eine Rekonstruktion durch Inversion ausschliesst. -Um die quadratische Form wieder herzustellen müssen wir zwei Spalten aus der Matrix entfernen. -Wir kennen aber das Resultat aus den letzten vier Spalten, da wir wissen, das die Nachricht aus Nutzdatenteil und Fehlerkorrekturteil besteht, wobei der letzteres bekanntlich aus lauter Nullstellen besteht. +Um die quadratische Form wieder herzustellen, müssen wir zwei Spalten aus der Matrix entfernen. +Wir kennen aber das Resultat aus den letzten vier Spalten, da wir wissen, dass die Nachricht aus Nutzdatenteil und Fehlerkorrekturteil besteht, wobei das letztere bekanntlich aus lauter Nullstellen besteht. Wir nehmen die markierten Spalten in \[ \begin{pmatrix} @@ -99,7 +99,7 @@ Wir nehmen die markierten Spalten in m_0 \\ m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ \textcolor{darkgreen}{m_6} \\ \textcolor{darkgreen}{m_7} \\ \textcolor{darkgreen}{m_8} \\ \textcolor{darkgreen}{m_9} \\ \end{pmatrix} \] -aus der Matrix heraus und erhalten so das Überbestimmte Gleichungssystem +aus der Matrix heraus und erhalten so das überbestimmte Gleichungssystem \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ \textcolor{red}{7} \\ \textcolor{red}{4} \\ @@ -141,7 +141,7 @@ Die roten Zeilen können wir aufgrund der Überbestimmtheit ebenfalls entfernen \end{pmatrix} . \] -Nun können wir den Gauss-Algorithmus anwenden um die Matrix zu Invertieren. +Nun können wir den Gauss-Algorithmus anwenden, um die Matrix zu invertieren. \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ @@ -183,7 +183,7 @@ Multiplizieren wir nun aus, erhalten wir unseren Nutzdatenteil \[ m = [4,7,2,5,8,1] \] -zurück, den wir ursprünglich versendet haben. +zurück, den wir ursprünglich versandt haben. Wir möchten noch anmerken, dass es mehrere Wege für die Rekonstruktion des Nutzdatenteils gibt, diese aber alle auf dem Lokatorpolynom basieren. diff --git a/buch/papers/reedsolomon/zusammenfassung.tex b/buch/papers/reedsolomon/zusammenfassung.tex index a098107..ff3f35f 100644 --- a/buch/papers/reedsolomon/zusammenfassung.tex +++ b/buch/papers/reedsolomon/zusammenfassung.tex @@ -5,15 +5,15 @@ % \section{Zusammenfassung \label{reedsolomon:section:zf}} -\rhead{Zusammenfassung} \index{Reed-Solomon-Code, Zusammenfassung}% \index{Zusammenfassung Reed-Solomon-Code}% Dieser Abschnitt beinhaltet eine Übersicht über die Funktionsweise eines Reed-Solomon-Codes für beliebige endliche Körper. -\subsubsection{Schritt 1: primitives Element} +\subsubsection{Schritt 1: Primitives Element} Zu Beginn soll entschieden werden, in welchem endlichen Körper $\mathbb{F}_{q}$ gerechnet werden soll. Ausserdem muss im gewählten Körper eine primitive Einheitswurzel gefunden, bzw. bestimmt werden. +\rhead{Zusammenfassung} \subsubsection{Schritt 2: Codierung} Für die Codierung wird die Nachricht als Koeffizienten des Polynoms $m(X)$ geschrieben, anschliessend wird $a^i$ in $m(X)$ eingesetzt. Daraus ergibt sich die Codierungsmatrix diff --git a/buch/papers/spannung/main.tex b/buch/papers/spannung/main.tex index d2aeda9..14bab31 100644 --- a/buch/papers/spannung/main.tex +++ b/buch/papers/spannung/main.tex @@ -4,9 +4,9 @@ % (c) 2020 Hochschule Rapperswil % \chapter{Dreidimensionaler Spannungszustand\label{chapter:spannung}} -\lhead{Dreiachsiger Spannungszustand} +\lhead{Dreidimensionaler Spannungszustand} \begin{refsection} -\chapterauthor{Adrian Schuler und Thomas Reichlin} +\chapterauthor{Thomas Reichlin und Adrian Schuler} % TODO Text diff --git a/buch/papers/spannung/teil0.tex b/buch/papers/spannung/teil0.tex index f9afde0..f708055 100644 --- a/buch/papers/spannung/teil0.tex +++ b/buch/papers/spannung/teil0.tex @@ -9,7 +9,7 @@ Man spricht auch von einem Elementarwürfel. \begin{figure} \centering \includegraphics[width=0.4\linewidth,keepaspectratio]{papers/spannung/Grafiken/Bild2.png} - \caption{Infinitesimales Bodenelement mit den 9 Spannungen} + \caption{Infinitesimales Bodenelement mit den neun Spannungen} \label{fig:Bild2} \end{figure} @@ -27,8 +27,8 @@ Daraus können die äquivalenten Dehnungen $\varepsilon$ mit Hilfe des Hook'sche Daher gibt es auch den entsprechenden Dehnungszustand. -\section{Spannungszustand\label{spannung:section:Spannungsustand}} -\rhead{Spannungszustand} +\section{Einachsiger Spannungszustand\label{spannung:section:Spannungsustand}} +\rhead{Einachsiger Spannungszustand} Im einachsigen Spannungszustand herrscht nur die Normalspannung $\sigma_{11}$ (siehe Abbildung~\ref{fig:Bild1}). Das Hook'sche Gesetz beschreibt genau diesen 1D Spannungszustand. @@ -72,7 +72,8 @@ Es ist praktisch, die relative Dehnung $\varepsilon$ anzugeben und nicht eine ab \caption{1D Spannungszustand aus einer quaderförmigen Bodenprobe} \label{fig:Bild1} \end{figure} -Mithilfe vom Elastizitätsmodul $E$ als Proportionalitätskonstante lässt sich der eindimensionale Fall mit +Mithilfe vom Elastizitätsmodul $E$ (auch Youngscher Modul) als Proportionalitätskonstante lässt sich der eindimensionale Fall mit +\index{Youngscher Modul} \[ \sigma = diff --git a/buch/papers/spannung/teil1.tex b/buch/papers/spannung/teil1.tex index 10f7663..552c1cf 100644 --- a/buch/papers/spannung/teil1.tex +++ b/buch/papers/spannung/teil1.tex @@ -1,23 +1,23 @@ \section{Skalare, Vektoren, Matrizen und Tensoren\label{spannung:section:Skalare,_Vektoren,_Matrizen_und_Tensoren}} \rhead{Skalare, Vektoren, Matrizen und Tensoren} -Der Begriff Tensor kann als Überbegriff der mathematischen Objekte Skalar, Vektor und Matrix, betrachtet werden. +Der Begriff Tensor kann als Überbegriff der mathematischen Objekte Skalar, Vektor und Matrix betrachtet werden. \index{Tensor}% Allerdings sind noch höhere Stufen dieser Objekte beinhaltet. Skalare, Vektoren oder Matrizen sind daher auch Tensoren. Ein Skalar ist ein Tensor 0. Stufe. \index{Stufe}% Mit einem Vektor können mehrere Skalare auf einmal beschrieben werden. -Ein Vektor hat daher die Stufe 1 und ist höherstufig als ein Skalar. +Ein Vektor hat daher die Stufe 1 und ist höherstufiger als ein Skalar. Mit einer Matrix können wiederum mehrere Vektoren auf einmal beschrieben werden. -Eine Matrix hat daher die Stufe 2 und ist noch höherstufig als ein Vektor. +Eine Matrix hat daher die Stufe 2 und ist noch höherstufiger als ein Vektor. Versteht man diese Stufen, so versteht man den Sinn des Begriffs Tensor. Jede Stufe von Tensoren verlangt andere Rechenregeln. So zeigt sich auch der Nachteil von Tensoren mit Stufen höher als 2. Man ist also bestrebt höherstufige Tensoren mit Skalaren, Vektoren oder Matrizen zu beschreiben. -In den 40er Jahren des 19.~Jahrhunderts wurde der Begriff Tensor von Rowan Hamilton in die Mathematik eingeführt. -\index{Hamilton, Rowan}% +In den 40er Jahren des 19.~Jahrhunderts wurde der Begriff Tensor von William Rowan Hamilton in die Mathematik eingeführt. +\index{Hamilton, William Rowan}% James Clerk Maxwell hat bereits mit Tensoren operiert, ohne den Begriff Tensor gekannt zu haben. \index{Maxwell, James Clerk}% Erst Woldemar Voigt hat den Begriff in die moderne Bedeutung von Skalar, Matrix und Vektor verallgemeinert. diff --git a/buch/papers/spannung/teil2.tex b/buch/papers/spannung/teil2.tex index 8bf1968..fec0120 100644 --- a/buch/papers/spannung/teil2.tex +++ b/buch/papers/spannung/teil2.tex @@ -4,17 +4,17 @@ Durch komplexe Spannungsausbreitungen im Boden entstehen im 3D-Spannungszustand \begin{figure} \centering \includegraphics[width=0.30\linewidth,keepaspectratio]{papers/spannung/Grafiken/infinitesimalerWuerfel.png} - \caption{Beispiel eines Spannungszustandes; Vergrösserung eines infinitesimalen Bodenteilchen} + \caption{Beispiel eines Spannungszustandes; Vergrösserung eines infinitesimalen Bodenteilchens} \label{fig:infinitesimalerWuerfel} \end{figure} Ein Tensor 0.~Stufe, sprich ein Skalar, kann lediglich den 1D-Spannungszustand beschreiben. -Um den 3D-Spannungszustandes als ein mathematisches Objekt darstellen zu können, wird ein Tensor 2.~Stufe, sprich eine Matrix, eingesetzt. +Um den 3D-Spannungszustand als ein mathematisches Objekt darstellen zu können, wird ein Tensor 2.~Stufe, sprich eine Matrix, eingesetzt. Die Spannungen sind durch die zwei Indizes \( i, j\in\left\{1, 2, 3\right\} \) definiert. -Daher ergeben sich die neun Spannungen. +Daher ergeben sich die $9$ Spannungen. Die nachfolgenden Zusammenhänge sind in \cite{spannung:Voigtsche-Notation} beschrieben. Dieser Spannungstensor kann schliesslich mit $3^2$ Einträgen als $3\times3$ Matrix mit \[ @@ -48,7 +48,7 @@ Der Dehnungstensor ist ebenfalls ein Tensor 2.~Stufe und kann somit auch als $3\ \] dargestellt werden und beschreibt den gesamten Dehnungszustand. -Der Spannungs- und Dehnungstensor 2.~Stufe kann je in einen Tensor 1.~Stufe überführt werden, welches ein Spaltenvektor ist. +Der Spannungs- und Dehnungstensor 2.~Stufe kann je in einen Tensor 1.~Stufe überführt werden, welcher ein Spaltenvektor ist. Man darf Zeile um Zeile in eine Spalte notieren, sodass es einen Spaltenvektor ergibt. So ergibt sich der Spannungsvektor @@ -114,8 +114,8 @@ Dieser ist im 1D-Spannungszustand ein Tensor 0.~Stufe und somit ein Skalar, der Dieser Elastizitätstensor 4.~Stufe kann als Tensor 2.~Stufe, sprich als Matrix, dargestellt werden. So wird die Spannungsgleichung stark vereinfacht, da nun eine Matrix auf einen Vektor operiert. -Dieser Tensor muss für eine Spannung jeden Einfluss aus allen neun Dehnungen mit Konstanten erfassen. -Dies bedeutet um eine von neun Spannungen berechnen zu können müssen alle neun Dehnung mit unterschiedlichen Faktoren summiert werden. +Dieser Tensor muss für eine Spannung jeden Einfluss aus allen $9$ Dehnungen mit Konstanten erfassen. +Dies bedeutet um eine von $9$ Spannungen berechnen zu können müssen alle $9$ Dehnung mit unterschiedlichen Faktoren summiert werden. Es ergeben sich $9^2$ Einträge, welches mit den vier Indizes \( i, j, k, l\in\left\{1, 2, 3\right\} @@ -233,7 +233,7 @@ Die Normalspannung $\sigma_{22}$ lässt sich zum Beispiel als berechnen. \section{Reduzierte Spannungs- und Dehnungsgleichungen} - +\rhead{Reduzierte Spannungs- und Dehnungsgleichungen} Man betrachte nun die Eigenschaften des Elastizitätstensors. Dieser ist quadratisch und symmetrisch, die verschiedenen Einträge wechseln sich aber miteinander ab. Es ergeben sich keine Blöcke mit einheitlichen Einträgen. @@ -354,14 +354,19 @@ beziehungsweise \sigma_{12} \end{pmatrix} = +%\left( +%\begin{array}{ccc|ccc} \begin{pmatrix} C_{1111} & C_{1122} & C_{1133} & C_{1123} & C_{1113} & C_{1112} \\ C_{2211} & C_{2222} & C_{2233} & C_{2223} & C_{2213} & C_{2212} \\ C_{3311} & C_{3322} & C_{3333} & C_{3323} & C_{3313} & C_{3312} \\ +%\hline C_{2311} & C_{2322} & C_{2333} & C_{2323} & C_{2313} & C_{2312} \\ C_{1311} & C_{1322} & C_{1333} & C_{1323} & C_{1313} & C_{1312} \\ C_{1211} & C_{1222} & C_{1233} & C_{1223} & C_{1213} & C_{1212} \end{pmatrix} +%\end{array} +%\right) \begin{pmatrix} \varepsilon_{11} \\ \varepsilon_{22} \\ @@ -417,14 +422,19 @@ Dies ergibt die Spannungsgleichung, welche weit möglichst vereinfacht ist: \end{pmatrix} = \frac{E}{(1+\nu)(1-2\nu)} -\begin{pmatrix} +\left( +\begin{array}{ccc|ccc} +%\begin{pmatrix} 1- 2\nu & \nu & \nu & 0 & 0 & 0\\ \nu & 1- 2\nu & \nu & 0 & 0 & 0\\ \nu & \nu & 1- 2\nu & 0 & 0 & 0\\ +\hline 0 & 0 & 0 & \frac{1}{2} & 0 & 0\\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0\\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} -\end{pmatrix} +%\end{pmatrix} +\end{array} +\right) \begin{pmatrix} \varepsilon_{11}\\ \varepsilon_{22}\\ @@ -468,14 +478,19 @@ Durch einige Berechnungsschritte erhält man die Dehnungsgleichung: \end{pmatrix} = \frac{1}{E} -\begin{pmatrix} +\left( +\begin{array}{ccc|ccc} +%\begin{pmatrix} 1 & -\nu & -\nu & 0 & 0 & 0 \\ -\nu & 1 & -\nu & 0 & 0 & 0 \\ -\nu & -\nu & 1 & 0 & 0 & 0 \\ +\hline 0 & 0 & 0 & 2+2\nu & 0 & 0 \\ 0 & 0 & 0 & 0 & 2+2\nu & 0 \\ 0 & 0 & 0 & 0 & 0 & 2+2\nu -\end{pmatrix} +%\end{pmatrix} +\end{array} +\right) \begin{pmatrix} \sigma_{11}\\ \sigma_{22}\\ diff --git a/buch/papers/spannung/teil3.tex b/buch/papers/spannung/teil3.tex index c68c0d1..147fe01 100644 --- a/buch/papers/spannung/teil3.tex +++ b/buch/papers/spannung/teil3.tex @@ -13,7 +13,7 @@ Folglich gilt: \] Dadurch wird der Spannungszustand vereinfacht. Diesen vereinfachten Spannungszustand kann man mit den zwei geotechnischen Invarianten abbilden. -Die erste Invariante ist die volumetrische Spannung +Die erste Invariante ist die volumetrische oder auch hydrostatische Spannung \begin{equation} p = @@ -76,8 +76,8 @@ Die Faktoren mit den Dehnungskomponenten können so als \] eingeführt werden, mit \begin{align*} - \varepsilon_{v} &= \text{Hydrostatische Dehnung [-]} \\ - \varepsilon_{s} &= \text{Deviatorische Dehnung [-].} + \varepsilon_{v} &= \text{hydrostatische Dehnung [-]} \\ + \varepsilon_{s} &= \text{deviatorische Dehnung [-].} \end{align*} Die hydrostatische Dehnung $\varepsilon_{v}$ kann mit einer Kompression und die deviatorische Dehnung $\varepsilon_{s}$ mit einer Verzerrung verglichen werden. @@ -105,6 +105,7 @@ vereinfachen. Diese Spannungsgleichung mit den zwei Einträgen ($p$ und $q$) ist gleichwertig wie die ursprüngliche Spannungsgleichung mit den neun Einträgen ($\sigma_{11}$, $\sigma_{12}$, $\sigma_{13}$, $\sigma_{21}$, $\sigma_{22}$, $\sigma_{23}$, $\sigma_{31}$, $\sigma_{32}$, $\sigma_{33}$). -Mit dieser Formel \eqref{spannung:Matrixschreibweise} lassen sich verschieden Ergebnisse von Versuchen analysieren und berechnen. +Mit dieser Formel \eqref{spannung:Matrixschreibweise} lassen sich Ergebnisse von Versuchen analysieren und berechnen. Ein solcher Versuch, der oft in der Geotechnik durchgeführt wird, ist der Oedometer-Versuch. -Im nächsten Kapitel wird die Anwendung der Matrix an diesem Versuch beschrieben. +In Abschnitt~\ref{spannung:section:Oedometrischer Elastizitätsmodul} +wird die Anwendung der Matrix an diesem Versuch beschrieben. diff --git a/buch/papers/spannung/teil4.tex b/buch/papers/spannung/teil4.tex index 2e0de45..06d67c9 100644 --- a/buch/papers/spannung/teil4.tex +++ b/buch/papers/spannung/teil4.tex @@ -78,5 +78,5 @@ Mit diesen Gleichungen hat man das Gleichungssystem um $E_{\text{OED}}$ und $\si Die Poisson-Zahl muss als Kennwert gemäss der Bodenklasse gewählt werden. Den Versuch kann man auf einem $\sigma$-$\varepsilon$-Diagramm abtragen (siehe Abbildung~\ref{fig:DiagrammOedometer-Versuch}). Durch die Komprimierung nimmt der Boden mehr Spannung auf, und verformt sich zugleich weniger stark. -Mit diesem ermittelten $E_{\text{OED}}$ kann man nun weitere Berechnungen für die Geotechnik durchführen. +Mit diesem ermittelten $E_{\text{OED}}$ kann man nun weitere Berechnungen in der Geotechnik durchführen. diff --git a/buch/papers/uebersicht.tex b/buch/papers/uebersicht.tex index b809892..f095947 100644 --- a/buch/papers/uebersicht.tex +++ b/buch/papers/uebersicht.tex @@ -10,5 +10,133 @@ Im zweiten Teil kommen die Teilnehmer des Seminars selbst zu Wort. Die im ersten Teil dargelegten mathematischen Methoden und grundlegenden Modelle werden dabei verfeinert, verallgemeinert -und auch numerisch überprüft. +und auf vielfältige Weise angewandt. + +Den Anfang machen {\em Robine Luchsinger} und {\em Pascal Andreas Schmid}, +\index{Luchsinger, Robine}% +\index{Schmid, Pascal Andreas}% +die zeigen, wie man basierend auf der Adjazenzmatrix Suchalgorithmen +für Netzwerke aufbauen kann. +Sie konzentrieren sich dabei auf Verkehrsnetze, die die zusätzliche +Eigenschaft haben, eine geometrische Realsierung zu besitzen. +Diese führt zu zusätzlichen Einschränkungen, die einen positiven +Einfluss auf die Effizienz der Suchalgorithmen haben können. + +Die naive Umsetzung der Definition der Matrizenmultiplikation in +ein Coputerprogramm ist nicht unbedingt die effizienteste. +{\em Michael Schmid} stellt die Algorithmen von Strassen und +\index{Schmid, Michael}% +Windograd vor, welche ermöglichen, die Laufzeitkomplexität +von $O(n^3)$ auf $O(n^{2.8074})$ oder noch schneller zu verbessern. +Allerdings nur unter gewissen Voraussetzungen, die im Paper +ebenfalls diskutiert werden. + +Eine der schönsten Anwendungen der Gruppentheorie ist die +Kristallographie. +{\em Naoki Pross} und {\em Tim Tönz} zeigen, wie man mit ihrer +\index{Pross, Naoki}% +\index{Tönz, Tim}% +Hilfe Kristalle klassifizieren kann, und sie illustrieren am Beispiel +der Piezoelektrizität, dass man auch physikalische Eigenschaften daraus +ableiten kann. + +Der Reed-Solomon-Code ist ein Klassiker unter den fehlerkorrigierenden +Codes. +Berühmt gemacht durch seine Anwendung in den Voyager-Sonden und in CDs +und DVDs, begegnet er uns heute auch in den allgegenwärtigen QR-Codes. +Ein ganzes Arsenal von algebraischen Methoden ist nötig, um seine +Funktionsweise zu verstehen. +{\em Joshua Bär} und {\em Michael Steiner} zeigen in vielen Einzelschritten, +\index{Bär, Joshua}% +\index{Steiner, Michael}% +wie die man die einzelnen Ideen an vertrauteren Beispielen aus der +elementaren Algebra und der Fourier-Theorie verstehen kann. +Die Übertragung in einen Polynomring über einem endlichen Körper +ist dann nicht mehr schwierig. +Die Analogie wird deutlich, wenn man das Codierungsverfahren und +die diskrete Fourier-Transformation beide als Matrizen schreibt. + +Wer glaubt, mit linearen Abbildungen lassen sich nur gradlinige +Objekte beschreiben, liegt völlig falsch. +Die Arbeit von {\em Alain Keller} zeigt, dass die Iteration von +\index{Keller, Alain}% +affinen Abbildungen hochkomplexe Fraktale hervorbringen kann. +Solche iterierten Funktionsschemata erzeugen aber nicht nur schöne +Bilder, man kann daraus auch eine Idee zur Kompression von +Bildern ableiten. + +Es gibt zwar noch keine ernstzunehmenden Quantencomputer, aber man weiss +bereits, dass ein leistungsfähriger Quantencomputer viele der heute +im Internet üblichen Verschlüsselungsverfahren, allen voran das RSA-Verfahren, +brechen könnte. +Das McEliece-Kryptosystem kombiniert verschiedene Arten von Matrizen +mit zufälligem Rauschen und einem fehlerkorrigierenden Code. +Wie {\em Reto Fritsche} erklärt, kommt dabei ein Verschlüsselungsverfahren +\index{Fritsche, Reto}% +heraus, welches nach heutigem Wissensstand gegen Angriffe mit +Quantencomputern resistent ist. + +Vektoren und Matrizen bilden die Basis vieler geometrischer +Anwendungen. +Doch ist die Beschreibung von Bewegungen im Raum mit Matrizen nicht +immer einfach. +In der Ebene kann man die komplexen Zahlen als Modell verwenden, +wo Drehungen und Translationen durch einfache arithmetische +Operationen mit Zahlen beschrieben werden können. +{\em Marius Baumann} und {\em Thierry Schwaller} tauchen in die +\index{Baumann, Marius}% +\index{Schwaller, Thierry}% +geometrische Algebra ein, welche diese Idee verallgemeinert. +Sie illustrieren, wie sich mit geometrischer Algebra Bewegungen +in $\mathbb{R}^n$ einfach beschreiben lassen. +So gibt es zum Beispiel ein Euler-Formel, für Drehungen und Spiegelungen +kann die selbe Abbildungsformel verwendet werden und die Zusammensetzung +von Transformationen ist eine Multiplikation in einer Algebra, die +aus den Vektoren konstruiert worden ist. +In drei Dimensionen ist diese Algebra der Quaternionen zum Beispiel +in der Computergraphik sehr beliebt. + +Man soll sein Haus nicht auf Sand bauen, sagt eine Redensart. +Etwas mathematischer heisst das, dass man den Spannungszustand, +der von einem Gebäude im darunterliegenden Boden aufgebaut wird, +im Detail verstehen und modellieren können sollte. +Dazu muss man erst eine geeignete Darstellung finden. +{\em Thomas Reichlin} und {\em Adrian Schuler} zeigen, wie man +\index{Reichlin, Thomas}% +\index{Schuler, Adrian}% +dazu eigentlich über die Welt der Matrizen hinaus gehen muss und +sich mit sogenannten Tensoren herumschlagen muss. +Dank sinnvollen Annahmen über die reale Situation im Boden +kann man aber auf eine handlichere Beschreibung zurückkommen, +die wieder nur Matrizen verwendet. +Ausserdem ergeben sich daraus spezielle Blockstrukturen der +Matrizen. + +Ein Erdbeben versetzt alles auf der Erdoberfläche in Bewegung und +kann beträchtliche Schäden anrichten. +Daher wird die seismische Aktivität weiltweit überwacht. +Ein Seismograph enthält eine schwingungsfähige Masse, die die Bewegungen +aufzeichen kann. +Doch welcher Teil der aufgezeichneten Bewegung kommt vom Erdbeben +und welcher Teil ist Eigenschwingung der Messmasse? +Dieser Frage gehen {\em Fabio Viecelli} und {\em Lukas Zogg} nach. +\index{Viecelli, Fabio}% +\index{Zogg, Lukas}% +Die Antwort gelingt mit einem Klassiker unter den Ingenieur-Methoden: +dem Kalman-Filter. +Die Autoren stellen die für den Filter nötigen Matrizen zusammen +und illustrieren mit Hilfe von Simulationen, wie er funktioniert. + +Eine Matrix kann dazu verwende werden, die Kosten zusammenzustellen, +die die Lösung einzelner Aufgaben durch verschiedene Anbieter +verursachen würden. +Doch wie findet man jetzt diejenige Zuteilung der Aufgaben +zu den Anbietern, die die Gesamtkosten minimiert. +Für dieses klassische Zuordnungsproblem ist die +von {\em Marc Kühne} beschriebene ungarische Methode, +\index{Kühne, Marc}% +auch als Munkres-Algorithmus bekannt, eine besonders effiziente +Lösung. + + diff --git a/buch/papers/verkehr/main.tex b/buch/papers/verkehr/main.tex index 98d0581..7972988 100644 --- a/buch/papers/verkehr/main.tex +++ b/buch/papers/verkehr/main.tex @@ -4,8 +4,10 @@ % (c) 2020 Hochschule Rapperswil % \chapter{Verkehrsfluss und Verkehrsnetze\label{chapter:verkehr}} +\lhead{Verkehrsfluss und Verkehrsnetze} +\rhead{} \begin{refsection} -\chapterauthor{Pascal Andreas Schmid und Robine Luchsinger} +\chapterauthor{Robine Luchsinger und Pascal Andreas Schmid} \input{papers/verkehr/section1.tex} \input{papers/verkehr/section2.tex} diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 4a450f1..cc5893d 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -8,12 +8,13 @@ Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, a Aus verkehrsgeografischer Sicht besteht das Verkehrsnetz aus Kanten, Knotenpunkten und dem Hinterland. Die Knotenpunkte werden auch hier durch die Kanten verbunden, die den Verkehrsstrom aufnehmen, wobei das Hinterland durch einzelne Knoten versorgt wird. Die Aufteilung in Kanten und Knotenpunkte ermöglicht eine Vereinfachung komplexer Verkehrsnetze, damit sie mittels der Graphentheorie untersucht werden können. \index{Knotenpunkt}% \index{Hinterland}% -\index{Verkehrtsstrom}% +\index{Verkehrsstrom}% Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes. \index{Graphentheorie}% Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. \section{Suchalgorithmen} +\rhead{Suchalgorithmen} Inbesondere bei Graphen in Form von Verkehrsnetzen ist das Finden eines kürzesten Weges von Interesse. Mathematisch betrachtet handelt es sich hierbei um ein Optimierungsproblem, bei dem die Summe der Kantengewichte zwischen zwei Knoten minimiert werden soll. Zu diesem Zweck existieren verschiedene Suchalgorithmen. In den folgenden Abschnitten wird auf eine Auswahl davon eingegangen. Zuvor ist es jedoch notwendig, einige Begriffe und Eigenschaften von Suchalgorithmen zu definieren. \index{kürzester Weg}% \index{Optimierungsproblem}% @@ -98,6 +99,7 @@ ermittelt. \section{PageRank-Algorithmus} +\rhead{PageRank-Algorithmus} \index{PageRank-Algorithmus}% \index{Page, Larry}% \index{Brin, Sergey}% diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex index a0e88b6..90cea3f 100644 --- a/buch/papers/verkehr/section2.tex +++ b/buch/papers/verkehr/section2.tex @@ -7,6 +7,7 @@ Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenze \index{Zeitkomplexität}% Für den A*-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine definitive Angabe zur Zeitkomplexität machen. +\rhead{Versuchsreihe} Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. \subsection{Einfluss der Knotenzahl auf die Rechenzeit} diff --git a/buch/papers/verkehr/section3.tex b/buch/papers/verkehr/section3.tex index 50bae2a..76fb3b0 100644 --- a/buch/papers/verkehr/section3.tex +++ b/buch/papers/verkehr/section3.tex @@ -1,4 +1,5 @@ \section{Ausblick} +\rhead{Ausblick} \subsection{Optimierungsprobleme bei Graphen} Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Graphen aufstellen lassen. Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen. |
