diff options
author | Andreas Müller <andreas.mueller@ost.ch> | 2021-09-25 16:43:39 +0200 |
---|---|---|
committer | Andreas Müller <andreas.mueller@ost.ch> | 2021-09-25 16:43:39 +0200 |
commit | f88b8071a623096f9004007ced8ec97195aaa218 (patch) | |
tree | 9fad214708204690b2f724459234d66ffde8d12b /buch/chapters | |
parent | more missing periods (diff) | |
download | SeminarMatrizen-f88b8071a623096f9004007ced8ec97195aaa218.tar.gz SeminarMatrizen-f88b8071a623096f9004007ced8ec97195aaa218.zip |
zweite Lesung
Diffstat (limited to 'buch/chapters')
48 files changed, 614 insertions, 386 deletions
diff --git a/buch/chapters/05-zahlen/ganz.tex b/buch/chapters/05-zahlen/ganz.tex index 827346d..ab80d6f 100644 --- a/buch/chapters/05-zahlen/ganz.tex +++ b/buch/chapters/05-zahlen/ganz.tex @@ -6,7 +6,6 @@ % !TeX spellcheck = de_CH \section{Ganze Zahlen \label{buch:section:ganze-zahlen}} -\rhead{Ganze Zahlen} Die Menge der ganzen Zahlen löst das Problem, dass nicht jede Gleichung der Form $x+a=b$ mit $a, b \in \mathbb N$ eine Lösung $x \in \mathbb N$ hat. @@ -14,6 +13,7 @@ Dazu ist erforderlich, den natürlichen Zahlen die negativen Zahlen hinzuzufügen, also wieder die Existenz neuer Objekte zu postulieren, die die Rechenregeln weiterhin erfüllen. +\rhead{Ganze Zahlen} \subsubsection{Paare von natürlichen Zahlen} Die ganzen Zahlen können konstruiert werden als Paare $(u,v)$ von natürlichen Zahlen $u,v\in\mathbb{N}$. diff --git a/buch/chapters/05-zahlen/komplex.tex b/buch/chapters/05-zahlen/komplex.tex index f1f2f05..2f9378d 100644 --- a/buch/chapters/05-zahlen/komplex.tex +++ b/buch/chapters/05-zahlen/komplex.tex @@ -5,7 +5,6 @@ % \section{Komplexe Zahlen \label{buch:section:komplexe-zahlen}} -\rhead{Komplexe Zahlen} In den reellen Zahlen lassen sich viele algebraische Gleichungen lösen, die in $\mathbb{Q}$ nicht lösbar waren. Andere, z.~B.~die Gleichung @@ -31,6 +30,8 @@ Es muss darin Zahlen geben, deren Quadrat negativ ist und der Grössenvergleich dieser Zahlen untereinander ist nur eingeschränkt möglich. +\rhead{Komplexe Zahlen} + \subsubsection{Imaginäre und komplexe Zahlen} Den reellen Zahlen fehlen also Zahlen, deren Quadrat negativ ist. Nach inzwischen bewährtem Muster konstruieren wird die neuen Zahlen diff --git a/buch/chapters/10-vektorenmatrizen/ringe.tex b/buch/chapters/10-vektorenmatrizen/ringe.tex index ac64fa6..6c7e091 100644 --- a/buch/chapters/10-vektorenmatrizen/ringe.tex +++ b/buch/chapters/10-vektorenmatrizen/ringe.tex @@ -3,7 +3,7 @@ % % (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule % -\subsection{Ringe und Moduln +\subsection{Ring \label{buch:grundlagen:subsection:ringe}} Die ganzen Zahlen haben ausser der Addition mit neutralem Element $0$ auch noch eine Multiplikation mit dem neutralen Element $1$. diff --git a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex index 47cb2ba..aa0bf17 100644 --- a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex +++ b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex @@ -887,6 +887,7 @@ Der Vektorraum der linearen Abbildungen $f\colon U\to V$ kann mit einer Norm ausgestattet werden, wenn $U$ und $V$ jeweils eine Norm haben. \begin{definition} +\label{buch:vektoren-matrizen:def:operatornorm} Seien $U$ und $V$ Vektorräume über $\mathbb{R}$ oder $\mathbb{C}$ und $f\colon U\to V$ eine lineare Abbildung. Die {\em Operatornorm} der linearen Abbildung ist diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index da8997d..8052d4c 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -6,7 +6,6 @@ % !TeX spellcheck = de_CH \section{Wurzeln \label{buch:section:wurzeln}} -\rhead{Wurzeln} Im Körper $\mathbb{Q}$ kann man zum Beispiel die Wurzel aus $2$ nicht ziehen. Das Problem haben wir in Abschnitt~\ref{buch:section:reelle-zahlen} @@ -23,6 +22,7 @@ da man diese nicht in $\mathbb{R}$ einbetten kann, also keine bekannte Menge von Zahlen existiert, in der wir die Wurzel $\sqrt{2}$ finden könnten. +\rhead{Wurzeln} Im Altertum fiel dieses Problem zunächst den Pythagoreern auf. Wenn $\sqrt{2}$ kein Bruch ist, was ist es dann? Im 15.~Jahrhundert stellte sich dieses Problem bei den Versuchen, die @@ -560,7 +560,7 @@ Zur Kontrolle berechnen wir das Produkt $b(X)\cdot a(X)$, es ist &= 3X^4+X^3+3X^2+6X. \intertext{ -Dieses Polynom muss jetzt mit dem Minimalpolynom $m(X)$ reduziert +Dieses Polynom muss jetzt mit dem Polynom $m(X)$ reduziert werden, wir subtrahieren dazu $3Xm(X)$ und erhalten} &= -5X^3-3X^2-3X diff --git a/buch/chapters/40-eigenwerte/chapter.tex b/buch/chapters/40-eigenwerte/chapter.tex index 65cf608..809373b 100644 --- a/buch/chapters/40-eigenwerte/chapter.tex +++ b/buch/chapters/40-eigenwerte/chapter.tex @@ -35,17 +35,19 @@ Potenzen von Matrizen und ihren invarianten Unterräumen. \index{Unterraum, invarianter}% Es ergibt sich bereits eine Normalform für nilpotente Matrizen. \index{nilpotent}% -In Abschnitt~\ref{buch:section:eigenwerte-eigenvektoren} wird daraus die +In Abschnitt~\ref{buch:section:eigenwerte-und-eigenvektoren} wird daraus die allgemeine Eigenwerttheorie entwickelt. Damit kann dann in Abschnitt~\ref{buch:section:normalformen} gezeigt werden, wie Matrizen in Normalform gebracht werden können. -Für viele Funktionen kann man auch den Wert $f(A)$ berechnen. +In Anwendungen möchte man oft $f(A)$ +für eine Funktion $f\colon \mathbb{C}\to\mathbb{C}$ berechnen. +%Für viele Funktionen kann man auch den Wert $f(A)$ berechnen. In Abschnitt~\ref{buch:section:analytische-funktionen-einer-matrix} wird gezeigt, wie dies für analytische Funktionen und für Funktionen möglich \index{analytische Funktion}% ist, die durch Polynome approximiert werden. -Es zeigt sich, dass dazu geeigneten Voraussetzungen an den sogenannten -Spektralradius gestelltw erden müssen. +Es zeigt sich, dass dazu geeigneten Voraussetzungen durch den sogenannten +Spektralradius erfüllt werden müssen. \index{Spektralradius}% Es stellt sich heraus, dass man nicht für alle Matrizen $A$ eine sinnvolle Definition von $f(A)$ für beliebige stetige Funktionen $f$ diff --git a/buch/chapters/40-eigenwerte/eigenwerte.tex b/buch/chapters/40-eigenwerte/eigenwerte.tex index f0d7b16..745dd5f 100644 --- a/buch/chapters/40-eigenwerte/eigenwerte.tex +++ b/buch/chapters/40-eigenwerte/eigenwerte.tex @@ -5,6 +5,7 @@ % \section{Eigenwerte und Eigenvektoren \label{buch:section:eigenwerte-und-eigenvektoren}} +\rhead{Eigenwerte und Eigenvektoren} In diesem Abschnitt betrachten wir Vektorräume $V=\Bbbk^n$ über einem beliebigen Körper $\Bbbk$ und quadratische Matrizen $A\in M_n(\Bbbk)$. @@ -32,7 +33,7 @@ heisst das {\em Spektrum} von $A$. \end{definition} Die Bedingung $v\ne 0$ dient dazu, pathologische Situationen auszuschliessen. -Für den Nullvektor gilt $A0=\lambda 0$ für jeden beliebigen Wert von +Für den Nullvektor $0\in V$ gilt $A0=\lambda 0$ für jeden beliebigen Wert von $\lambda\in\Bbbk$. Würde man $v=0$ zulassen, wäre jede Zahl in $\Bbbk$ ein Eigenwert, ein Eigenwert von $A$ wäre nichts besonderes. @@ -43,7 +44,7 @@ Vielfache von $v$ ist ebenfalls ein Eigenvektor. Zu einem Eigenwert kann man also einen Eigenvektor mit geeigneten Eigenschaften finden, zum Beispiel kann man für $\Bbbk = \mathbb{R}$ Eigenvektoren auf Länge $1$ normieren. -Im Folgenden werden wir oft die abkürzend linear unabhängige Eigenvektoren +Im Folgenden werden wir oft abkürzend linear unabhängige Eigenvektoren einfach als ``verschiedene'' Eigenvektoren bezeichnen. Wenn $v$ ein Eigenvektor von $A$ zum Eigenwert $\lambda$ ist, dann kann @@ -77,7 +78,7 @@ Für $\lambda\in\Bbbk$ heisst \[ E_\lambda = -\{ v\;|\; Av=\lambda v\} +\{ v\in V \mid Av=\lambda v\} \] der {\em Eigenraum} zum Eigenwert $\lambda$. \index{Elambda(A)@$E_\lambda(A)$}% @@ -110,7 +111,7 @@ oder $A=\lambda I$. \end{proof} Wenn man die Eigenräume von $A$ kennt, dann kann man auch die Eigenräume -von $A+\mu E$ berechnen. +von $A+\mu I$ berechnen. Ein Vektor $v\in E_\lambda$ erfüllt \[ Av=\lambda v @@ -162,7 +163,7 @@ B \] und wir berechnen davon die vierte Potenz \[ -D=B^4=(A-E)^4 +D=B^4=(A-I)^4 = \begin{pmatrix} 0&0& 0&0\\ @@ -207,19 +208,21 @@ Als erstes überprüfen wir, ob diese Basisvektoren tatsächlich invariante Unterräume sind. Für $\mathcal{J}(A-I) = \langle b_1,b_2\rangle$ berechnen wir -\begin{align*} +\[ +\begin{aligned} (A-I)b_1 &= \begin{pmatrix} 0\\4\\4\\1 \end{pmatrix} = -4b_2+b_1, +4b_2+b_1&&\in\langle b_1,b_2\rangle, \\ (A-I)b_2 &= \begin{pmatrix} 0\\1\\1\\0 \end{pmatrix} = -b_2. -\end{align*} +b_2&&\in\langle b_1,b_2\rangle. +\end{aligned} +\] Dies beweist, dass $\mathcal{J}(A-I)$ invariant ist. In dieser Basis hat die von $A-I$ beschriebene lineare Abbildung auf $\mathcal{J}(A-I)$ die Matrix @@ -268,7 +271,7 @@ A' \] die Blöcke gehören zu den invarianten Unterräumen $\mathcal{K}(A-I)$ und $\mathcal{K}(A-I)$. -Die aus $A-E$ gewonnen invarianten Unterräume sind offenbar auch invariante +Die aus $A-I$ gewonnenen invarianten Unterräume sind offenbar auch invariante Unterräume für $A$. \end{beispiel} @@ -280,7 +283,7 @@ Unterraum = \mathcal{K}(A-\lambda I) \] -der {\em verallgemeinerte Eigenraum} von $A$. +der {\em verallgemeinerte Eigenraum} von $A$ zum Eigenwert $\lambda$. \index{verallgemeinerter Eigenraum}% \index{Eigenraum, verallgemeinerter}% \end{definition} @@ -305,10 +308,11 @@ V \oplus \underbrace{\mathcal{J}(A-\lambda_1 I)}_{\displaystyle =V_2}, \] +in invariante Unterräume, wobei $\mathcal{E}_{\lambda_1}(A)\ne 0$ ist. Die Matrix $A-\lambda_1 I$ eingeschränkt auf $\mathcal{E}_{\lambda_1}(A)$ ist nilpotent. -Man kann sagen, auf dem Unterraum $\mathcal{E}_{\lambda_i}(A)$ hat +Man kann daher sagen, auf dem Unterraum $\mathcal{E}_{\lambda_i}(A)$ hat $A$ die Form $\lambda_1 I + N$, wobei $N$ nilpotent ist. Die Zerlegung in invariante Unterräume ist zwar mit Hilfe von $A-\lambda_1I$ @@ -414,7 +418,7 @@ hat als charakteristisches Polynom, welches $\lambda$ als einzige Nullstelle hat. Wenn die Einträge oberhalb der Diagonalen nicht alle 0 sind, -dann hat der Eigenraum der Matrix Dimension, die keiner ist als +dann hat der Eigenraum der Matrix eine Dimension, die kleiner ist als $n$. Man kann also im Allgemeinen für jede Nullstelle des charakteristischen Polynoms nicht mehr als einen Eigenvektor (d.~h.~einen eindimensionalen @@ -424,7 +428,7 @@ Wenn das charakteristische Polynom von $A$ keine Nullstellen in $\Bbbk$ hat, dann kann es auch keine Eigenvektoren in $\Bbbk^n$ geben. Gäbe es nämlich einen solchen Vektor, dann müsste eine der Komponenten des Vektors von $0$ verschieden sein. -Wir nehmen an, dass es die Komponente in Zeile $k$ ist. +Nehmen wir an, dass es die Komponente in Zeile $k$ ist. Die Komponente $v_k$ kann man auf zwei Arten berechnen, einmal als die $k$-Komponenten von $Av$ und einmal als $k$-Komponente von $\lambda v$: \[ @@ -494,7 +498,7 @@ diagonalisieren, nicht aber über dem Körper $\mathbb{Q}$. Da $A'$ Diagonalform hat mit $\pm\sqrt{2}$ auf der Diagonalen, folgt $A^{\prime 2} = 2I$, die Matrix $A'$ erfüllt also die Gleichung \begin{equation} -A^{\prime 2}-I= \chi_{A}(A) = 0. +A^{\prime 2}-2I= \chi_{A}(A) = 0. \label{buch:grundlagen:eqn:cayley-hamilton-beispiel} \end{equation} Die Gleichung~\ref{buch:grundlagen:eqn:cayley-hamilton-beispiel} diff --git a/buch/chapters/40-eigenwerte/grundlagen.tex b/buch/chapters/40-eigenwerte/grundlagen.tex index b41da1d..2ecba95 100644 --- a/buch/chapters/40-eigenwerte/grundlagen.tex +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -93,7 +93,7 @@ folgt \begin{equation} \Bbbk^n = -\operatorname{im}E +\operatorname{im}I = \operatorname{im}A^0 = @@ -113,12 +113,12 @@ folgt \label{buch:eigenwerte:eqn:Jkchain} \end{equation} Für die Kerne gilt etwas Ähnliches, sie werden immer grösser. -Ein Vektor $x\in \mathcal{K}^k(A)$ erfüllt $A^kx=0$. -Dann erfüllt er aber erst recht auch +Wenn ein Vektor $x\in \mathcal{K}^k(A)$ die Bedingung $A^kx=0$ erfüllt, +dann erfüllt er erst recht auch \[ A^{k+1}x=A\underbrace{A^kx}_{\displaystyle=0}=0, \] -also ist $x\in\mathcal{K}^k(A)$. +also ist $x\in\mathcal{K}^{k+1}(A)$. Es folgt \begin{equation} \{0\} @@ -166,6 +166,8 @@ so, dass \end{array} \] ist. +Mit anderen Worten: ab der $k$-ten Potenz ändern sich +$\mathcal{K}^k(A)$ und $\mathcal{J}^k(A)$ nicht mehr. \end{satz} \begin{proof}[Beweis] @@ -280,12 +282,12 @@ gilt. \index{Unterraum, invarianter}% \end{definition} -Der Kern $\ker A$ einer linearen Abbildung ist trivialerweise ein +Der Kern $\ker A$ einer linearen Abbildung ist trivialerweise ein invarianter Unterraum, da alle Vektoren in $\ker A$ auf $0\in\ker A$ abgebildet werden. Ebenso ist natürlich $\operatorname{im}A$ ein invarianter Unterraum, -denn jeder Vektor wird in $\operatorname{im}A$ abgebildet, insbesondere -auch jeder Vektor in $\operatorname{im}A$. +denn jeder Vektor aus $V$ wird in das Bild $\operatorname{im}A$ hinein +abgebildet, insbesondere auch jeder Vektor aus $\operatorname{im}A\subset V$. \begin{satz} \label{buch:eigenwerte:satz:KJinvariant} @@ -332,7 +334,7 @@ also ist $f$ auf $\mathcal{J}^k(A)$ auch injektiv. Die beiden Unterräume $\mathcal{J}(A)$ und $\mathcal{K}(A)$ sind Bild und Kern der iterierten Abbildung mit Matrix $A^k$. -Das bedeutet, dass $\dim\mathcal{J}(A)+\mathcal{K}(A)=n$. +Das bedeutet, dass $\dim\mathcal{J}(A)+\dim\mathcal{K}(A)=n$. Da $\mathcal{K}(A)=\ker A^k$ und andererseits $A$ injektiv ist auf $\mathcal{J}(A)$, muss $\mathcal{J}(A)\cap\mathcal{K}(A)=0$. Es folgt, dass $V=\mathcal{J}(A) + \mathcal{K}(A)$. @@ -370,7 +372,7 @@ Eigenschaften. Die Zerlegung von $V$ in die beiden invarianten Unterräume $\mathcal{J}(A)$ und $\mathcal{K}(A)$ reduziert die lineare Abbildung auf zwei Abbildungen mit speziellen Eigenschaften. -Es wurde bereits in Satz~\label{buch:eigenwerte:satz:fJinj} gezeigt, +Es wurde bereits in Satz~\ref{buch:eigenwerte:satz:fJinj} gezeigt, dass die Einschränkung auf $\mathcal{J}(A)$ injektiv ist. Die Einschränkung auf $\mathcal{K}(A)$ bildet nach Definition~\ref{buch:eigenwerte:def:KundJ} alle @@ -405,7 +407,7 @@ Wir zeigen jetzt, dass sich bei der Multiplikation die nicht verschwinden Elemente bei der Multiplikation noch rechts oben verschieben. Dazu multiplizieren wir zwei Matrizen $B$ und $C$ mit -$b_{i\!j}=0$ für $i+k>j$ und $c_{i\!j}=0$ für $i+l>j$. +$b_{i\!j}=0$ für $i+k<j$ und $c_{i\!j}=0$ für $i+l<j$. In der folgenden graphischen Darstellung der Matrizen sind die Bereiche, wo die Matrixelemente verschwinden, weiss. \begin{center} @@ -417,18 +419,18 @@ Die blau eingefärbten Elemente in dieser Zeile und Spalte sind $0$. Aus der Darstellung ist abzulesen, dass das Produkt verschwindet, wenn die roten, von $0$ verschiedenen Elemente von den blauen Elementen annihiliert werden. -Dies passiert immer, wenn $i+k>j-l$ ist, oder $i+(k+l)> j$. +Dies passiert immer, wenn $i+k<j-l$ ist, oder $i+(k+l)< j$. Wir wenden diese Beobachtung jetzt auf die Potenzen $A^s$ an. Für die Matrixelemente von $A^s$ schreiben wir $a^s_{i\!j}$. Wir behaupten, dass die Matrixelemente von $A^s$ die Bedingung -$a_{i\!j}^s=0$ für $i+s>j$ erfüllen. +$a_{i\!j}^s=0$ für $i+s<j$ erfüllen. Dies ist für $s=1$ nach Voraussetzung richtig, dies ist die Induktionsverankerung. Nehmen wir jetzt an, dass $a_{i\!j}^s=0$ für $i+s>j$, dann folgt aus obiger Rechnung, dass $a_{i\!j}^{s+1}=0$ für $i+s+1>j$, so dass die Bedingung auch für $A^s$ gilt (Induktionsschritt). -Mit vollständiger Induktion folgt, dass $a_{i\!j}^s=0$ für $i+s>j$. +Mit vollständiger Induktion folgt, dass $a_{i\!j}^s=0$ für $i+s<j$. Insbesondere ist $A^n=0$, die Matrix $A$ ist nilpotent. \end{beispiel} @@ -476,6 +478,7 @@ In dieser Basis hat die Matrix die Form~\ref{buch:eigenwerte:eqn:nnilpotent}. \end{proof} \begin{definition} +\label{buch:eigenwerte:def:Nn} Wir bezeichnen mit $N_n$ eine Matrix der Form \eqref{buch:eigenwerte:eqn:nnilpotent}. \end{definition} @@ -544,20 +547,31 @@ Abhängigkeit von $k$ In der Abbildung~\ref{buch:eigenwte:fig:jknilp} sind die Dimensionen von Kern und Bild der Matrix \[ +\def\temp#1{\multicolumn{1}{|c}{$#1\mathstrut$}} +\def\rand#1{\multicolumn{1}{c|}{$#1\mathstrut$}} \setcounter{MaxMatrixCols}{12} -A=\begin{pmatrix} -0& & & & & & & & & & & \\ - &0& & & & & & & & & & \\ - & &0& & & & & & & & & \\ - & & &0& & & & & & & & \\ - & & & &0&1& & & & & & \\ - & & & & &0& & & & & & \\ - & & & & & &0&1& & & & \\ - & & & & & & &0&1& & & \\ - & & & & & & & &0&1& & \\ - & & & & & & & & &0&1& \\ - & & & & & & & & & &0& -\end{pmatrix} +A=\left( +\begin{array}{ccccccccccc} +\cline{1-1} +\temp{0}&\multicolumn{1}{|c}{}& & & & & & & & & \\ +\cline{1-2} + &\temp{0}&\multicolumn{1}{|c}{}& & & & & & & & \\ +\cline{2-3} + & &\temp{0}&\multicolumn{1}{|c}{}& & & & & & & \\ +\cline{3-4} + & & &\temp{0}&\multicolumn{1}{|c}{}& & & & & & \\ +\cline{4-6} + & & & &\temp{0}&1&\multicolumn{1}{|c}{}& & & & \\ + & & & &\temp{ }&0&\multicolumn{1}{|c}{}& & & & \\ +\cline{5-11} + & & & & & &\temp{0}&1& & &\rand{ }\\ + & & & & & &\temp{ }&0&1& &\rand{ }\\ + & & & & & &\temp{ }& &0&1&\rand{ } \\ + & & & & & &\temp{ }& & &0&\rand{1}\\ + & & & & & &\temp{ }& & & &\rand{0}\\ +\cline{7-11} +\end{array} +\right) \] dargestellt. Die Matrix $A^k$ ist in den kleinen Quadraten am unteren Rand der Matrix @@ -574,7 +588,7 @@ bilden daher eine Basis des Bildes von $A^k$. \subsection{Basis für die Normalform einer nilpotenten Matrix bestimmen \label{buch:subsection:normalform-einer-nilpotenten-matrix}} Die Zerlegung in die invarianten Unterräume $\mathcal{J}^k(f)$ und -$\mathcal{K}^k(f)$ ermöglichen, eine Basis zu finden, in der die +$\mathcal{K}^k(f)$ ermöglicht, eine Basis zu finden, in der die Matrix von $f$ die Blockform \eqref{buch:eigenwerte:eqn:allgnilpotent} hat. In diesem Abschnitt soll die Konstruktion einer solchen Basis @@ -596,7 +610,7 @@ Die vertikalen Rechtecke im linken Teil der Abbildung symbolisieren die Unterräume $\mathcal{K}^k(A)$. Es ist bekannt, dass $\mathcal{K}^k(A) \subset \mathcal{K}^{k+1}(A)$ ist, die Einbettung wird in der Abbildung durch graue Rechtecke dargestellt. -Es sei wieder $l$ der Exponent, für den $\mathcal{K}^l(A)=\Bbbk^n$ wird. +Es sei $l$ der Exponent, für den $\mathcal{K}^l(A)=\Bbbk^n$ wird. Da $\mathcal{K}^{l-1}(A)\ne \mathcal{K}^l(A)$ ist, muss es einen komplementären Unterraum geben, in dem eine Basis gewählt wird. Jeder der Vektoren $b_1,\dots,b_s$ dieser Basis gibt Anlass zu einem @@ -611,7 +625,7 @@ die Vektoren $Ab_1,\dots,Ab_s$. Es ist aber möglich, dass diese Vektoren nicht den ganzen Raum $\mathcal{K}^{l-1}(A)$ erzeugen. In diesem Fall lassen sich die Vektoren mit Hilfe weiterer Vektoren -$b_{s+1},\dots,b_{s+r}$ zu einer Basisi von $\mathcal{K}^{l-1}(A)$ +$b_{s+1},\dots,b_{s+r}$ zu einer Basis von $\mathcal{K}^{l-1}(A)$ ergänzen. Wie vorhin gibt jeder der Vektoren $b_{s+i}$ Anlass zu einem Block der Form $N_{l-1}$, der auf dem Unterraum @@ -640,7 +654,8 @@ A \] in Blockform soll nach der oben beschriebenen Methode ermittelt werden. Zunächst kann man nachrechnen, dass $A^2=0$ ist. -Der Kern von $A$ ist der Lösungsraum der Gleichung $Ax=0$, da alle Zeilen +Der Kern von $A$ ist der Lösungsraum $\mathbb{L}$ der Gleichung $Ax=0$, +da alle Zeilen Vielfache der ersten Zeile sind, reicht es zu verlangen, dass die Komponenten $x_i$ der Lösung die Gleichung \[ @@ -674,7 +689,7 @@ B=\begin{pmatrix*}[r] 2& 0& -21\\ 1& 0& -6 \end{pmatrix*} -\qquad\text{mit Inverser} +\qquad\text{mit der Inversen} \qquad B^{-1}=\begin{pmatrix*}[r] 0&-\frac23& \frac73\\ @@ -682,7 +697,7 @@ B^{-1}=\begin{pmatrix*}[r] 1& \frac13&-\frac23 \end{pmatrix*} \] -transformiert die Matrix $A$ auf den Block $N_3$: +transformiert die Matrix $A$ auf die Blockform \[ B^{-1}AB = @@ -699,9 +714,7 @@ B^{-1}\begin{pmatrix*}[r] &0&1\\ &0&0 \end{array} -\right) -= -N_3. +\right). \qedhere \] \end{beispiel} diff --git a/buch/chapters/40-eigenwerte/images/dimjk.pdf b/buch/chapters/40-eigenwerte/images/dimjk.pdf Binary files differindex fcfe4da..03d0eda 100644 --- a/buch/chapters/40-eigenwerte/images/dimjk.pdf +++ b/buch/chapters/40-eigenwerte/images/dimjk.pdf diff --git a/buch/chapters/40-eigenwerte/images/dimjk.tex b/buch/chapters/40-eigenwerte/images/dimjk.tex index 28e0f9f..906aaea 100644 --- a/buch/chapters/40-eigenwerte/images/dimjk.tex +++ b/buch/chapters/40-eigenwerte/images/dimjk.tex @@ -34,9 +34,9 @@ \fill[color=darkgreen!40] ({5*\sx},0) rectangle ({8*\sx},{6-2.4}); \draw[color=darkgreen,line width=2pt] ({3*\sx},{6-6}) -- ({3*\sx},{6-2.9}); -\node[color=darkgreen] at ({3*\sx},{6-4.45}) [rotate=90,above] {$\dim\mathcal{K}^k(A)$}; +\node[color=darkgreen] at ({3*\sx},{6-4.45}) [rotate=90,above] {$\dim\mathcal{K}^i(A)$}; \draw[color=orange,line width=2pt] ({3*\sx},{6-0}) -- ({3*\sx},{6-2.9}); -\node[color=orange] at ({3*\sx},{6-1.45}) [rotate=90,above] {$\dim\mathcal{J}^k(A)$}; +\node[color=orange] at ({3*\sx},{6-1.45}) [rotate=90,above] {$\dim\mathcal{J}^i(A)$}; \node[color=orange] at ({6.5*\sx},{6-1.2}) {bijektiv}; \node[color=darkgreen] at ({6.5*\sx},{6-4.2}) {konstant}; @@ -53,7 +53,7 @@ \draw \pfad; -\draw[->] (-0.5,0) -- ({8*\sx+0.5},0) coordinate[label={$k$}]; +\draw[->] (-0.5,0) -- ({8*\sx+0.5},0) coordinate[label={$i$}]; \draw[->] (-0.5,6) -- ({8*\sx+0.5},6); \foreach \x in {0,...,8}{ @@ -63,15 +63,15 @@ \node at ({\x*\sx},-0.05) [below] {$\x$}; } \node at ({4*\sx},-0.05) [below] {$\dots\mathstrut$}; -\node at ({5*\sx},-0.05) [below] {$l$}; -\node at ({6*\sx},-0.05) [below] {$l+1$}; -\node at ({7*\sx},-0.05) [below] {$l+2$}; -\node at ({8*\sx},-0.05) [below] {$l+3$}; +\node at ({5*\sx},-0.05) [below] {$k$}; +\node at ({6*\sx},-0.05) [below] {$k+1$}; +\node at ({7*\sx},-0.05) [below] {$k+2$}; +\node at ({8*\sx},-0.05) [below] {$k+3$}; \node[color=orange] at ({1.2*\sx},5.6) - {$\mathcal{J}^k(A)\supset\mathcal{J}^{k+1}(A)$}; + {$\mathcal{J}^i(A)\supset\mathcal{J}^{i+1}(A)$}; \node[color=darkgreen] at ({1.2*\sx},0.4) - {$\mathcal{K}^k(A)\subset\mathcal{K}^{k+1}(A)$}; + {$\mathcal{K}^i(A)\subset\mathcal{K}^{i+1}(A)$}; \end{tikzpicture} \end{document} diff --git a/buch/chapters/40-eigenwerte/images/sp.pdf b/buch/chapters/40-eigenwerte/images/sp.pdf Binary files differindex b93b890..fe707cf 100644 --- a/buch/chapters/40-eigenwerte/images/sp.pdf +++ b/buch/chapters/40-eigenwerte/images/sp.pdf diff --git a/buch/chapters/40-eigenwerte/images/wurzelapprox.pdf b/buch/chapters/40-eigenwerte/images/wurzelapprox.pdf Binary files differindex 01fa714..005a43e 100644 --- a/buch/chapters/40-eigenwerte/images/wurzelapprox.pdf +++ b/buch/chapters/40-eigenwerte/images/wurzelapprox.pdf diff --git a/buch/chapters/40-eigenwerte/normalformen.tex b/buch/chapters/40-eigenwerte/normalformen.tex index 96cb18b..c69329b 100644 --- a/buch/chapters/40-eigenwerte/normalformen.tex +++ b/buch/chapters/40-eigenwerte/normalformen.tex @@ -72,8 +72,16 @@ $m(x)=(x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_m)$ mit der Eigenschaft $m(A)=0$. Dies ist auch das Polynom von kleinstmöglichem Grad, denn für jeden Eigenwert muss ein entsprechender Linearfaktor in so einem Polynom vorkommen. + +\begin{definition} +\label{buch:normalformen:def:minimalpolynom} +Das {\em Minimalpolynom} $m_A(X)\in\Bbbk[X]$ einer Matrix +\index{Minimalpolynom} +$A\in M_{n}(\Bbbk)$ ist das Polynom kleinstmöglichen Grades, für +das $m_A(X)=0$ gilt. +\end{definition} + Das Polynom $m(x)$ ist daher das Minimalpolynom der Matrix $A$. -\index{Minimalpolynome}% Da jeder Faktor in $m(x)$ auch ein Faktor von $\chi_A(x)$ ist, folgt wieder $\chi_A(A)=0$. Ausserdem ist über dem Körper $\Bbbk'$ das Polynom $m(x)$ ein Teiler @@ -337,8 +345,8 @@ wird. Die nicht reellen Eigenwerte von $A$ treten in konjugiert komplexen Paaren $\lambda_i$ und $\overline{\lambda}_i$ auf. -Wir betrachten im Folgenden nur ein einziges Paar $\lambda=a+ib$ und -$\overline{\lambda}=a-ib$ von konjugiert komplexen Eigenwerten mit +Wir betrachten im Folgenden nur ein einziges Paar $\lambda=\alpha+i\beta$ und +$\overline{\lambda}=\alpha-i\beta$ von konjugiert komplexen Eigenwerten mit nur je einem einzigen $n\times n$-Jordan-Block $J$ und $\overline{J}$. Ist $\mathcal{B}=\{b_1,\dots,b_n\}$ die Basis für den Jordan-Block $J$, dann kann man die Vektoren @@ -377,8 +385,8 @@ J&0\\ & & & &\lambda&&&&&\\ &&&& &\overline{\lambda}&1&& & \\ &&&& &&\overline{\lambda}&1& & \\ -&&&& &&&\overline{\lambda} &\dots& \\ -&&&& &&& &\dots&1\\ +&&&& &&&\overline{\lambda} &\ddots& \\ +&&&& &&& &\ddots&1\\ &&&& &&& &&\overline{\lambda}\\ \end{pmatrix}. \] @@ -386,24 +394,24 @@ J&0\\ Die Jordan-Normalform bedeutet, dass \[ \begin{aligned} -Ab_1&=\lambda b_1 & - A\overline{b}_1 &= \overline{\lambda} \overline{b}_1 \\ -Ab_2&=\lambda b_2 + b_1 & - A\overline{b}_2 &= \overline{\lambda} \overline{b}_2 +\overline{b_1}\\ -Ab_3&=\lambda b_3 + b_2 & - A\overline{b}_3 &= \overline{\lambda} \overline{b}_3 +\overline{b_2}\\ - &\;\vdots & +Ab_1&=\lambda b_1 &&\Rightarrow& + A\overline{b}_1 &= \overline{\lambda} \overline{b}_1, \\ +Ab_2&=\lambda b_2 + b_1 &&\Rightarrow& + A\overline{b}_2 &= \overline{\lambda} \overline{b}_2 +\overline{b_1},\\ +Ab_3&=\lambda b_3 + b_2 &&\Rightarrow& + A\overline{b}_3 &= \overline{\lambda} \overline{b}_3 +\overline{b_2},\\ + &\;\vdots && & &\;\vdots \\ -Ab_n&=\lambda b_n + b_{n-1} & - A\overline{b}_n &= \overline{\lambda} \overline{b}_n +\overline{b_{n-1}} +Ab_n&=\lambda b_n + b_{n-1} &&\Rightarrow& + A\overline{b}_n &= \overline{\lambda} \overline{b}_n +\overline{b_{n-1}}. \end{aligned} \] Für die Linearkombinationen \begin{equation} \begin{aligned} -c_i &= \frac{b_i+\overline{b}_i}{\sqrt{2}}, +c_k &= \frac{b_k+\overline{b}_k}{\sqrt{2}}, & -d_i &= \frac{b_i-\overline{b}_i}{i\sqrt{2}} +d_k &= \frac{b_k-\overline{b}_k}{i\sqrt{2}} \end{aligned} \label{buch:eigenwerte:eqn:reellenormalformumrechnung} \end{equation} diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index c0d4de9..1ac50a2 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -45,7 +45,7 @@ kann man auch p(A) = a_nA^n + a_{n-1}A^{n-1} + \dots + a_1A + a_0I \] berechnen. -In der Jordan-Normalform können die Potenzen $A^k$ leicht zusammengstellt +In der Jordan-Normalform können die Potenzen $A^k$ leicht zusammengestellt werden, sobald man die Potenzen von Jordan-Blöcken berechnet hat. \begin{satz} @@ -103,26 +103,31 @@ Die Herkunft der Binomialkoeffizienten wird klar, wenn man \[ J_n(\lambda) = \lambda I + N_n \] -schreibt, wobei $N_n$ die Matrix \eqref{buch:eigenwerte:eqn:nnilpotent} ist. +schreibt, wobei $N_n$ die Matrix \eqref{buch:eigenwerte:eqn:nnilpotent} +von Definition~\ref{buch:eigenwerte:def:Nn} von +Seite~\pageref{buch:eigenwerte:def:Nn} ist. Die Potenzen von $N_n$ haben die Matrix-Elemente \[ -(N_n^k)_{i\!j} +(N_n^l)_{i\!j} = -\delta_{i,j-k} +\delta_{i,j-l} = \begin{cases} -1&\qquad j-i=k\\ +1&\qquad j-i=l\\ 0&\qquad\text{sonst,} \end{cases} \] sie haben also Einsen genau dort, wo in der -\label{buch:eigenwerte:eqn:Jnkpotenz} die Potenz $\lambda^{k}$ steht. -Die $k$-te Potenz von $J_n(\lambda)$ kann dann mit dem binomischen +Matrix +\eqref{buch:eigenwerte:eqn:Jnkpotenz} die Potenz $\lambda^{k-l}$ steht. +Die $k$-te Potenz von $J_n(\lambda)$ kann daraus mit dem binomischen Satz berechnet werden: \[ J_n(\lambda)^k = -\sum_{l=0}^k \binom{k}{l}\lambda^l N_n^{k-l}, +(N_n+\lambda I)^k += +\sum_{l=0}^k \binom{k}{l} N_n^{l} \lambda^{k-l}, \] dies ist genau die Form \eqref{buch:eigenwerte:eqn:Jnkpotenz}. \end{proof} @@ -155,7 +160,7 @@ Ist andererseits $p(X)-q(X)=m(X)t(X)$, dann ist $p(A)-q(A)=m(A)t(A)=0\cdot t(A) = 0$, also $p(A)=q(A)$. \end{proof} -Über einem Körper $\Bbbk'\supset\Bbbk$, über dem das charakteristische +Über einem Körper $\Bbbk'\supset\Bbbk$, in dem das charakteristische Polynom in Linearfaktoren zerfällt, kann man das Minimalpolynom aus der Jordanschen Normalform ableiten. Es ist @@ -272,7 +277,7 @@ wie zu erwarten war. Wenn sich zwei Polynome nur um das charakteristische Polynom unterscheiden, dann haben sie den gleichen Wert auf $A$. -Das Polynom $p_1(X)=X^3$ unterschiedet sich vom Polynom +Das Polynom $p_1(X)=X^3$ unterscheidet sich vom Polynom $p_2(X)=7X^2-16X+12=\chi_A(X)+X^3=p_1(X)+\chi_A(X)$ um das charakteristische Polynom, welches wir bereits als das Minimalpolynom von $A$ erkannt haben. @@ -318,8 +323,8 @@ für alle Eigenwerte $\lambda$ von $A$. Über dem Körper der komplexen Zahlen ist die Bedingung, dass die Differenz $d(X)=p_1(X)-p_2(X)$ vom Minimalpolynom geteilt werden muss, gleichbedeutend -damit, dass $p_1(X)$ und $p_2(X)$ die gleichen Nullstellen mit den gleichen -Vielfachheiten haben. +damit, dass $p_1(X)-p_2(X)$ mindestens alle Nullstellen des Minimalpolynoms +mit mindestens so grossen Vielfachheiten haben muss. Eine andere Art, dies auszudrücken, ist, dass $p_1(x)$ und $p_2(X)$ die gleichen Werte und Ableitungen bis zur Ordnung $q_i-1$ haben, wenn $q_i$ der Exponente von $\lambda_I-X$ im Minimalpolynom von $A$ ist. @@ -340,7 +345,7 @@ A^{i-k}A^k = A^{i-k}(-a_{k-1}A^{k-1}+ \dots + a_1 A + a_0I) \] -in einer Linearkombination kleinerer Potenzen reduzieren. +auf einer Linearkombination kleinerer Potenzen reduzieren. Jedes Polynom vom Grad $\ge k$ kann also reduziert werden in ein Polynom vom Grad $<k$ mit dem gleichen Wert auf $A$. @@ -381,7 +386,8 @@ Solche Polynome gibt es dank dem Satz von Stone-Weierstrass immer: \begin{satz}[Stone-Weierstrass] Ist $I\subset\mathbb{R}$ kompakt, dann lässt sich jede stetige Funktion $f(x)$ -durch eine Folge $p_n(x)$ beliebig genau approximieren. +durch eine Folge von reellen Polynomen +$p_n(x)$ beliebig genau approximieren. \end{satz} Die Hoffnung ist, $f(A)$ als Grenzwert der Approximationen $p_n(A)$ @@ -389,25 +395,25 @@ zu definieren. Dazu muss sichergestellt sein, dass verschiedene Approximationen der Funktion $f$ den gleichen Grenzwert $\lim_{n\to\infty}p_n(A)$ ergeben. -Im Folgenden soll genauer untersucht werden, ob sich von der +Im Folgenden soll genauer untersucht werden, ob von der Konvergenz einer Folge $p_n(x)$ auf die Konvergenz von $p_n(A)$ geschlossen werden kann. -Wir haben schon gezeigt, dass es dabei auf die höheren Potenzen gar nicht -ankommt, nach Satz~\ref{buch:eigenwerte:satz:reduktion} kann man ein -approximierendes Polynom immer durch ein Polynom von kleinerem Grad -als das Minimalpolynom ersetzen. +%Wir haben schon gezeigt, dass es dabei auf die höheren Potenzen gar nicht +%ankommt, nach Satz~\ref{buch:eigenwerte:satz:reduktion} kann man ein +%approximierendes Polynom immer durch ein Polynom von kleinerem Grad +%als das Minimalpolynom ersetzen. -\begin{definition} -\index{Norm}% -Die {\em Norm} einer Matrix $M$ ist +Wir erinnern in diesem Zusammenhang an die Definition +\ref{buch:vektoren-matrizen:def:operatornorm} +der Operatornorm. +Die Norm einer Matrix $M$ ist \[ \|M\| = -\max\{|Mx|\,|\, x\in\mathbb R^n\wedge |x|=1\}. +\sup\{|Mx|\,|\, x\in\mathbb R^n\wedge |x|=1\}. \] Für einen Vektor $x\in\mathbb R^n$ gilt $|Mx| \le \|M\|\cdot |x|$. -\end{definition} \begin{beispiel} Die Matrix @@ -548,7 +554,7 @@ f(z) \end{equation} \index{Potenzreihe} haben, wie -zum Beispiel $e^x$, $\sin x$ oder $\cos x$, haben eine in der Folge +zum Beispiel $e^x$, $\sin x$ oder $\cos x$, haben in der Folge der Partialsummen \[ p_n(z) = \sum_{k=0}^n a_kz^k @@ -572,10 +578,10 @@ folgt, dass \le \limsup_{n\to\infty} \sqrt[n]{|a_n|} \cdot -\limsup_{n\to\infty} \|M^k\|^{\frac1k} +\limsup_{n\to\infty} \|M^n\|^{\frac1n} = \frac{1}{\varrho} -\limsup_{n\to\infty} \|M^k\|^{\frac1k} +\limsup_{n\to\infty} \|M^n\|^{\frac1n} \] sein muss. Dies führt uns auf die Grösse @@ -593,12 +599,32 @@ Die Zahl $\pi(M)$ erlaubt zunächst einmal zu bestimmen, wie sich die Potenzen $M^k$ entwickeln. Für Zahlen ist diese Frage sehr einfach zu entscheiden: wenn $q>1$ ist, dann geht $q^n\to\infty$, wenn $|q|<1$ ist, dann geht $q^n\to 0$. -Für Matrizen ist die Frage etwas schieriger. +Für Matrizen ist die Frage etwas schwieriger. Man kann sich vorstellen, dass eine Streckung in einer Richtung von einer Stauchung in eine andere Richtung kompensiert wird, wenn dazwischen eine Drehung stattfindet. Es ist also durchaus möglich, dass $\|M\|>1$ ist, die -Iterierten $M^k$ aber trotzdem gegen $0$ gehen. +Iterierten $M^k$ aber trotzdem gegen $0$ gehen, wie das folgende +Beispiel zeigt. + +\begin{beispiel} +Die nilpotente Matrix $2N_2$ kann man sich vorstellen als eine Drehmatrix +um $-90^\circ$ gefolgt von einer Projektion und Streckung um den Faktor +$2$ auf die erste Achse: +\[ +\begin{pmatrix}2&0\\0&0\end{pmatrix} +R_{-90^\circ} += +\begin{pmatrix}2&0\\0&0\end{pmatrix} +\begin{pmatrix} 0&1\\-1&0 \end{pmatrix} += +\begin{pmatrix} +0&2\\0&0 +\end{pmatrix} +=2N_2. +\] +Wegen $(2N_2)^2=0$ folgt $\pi(2N_2)=0$, obwohl $\|2N_2\|=2$ ist. +\end{beispiel} Ist $\pi(M) > 1$, dann gibt es Anfangsvektoren $v$ für die Iteration, für die $M^kv$ über alle Grenzen wächst. @@ -614,7 +640,7 @@ Der Grenzwert \[ \pi(M) = -\limsup_{n\to\infty} \|M^k\|^{\frac1k} +\limsup_{n\to\infty} \|M^n\|^{\frac1n} \] heisst {\em Gelfand-Radius} der Matrix $M$. \index{Gelfand-Radius}% @@ -639,8 +665,8 @@ Eigenwertes. \index{rho(M)@$\varrho(M)$}% \end{definition} -Wir wollen in diesem Abschnitt zeigen, dass der Gelfand-Radius mit -dem Spektralradius übereinstimmt. +Wir wollen in diesem Abschnitt das als Satz von Gelfand bekannte Resultat +beweisen, dass der Gelfand-Radius mit dem Spektralradius übereinstimmt. Dies liefert uns ein vergleichsweise einfach auszuwertendes Konvergenzkriterium. \index{Konvergenzkriterium}% @@ -693,11 +719,11 @@ A^k v_1 + A^k v_2 + \dots + A^k v_n Für den Grenzwert braucht man die Norm von $A^kv$, also \begin{align} |A^kv| -&= |\lambda_1^k v_1 + \lambda_2^k v_2 + \dots + \lambda_3 v_3| +&= |\lambda_1^k v_1 + \lambda_2^k v_2 + \dots + \lambda_n^k v_n| \notag \\ \Rightarrow\qquad -\frac{|A^kv|}{\lambda_1^k} +\frac{|A^kv|}{|\lambda_1^k|} &= \biggl| v_1 + @@ -784,8 +810,8 @@ Selbstverständlich lässt sich das Lemma auf Blockmatrizen mit beliebig vielen diagonalen Blöcken verallgemeinern. \index{Blockmatrix}% -Für Diagonalmatrizen der genannten Art sind aber auch die -Eigenwerte leicht zu bestimmen. +Für Blockmatrizen der Art \ref{buch:spektralradius:eqn:blockmatrix} +sind aber auch die Eigenwerte leicht zu bestimmen. \index{Diagonalmatrix}% Hat $B$ die Eigenwerte $\lambda_i^{(B)}$ mit $1\le i\le n$ und $C$ die Eigenwerte $\lambda_j^{(C)}$ mit $1\le j\le m$, dann ist das charakteristische @@ -840,8 +866,8 @@ J_{n_1}(\lambda_1) & 0 & \dots & 0 \\ \] geschrieben werden kann. Die früheren Beobachtungen über den Spektralradius und den -Gelfand-Radius von Blockmatrizen führen uns dazu, dass -nur gezeigt werden muss, dass nur die Gleichheit des Gelfand-Radius +Gelfand-Radius von Blockmatrizen führen uns dazu, +dass nur die Gleichheit des Gelfand-Radius und des Spektral-Radius von Jordan-Blöcken gezeigt werden muss. \subsubsection{Potenzen von Jordan-Blöcken} @@ -900,7 +926,7 @@ Satz~\ref{buch:spektralradius:satz:grenzwert}. \index{Satz von Gelfand}% \index{Gelfand!Satz von}% \label{buch:satz:gelfand} -Für jede komplexe $n\times n$-Matrix $A$ gilt +Für eine komplexe $n\times n$-Matrix $A$ gilt \[ \pi(A) = @@ -916,7 +942,7 @@ Spektralradius ein scharfes Kriterium dafür ist, ob $\|A^k\|$ gegen 0 oder $\infty$ konvergiert. Andererseits ändert ein Faktor $t$ in der Matrix $A$ den Spektralradius ebenfalls um den gleichen Faktor, also $\varrho(tA)=t\varrho(A)$. -Natürlich gilt auch +Natürlich gilt dies wegen \[ \pi(tA) = @@ -926,8 +952,9 @@ Natürlich gilt auch = t\lim_{k\to\infty} \|A^k\|^\frac1k = -t\pi(A). +t\pi(A) \] +auch für den Gelfand-Radius. Wir betrachten jetzt die Matrix \[ diff --git a/buch/chapters/40-eigenwerte/spektraltheorie.tex b/buch/chapters/40-eigenwerte/spektraltheorie.tex index 94a64e1..1023d20 100644 --- a/buch/chapters/40-eigenwerte/spektraltheorie.tex +++ b/buch/chapters/40-eigenwerte/spektraltheorie.tex @@ -5,6 +5,7 @@ % \section{Spektraltheorie \label{buch:section:spektraltheorie}} +\rhead{Spektraltheorie} Aufgabe der Spektraltheorie ist, Bedingungen an eine Matrix $A$ und eine \index{Spektraltheorie} Funktion $f(z)$ zu finden, unter denen es möglich ist, $f(A)$ auf @@ -28,8 +29,8 @@ unklar. Da der Abstand zweier Matrizen $A$ und $B$ in der Operatornorm mit der grössten Abweichung $\|(A-B)v\|$ für Einheitsvektoren $v$ gemessen wird, ist es einigermassen plausibel, dass -die grösse Abweichung zwischen zwei Polynomen $|p(z) - q(z)|$ auf -der Menge $K$ kleine sein muss, wenn $\|p(A)-q(A)\|$ klein +die grösste Abweichung zwischen zwei Polynomen $|p(z) - q(z)|$ auf +der Menge $K$ klein sein muss, wenn $\|p(A)-q(A)\|$ klein sein soll. Da die Differenz $p(z)-q(z)$ für beliebige Polynome, die sich nicht nur um eine Konstante unterscheiden, mit $z$ über alle Grenzen wächst, @@ -80,8 +81,8 @@ Abschnitt~\ref{buch:subsetion:stone-weierstrass} dargestellt wird, ist ein sehr allgemeines Approximationsresultat, welches nicht nur zeigt, dass die Approximation unter einigermassen natürlichen Voraussetzungen beliebig genau möglich ist, sondern uns im komplexen Fall auch -weitere Einsicht dafür geben kann, welche Voraussetzungen an eine -komplexe Matrix gestellt werden müssen, damit man damit rechnen kann, +weitere Einsicht in die Voraussetzungen an eine +komplexe Matrix geben kann, damit man damit rechnen kann, dass die Approximation zu einer konsistenten Definition von $f(A)$ führt. % @@ -136,14 +137,14 @@ p(z_i) = \sum_{j=0}^n f(z_j) \delta_{i\!j} = -f_(z_i) +f(z_i) \] annimmt. Das Polynom $p(z)$ heisst das {\em Legendre-Interpolationspolynom}. -Zwar lässt sich also für eine endliche Menge von komplexen Zahlen immer -ein Polynom finden, welches vorgeschriebene Wert in allen diesen Zahlen -annimmt, doch ist die Stabilität für grosse $n$ eher beschränkt. +Zwar lässt sich auf diese Weise für eine endliche Menge von komplexen Zahlen +immer ein Polynom finden, welches vorgeschriebene Wert in allen diesen Zahlen +annimmt, doch ist die Stabilität für grosse $n$ eher schlecht. \subsubsection{Gleichmassige Approximation mit Bernstein-Polynomen} @@ -175,8 +176,7 @@ gegen die Funktion $f(t)$. Über die Konvergenz ausserhalb des reellen Intervalls wird nichts ausgesagt. Die Approximation mit Bernstein-Polynomen ist daher nur sinnvoll, -wenn man weiss, dass die Eigenwerte der Matrix reell sind, was im -wesentlichen auf diagonalisierbare Matrizen führt. +wenn man weiss, dass die Eigenwerte der Matrix reell sind. Für ein anderes Interval $[a,b]$ kann man ein Approximationspolynom erhalten, indem man die affine Transformation @@ -205,7 +205,7 @@ In diesem Fall liefert der Satz von Stone-Weierstrass die Aussage, dass sich jede stetige periodische Funktion gleichmässig durch trigonometrische Polynome approximieren lässt. -Die Aussage des Satz von Stone-Weierstrass über reelle Funktionen +Die Aussage des Satzes von Stone-Weierstrass über reelle Funktionen lässt sich nicht auf komplexe Funktionen erweitern. Von besonderem Interesse ist jedoch, dass der Beweis des Satz zeigt, warum solche Aussagen für komplexe Funktionen nicht mehr @@ -286,7 +286,7 @@ Die Variable $x\in[a,b]$ trennt natürlich die Punkte, die Algebra der Polynome in der Variablen $x$ enthält also sicher Funktionen, die in verschiedenen Punkten des Intervalls auch verschiedene Werte annehmen. Nicht ganz so selbstverständlich ist aber, dass sich daraus bereits -ergibt, dass jede beliebige Funktion sich als Polynome in $x$ +ergibt, dass jede beliebige Funktion sich durch Polynome in $x$ approximieren lässt. Dies ist der Inhalt des folgenden Satzes von Stone-Weierstrass. @@ -357,9 +357,9 @@ der selben Grösse. \end{figure} \begin{proof}[Beweis] -Wer konstruieren zunächst das in +Wir konstruieren zunächst das in Abbildung~\ref{buch:eigenwerte:fig:wurzelverfahren} -visualierte Verfahren, mit dem für jede Zahl $a\in[0,1]$ +visualisierte Verfahren, mit dem für jede Zahl $a\in[0,1]$ die Wurzel $\sqrt{a}$ berechnet werden kann. Sei $u < \sqrt{a}$ eine Approximation der Wurzel. Die Approximation ist der exakte Wert der Lösung, wenn $a-u^2=0$. @@ -392,8 +392,9 @@ von Funktionen approximieren. Da $A$ eine Algebra ist, ist $f^2\in A$. Sei ausserdem $m^2=\sup \{f(x)^2\;|\;x\in K\}$, so dass $f^2/m^2$ eine Funktion mit Werten im Intervall $[0,1]$ ist. -Die Funktionen $f_n(x)=mu_n(f(x)^2/m^2)$ sind ebenfalls in $A$ und -approximieren gleichmässig $\sqrt{f(x)^2}=|f(x)|$. +Die Funktionen $f_n(x)=mu_n(f(x)^2/m^2)$ sind ebenfalls in $A$, +bilden eine monoton wachsende Folge von Funktionen und +approximieren $\sqrt{f(x)^2}=|f(x)|$ gleichmässig. \item Schritt: Für zwei Funktionen $f,g\in A$ gibt es eine monoton wachsende Folge, die $\max(f,g)$ gleichmässig beliebig genau approximiert @@ -454,8 +455,8 @@ derart, dass $g_y(y)=f(y)$ und $g_y(x) \le f(x) + \varepsilon$ für $x\in K$. Da $g_y$ stetig ist, gilt ausserdem $g_y(x) \ge f(x) -\varepsilon$ in einer Umgebung $U_y$ von $y$. -Da $K$ kompakt ist, kann man endlich viele $y_i$ derart, dass die $U_{y_i}$ -immer noch ganz $K$ überdecken. +Da $K$ kompakt ist, kann man endlich viele $y_i$ derart wählen, +dass die $U_{y_i}$ immer noch ganz $K$ überdecken. Die Funktion $g=\sup g_{y_i}$ erfüllt dann überall $g(x) \le f(x)+\varepsilon$, weil jede der Funktionen $g_y$ diese Ungleichung erfüllt. Ausserdem gilt für $x\in V_{x_j}$ @@ -701,17 +702,11 @@ Matrizen erfüllen $A^*=\pm A$ und damit AA^* = \pm A^2 = A^*A. \) \item -Symmetrische und antisymmetrische Matrizen sind normal, +Symmetrische und antisymmetrische reelle Matrizen sind normal. \index{symmetrisch}% \index{antisymmetrisch}% -denn aus $A=A^t$ folgt $A^*=\overline{A}^t$ und damit -\begin{align*} -AA^* &= A\overline{A}^t = -\\ -A^*A &= -\end{align*} \item -Unitäre Matrizen $U$ sind normal, das $UU^*=I=U^*U$ gilt. +Unitäre Matrizen $U$ sind normal, da $UU^*=I=U^*U$ gilt. \index{unitär}% \item Orthogonale Matrizen sind normal wegen $O(n) = U(n) \cap M_n(\mathbb{R})$. @@ -771,20 +766,20 @@ und $AB$ normal. \begin{proof}[Beweis] Zunächst folgt aus $AB^*=B^*A$ auch $A^*B = (B^*A)^* = (AB^*)^* = BA^*$. -Der Beweis erfolgt durch Nachrechnen: +Der Beweis, dass $A+B$ normal ist, erfolgt durch Nachrechnen: \begin{align*} (A+B)(A+B)^* &= -AA^* + AB^* + BA^*+BB^* +AA^* + {\color{red}AB^*} + {\color{blue}BA^*}+BB^* \\ (A+B)^*(A+B) &= -A^*A + A^*B + B^*A + B^*B +A^*A + {\color{blue}A^*B} + {\color{red}B^*A} + B^*B \end{align*} Die ersten und letzten Terme auf der rechten Seite stimmen überein, weil $A$ und $B$ normal sind. -Die gemischten Terme stimmen überein wegen der Vertauschbarkeit von -$A$ und $B^*$. +Die gleichfarbigen gemischten Terme stimmen überein wegen der +Vertauschbarkeit von $A$ und $B^*$. Für das Produkt rechnet man \begin{align*} @@ -825,16 +820,16 @@ Es gibt eine grosse Zahl äquivalenter Eigenschaften für normale Matrizen. Die folgenden Eigenschaften sind äquivalent: \begin{enumerate} \item -Die Matrix $A$ ist mit einer unitären Matrix diagonalisierbar +Die Matrix $A$ ist mit einer unitären Matrix diagonalisierbar. \item -Es gibt eine orthonormale Basis von Eigenvektoren von $A$ für $\mathbb{C}^n$ +Es gibt eine orthonormale Basis von Eigenvektoren von $A$ für $\mathbb{C}^n$. \item -Für jeden Vektor $x\in\mathbb{C}^n$ gilt $\|Ax\|=\|A^*x\|$ +Für jeden Vektor $x\in\mathbb{C}^n$ gilt $\|Ax\|=\|A^*x\|$. \item Die Frobenius-Norm der Matrix $A$ kann mit den Eigenwerten $\lambda_i$ \index{Frobenius-Norm}% von $A$ berechnet werden: -$\operatorname{Spur}(A^*A) = \sum_{i=1}^n |\lambda_i|^2$ +$\operatorname{Spur}(A^*A) = \sum_{i=1}^n |\lambda_i|^2$. \item Der hermitesche Teil $\frac12(A+A^*)$ und der antihermitesche Teil $\frac12(A-A^*)$ von $A$ vertauschen. @@ -843,7 +838,7 @@ $\frac12(A-A^*)$ von $A$ vertauschen. \item $A^*$ ist ein Polynom vom Grad $n-1$ in $A$. \item -Es gibt eine unitäre Matrix $U$ derart, dass $A^*=AU$ +Es gibt eine unitäre Matrix $U$ derart, dass $A^*=AU$. \index{unitär}% \item Es gibt eine Polarzerlegung $A=UP$ mit einer unitären Matrix $U$ und diff --git a/buch/chapters/50-permutationen/chapter.tex b/buch/chapters/50-permutationen/chapter.tex index e3b6742..041e3b2 100644 --- a/buch/chapters/50-permutationen/chapter.tex +++ b/buch/chapters/50-permutationen/chapter.tex @@ -27,9 +27,9 @@ Formel für die Determinante einer Matrix führt. \input{chapters/50-permutationen/determinante.tex} \section*{Übungsaufgaben} -\rhead{Übungsaufgaben} \aufgabetoplevel{chapters/50-permutationen/uebungsaufgaben} \begin{uebungsaufgaben} \uebungsaufgabe{5001} +\rhead{Übungsaufgaben} \end{uebungsaufgaben} diff --git a/buch/chapters/50-permutationen/determinante.tex b/buch/chapters/50-permutationen/determinante.tex index b30f9a2..b8298b1 100644 --- a/buch/chapters/50-permutationen/determinante.tex +++ b/buch/chapters/50-permutationen/determinante.tex @@ -6,7 +6,6 @@ % \section{Determinante \label{buch:section:determinante}} -\rhead{Determinante} Das Signum einer Permutationsmatrizen lässt sich gemäss~\eqref{buch:permutationen:determinante} mit der Determinanten berechnen. @@ -27,7 +26,7 @@ Die Matrizen $A_{i\!j}$ sind die Minoren der Matrix $A$ (siehe auch Seite~\pageref{buch:linear:def:minor}). In den Produkten $a_{i\!j}\cdot\det(A_{i\!j})$ enthält die Untermatrix $A_{i\!j}$ weder Elemente der Zeile $i$ noch der -Zeile $j$. +Spalte $j$. Die Summanden auf der rechten Seite von \eqref{buch:permutationen:entwicklungssatz} sind daher Produkte der Form @@ -52,6 +51,7 @@ i_1&i_2&i_3&\dots&i_n \] eine Permutation ist. +\rhead{Determinante} Die Determinante muss sich daher als Summe über alle Permutationen in der Form \begin{equation} diff --git a/buch/chapters/50-permutationen/endlich.tex b/buch/chapters/50-permutationen/endlich.tex index 2577b48..3fa6aa7 100644 --- a/buch/chapters/50-permutationen/endlich.tex +++ b/buch/chapters/50-permutationen/endlich.tex @@ -44,7 +44,7 @@ aus zwei identischen Zeilen. Die Verknüpfung zweier solcher Permutationen kann leicht graphisch dargestellt werden: dazu werden die beiden Permutationen untereinander geschrieben und Spalten der zweiten Permutation -in der Reihen folge der Zahlen in der zweiten Zeile der ersten +in der Reihenfolge der Zahlen in der zweiten Zeile der ersten Permutation angeordnet. Die zusammengesetzte Permutation kann dann in der zweiten Zeile der zweiten Permutation abgelesen werden: @@ -75,7 +75,7 @@ dass die Zahlen in der ersten Zeile ansteigend sind: \subsection{Zyklenzerlegung \label{buch:subsection:zyklenzerlegung}} -Eine Permutation $\sigma\in S_n$ kann auch mit sogenanten Zyklenzerlegung +Eine Permutation $\sigma\in S_n$ kann auch mit der sogenanten Zyklenzerlegung \index{Zyklenzerlegung}% analysiert werden. @@ -98,7 +98,8 @@ Zum Beispiel: \begin{center} \includegraphics{chapters/50-permutationen/images/zyklenzerlegung.pdf} \end{center} -Der folgende Algorithmus findet die Zyklenzerlegung einer Permutation. +Der folgende Satz stellt einen Algorithmus bereit, mit dem die +Zyklenzerlegung einer Permutation gefunden werden kann. \begin{satz} Sei $\sigma\in S_n$ eine Permutation. Der folgende Algorithmus findet @@ -143,7 +144,7 @@ m = \operatorname{kgV} (|Z_1|,|Z_2|,\dots,|Z_k|). Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen {\em konjugiert}, wenn \index{konjugiert} es ein Element $c\in G$ gibt derart, dass $cg_1c^{-1}=g_2$. -Bei Matrizen bedeutet dies bedeutet, dass die beiden Matrizen durch +Bei Matrizen bedeutet dies, dass die beiden Matrizen durch Basiswechsel auseinander hervorgehen. Dasselbe lässt sich auch im Kontext der symmetrischen Gruppe sagen. @@ -175,16 +176,16 @@ $\sigma_1^k\gamma = \gamma\sigma_2^k$, also \[ \gamma(Z_i) = -\{\gamma(x),\sigma_1(\gamma(x)),\sigma_1^2(\gamma(x)),\dots\}, +\{\gamma(x),\sigma_1(\gamma(x)),\sigma_1^2(\gamma(x)),\dots\}. \] -Also ist $\gamma(Z_i)$ ein Zyklus von $\sigma_1$. +Somit ist $\gamma(Z_i)$ ein Zyklus von $\sigma_1$. Die Permutation $\gamma$ bildet also Zyklen von $\sigma_2$ auf Zyklen von $\sigma_1$ ab. Es folgt daher der folgende Satz: \begin{satz} Seien $\sigma_1,\sigma_2\in S_n$ konjugiert $\sigma_1=\gamma\sigma_2\gamma^{-1}$ -mit dem $\gamma\in S_n$. +mit $\gamma\in S_n$. Wenn $Z_1,\dots,Z_k$ die Zyklen von $\sigma_2$ sind, dann sind $\gamma(Z_1),\dots,\gamma(Z_k)$ die Zyklen von $\sigma_1$. \end{satz} diff --git a/buch/chapters/50-permutationen/images/permutation.pdf b/buch/chapters/50-permutationen/images/permutation.pdf Binary files differindex cdfa186..f620b81 100644 --- a/buch/chapters/50-permutationen/images/permutation.pdf +++ b/buch/chapters/50-permutationen/images/permutation.pdf diff --git a/buch/chapters/50-permutationen/images/permutation.tex b/buch/chapters/50-permutationen/images/permutation.tex index ee58d4a..fca7aa5 100644 --- a/buch/chapters/50-permutationen/images/permutation.tex +++ b/buch/chapters/50-permutationen/images/permutation.tex @@ -35,7 +35,7 @@ \begin{pmatrix} 1&2&3&4&5&6\\ 2&1&3&5&6&4 -\end{pmatrix} +\end{pmatrix}. $}; \end{tikzpicture} diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex index 037c441..8977635 100644 --- a/buch/chapters/50-permutationen/matrizen.tex +++ b/buch/chapters/50-permutationen/matrizen.tex @@ -9,7 +9,7 @@ Die Eigenschaft, dass eine Vertauschung das Vorzeichen kehrt, ist eine wohlbekannte Eigenschaft der Determinanten. In diesem Abschnitt soll daher eine Darstellung von Permutationen -als Matrizen gezeigt werden und die Verbindung zwischen dem +als Matrizen vorgestellt werden und die Verbindung zwischen dem Vorzeichen einer Permutation und der Determinanten hergestellt werden. \index{Determinante}% @@ -64,8 +64,8 @@ A_\sigma \begin{definition} \label{buch:permutationen:def:permutationsmatrix} \index{Permutationsmatrix}% -Eine {\em Permutationsmatrix} ist eine Matrix $P\in M_n(\Bbbk)$ -derart, die in jeder Zeile und Spalte genau eine $1$ enthalten ist, +Eine {\em Permutationsmatrix} ist eine Matrix $P\in M_n(\Bbbk)$, +die in jeder Zeile und Spalte genau eine $1$ enthält, während alle anderen Matrixelemente $0$ sind. \end{definition} diff --git a/buch/chapters/50-permutationen/transpositionen.tex b/buch/chapters/50-permutationen/transpositionen.tex index 5815c8a..dcbf2e0 100644 --- a/buch/chapters/50-permutationen/transpositionen.tex +++ b/buch/chapters/50-permutationen/transpositionen.tex @@ -5,7 +5,6 @@ % \section{Permutationen und Transpositionen \label{buch:section:permutationen-und-transpositionen}} -\rhead{Transpositionen} Im vorangegangenen Abschnitt haben wir Permutationen durch die Zyklenzerlegung charakterisiert. Es zeigt sich aber, dass sich eine Permutation in noch elementarere @@ -26,6 +25,7 @@ x&\qquad\text{sonst.} \end{cases} \] \end{definition} +\rhead{Transpositionen} Eine Transposition hat genau einen Zyklus der Länge $2$, alle anderen Zyklen haben die Länge $1$. @@ -91,7 +91,7 @@ d.~h. \operatorname{sgn}(\sigma_1) \operatorname{sgn}(\sigma_2). \] -Da ganz offensichtlich $\sigma_1\sigma_2$ mit $k_1+k_2$ Transpositionen +Offensichtlich kann $\sigma_1\sigma_2$ mit $k_1+k_2$ Transpositionen geschrieben werden kann, wenn $\sigma_i$ mit $k_i$ Transpositionen geschrieben werden kann. @@ -113,7 +113,7 @@ S_n. \] \index{Kern}% \index{alterniernde Gruppe}% -heisst die {\em alternierende Gruppe} der Ordnung $n$ +heisst die {\em alternierende Gruppe} der Ordnung $n$. Die Elemente von $A_n$ heissen auch die {\em geraden} Permutationen, \index{gerade Permutation}% \index{ungerade Permutation}% diff --git a/buch/chapters/60-gruppen/chapter.tex b/buch/chapters/60-gruppen/chapter.tex index 4f2fb5a..6f55f23 100644 --- a/buch/chapters/60-gruppen/chapter.tex +++ b/buch/chapters/60-gruppen/chapter.tex @@ -7,8 +7,8 @@ \label{buch:chapter:matrizengruppen}} \lhead{Matrizengruppen} \rhead{} -Matrizen können dazu verwendet werden, Symmetrien von geometrischen oder -physikalischen Systemen zu beschreiben. +Matrizen können dazu verwendet werden, Symmetrien von geometrischen Objekten +oder physikalischen Systemen zu beschreiben. \index{Symmetrie}% \index{physikalisches System}% Neben diskreten Symmetrien wie zum Beispiel Spiegelungen gehören dazu @@ -44,8 +44,8 @@ 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. +so eng, dass sich die meisten Eigenschaften der Lie-Gruppe aus den +Eigenschaften der Lie-Algebra ableiten lassen. Die Verbindung wird hergestellt durch die Exponentialabbildung. Ziel dieses Kapitels ist, die Grundzüge dieses interessanten Zusammenhangs darzustellen. diff --git a/buch/chapters/60-gruppen/lie-algebren.tex b/buch/chapters/60-gruppen/lie-algebren.tex index 0f6429f..b84b244 100644 --- a/buch/chapters/60-gruppen/lie-algebren.tex +++ b/buch/chapters/60-gruppen/lie-algebren.tex @@ -5,7 +5,6 @@ % \section{Lie-Algebren \label{buch:section:lie-algebren}} -\rhead{Lie-Algebren} Im vorangegangenen Abschnitt wurde gezeigt, dass alle beschriebenen Matrizengruppen als Untermannigfaltigkeiten im $n^2$-dimensionalen Vektorraum $M_n(\mathbb{R})$ betrachtet werden können. @@ -29,6 +28,7 @@ Lie-Algebra von $\operatorname{SO}(3)$ mit dem Vektorprodukt in $\mathbb{R}^3$ übereinstimmt. \index{Vektorprodukt}% +\rhead{Lie-Algebren} % % Die Lie-Algebra einer Matrizengruppe % @@ -92,24 +92,25 @@ e^{At}e^{Bt} - e^{(A+B)t} = (AB-BA) \frac{t^2}{2} + \ldots = +\phantom{-} [A,B]\frac{t^2}{2}+\ldots \\ e^{Bt}e^{At} - e^{(A+B)t} &= \biggl(BA-\frac{AB+BA}2\biggr)t^2 -+\ldots ++\ldots, = (BA-AB) \frac{t^2}{2} +\ldots = --[A,B]\frac{t^2}{2} +-[A,B]\frac{t^2}{2}+\ldots, \\ e^{At}e^{Bt}-e^{Bt}e^{At} &= (AB-BA)t^2+\ldots = -\phantom{-}[A,B]t^2+\ldots +\phantom{-}[A,B]t^2+\ldots, \end{align*} wobei $[A,B]=AB-BA$ abgekürzt wird. @@ -247,15 +248,15 @@ Solche Matrizen haben die Form \] Die antisymmetrischen Matrizen \[ -\omega_{23} +\Omega_{23} = \begin{pmatrix} 0&0&0\\0&0&-1\\0&1&0\end{pmatrix}, \quad -\omega_{31} +\Omega_{31} = \begin{pmatrix} 0&0&1\\0&0&0\\-1&0&0\end{pmatrix}, \quad -\omega_{12} +\Omega_{12} = \begin{pmatrix} 0&1&0\\-1&0&0\\0&0&0\end{pmatrix} \] @@ -263,11 +264,11 @@ bilden eine Basis für $\operatorname{so}(3)$, man kann \[ \Omega = -\omega_1\omega_{23} +\omega_1\Omega_{23} + -\omega_2\omega_{31} +\omega_2\Omega_{31} + -\omega_3\omega_{12} +\omega_3\Omega_{12} \] schreiben. Der Vektorraum $\operatorname{so}(3)$ ist also dreidimensional. @@ -276,7 +277,7 @@ Die Kommutatoren der Basisvektoren sind \begin{equation} \setlength\arraycolsep{4pt} \begin{aligned} -[\omega_{23},\omega_{31}] +[\Omega_{23},\Omega_{31}] &= \begin{pmatrix} 0&-1&0\\ @@ -284,10 +285,10 @@ Die Kommutatoren der Basisvektoren sind 0&0&0 \end{pmatrix} = -\omega_{12}, +\Omega_{12}, %\\ & -[\omega_{31},\omega_{12}] +[\Omega_{31},\Omega_{12}] &= \begin{pmatrix} 0&0&0\\ @@ -295,10 +296,10 @@ Die Kommutatoren der Basisvektoren sind 0&1&0 \end{pmatrix} = -\omega_{23}, +\Omega_{23}, %\\ & -[\omega_{12},\omega_{23}] +[\Omega_{12},\Omega_{23}] &= \begin{pmatrix} 0&0&1\\ @@ -306,7 +307,7 @@ Die Kommutatoren der Basisvektoren sind -1&0&0 \end{pmatrix} = -\omega_{31}, +\Omega_{31}, \end{aligned} \label{buch:gruppen:eqn:so3-kommutatoren} \end{equation} @@ -324,19 +325,19 @@ Achse ist eine Drehung um die $x_3$-Achse. 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}$ +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 +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 +Aus der Rodrigues-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}$ +$\Omega\vec{x} = \vec{\omega}\times\vec{x}$ ausgedrückt werden. Die Wirkung von $I+t\Omega$ auf einem Vektor $\vec{x}$ ist @@ -482,10 +483,10 @@ somit ist \operatorname{sl}_n(\mathbb{R}) = \{ -A\in M_n(\mathbb{R})\;|\; \operatorname{Spur}(A)=0 +A\in M_n(\mathbb{R}) \mid \operatorname{Spur}(A)=0 \} \] -mit dem Kommutator eine Lie-Algebra. +mit dem Kommutator von Matrizen als Lie-Klammer eine Lie-Algebra. % % Die Lie-Algebra von U(n) @@ -496,8 +497,8 @@ Die Lie-Gruppe U(n) = \{ -A\in M_n(\mathbb{C} -\;|\; +A\in M_n(\mathbb{C}) +\mid AA^*=I \} \] @@ -507,7 +508,7 @@ AA^*=I 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)$ +Sei $\gamma(t)$ eine differenzierbare Kurve in $\operatorname{U}(n)$ derart, dass $\gamma(0)=I$. Die Ableitung der Identität $AA^*=I$ führt dann auf \begin{equation*} @@ -568,7 +569,7 @@ imaginär. % \subsection{Die Lie-Algebra von $\operatorname{SU}(2)$} Die Lie-Algebra $\operatorname{su}(n)$ besteht aus den -spurlosen antihermiteschen Matrizen. +spurlosen antihermiteschen $2\times 2$-Matrizen. \index{su(n)@$\operatorname{su}(n)$}% Sie erfüllen daher die folgenden Bedingungen: \[ @@ -658,7 +659,7 @@ Diese Matrizen heissen die {\em Pauli-Matrizen}, sie haben die Kommutatoren 2i\sigma_2, \end{align*} Bis auf eine Skalierung stimmt dies überein mit den Kommutatorprodukten -der Matrizen $\omega_{23}$, $\omega_{31}$ und $\omega_{12}$ +der Matrizen $\Omega_{23}$, $\Omega_{31}$ und $\Omega_{12}$ in \eqref{buch:gruppen:eqn:so3-kommutatoren}. Die Matrizen $-\frac12i\sigma_j$ haben die Kommutatorprodukte \begin{align*} @@ -688,9 +689,9 @@ Die Matrizen $-\frac12i\sigma_j$ haben die Kommutatorprodukte \end{align*} Die lineare Abbildung, die \begin{align*} -\omega_{23}&\mapsto -{\textstyle\frac12}i\sigma_1\\ -\omega_{31}&\mapsto -{\textstyle\frac12}i\sigma_2\\ -\omega_{12}&\mapsto -{\textstyle\frac12}i\sigma_3 +\Omega_{23}&\mapsto -{\textstyle\frac12}i\sigma_1\\ +\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)$ auf die Lie-Algebra $\operatorname{su}(2)$. diff --git a/buch/chapters/60-gruppen/lie-gruppen.tex b/buch/chapters/60-gruppen/lie-gruppen.tex index 94df38e..9f0c26f 100644 --- a/buch/chapters/60-gruppen/lie-gruppen.tex +++ b/buch/chapters/60-gruppen/lie-gruppen.tex @@ -26,7 +26,7 @@ $\operatorname{GL}_n(\mathbb{R})$ heraus. \subsection{Mannigfaltigkeitsstruktur der Matrizengruppen \label{buch:subsection:mannigfaltigkeitsstruktur-der-matrizengruppen}} -Eine Matrizengruppe wird automatsich zu einer Mannigfaltigkeit, +Eine Matrizengruppe wird automatisch zu einer Mannigfaltigkeit, wenn es gelingt, eine Karte für eine Umgebung des neutralen Elements zu finden. Dazu muss gezeigt werden, dass sich aus einer solchen Karte für jedes @@ -46,7 +46,7 @@ gU_e h\mapsto \varphi_e(g^{-1}h) \] eine Karte für die Umgebung $U_g$ des Gruppenelementes $g$. -schreibt man $l_{g}$ für die Abbildung $h\mapsto gh$, dann +Schreibt man $l_{g}$ für die Abbildung $h\mapsto gh$, dann kann man die Kartenabbildung auch $\varphi_g = \varphi_e\circ l_{g^{-1}}$ schreiben. @@ -98,8 +98,9 @@ Mannigfaltigkeit ist derart, dass die Abbildungen \begin{align*} G\times G \to G &: (g_1,g_2)\mapsto g_1g_2 \\ -G\to G &: g \mapsto g^{-1} +G\to G &: g \mapsto g^{-1}, \end{align*} +die zu den Gruppenoperationen gehören, differenzierbare Abbildungen zwischen Mannigfaltigkeiten sind. \end{definition} @@ -354,13 +355,83 @@ entstehen aus $J$ durch Drehung mit der Matrix $R_\alpha$ und Skalierung mit der Winkelgeschwindigkeit $\dot{\alpha}(t)$. \index{Winkelgeschwindigkeit}% +\subsection{Symmetrien des harmonischen Oszillators +\label{buch:gruppen:symmetrien-harm-osz}} +Im Abschnitt über den harmonischen Oszillator +auf Seite~\pageref{buch:gruppen:harmonischer-oszillator} +wurde für die Einparameteruntergruppe +$\Phi_t\in\operatorname{GL}_2(\mathbb{R})$ der +Ausdruck~\eqref{buch:gruppen:eqn:phi} gefunden. +Die Ableitung von $\Phi_t$ an der Stelle $t=0$ ist +\begin{align*} +\frac{d}{dt}\Phi_t\bigg|_{t=0} +&= +\frac{d}{dt} +\begin{pmatrix} +\cos\omega t&-\frac{1}{\omega}\sin\omega t\\ +\omega\sin\omega t&\cos\omega t +\end{pmatrix} +\bigg|_{t=0} += +\begin{pmatrix} +-\omega\sin\omega t&-\cos\omega t\\ +\omega^2\cos\omega t&-\omega\sin\omega t +\end{pmatrix} +\bigg|_{t=0} += +\begin{pmatrix} +0&-1\\\omega^2&0 +\end{pmatrix} += +A. +\end{align*} +Die Potenzen von $A$ sind +\[ +A^2 += +\begin{pmatrix} -\omega^2&0\\0&-\omega^2\end{pmatrix} += +-\omega^2 I, +\quad +A^3 += +-\omega^2 A, +\quad +A^4 += +\omega^4 I. +\] +Die Potenzen wiederholen sich bis auf den Faktor $\omega^4$ mit Periode 4. +Damit kann man jetzt die Exponentialabbildung für $At$ berechnen: +\begin{align*} +e^{At} +&= +I+At+\frac{A^2t^2}{2!}+\frac{A^3t^3}{3!}+\frac{A^4t^4}{4!}+\frac{A^5t^5}5!+\dots +\\ +&= +I+\frac{1}{\omega}A\omega t-I\frac{\omega^2t^2}{2!} +-\frac1{\omega}A\frac{\omega^3t^3}{3!} ++\frac{\omega^4t^4}{4!} ++\frac{1}{\omega}\frac{\omega^5t^5}5!+\dots +\\ +&= I\cos\omega t + \frac1{\omega}A\sin\omega t += +\begin{pmatrix} +\cos\omega t &-\frac{1}{\omega}\sin\omega t\\ +\omega\sin\omega t & \cos\omega t +\end{pmatrix} = \Phi_t. +\end{align*} +Der Fluss der Differentialgleichung des harmonischen Oszillators ist +also nichts anderes als die Exponentialabbildung der Ableitung $A$ zur +Zeit $t=0$. + % % 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. +Lie-Gruppe, die in diesem Abschnitt untersucht werden soll. \subsubsection{Skalarprodukt} Lineare Abbildungen des Raumes $\mathbb{R}^n$ können durch @@ -368,22 +439,23 @@ $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 nicht, wenn -für jedes beliebige Paar $x,y$ von Vektoren gilt -$\langle Ax,Ay\rangle = \langle x,y\rangle$. +für jedes beliebige Paar $x,y$ von Vektoren +$\langle Ax,Ay\rangle = \langle x,y\rangle$ gilt. Das Standardskalarprodukt kann mit dem Matrixprodukt ausgedrückt werden: -\[ +\begin{equation} \langle Ax,Ay\rangle = (Ax)^tAy = x^tA^tAy -= +\overset{!}{=} x^ty = \langle x,y\rangle -\] +\label{buch:gruppen:eqn:orthogonalbed} +\end{equation} für jedes Paar von Vektoren $x,y\in\mathbb{R}$. - +% 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 @@ -393,11 +465,12 @@ 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_{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 Matrixelemente von $A^tA$ können +mit der Bedingung \eqref{buch:gruppen:eqn:orthogonalbed} +berechnet werden als +$\langle A^tAe_i, e_j\rangle =\langle e_i,e_j\rangle = \delta_{i\!j}$. +Die Matrix $A$ erfüllt also $AA^t=I$ oder $A^{-1}=A^t$. +Solche Matrizen heissen {\em orthogonale} Matrizen. \index{orthogonale Matrix}% Die Menge $\operatorname{O}(n)$ der isometrischen Abbildungen \index{O(n)@$\operatorname{O}(n)$}% @@ -425,9 +498,10 @@ Im Spezialfall $n=2$ ist die Gruppe $\operatorname{O}(2)$ eindimensional. \subsubsection{Tangentialvektoren} Die orthogonalen Matrizen bilden eine abgeschlossene Untermannigfaltigkeit von $\operatorname{GL}_n(\mathbb{R})$, nicht jede Matrix $M_n(\mathbb{R})$ -kann also ein Tangentialvektor von $O(n)$ sein. +kann also ein Tangentialvektor von $\operatorname{O}(n)$ sein. Um herauszufinden, welche Matrizen als Tangentialvektoren in Frage -kommen, betrachten wir eine Kurve $\gamma\colon\mathbb{R}\to O(n)$ +kommen, betrachten wir eine Kurve +$\gamma\colon\mathbb{R}\to \operatorname{O}(n)$ von orthogonalen Matrizen mit $\gamma(0)=I$. Orthogonal bedeutet \[ @@ -465,11 +539,39 @@ 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_{i\!j}$ mit den Matrixelementen -$(A_{i\!j})_{i\!j}=-1$ und $(A_{i\!j})_{ji}=1$ +Für jedes Paar $i<j$ ist die Matrix +\begin{equation} +\begin{tikzpicture}[>=latex,thick,baseline=(O)] +\coordinate (O) at (0,0); +\draw[dotted,color=gray] (-1.2,0.42) -- (2.5,0.42); +\draw[dotted,color=gray] (-1.2,-0.4) -- (2.5,-0.4); +\draw[dotted,color=gray] (-0.14,-1.4) -- (-0.14,1.4); +\draw[dotted,color=gray] (0.96,-1.4) -- (0.96,1.4); +\node at (2.5,0.42) [right] {$i\mathstrut$}; +\node at (2.5,-0.40) [right] {$j\mathstrut$}; +\node at (-0.14,1.4) [above] {$i\mathstrut$}; +\node at (0.96,1.4) [above] {$j\mathstrut$}; +\node at (0,0) {$\displaystyle +\Omega_{i\!j} += +\begin{pmatrix*}[r] +& & & & & & & & \\ +& & & & & & & & \\ +& & &0& &-1& & & \\ +& & & & & & & & \\ +& & &1& & 0& & & \\ +& & & & & & & & \\ +& & & & & & & & +\end{pmatrix*} +$}; +\end{tikzpicture} +\label{buch:gruppen:eqn:Omega} +\end{equation} +mit den Matrixelementen +$(\Omega_{i\!j})_{i\!j}=-1$ und $(\Omega_{i\!j})_{ji}=1$ antisymmetrisch. -Für $n=2$ ist $A_{12}=J$. -Die $n(n-1)/2$ Matrizen $A_{i\!j}$ bilden eine Basis des +Für $n=2$ ist $\Omega_{12}=J$. +Die $n(n-1)/2$ Matrizen $\Omega_{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)$ @@ -489,8 +591,9 @@ Die Gruppe \[ \operatorname{SO}(n) = -\{A\in\operatorname{O}(n)\;|\; \det A=1\} +\{A\in\operatorname{O}(n)\mid\det A=1\} \] +der orientierungserhaltenden Isometrien von $\mathbb{R}^n$ heisst die {\em spezielle orthogonale Gruppe}. \index{spezielle orthogonale Gruppe}% \index{orthogonale Gruppe, speziell}% @@ -537,13 +640,13 @@ R_{z,\gamma} \end{pmatrix} \\ &= -e^{A_{23}t} +e^{\Omega_{23}t} & &= -e^{-A_{13}t} +e^{-\Omega_{13}t} & &= -e^{A_{21}t} +e^{\Omega_{21}t} \end{align*} die Drehungen um die Koordinatenachsen um den Winkel $\alpha$ beschreiben. @@ -564,15 +667,15 @@ $|\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. - +Achse tangential an die Bahn von $\vec{x}$ unter der Drehung ist +(siehe Abbildung~\ref{buch:lie:fig:rodrigues}). +% 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}): +trigonometrischen Funktionen beschreiben: \begin{align} \vec{x} \mapsto @@ -595,10 +698,13 @@ R_\alpha\vec{x} \vec{k}\times\vec{x}\sin\alpha. \label{buch:lie:eqn:rodrigues} \end{align} -Dies ist bekannt als die {\em Formel von Rodrigues} +\eqref{buch:lie:eqn:rodrigues} +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$ +Wir halten noch fest, dass die Ableitung +von \eqref{buch:lie:eqn:rodrigues} +an der Stelle $\alpha=0$ der Tangentialvektor \begin{equation} \frac{d}{d\alpha}R_\alpha\vec{x}\,\bigg|_{\alpha=0} @@ -631,9 +737,9 @@ Die volumenerhaltenden Abbildungen bilden die Gruppe = \{ A\in M_n(\mathbb{R}) -\;|\; +\mid \det (A) = 1 -\} +\}, \] sie heisst die {\em spezielle lineare Gruppe}. \index{spezielle lineare Gruppe}% @@ -651,7 +757,7 @@ Für alle $t\in\mathbb{R}$ ist $\det A(t)=1$, daher ist die Ableitung \quad\text{an der Stelle $t=0$.} \] Für $n=2$ ist -\begin{align*} +\begin{align} A(t) &= \begin{pmatrix} @@ -665,22 +771,29 @@ c(t)&d(t) \det A(t)\bigg|_{t=0} &= \frac{d}{dt}\bigl(a(t)d(t)-b(t)c(t)\bigr)\bigg|_{t=0} +\notag \\ &&&& &= \dot{a}(0) d(0)+a(0)\dot{d}(0) - \dot{b}(0) c(0)-b(0)\dot{c}(0) +\notag \\ &&&& &= \dot{a}(0) + \dot{d}(0) +\notag \\ &&&& +\frac{d}{dt} +\det A(t)\bigg|_{t=0} &= \operatorname{Spur}\frac{dA}{dt}. -\end{align*} -Dies gilt nicht nur im Falle $n=2$, sondern ganz allgemein für beliebige +\label{buch:gruppen:eqn:spurformel} +\end{align} +Die Spurformel~\eqref{buch:gruppen:eqn:spurformel} +gilt nicht nur im Falle $n=2$, sondern ganz allgemein für beliebige $n\times n$-Matrizen. \begin{satz} @@ -691,8 +804,10 @@ mit $A(0)=I$, dann ist $\operatorname{Spur}\dot{A}(0)=0$. \begin{proof}[Beweis] Die Entwicklung der Determinante von $A$ nach der ersten Spalte ist \[ -\det A(t) = \sum_{i=1}^n (-1)^{i+1} a_{i1}(t) \det A_{i1}(t). +\det A(t) = \sum_{i=1}^n (-1)^{i+1} a_{i1}(t) \det A_{i1}(t), \] +Wobei $A_{i\!j}(t)$ der $i$-$k$-Minor von $A(t)$ ist +(Seite~\pageref{buch:linear:def:minor}). Die Ableitung nach $t$ ist \[ \frac{d}{dt} \det A(t) @@ -824,8 +939,13 @@ Abbildung~\ref{buch:gruppen:fig:sl2} visualisiert. Die Matrizen $e^{At}$ sind Streckungen der einen Koordinatenachse und Stauchungen der anderen derart, dass das Volumen erhalten bleibt. +Die Bahn eines Punktes unter Wirkung von $e^{At}$ ist eine Hyperbel +mit den Koordinatenachsen als Asymptoten. + Die Matrizen $e^{Bt}$ sind Drehmatrizen, die Längen und Winkel und damit erst recht den Flächeninhalt erhalten. +Die Bahn eines Punktes ist ein Kreis um den Nullpunkt. + Die Matrizen der Form $e^{Ct}$ haben die Vektoren $(1,\pm1)$ als Eigenvektoren: \begin{align*} @@ -869,6 +989,8 @@ Die Matrizen $e^{Ct}$ strecken die Richtung $(1,1)$ um $e^t$ und die dazu orthogonale Richtung $(1,-1)$ um den Faktor $e^{-t}$. Dies ist die gegenüber $e^{At}$ um $45^\circ$ verdrehte Situation, auch diese Matrizen sind flächenerhaltend. +Die Bahnen einzelner Punkte unter $e^{Ct}$ sind Hyperbeln mit +den Winkelhalbierenden als Asymptoten. \begin{figure} \centering \includegraphics{chapters/60-gruppen/images/scherungen.pdf} diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex index 7222c2c..ece02b5 100644 --- a/buch/chapters/60-gruppen/symmetrien.tex +++ b/buch/chapters/60-gruppen/symmetrien.tex @@ -28,7 +28,8 @@ ergeben die gleichen Werte wie Messungen entsprechenden Strecken in der linken Hälfte, was den Begriff Symmetrie rechtfertigt. \label{buch:lie:bild:castlehoward}} \end{figure} -In der Physik wird dem Begriff der Symmetrie daher auch eine erweiterte + +In der Physik wird dem Begriff der Symmetrie eine erweiterte Bedeutung gegeben. Jede Transformation eines Systems, welche bestimmte Grössen nicht verändert, wird als Symmetrie bezeichnet. @@ -39,7 +40,7 @@ Koordinatensystems ändert daher die Bewegungsgleichungen nicht, sie ist eine Symmetrie des Systems. Umgekehrt kann man fragen, welche Symmetrien ein System hat. -Da sich Symmetrien zusammensetzen und umkehren lassen, kann man in davon +Da sich Symmetrien zusammensetzen und umkehren lassen, kann man davon ausgehen, dass die Symmetrietransformationen eine Gruppe bilden. Besonders interessant ist dies im Falle von Transformationen, die durch Matrizen beschrieben weren. @@ -94,8 +95,8 @@ ihre Normale erhalten. 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$ unveränder bleibt, können wir +Zu jeder linearen Abbildung $f\colon\mathbb{R}^n\to\mathbb{R}^n$, unter der +ein geometrisches Objekt in $\mathbb{R}^n$ unverändert 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$ usw., die wir auch $f^n$ mit $n\in\mathbb{N}$ schreiben werden, @@ -131,9 +132,8 @@ beschrieben werden. Ein Kreis um den Nullpunkt bleibt unter jeder dieser Drehungen invariant. 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. +Ein vorgegebener Punkt bewegt sich unter der Wirkung der Drehung +$R_\alpha$ auf einem Kreis um den Nullpunkt. \begin{definition} \label{buch:lie:def:einparameteruntergruppe} @@ -148,7 +148,7 @@ Die Abbildung \[ \varphi \colon -\mathbb{R}\to\operatorname{GL}_n(\mathbb{R}) +\mathbb{R}\to\operatorname{GL}_2(\mathbb{R}) : \alpha \mapsto R_{\alpha} @@ -161,6 +161,7 @@ R_{\alpha} ist also eine Einparameteruntergruppe von $\operatorname{GL}_2(\mathbb{R})$. \subsubsection{Der harmonische Oszillator} +\label{buch:gruppen:harmonischer-oszillator} \index{harmonischer Oszillator}% \index{Oszillator}% \begin{figure} @@ -171,8 +172,9 @@ Differentialgleichung~\eqref{chapter:gruppen:eqn:phasenraumdgl} 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$ +Eine Masse $m$ ist aufgehängt an einer Feder mit der Federkonstanten $K$ \index{Federkonstante}% +und schwingt um die Ruhelage $x=0$ entsprechend der Differentialgleichung \[ m\frac{d^2}{dt^2} x(t) = -Kx(t). @@ -242,7 +244,7 @@ p(t) \end{equation} schreiben. Die Matrizen $\Phi_t$ bilden eine Einparameteruntergruppe von -$\operatorname{GL}_n(\mathbb{R})$, da +$\operatorname{GL}_2(\mathbb{R})$, da \begin{align*} \Phi_s\Phi_t &= @@ -284,10 +286,10 @@ 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})$. +Matrizen in $\operatorname{GL}_2(\mathbb{R})$. Der Grund dafür ist, dass die Differentialgleichung~\eqref{chapter:gruppen:eqn:phasenraumdgl} -linear ist. +linear zu sein braucht. Dies hat zur Folge, dass für zwei Anfangsbedingungen $x_1,x_2\in\mathbb{R}^2$ die Lösung für Linearkombinationen $\lambda x_1+\mu x_2$ durch Linearkombination der Lösungen erhalten werden kann, also @@ -377,12 +379,14 @@ $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 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 +Solche Zwangskräfte leisten keine Arbeit, sorgen aber zum Beispiel +dafür, dass die Vektoren $f(t,x)$ für Punkte $x$ auf der Kugeloberfläche immer tangential an die Kugel sind. Trotzdem ist der Tangentialvektor oder der Geschwindigkeitsvektor 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. +Der Betrag der Zwangskräfte hängt von der Krümmung der Fläche ab. Um die Idee einer Differentialgleichung auf einer beliebigen Fläche konsistent zu machen, ist daher notwendig, die Idee einer Tagentialrichtung @@ -417,8 +421,8 @@ kann das Problem lösen, indem er eine lokale Karte für das Gebiet um den Pol erstellt. Dafür kann er beliebige Koordinaten verwenden, zum Beispiel auch ein kartesisches Koordinatensystem, er muss nur eine Methode haben, -wie er seine Koordinaten wieder auf geographische Länge und Breite -umrechnen will. +nach der er seine Koordinaten wieder auf geographische Länge und Breite +umrechnen kann. Und wenn er über Geschwindigkeiten kommunizieren will, dann muss er auch Ableitungen von Kurven in seinem kartesischen Koordinatensystem umrechnen können auf die Kugelkoordinaten. @@ -475,7 +479,7 @@ Karten und Atlanten regeln also nur, wie sich verschiedene lokale Koordinatensysteme ineinander umrechnen lassen. \begin{beispiel} -$M=\mathbb{R}^n$ ist eine differenzierbare Mannigfaltigkeit denn +$M=\mathbb{R}^n$ ist eine differenzierbare Mannigfaltigkeit, denn die identische Abbildung $M\to \mathbb{R}^n$ ist eine Karte und ein Atlas von $M$. \end{beispiel} @@ -494,19 +498,23 @@ gibt. Die Projektionen auf die einzelnen Koordinaten liefern die folgenden vier Karten: \begin{align*} -\varphi_1&\colon U_{x>0}\{(x,y)\;|\;x^2+y^2=1\wedge x>0\} \to\mathbb{R} +\color{red} +\varphi_1&{\color{red}\colon U_{x>0}=\{(x,y)\;|\;x^2+y^2=1\wedge x>0\}}\to\mathbb{R} : (x,y) \mapsto y \\ -\varphi_2&\colon U_{x<0}\{(x,y)\;|\;x^2+y^2=1\wedge x<0\} \to\mathbb{R} +\color{blue} +\varphi_2&{\color{blue}\colon U_{x<0}=\{(x,y)\;|\;x^2+y^2=1\wedge x<0\}}\to\mathbb{R} : (x,y) \mapsto y \\ -\varphi_3&\colon U_{y>0}\{(x,y)\;|\;x^2+y^2=1\wedge y>0\} \to\mathbb{R} +\color{darkgreen} +\varphi_3&{\color{darkgreen}\colon U_{y>0}=\{(x,y)\;|\;x^2+y^2=1\wedge y>0\}}\to\mathbb{R} : (x,y) \mapsto x \\ -\varphi_4&\colon U_{y<0}\{(x,y)\;|\;x^2+y^2=1\wedge y<0\} \to\mathbb{R} +\color{orange} +\varphi_4&{\color{orange}\colon U_{y<0}=\{(x,y)\;|\;x^2+y^2=1\wedge y<0\}}\to\mathbb{R} : (x,y) \mapsto x \end{align*} @@ -526,36 +534,44 @@ ist je nach Quadrant durch &\text{1.~Quadrant}& \varphi_{31} &= -\varphi_3\circ\varphi_1^{-1}\colon y\mapsto\phantom{-}\sqrt{1-y^2\mathstrut} +{\color{darkgreen}\varphi_3}\circ{\color{red}\varphi_1}^{-1} +\colon +y\mapsto\phantom{-}{\textstyle\sqrt{1-y^2\mathstrut}} & D\varphi_{31} &= -\frac{y}{\sqrt{1-y^2\mathstrut}} \\ &\text{2.~Quadrant}& -\varphi_{24} +\varphi_{23} &= -\varphi_3\circ\varphi_1^{-1}\colon x\mapsto\phantom{-}\sqrt{1-x^2\mathstrut} +{\color{blue}\varphi_2}\circ{\color{darkgreen}\varphi_3}^{-1} +\colon +x\mapsto\phantom{-}{\textstyle\sqrt{1-x^2\mathstrut}} & -D\varphi_{24} +D\varphi_{23} &= -\frac{x}{\sqrt{1-x^2\mathstrut}} \\ &\text{3.~Quadrant}& \varphi_{42} &= -\varphi_3\circ\varphi_1^{-1}\colon y\mapsto-\sqrt{1-y^2\mathstrut} +{\color{orange}\varphi_4}\circ{\color{blue}\varphi_2}^{-1} +\colon +y\mapsto-{\textstyle\sqrt{1-y^2\mathstrut}} & D\varphi_{42} &= \phantom{-}\frac{y}{\sqrt{1-y^2\mathstrut}} \\ &\text{4.~Quadrant}& -\varphi_{14} +\varphi_{41} &= -\varphi_3\circ\varphi_1^{-1}\colon x\mapsto-\sqrt{1-x^2\mathstrut} +{\color{red}\varphi_1}\circ{\color{orange}\varphi_4}^{-1} +\colon +x\mapsto-{\textstyle\sqrt{1-x^2\mathstrut}} & -D\varphi_{14} +D\varphi_{41} &= \phantom{-}\frac{x}{\sqrt{1-x^2\mathstrut}} \end{align*} @@ -725,7 +741,7 @@ 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 Matrizengruppen erfolgreich, +Dieser Ansatz ist für alle Matrizengruppen generell erfolgreich, wie wir später sehen werden. Ein weiterer Ansatz, Tangentialvektoren zu vergleichen, ist die Idee, diff --git a/buch/chapters/60-gruppen/uebungsaufgaben/6001.tex b/buch/chapters/60-gruppen/uebungsaufgaben/6001.tex index 2acf6f6..1cde6e3 100644 --- a/buch/chapters/60-gruppen/uebungsaufgaben/6001.tex +++ b/buch/chapters/60-gruppen/uebungsaufgaben/6001.tex @@ -48,7 +48,7 @@ D_\alpha&\vec{t}\\ \right| \; \alpha\in\mathbb{R},\vec{t}\in\mathbb{R}^2 -\right\} +\right\}. \] Wir kürzen die Elemente von $G$ auch als $(\alpha,\vec{t})$ ab. \begin{teilaufgaben} @@ -181,7 +181,7 @@ Y 0&0&0\\ 0&0&1\\ 0&0&0 -\end{pmatrix} +\end{pmatrix}. \end{align*} \item Die Vertauschungsrelationen sind @@ -226,7 +226,7 @@ DY-YD &= XY-YX = -0-0=0 +0-0=0. \qedhere \end{align*} \end{teilaufgaben} diff --git a/buch/chapters/60-gruppen/uebungsaufgaben/6002.tex b/buch/chapters/60-gruppen/uebungsaufgaben/6002.tex index 14fbe2b..a154703 100644 --- a/buch/chapters/60-gruppen/uebungsaufgaben/6002.tex +++ b/buch/chapters/60-gruppen/uebungsaufgaben/6002.tex @@ -117,12 +117,12 @@ Dies ist am einfachsten in der Matrixform nachzurechnen: \begin{pmatrix} e^{s_1}&0\\0&1\end{pmatrix} \begin{pmatrix} e^{s_2}&0\\0&1\end{pmatrix} &= -\begin{pmatrix}e^{s_1+s_2}&0\\0&1\end{pmatrix} +\begin{pmatrix}e^{s_1+s_2}&0\\0&1\end{pmatrix}, & \begin{pmatrix} 1&t_1\\0&1\end{pmatrix} \begin{pmatrix} 1&t_2\\0&1\end{pmatrix} &= -\begin{pmatrix} 1&t_1+t_2\\0&1\end{pmatrix} +\begin{pmatrix} 1&t_1+t_2\\0&1\end{pmatrix}. \end{align*} \item Die Tangentialvektoren werden erhalten durch ableiten der @@ -138,7 +138,7 @@ T &= \frac{d}{dt} \begin{pmatrix}1&t\\0&1\end{pmatrix}\bigg|_{t=0} = -\begin{pmatrix}0&1\\0&0\end{pmatrix} +\begin{pmatrix}0&1\\0&0\end{pmatrix}. \end{align*} \item Der Kommutator ist \[ diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 845e640..5bae074 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -12,7 +12,7 @@ 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 +Ziel dieses Abschnitts ist, Graphen und ihre zugehörigen Matrizen zu definieren und erste Eigenschaften des Graphen mit algebraischen Mitteln abzuleiten. Die Präsentation ist allerdings nur ein erster Einstieg, tiefer @@ -37,7 +37,7 @@ Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten mit sogenannten Kanten \index{Kante}% verbunden werden. -Bei einen ungerichteten Graphen sind die beiden Endpunkte einer Kante +Bei einem ungerichteten Graphen sind die beiden Endpunkte einer Kante gleichwertig, es gibt keine bevorzugte Reihenfolge oder Richtung der Kante. Eine Kante ist daher vollständig spezifiziert, wenn wir die @@ -110,8 +110,8 @@ Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom Knoten $a$ wieder zu $a$ zurück führt. Man kann einen ungerichteten Graphen in einen gerichteten Graphen -verwandeln, indem jede Kante $\{a,b\}$ durch zwei Kanten -$(a,b)$ und $(b,a)$ ersetzt wird. +verwandeln, indem jede Kante $\{u,v\}$ durch zwei Kanten +$(u,v)$ und $(v,u)$ ersetzt wird. Aus dem ungerichteten Graphen $(V,E)$ mit Knotenmenge $V$ und Kantenmenge $E$ wird so der gerichtete Graph $(V,E')$ mit der Kantenmenge @@ -119,13 +119,13 @@ $(V,E')$ mit der Kantenmenge E' = \{ -(a,e) +(u,v) \,|\, -\{a,e\}\in E +\{u,v\}\in E \}. \end{equation*} Eine umgekehrte Zuordnung eines gerichteten zu einem ungerichteten -Graphen ist nicht möglich, da eine ``Schleife'' $(a,a)$ nicht in eine Kante +Graphen ist nicht möglich, da eine ``Schleife'' $(v,v)$ nicht in eine Kante des ungerichteten Graphen abgebildet werden kann. In einem gerichteten Graphen kann man sinnvoll von gerichteten Pfaden @@ -224,8 +224,8 @@ 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 beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von -vollständiger Induktion. +Wir beweisen mit Hilfe von vollständiger Induktion, +dass $A^n$ Pfade der Länge $n$ zählt. Es ist klar, dass $A^1$ die genannte Eigenschaft hat. Der Fall $A^1$ dient daher als Induktionsverankerung. @@ -233,7 +233,7 @@ 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. +%Dies ist die Induktionsannahme. 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 @@ -294,7 +294,8 @@ sind. \caption{Peterson-Graph mit zehn Knoten. \label{buch:figure:peterson}} \end{figure} -Der Peterson-Graph hat die Adjazenzmatrix +Der Peterson-Graph von Abbildung~\ref{buch:figure:peterson} +hat die Adjazenzmatrix \[ G = @@ -376,7 +377,7 @@ ist eine Abbildung $l\colon E\to L$. \index{Beschriftung}% \end{definition} -Einen gerichteten, beschrifteten Graphen können wir gleichwertig +Einen gerichteten, beschrifteten Graphen können wir 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. @@ -386,12 +387,12 @@ noch den Wert der Beschriftung enthalten. Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von Knoten und eine Menge von beschrifteten Kanten der Form \[ -E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $a$ nach $b$}\}. +E \{ (u,v,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $u$ nach $v$}\}. \] Die Menge $L$ enthält die möglichen Beschriftungen der Kanten. \end{definition} -Diese Definition gestattet, dass zwischen zwei Knoten $a$ und $e$ +Diese Definition gestattet, dass zwischen zwei Knoten $u$ und $v$ mehrere Kanten vorhanden sind, die sich durch die Beschriftung unterscheiden. @@ -492,13 +493,13 @@ negativ. \subsubsection{Anwendung: Netlist} Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen -ist eine eletronische Schaltung. +ist eine elektronische Schaltung. Die Knoten des Graphen sind untereinander verbundene Leiter, sie werden auch {\em nets} genannt. Die beschrifteten Kanten sind die elektronischen Bauteile, die solche -Nets miteinander verbinden. +nets miteinander verbinden. Die Inzidenzmatrix beschreibt, welche Anschlüsse eines Bauteils mit -welchen Nets verbunden werden müssen. +welchen nets verbunden werden müssen. Die Informationen in der Inzidenzmatrix werden also in einer Applikation zum Schaltungsentwurf in ganz natürlicher Weise erhoben. @@ -547,9 +548,10 @@ $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)$. +genau dann von $0$ verschieden, wenn es in $G$ eine Verbindung zwischen +den beiden Knoten gibt. +Im Produkt $B(G')B(G')^t$ summieren sie sich zu den ausserdiagonalen +Elementen von $-A(G)$. Damit ist die Formel \eqref{buch:graphen:eqn:laplace-definition} nachgewiesen. diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex index 1fb61b6..14240f4 100644 --- a/buch/chapters/70-graphen/chapter.tex +++ b/buch/chapters/70-graphen/chapter.tex @@ -22,8 +22,7 @@ Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl 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}% +Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes NP-vollständige Problem in ein Graphenproblem umformulieren lässt. \index{Komplexitätstheorie}% @@ -46,7 +45,7 @@ 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, oder im -vorliegenden Fall Zeitintervalle, die Knoten +vorliegenden Fall Zeitintervallen, die Knoten des Graphen so einzufärben, dass benachbarte Knoten niemals die gleiche Farbe haben. diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex index b718b65..9767c71 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -26,7 +26,7 @@ chromatischen Zahl und der Unabhängigkeitszahl erfasst werden. \begin{definition} Die {\em chromatische Zahl} $\operatorname{chr}G$ eines Graphen $G$ ist -die minimale Anzahl von Farben, die Einfärben der Knoten eines Graphen +die minimale Anzahl von Farben, die zum Einfärben der Knoten eines Graphen nötig sind, sodass benachbarte Knoten verschiedene Farben haben. \index{chromatische Zahl} \end{definition} @@ -158,7 +158,7 @@ $\operatorname{chr}G \le d+1$. Wir führen den Beweis mit Hilfe von vollständiger Induktion nach der Anzahl Knoten eines Graphen. 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 +daher $d=0$ und $d+1=1$ Farbe reicht auch tatsächlich zur Einfärbung des einen Knotens. Wir nehmen jetzt an, die Behauptung sei für Graphen mit $n-1$ Knoten bereits @@ -220,7 +220,7 @@ Somit ist \end{equation} 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 +er auch als \[ \overline{d}=\frac{2\cdot|E|}{|V|} \] @@ -257,7 +257,9 @@ ist der grösste Eigenwert, also genau die Grösse, auf die die Sätze~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} und \ref{buch:wahrscheinlichkeit:satz:perron-frobenius2} anwendbar sind. -Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend +Dazu muss die Matrix allerdings primitiv sein +(Definition~\ref{buch:positiv:def:primitiv} in Kapitel~\ref{buch:chapter:wahrscheinlichkeit}), +was gleichbedeutend \index{primitive Matrix}% ist damit, dass der Graph zusammenhängend ist. Im folgenden soll dies daher jeweils angenommen werden. @@ -292,8 +294,8 @@ Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist = \sum_{u\sim v} f(u). \] -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 +Die Summe der Komponenten $A(G)f$ kann man durch Multiplikation +von $A(G)f$ mit einem Zeilenvektor $U^t$ aus lauter Einsen erhalten, also \begin{equation} \begin{aligned} {\color{red} diff --git a/buch/chapters/70-graphen/waerme.tex b/buch/chapters/70-graphen/waerme.tex index bfeff74..ac49880 100644 --- a/buch/chapters/70-graphen/waerme.tex +++ b/buch/chapters/70-graphen/waerme.tex @@ -5,6 +5,7 @@ % \section{Wärmeleitung auf einem Graphen \label{buch:section:waermeleitung-auf-einem-graphen}} +\rhead{Wärmeleitung auf einem Graphen} Die Vektoren, auf denen die Laplace-Matrix operiert, können als Funktionen betrachtet werden, die jedem Knoten einen Wert zuordnen. Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung @@ -44,8 +45,6 @@ wird, codiert ebenfalls wesentliche Informationen über den Graphen. Je mehr Kanten es zwischen verschiedenen Teilen eines Graphen gibt, desto schneller findet der Wärmeaustausch zwischen diesen Teilen statt. -Die Lösungen der Wärmeleitungsgleichung liefern also Informationen -über den Graphen. \subsection{Eigenwerte und Eigenvektoren \label{buch:subsection:ein-zyklischer-graph}} @@ -165,13 +164,13 @@ s_k(l) &= \sin\frac{2\pi kl}{n} = -\Im \chi_k(l) +\Im \chi_k(l), \\ c_k(l) &= \cos\frac{2\pi kl}{n} = -\Re\chi_k(l) +\Re\chi_k(l). \end{aligned} \] Das Skalarprodukt dieser Funktionen ist @@ -189,14 +188,16 @@ e^{\frac{2\pi i}{n}(m'-m)l} = \delta_{mm'} \] -Die Funktionen bilden daher eine Orthonormalbasis des Raums der -Funktionen auf $G$. +Die Funktionen bilden daher eine Orthonormalbasis des komplexen +Vektorraums der +komplexen Funktionen auf $G$ mit dem sesquilinearen Skalarprodut. Wegen $\overline{e_m} = e_{-m}$ folgt, dass für gerade $n$ die Funktionen \[ c_0, c_1,s_1,c_2,s_2,\dots c_{\frac{n}2-1},c_{\frac{n}2-1},c_{\frac{n}2} \] -eine orthonormierte Basis. +eine orthonormierte Basis des reellen Vektorraumes der reellen Funktionen +auf $G$ mit dem gewöhnlichen Skalarprodukt. \subsection{Standardbasis und Eigenbasis \label{buch:subsection:standardbasis-und-eigenbasis}} diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index 073deab..c453eb9 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -18,7 +18,11 @@ Wenn man einen Standardbasisvektor in einem Knoten $i$ als Anfangstemperaturverteilung verwendet, erwartet man eine Lösung, die für kleine Zeiten $t$ die Energie immer in der Nähe des Knotens $i$ konzentriert hat. -Weder die Standardbasis noch die Eigenbasis haben diese Eigenschaft. +Es werden daher mit der Zeit immer stärkere benachbarte Standardbasisvektoren +in der Lösung auftreten. +Auch die Eigenbasis hilft nicht, dieses Lösungsverhalten aufzuzeigen: +sie sind im Definitionsgebiet stark delokalisiert und daher die allmählich +abnehmende Lokalisierung der Lösung nicht wiedergeben. \subsection{Vergleich mit der Wärmeleitung auf $\mathbb{R}$} Ein ähnliches Phänomen findet man bei der Wärmeausbreitung gemäss @@ -29,7 +33,7 @@ der partiellen Differentialgleichung Die von Fourier erfundene Methode, die Fourier-Theorie, verwendet die Funktionen $e^{ik x}$, die Eigenvektoren der zweiten Ableitung $\partial^2/\partial x^2$ sind. -Diese haben das gleiche Problem, der Betrag von $e^{ikx}$ ist $1$, die +Diese haben das gleiche Problem: Der Betrag von $e^{ikx}$ ist $1$, die Entfernung von einem Punkt spielt überhaupt keine Rolle. Die Funktion \[ @@ -90,7 +94,7 @@ wenigstens ablesen, dass für zunehmende Zeit die hohen Frequenzen sehr schnell gedämpft werden. Die hohen Frequenzen erzeugen also den scharfen Peak für Zeiten nahe -beim Knoten $i$, die zu kleineren $\lambda_i$ beschreiben die Ausbreitung +beim Knoten $i$, die kleineren $\lambda_i$ beschreiben die Ausbreitung über grössere Distanzen. Die Fundamentallösung interpoliert also in einem gewissen Sinne zwischen den Extremen der Standardbasis und der Eigenbasis. @@ -142,7 +146,7 @@ Es stellt sich daher die Frage, ob man für eine beliebige Menge \( T= \{ t_1,t_2,\dots\} \) -von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ zu finden +von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ finden derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus $\chi_0$ durch Dilatation entstanden vorstellen kann. @@ -174,8 +178,8 @@ die in der Umgebung eines Knotens wie die konstante Funktion aussehen. Das Mutter-Wavelet einer Wavelet-Analyse definiert, in welchem Mass sich Funktionen im Orts- und im Frequenzraum lokalisieren lassen. Die Standardbasis der Funktionen auf einem Graphen repräsentieren die -perfekte örtliche Lokalisierung, Eigenbasis der Laplace-Matrix $L$ repräsentiert -die perfekte Lokalisierung im Frequenzraum. +perfekte örtliche Lokalisierung, die Eigenbasis der Laplace-Matrix +$L$ repräsentiert die perfekte Lokalisierung im Frequenzraum. Sei $g(\lambda)\ge 0$ eine Funktion im Frequenzraum, die für $\lambda\to0$ und $\lambda\to\infty$ rasch abfällt mit einem Maximum irgendwo dazwischen (Abbildung~\ref{buch:graphs:fig:lokalisierung}). @@ -190,11 +194,13 @@ Natürlich sind vor allem die Werte auf den Eigenwerten $\lambda_0 < \lambda_1\le \dots\le \lambda_n$ der Laplace-Matrix von Interesse. -Die Matrix $g(L)$ kann mit Hilfe der Spektraltheorie berechnet werden, +Die Matrix $g(L)$ kann mit Hilfe der Spektraltheorie +von Abschnitt~\ref{buch:section:spektraltheorie} +berechnet werden, was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren der Laplace-Matrix bereits bekannt sind. Die Matrix $\chi^t$ bildet die Standardbasisvektoren in die -Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum ab, +Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum, $\chi$ vermittelt die Umkehrabbildung. Mit der Spektraltheorie findet man für die Abbildung $g(L)$ die Matrix \begin{equation} @@ -255,7 +261,7 @@ Wir erhalten daher in den Spalten von $h(L)$ Vektoren, die um die einzelnen Knoten lokalisiert sind. \subsubsection{Rekonstruktion} -Die Operatoren $h(L)$ und $g_i(L)$ erzeugen analysieren eine Funktion +Die Operatoren $h(L)$ und $g_i(L)$ analysieren eine Funktion nach den verschiedenen Frequenzen mit den Skalierungsfaktoren $a_i$, aber die Rekonstruktion ist noch nicht klar. Diese wäre einfacher, wenn die Operatoren zusammen die identische diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index c9d0d8c..c8d6379 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -71,7 +71,7 @@ mehr Gewicht als eine Seite mit vielen Links, unter denen der Link auf die Seite $j$ einer von Vielen ist. Im Beispiel-Internet der Abbildung~\ref{buch:figure:modellinternet} signalisiert die Seite $6$ mit nur einem Link auf die Seite $8$ -viel deutlicher, dass $8$ eine wichtige Seite ist, also die die +viel deutlicher, dass $8$ eine wichtige Seite ist, also dies die Seite $5$ tut, die auch noch zwei andere Links enthält. Wir können diesen Unterschied berücksichtigen, indem wir zu einem Wahrscheinlichkeitsmodell übergehen, was wir im folgenden Abschnitt @@ -91,7 +91,7 @@ einer bestimmten Seite landet. Wir bezeichnen mit $S_i$ das Ereignis, dass sich der Besucher auf der Seite mit der Nummer $i$ befindet, wobei $i=1,\dots,N$. Gesucht ist die Wahrscheinlichkeit $P(S_i)$. -Ohne weitere Information müssten wir davon ausgehen, dass jede Seite +Ohne weitere Information müssen wir davon ausgehen, dass jede Seite etwa gleich wahrscheinlich ist, dass also $P(S_i) = 1/N$. Wir wissen jedoch mehr. @@ -128,6 +128,7 @@ Falls es einen Link gibt, ist $P(S'_j\mid S_i)\ge 0$. A priori wissen wir nicht, wie wahrscheinlich es ist, dass der Besucher dem Link auf die Seite $j$ folgt, normalerweise werden nicht alle Links mit gleicher Wahrscheinlichkeit verwendet. +Darüber hben wir aber keine Detailinformation. Wir nehmen daher vereinfachend an, dass alle Links gleich wahrscheinlich sind. Enthält die Seite $i$ genau $n_i$ Links, dann ist die Wahrscheinlichkeit, @@ -142,13 +143,13 @@ Es gilt \begin{equation} P(S'_j) = -P(S'j\mid S_1) P(S_1) +P(S'_j\mid S_1) P(S_1) + -P(S'j\mid S_2) P(S_2) +P(S'_j\mid S_2) P(S_2) + \dots + -P(S'j\mid S_N) P(S_N) +P(S'_j\mid S_N) P(S_N) = \sum_{i=1}^N P(S_j'\mid S_i)P(S_i) . @@ -212,7 +213,7 @@ entlang eines Links. \begin{beispiel} Für das Beispiel-Internet von Abbildung~\ref{buch:figure:modellinternet} -ist die zugehörige Matrix +ist die zugehörige Link-Matrix \begin{equation} H = \begin{pmatrix} @@ -423,7 +424,7 @@ diskutiert wird. Natürlich ist die heutzutage verwendete Matrix mit Sicherheit komplizierter. In der vorgestellten Form unterstützt sie zum Beispiel auch das folgende -Geschäftsmodell, welches in der Anfangszeit von Google eine Zeitlang +Geschäftsmodell, welches in der Anfangszeit von Google eine Zeit lang erfolgreich war. Ein Anbieter betreibt zu diesem Zweck eine grosse Zahl von Websites, deren Seiten im Wesentlichen aus Suchbegriffen und Links untereinander @@ -457,7 +458,7 @@ Relevanz einer Seite. Wir nehmen an, dass sich diese Wahscheinlichkeit nur langsam ändert. Diese Annahme trifft nicht zu für neue Nachrichten, die durchaus eine -hohe Relevanz haben, für es aber noch nicht viele Links geben kann, +hohe Relevanz haben, für die es aber noch nicht viele Links geben kann, die die Relevanz in der Google-Matrix erkennbar machen. Die Annahme bedeutet, dass sich die Verteilung $p$ sehr viel langsamer ändert als der Navigationsprozess entlang der Links erfolgt. @@ -516,7 +517,7 @@ p Der Vektor $p_0$ ist ein Einheitsvektor in der euklidischen Norm. Er kann daher nicht eine Wahrscheinlichkeitsverteilung sein, da sich die Elemente nicht zu $1$ summieren. -Die $L^1$-Norm $\|\;\cdot\;\|_1$ eines Vektors ist die Summe der Beträge aller +Die $l^1$-Norm $\|\;\cdot\;\|_1$ eines Vektors ist die Summe der Beträge aller Elemente eines Vektors. Indem man $p_0$ durch die Summe aller Einträge von $p_0$ teilt, erhält man die Wahrscheinlichkeitsverteilung $p$. @@ -580,9 +581,9 @@ Numerische Ungenauigkeiten können bewirken, dass die Iteration mit der Matrix $A/\lambda_1$ trotzdem nicht konvergiert. Man kann dies komponsieren, indem man nach jeder Iteration normiert. Da der gesuchte Eigenvektor eine Wahrscheinlichkeitsverteilung sein muss, -muss die $L^1$-Norm $1$ sein. -Statt mit der euklidischen $L^2$-Norm zu normieren, normiert man daher -besser mit der $L^1$-Norm. +muss die $l^1$-Norm $1$ sein. +Statt mit der euklidischen $l^2$-Norm zu normieren, normiert man daher +besser mit der $l^1$-Norm. Damit ergibt sich das folgende Verfahren zur Bestimmung der Pagerank-Verteilung $p$ für die Google-Matrix. diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg Binary files differindex b79b07b..565ae99 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf Binary files differindex ac4c0ff..46207a5 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png Binary files differindex f4c6294..46e6895 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png diff --git a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf Binary files differindex 0cca2e1..fb8a6bc 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf +++ b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf Binary files differindex d534c8f..457a650 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex index c2fab2e..3cf2f2f 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex @@ -14,6 +14,8 @@ \def\skala{1} \begin{tikzpicture}[>=latex,thick,scale=\skala] +\definecolor{darkgreen}{rgb}{0,0.6,0} + \def\punkt#1#2#3{ \fill[color=white] #1 circle[radius=0.10]; \fill[color=#2] #1 circle[radius=0.13]; @@ -68,6 +70,11 @@ } } +\fill[color=darkgreen!20] + (-0.5,{-4.2*\ys}) rectangle ({5*\xs+0.5},{-0.8*\ys}); +\fill[color=blue!20] + (-0.5,{-8.2*\ys}) rectangle ({5*\xs+0.5},{-4.8*\ys}); + \begin{scope} \clip (-0.5,{-8.5*\ys}) rectangle ({5*\xs+0.5},-0.5); \fan{-1}{gray} diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg Binary files differindex 53544cb..aaa5f80 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf Binary files differindex 39aa3cd..7a17ed1 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.png b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png Binary files differindex a2bd9bf..2ea451d 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/positiv.png +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 6dad883..226c3d3 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -23,17 +23,17 @@ Ein stochastischer Prozess ist eine Familie von Zufallsvariablen \index{Zufallsvariable}% $X_t$ mit Werten in einer Menge $\mathcal{S}$ von Zuständen. Der Parameter $t$ wird üblicherweise als die Zeit interpretiert, -er kann beliebige reelle Werte oder diskrete Werte annahmen, im letzten +er kann beliebige reelle oder diskrete Werte annehmen, im letzten Fall spricht man von einem Prozess mit diskreter Zeit. Das Ereignis $\{X_t=x\}$ wird gelesen als ``zur Zeit $t$ befindet sich der Prozess im Zustand $x$''. Mit $P(X_t = x)$ wir die Wahrscheinlichkeit bezeichnet, dass sich der Prozess zur Zeit $t$ im Zustand $x$ befindet. -Die Funktion $t\mapsto X_t$ beschreiben also den zeitlichen Ablauf +Die Funktion $t\mapsto X_t$ beschreibt also den zeitlichen Ablauf der vom Prozess durchlaufenen Zustände. Dies ermöglicht, Fragen nach dem Einfluss früherer Zustände, -also des Eintretens eines Ereignisses $\{X_{t_0}=x\}$ auf das Eintreten eines +also des Eintretens eines Ereignisses $\{X_{t_0}=x\}$, auf das Eintreten eines Zustands $s\in\mathcal{S}$ zu einem späteren Zeitpunkt $t_1>t_0$ zu studieren. Das Ereignis $\{X_t = x\}$ kann man sich als abhängig von der Vorgeschichte @@ -41,17 +41,17 @@ vorstellen. \index{Vorgeschichte}% Die Vorgeschichte besteht dabei aus dem Eintreten gewisser Ereignisse \[ -\{X_0=x_0\}, -\{X_1=x_1\}, -\{X_2=x_2\}, -\dots, +\{X_0=x_0\},\; +\{X_1=x_1\},\; +\{X_2=x_2\},\; +\dots,\; \{X_n=x_n\} \] zu früheren Zeiten $t_0<t_1<\dots<t_n<t$. Die bedingte Wahrscheinlichkeit \begin{equation} P(X_t = x \mid -X_{t_n}=x_n\wedge X_{t_{n-1}}=x_{n-1}\wedge\dots\wedge X_{t_1}=x_1\wedge +X_{t_n}=x_n\wedge X_{t_{n-1}}=x_{n-1}\wedge\ldots\wedge X_{t_1}=x_1\wedge X_{t_0}=x_0) \label{buch:wahrscheinlichkeit:eqn:historybedingt} \end{equation} @@ -62,7 +62,7 @@ die Zustände $x_0,x_1,\dots,x_n$ durchlaufen hat. \subsubsection{Gedächtnislosigkeit} \index{Markov-Eigenschaft}% In vielen Fällen ist nur der letzte durchlaufene Zustand wichtig. -Die Zustände in den Zeitpunkten $t_0<\dots<t_{n-1}$ haben dann keinen +Die Zustände zu den Zeitpunkten $t_0<\dots<t_{n-1}$ haben dann keinen Einfluss auf die Wahrscheinlichkeit. Auf die bedingte Wahrscheinlichkeit~\eqref{buch:wahrscheinlichkeit:eqn:historybedingt} @@ -170,7 +170,7 @@ p_{x_1x_0}(t_1,s) \prod_{i=0}^{n} p_{x_{i+1}x_i}(t_{i+1}t_i) \] -heisst die {\em Pfadwahrscheinlichkeit} für genannten Pfad. +heisst die {\em Pfadwahrscheinlichkeit} für den genannten Pfad. \index{Pfadwahrscheinlichkeit}% \end{definition} @@ -256,7 +256,7 @@ Die Summe der Elemente einer Spalte \begin{beispiel} Die Permutationsmatrix einer Permutation $\sigma\in S_n$ -(Abschnitt~\label{buch:section:permutationsmatrizen}) +(Abschnitt~\ref{buch:section:permutationsmatrizen}) \index{Permutationsmatrix}% ist eine Matrix mit Einträgen $0$ und $1$, so dass die erste Bedingung erfüllt ist. @@ -329,8 +329,8 @@ Die Summe aller Zeilen von $T-I$ ist also $0$, die Matrix $T-I$ ist singulär. Dass $T-I$ singulär ist, garantiert aber noch nicht, -dass alle Einträge in einem zum Eigenwert $1$ -Eigenvektor auch tatsächlich nichtnegativ gewählt werden können. +dass alle Einträge in einem Eigenvektor zum Eigenwert $1$ +auch tatsächlich nichtnegativ gewählt werden können. Die Perron-Frobienus-Theorie von \index{Perron-Frobenius-Theorie}% Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} @@ -405,16 +405,17 @@ Eine eindeutige stationäre Verteilung können wir also nur erwarten, wenn alle Zustände miteinander kommunizieren. \begin{definition} -Eine homogene Markov-Kette heisst {\em irreduzibel}, alle Zustände miteinander -kommunizieren. +Eine homogene Markov-Kette heisst {\em irreduzibel}, +wenn alle Zustände miteinander kommunizieren. \index{irreduzible Markov-Kette} \end{definition} \begin{figure} \centering \includegraphics{chapters/80-wahrscheinlichkeit/images/markov2.pdf} -\caption{Diese Markov-Kette zerfällt in verschiedene irreduzible -Markov-Ketten, dere Zustandsmengen nicht miteinander kommunizieren. +\caption{Diese Markov-Kette zerfällt in zwei verschiedene irreduzible +Markov-Ketten (blau und grün hinterlegt), +deren Zustandsmengen nicht miteinander kommunizieren. Solche Markov-Ketten können unabhängig voneinander studiert werden. \label{buch:wahrscheinlichkeit:fig:markovzerfall}} \end{figure} @@ -580,7 +581,7 @@ Die konstante Verteilung $\frac13U$ ist offensichtlich eine stationäre Verteilung. In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} wird gezeigt, dass es die einzige ist. -Sei jetzt $p(0)$ eine beliebiger Vektor in $\mathbb{R}^3$ mit +Sei jetzt $p(0)$ ein beliebiger Vektor in $\mathbb{R}^3$ mit nichtnegativen Einträgen, die sich zu $1$ summieren. Dann bilden die Vektoren $p(n)=T^np(0)$ einen Dreierzyklus \begin{align*} @@ -718,7 +719,7 @@ heisst {\em absorbierend}, wenn $T_{ii}=1$ ist. Eine Markov-Kette mit mindestens einem absorbierenden Zustand heisst {\em absorbierende Markov-Kette}. \index{absorbierende Markov-Kette}% -Nicht absorbierende Zustände heissen {\em transient} +Nicht absorbierende Zustände heissen {\em transient}. \index{transienter Zustand}% \end{definition} @@ -827,7 +828,7 @@ B_{k}=\begin{cases} 0&\qquad\text{sonst,} \end{cases} \] -die genau dann $1$ ist, wenn der Prozess ausgehend von $j$ im Zustand +die genau dann $1$ ist, wenn der Prozess ausgehend vom Zustand $j$ beim $k$-ten Schritt den Zustand $i$ besucht. Die Zufallsvariable der Anzahl $B$ der Besuche des Zustands $i$ ist die Summe der $B_k$. @@ -836,7 +837,7 @@ jetzt als Erwartungswert ausdrücken lässt, es ist $P(X_k=i \mid X_0=j) = E(B_k)$. Damit lässt sich jetzt die Fundamentalmatrix auf andere Art interpretieren. -Der Eintrag $N_{i\!j}$ ist +Der Eintrag $F_{i\!j}$ ist \begin{align*} F_{i\!j} &= @@ -855,7 +856,7 @@ P(X_2=i\mid X_0=j) &=E(B_0+B_1+B_2+\dots) =E(B). \end{align*} -Die Summe der $B_k$ ist aber die erwartete Anzahl der Besuch im Zustand $i$. +Die Summe der $B_k$ ist die erwartete Anzahl der Besuch im Zustand $i$. \begin{satz} \label{buch:markov:satz:anzahlbesuche} @@ -866,9 +867,12 @@ Element $F_{i\!j}$ der Fundamentalmatrix $F=(I-Q)^{-1}$. \subsubsection{Absorptionszeit} \index{Absorptionszeit}% +\begin{frage} Wie lange dauert es im Mittel, bis der Prozess ausgehend vom Zustand $j$ in einem Absorbptionszustand $i$ stecken bleibt? -Sie ist gleich gross wie die Zeit, während der der Prozess nicht absorbierende +\end{frage} +Die Absorptionszeit ist gleich gross wie die Zeit, +während der der Prozess nicht absorbierende Zustände besucht. Die Zeit $t_j$, bis der Prozess in einen absorbierenden Zustand wechselt, ist also die erwartete Anzahl Besuche nicht absorbierender Zustände. @@ -878,7 +882,7 @@ t_j = \sum_{\text{$i$ nicht absorbierend}} E(\text{Anzahl Besuche von $i$}\mid X_0=j) = -\sum_{\text{$i$ nicht absorbierend}} F_{i\!j}. +\sum_{i} F_{i\!j}. \] $t_j$ ist also die Summe der Elemente der Spalte $j$ der Fundamentalmatrix $F$. Man kann diese Summe auch vektoriell schreiben mit einem Zeilenvektor $U^t$ @@ -897,10 +901,12 @@ Einträge in Spalte $j$ der Fundamentalmatrix $F$. \subsubsection{Absorptionswahrscheinlichkeit} \index{Absorptionswahrscheinlichkeit}% +\begin{frage} Wie gross ist die Wahrscheinlichkeit, dass der Prozess ausgehend von Zustand $j$ irgendwann im Zustand $i$ absorbiert wird? +\end{frage} Die Potenzen $T^k$ der Übergangsmatrix enthalten in Zeile $j$ -und Spalte $i$ die Wahrscheinlichkeit, dass nach spätestens $k$ Schritten +und Spalte $i$ die Wahrscheinlichkeit, dass dies nach spätestens $k$ Schritten geschehen ist. Wir müssen daher den Grenzwert \( @@ -925,9 +931,11 @@ die Wahrscheinlichkeit, dass der Prozess ausgehend vom Zustand $j$ irgendwann im Zustand $i$ absorbiert wird. \subsubsection{Absorption über den letzten Zustand $l$} +\begin{frage} Wie gross ist die Wahrscheinlichkeit, dass die von $j$ ausgehende Absorption in den Zustand $i$ als letzten Zustand vor der Absorption den Zustand $l$ hat? +\end{frage} Wir schreiben $l\overset{\smash{k}}{\twoheadrightarrow} i$ für das Ereignis, dass der Prozess im $k$-ten Schritt über den letzten Zustand $l$ in den Absorbtionszustand $i$ übergeht. @@ -970,8 +978,11 @@ geschrieben werden. \subsubsection{Wartezeit für eine beliebige Markov-Kette} \index{Wartezeit}% -Die mittlere Wartezeit bis zum Erreichen eines Zustands in einer -beliebigen Markov-Kette kann mit der +\begin{frage} +Wie gross ist die mittlere Wartezeit, bis eine beliebige Markov-Kette +einen bestimmten Zustand erreicht? +\end{frage} +Auch diese mittlere Wartezeit kann mit der Theorie zur Berechnung der Absorptionszeit berechnet werden. Dazu modifiziert man den Prozess dahingehend, dass der Zielzustand ein absorbierender Zustand wird. diff --git a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex index f27da0b..105e7ab 100644 --- a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex +++ b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex @@ -5,7 +5,6 @@ % \section{Das Paradoxon von Parrondo \label{buch:section:paradoxon-von-parrondo}} -\rhead{Das Paradoxon von Parrondo} Das Paradoxon von Parrondo ist ein der Intuition widersprechendes Beispiel für eine Kombination von Spielen mit negativer Gewinnerwartung, deren Kombination zu einem Spiel mit positiver Gewinnerwartung führt. @@ -18,6 +17,8 @@ eine sehr einfache Analyse. \subsection{Die beiden Teilspiele \label{buch:subsection:teilspiele}} +\rhead{Das Paradoxon von Parrondo} + \subsubsection{Das Spiel $A$} Das Spiel $A$ besteht darin, eine Münze zu werfen. Je nach Ausgang gewinnt oder verliert der Spieler eine Einheit. @@ -69,8 +70,9 @@ Dreierreste des Kapitals. \end{figure}% Für den Verlauf des Spiels spielt nur der Dreierrest des Kapitals eine Rolle. -Es gibt daher drei mögliche Zustände $0$, $1$ und $2$. -In einem Spielzug finde ein Übergang in einen anderen Zustand +Es gibt daher drei mögliche Zustände $0$, $1$ und $2$ +(Abbildung~\ref{buch:wahrscheinlichkeit:fig:spielB}). +In einem Spielzug findet ein Übergang in einen anderen Zustand statt, der Eintrag $b_{ij}$ ist die Wahrscheinlichkeit \[ b_{ij} @@ -188,7 +190,7 @@ E(Y\mid K\equiv 2) \end{pmatrix} = U^t -G\odot B. +(G\odot B). \] Die Gewinnerwartung ist dann das Produkt \[ @@ -369,7 +371,7 @@ P(Y=+1\mid K\equiv 2) \cdot P(K\equiv 2) \frac{13}{26} = \frac12 -\\ +\\[8pt] P(Y=-1) &= P(Y=-1\mid K\equiv 0) \cdot P(K\equiv 0) diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index 159d6d3..4e57fe0 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -29,16 +29,16 @@ erklärt. \label{buch:subsection:elementare-eigenschaften}} In diesem Abschnitt betrachten wir ausschliesslich reelle Vektoren und Matrizen. -Die Komponenten sind somit immer mit miteinander vergleichbar, daraus +Die Komponenten sind somit immer miteinander vergleichbar, daraus lässt sich auch eine Vergleichsrelation zwischen Vektoren ableiten. \begin{definition} Ein Vektor $v\in\mathbb{R}^n$ heisst {\em positiv}, geschrieben -$v>0$, wenn alle seine Komponenten positiv sind: $v_i>0\forall i$. +$v>0$, wenn alle seine Komponenten positiv sind: $v_i>0\,\forall i$. Ein Vektor $v\in\mathbb{R}^n$ heisst {\em nichtnegativ}, in Formeln $v\ge 0$, wenn alle -seine Komponenten nicht negativ sind: $v_i\ge 0\forall i$. +seine Komponenten nicht negativ sind: $v_i\ge 0\,\forall i$. \index{positiver Vektor}% \index{nichtnegativer Vektor}% \end{definition} @@ -67,9 +67,9 @@ Die Definition funktionieren analog auch für Matrizen: \begin{definition} Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em positiv}, -wenn alle ihre Einträge $a_{i\!j}$ positiv sind: $a_{i\!j}>0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ positiv sind: $a_{i\!j}>0\,\forall i,j$. Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em nichtnegativ}, -wenn alle ihre Einträge $a_{i\!j}$ nichtnegativ sind: $a_{i\!j}\ge 0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ nichtnegativ sind: $a_{i\!j}\ge 0\,\forall i,j$. \index{positive Matrix}% \index{nichtnegative Matrix}% Man schreibt $A>B$ bzw.~$A\ge B$ wenn $A-B>0$ bzw.~$A-B\ge 0$. @@ -132,7 +132,7 @@ und dass daher für alle $n\ge 5$ die Matrix $A^n$ positiv ist. Die Eigenschaft der Matrix $A$ von \eqref{buch:wahrscheinlichkeit:eqn:diffusion}, dass $A^n>0$ -für genügend grosses $n$ ist bei Permutationsmatrizen nicht +für genügend grosses $n$ ist, ist bei Permutationsmatrizen nicht vorhanden. Die Zyklen-Zerlegung einer Permutationsmatrix zeigt, welche Unterräume von $\mathbb{R}^n$ die iterierten Bilder eines @@ -144,14 +144,16 @@ Unterräumen statt. \begin{beispiel} Die Matrix \begin{equation} -A=\begin{pmatrix} +A=\left(\begin{array}{ccc|ccc} 0.9&0.1& & & & \\ 0.1&0.8&0.1& & & \\ &0.1&0.9& & & \\ +\hline & & &0.9&0.1& \\ & & &0.1&0.8&0.1\\ & & & &0.1&0.9 -\end{pmatrix} +\end{array} +\right) \label{buch:wahrscheinlichkeit:eqn:diffusionbloecke} \end{equation} besteht aus zwei $3\times 3$-Blöcken. @@ -164,6 +166,7 @@ Teilmatrizen, aber die Matrix $A^n$ ist für alle $n$ nicht positiv. \end{beispiel} \begin{definition} +\label{buch:positiv:def:primitiv} Eine nichtnegative Matrix mit der Eigenschaft, dass $A^n>0$ für ein genügend grosses $n$, heisst {\em primitiv}. \index{primitive Matrix}% @@ -323,6 +326,7 @@ gleiche Richtung haben (rot). Hier dargestellt am Beispiel von Zahlen in der komplexen Zahlenebene. In dieser Form wird die verallgemeinerte Dreiecksungleichung in Satz~\ref{buch:wahrscheinlichkeit:satz:verallgdreieckC} +angewendet. \label{buch:wahrscheinlichkeit:fig:dreieck}} \end{figure} @@ -344,7 +348,7 @@ gewöhnliche Dreiecksungleichung. Wir nehmen daher jetzt an, die Aussage sei für $n$ bereits bewiesen, wir müssen sie für $n+1$ beweisen. -Die Summe von $n+1$ Vektoren kann man $u=u_1+\dots+u_n$ und $v=u_{n+1}$ +Die Summe von $n+1$ Vektoren kann man in $u=u_1+\dots+u_n$ und $v=u_{n+1}$ aufteilen. Es gilt nach der gewöhnlichen Dreiecksungleichung, dass \[ @@ -465,8 +469,8 @@ Das ist nur möglich, wenn $\lambda > 0$. Wenn $v$ ein Eigenvektor von $A$ ist, dann ist auch jedes Vielfache davon ein Eigenvektor, insbesondere können einzelne Komponenten des Vektors $v$ auch negativ sein. -Der folgende Satz zeigt aber, dass man der Vektor aus den Beträgen -von der Komponenten von $v$ ebenfalls ein Eigenvektor zum +Der folgende Satz zeigt aber, dass der Vektor aus den Beträgen +der Komponenten von $v$ ebenfalls ein Eigenvektor zum gleichen Eigenwert ist. Insbesondere gibt es immer einen nichtnegativen Eigenvektor. diff --git a/buch/chapters/90-crypto/elliptisch.tex b/buch/chapters/90-crypto/elliptisch.tex index ed264d3..99ed4cd 100644 --- a/buch/chapters/90-crypto/elliptisch.tex +++ b/buch/chapters/90-crypto/elliptisch.tex @@ -6,6 +6,7 @@ \section{Elliptische Kurven \label{buch:section:elliptische-kurven}} \index{elliptische Kurve}% +\rhead{Elliptische Kurven} Das Diffie-Hellman-Verfahren basiert auf der Schwierigkeit, in einem Körper $\mathbb{F}_p$ die Gleichung $a^x=b$ nach $x$ aufzulösen. Die Addition in $\mathbb{F}_p$ wird dazu nicht benötigt. diff --git a/buch/chapters/95-homologie/fixpunkte.tex b/buch/chapters/95-homologie/fixpunkte.tex index 1b86797..de9dff5 100644 --- a/buch/chapters/95-homologie/fixpunkte.tex +++ b/buch/chapters/95-homologie/fixpunkte.tex @@ -5,7 +5,6 @@ % \section{Fixpunkte \label{buch:section:fixpunkte}} -\rhead{Fixpunkte} Zu jeder Abbildung $f\colon X\to X$ eines topologischen Raumes in sich selbst gehört die zugehörige lineare Abbildung $f_*\colon H_*(X)\to H_*(X)$ der Homologiegruppen. @@ -24,6 +23,8 @@ analysieren. %\begin{satz}[Brower] %\end{satz} +\rhead{Fixpunkte} + %\subsection{Lefshetz-Fixpunktsatz %\label{buch:subsection:lefshetz}} Eine Selbstabbildung $f_*\colon C_*\to C_*$ von Kettenkomplexen führt auf |