diff options
author | JODBaer <JODBaer@github.com> | 2021-08-02 16:46:59 +0200 |
---|---|---|
committer | JODBaer <JODBaer@github.com> | 2021-08-02 16:46:59 +0200 |
commit | 9f22156ea159efa4f688f4d476c57bab9cfe4531 (patch) | |
tree | f0bb1fc0c7bfa0887bba2e34e2668e85c1c48959 | |
parent | save (diff) | |
parent | Merge pull request #60 from Kuehnee/master (diff) | |
download | SeminarMatrizen-9f22156ea159efa4f688f4d476c57bab9cfe4531.tar.gz SeminarMatrizen-9f22156ea159efa4f688f4d476c57bab9cfe4531.zip |
Merge remote-tracking branch 'upstream/master' into Baer
-rw-r--r-- | buch/papers/clifford/6_PauliMatrizen.tex | 2 | ||||
-rw-r--r-- | buch/papers/clifford/7_Reflektion.tex | 62 | ||||
-rw-r--r-- | buch/papers/clifford/8_Rotation.tex | 109 | ||||
-rw-r--r-- | buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png | bin | 0 -> 1179631 bytes | |||
-rw-r--r-- | buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png | bin | 0 -> 117508 bytes | |||
-rw-r--r-- | buch/papers/munkres/figures/ganzzahlige_punkte.png | bin | 0 -> 257390 bytes | |||
-rw-r--r-- | buch/papers/munkres/teil1.tex | 25 | ||||
-rw-r--r-- | buch/papers/munkres/teil2.tex | 4 | ||||
-rw-r--r-- | buch/papers/munkres/teil3.tex | 82 | ||||
-rw-r--r-- | buch/papers/punktgruppen/crystals.tex | 84 | ||||
-rw-r--r-- | buch/papers/punktgruppen/figures/projections.pdf | bin | 26440 -> 27957 bytes | |||
-rw-r--r-- | buch/papers/punktgruppen/intro.tex | 8 | ||||
-rw-r--r-- | buch/papers/punktgruppen/main.tex | 1 | ||||
-rw-r--r-- | buch/papers/punktgruppen/piezo.tex | 62 | ||||
-rw-r--r-- | buch/papers/punktgruppen/references.bib | 14 | ||||
-rw-r--r-- | buch/papers/punktgruppen/symmetry.tex | 28 | ||||
-rw-r--r-- | buch/papers/punktgruppen/tikz/projections.tex | 2 |
17 files changed, 309 insertions, 174 deletions
diff --git a/buch/papers/clifford/6_PauliMatrizen.tex b/buch/papers/clifford/6_PauliMatrizen.tex index e41275a..4438aeb 100644 --- a/buch/papers/clifford/6_PauliMatrizen.tex +++ b/buch/papers/clifford/6_PauliMatrizen.tex @@ -91,7 +91,7 @@ bestätigt. Man kann bei den Definitionen \ref{def:defPauli} und \ref{def:defPau \begin{hilfssatz} Ein beliebiger Multivektor \begin{align} \label{MultiVektorAllg} - M = a_0\mathbf{e}_0 + a_1\mathbf{e}_1 + a_2\mathbf{e}_3 + a_{12}\mathbf{e}_{12} + a_{23}\mathbf{e}_{23} + a_{31}\mathbf{e}_{31} + a_{123}\mathbf{e}_{123}\\ + M = a_0\mathbf{e}_0 + a_1\mathbf{e}_1 + a_2\mathbf{e}_3 + a_{12}\mathbf{e}_{12} + a_{23}\mathbf{e}_{23} + a_{31}\mathbf{e}_{31} + a_{123}\mathbf{e}_{123} \end{align} erhält durch das einsetzten der Formel Matrizen \eqref{Pauli} und \eqref{Pauli2} die Form \begin{align} diff --git a/buch/papers/clifford/7_Reflektion.tex b/buch/papers/clifford/7_Reflektion.tex index bdfb4e8..549848c 100644 --- a/buch/papers/clifford/7_Reflektion.tex +++ b/buch/papers/clifford/7_Reflektion.tex @@ -6,15 +6,15 @@ \section{Spiegelung} \rhead{Spiegelung} -Die Spiegelung ist eine grundlegende, geometrische Operation, aus welcher man weitere, wie beispielsweise die später beschriebene Rotation, ableiten kann. Da die geometrische Algebra für geometrische Anwendungen ausgelegt ist, sollte die Spiegelung auch eine einfache, praktische Formulierung besitzen. +Die Spiegelung ist eine grundlegende, geometrische Operation, aus welcher man weitere Operationen, wie beispielsweise die später beschriebene Rotation, ableiten kann. Da die geometrische Algebra für geometrische Anwendungen ausgelegt ist, sollte die Spiegelung auch eine einfache, praktische Formulierung besitzen. \begin{figure} \centering \begin{tikzpicture} \draw[thin,gray!40] (-3,-1) grid (3,3); \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; \draw[<->] (0,-1)--(0,3) node[above]{$a_2$}; + \draw[blue, line width=1.0pt] (0,3)--(0,-1) node[anchor=south east]{$\sigma_u$}; \draw[line width=2pt,black,-stealth](0,0)--(2,2) node[anchor=south east]{$\boldsymbol{v}$}; - \draw[line width=1.5pt,blue,-stealth](0,0)--(0,2.5) node[anchor=south east]{$\boldsymbol{u}$}; \draw[line width=2pt,black,-stealth](0,0)--(-2,2) node[anchor=south east]{$\boldsymbol{v'}$}; \draw[line width=1.5pt,gray,-stealth](0,0)--(1,0) node[anchor=north]{$\boldsymbol{e_1}$}; \draw[line width=1.5pt,gray,-stealth](0,0)--(0,1) node[anchor=north east]{$\boldsymbol{e_2}$}; @@ -22,62 +22,74 @@ Die Spiegelung ist eine grundlegende, geometrische Operation, aus welcher man we 0.25cm]{$\boldsymbol{v_{\perp u}}$}; \draw[line width=1.5pt,red,-stealth](-2,2)--(0,2) node[xshift=-1cm, yshift= 0.25cm]{$\boldsymbol{v_{\perp u}}$}; - \draw[line width=1.5pt,purple,-stealth](0,1.5)--(1,1.5) node[xshift=-0.5cm, yshift=-0.25cm]{$\boldsymbol{\hat{n}}$}; + \draw[line width=1.5pt,blue,-stealth](0,0.05)--(1,0.05) node[xshift=-0.5cm, yshift=-0.25cm]{$\boldsymbol{\hat{u}}$}; \end{tikzpicture} - \caption{Spiegelung des Vektors \textbf{v} an Spiegelachse bzw. Vektor \textbf{u}} + \caption{Spiegelung des Vektors $\mathbf{v}$ an der Spiegelebene $\sigma_u$ mit dem Normalenvektor $\mathbf{\hat{u}}$} \label{BildSpiegelung} \end{figure} \subsection{Linearen Algebra} Aus der linearen Algebra ist bekannt, dass man eine Spiegelung an einer Ebene wie folgt beschreiben kann. \begin{definition} - Die Spiegelungsgleichung in der linearen Algebra mit dem Normalenvektor $\mathbf{\hat{n}}$ zur Spiegelebene ist + Die Abbildung der Spiegelung in der linearen Algebra mit dem Normalenvektor $\mathbf{\hat{u}}$ zur Spiegelebene ist \begin{equation} \label{RefLinAlg} - \mathbf{v^{'}} = \mathbf{v} - 2 \cdot \mathbf{v_{\parallel \hat{n}}} = \mathbf{v} - 2 \cdot \mathbf{v_{\perp u}}. + \mathbf{v} = \mathbf{v_{\perp u}} + \mathbf{v_{\parallel u}} \enspace\mapsto\enspace \mathbf{v'} = \mathbf{v_{\perp u}} - \mathbf{v_{\parallel u}} = \mathbf{v} - 2 \cdot \mathbf{v_{\parallel u}}. \end{equation} - Per Definition sind $\mathbf{v_{\parallel \hat{n}}} = \mathbf{v_{\perp u}}$. In der geometrischen Algebra verwenden wir aber in den Formeln Vektoren, welche Spiegelachsen, nicht Spiegelebenen, repräsentieren. \end{definition} -Es scheint für diese Formel aber umständlich zu sein, weitere Spiegelungen mit weiteren Spiegelebenen anzufügen. Man kann diese Abbildung aber auch als Matrix schreiben. Sei $\mathbf{\hat{n}}$ ein Normalenvektor auf die Spiegelungs-Achse bzw. -Ebene, also $\mathbf{\hat{n}}\perp \mathbf{u}$, und sei ausserdem normiert $|\mathbf{\hat{n}}| = 1$, dann kann man die Spiegelung durch die Matrix +Es scheint für diese Formel \eqref{RefLinAlg} aber umständlich zu sein, weitere Spiegelungen mit weiteren Spiegelebenen anzufügen. Weil man $\mathbf{v_{\parallel u}}$ auch als Skalarprodukt $\mathbf{v_{\parallel u}} = \mathbf{\hat{u}} \cdot \mathbf{v}$ schreiben kann, ist es leicht diese Abbildung auch als Matrix darzustellen. Sei $\mathbf{\hat{u}}$ ein Normalenvektor auf die Spiegelungsebene, also $\mathbf{\hat{u}}\perp \sigma_u$, und sei ausserdem normiert $|\mathbf{\hat{u}}| = 1$, dann kann man die Spiegelung durch die Matrix \begin{align} - S = E - 2\dfrac{1}{|\mathbf{n}|^2}\mathbf{nn}^t + S = E - 2\mathbf{\hat{u}\hat{u}}^t \end{align} beschrieben werden. In der zweiten und dritten Dimension ergibt die Berechnung \begin{align} \label{Spiegelmatrizen} S_2 = \begin{pmatrix} - 1-2n_1^2 & -2n_1n_2 \\ - -2n_1n_2 & 1-2n_2^2 - \end{pmatrix} \quad + 1-2u_1^2 & -2u_1u_2 \\ + -2u_1u_2 & 1-2u_2^2 + \end{pmatrix}\enspace\text{und}\enspace S_3 = \begin{pmatrix} - 1-2n_1^2 & -2n_1n_2 & -2n_1n_3\\ - -2n_1n_2 & 1-2n_2^2 & -2n_2n_3\\ - -2n_1n_3 & -2n_2n_3 & 1-2n_3^2\\ + 1-2u_1^2 & -2u_1u_2 & -2u_1u_3\\ + -2u_1u_2 & 1-2u_2^2 & -2u_2u_3\\ + -2u_1u_3 & -2u_2u_3 & 1-2u_3^2\\ \end{pmatrix}. \end{align} -Diese Spiegelmatrizen gehören der orthogonalen Matrizengruppe $S\in \text{O}(n)$ an. Die Matrizengruppe $\text{O}(n)$ haben die Eigenschaft $S^t S = E$, was bedeutet, dass die Länge und Winkel bei der Abbildung beibehalten bleiben. Zusätzlich sind die Spiegelmatrizen symmetrisch, es gilt $S^t = S$. Somit liefert zweimal dieselbe Spiegelung wieder die identische Abbildung, wie man aus +Diese Spiegelmatrizen gehören der orthogonalen Matrizengruppe $S_n\in \text{O}(n)$ an. Die Matrizengruppe $\text{O}(n)$ haben die Eigenschaft $S_n^t S_n = E$, was bedeutet, dass die Länge und Winkel bei der Abbildung beibehalten bleiben. Zusätzlich sind die Spiegelmatrizen symmetrisch, es gilt $S_n^t = S_n$. Somit liefert zweimal dieselbe Spiegelung wieder die identische Abbildung, wie man aus \begin{align} - S^t S = S^2 = E + S_n^t S_n = S_n^2 = E \end{align} schliessen kann. \subsection{Geometrische Algebra} -Um die folgenden Formeln zu verstehen, definieren wir zuerst die Inverse eines Vektors, welche in dieser Form nicht in der linearen Algebra nicht existiert. +Wir definieren zuerst die Inverse eines Vektors, welche in dieser Form nicht in der linearen Algebra nicht existiert. \begin{definition} Die Inverse eines Vektors wird definiert als - \begin{align} - \mathbf{u}^{-1} = \dfrac{\mathbf{u}}{|\mathbf{u}|^2} \Rightarrow \mathbf{uu}^{-1} = \dfrac{\mathbf{u}^2}{|\mathbf{u}|^2} = 1. + \begin{align} \label{InverseGA} + \mathbf{u}^{-1} = \dfrac{\mathbf{u}}{|\mathbf{u}|^2}. \end{align} - Wie schon aus anderen algebraischen Strukturen bekannt, ergibt ein Element, hier $\mathbf{u}$, multipliziert mit dessen Inversen, hier $\mathbf{u}^{-1}$, das neutrale Element der Struktur, hier 1. \end{definition} +Diese Definition ist sinnvoll, da wegen $\mathbf{u}^2 = |\mathbf{u}|^2$ folgt +\begin{align} + \mathbf{uu}^{-1} = \mathbf{u} \frac{\mathbf{u}}{|\mathbf{u}|^2} = \frac{\mathbf{u}^2}{|\mathbf{u}|^2} = \frac{|\mathbf{u}|^2}{|\mathbf{u}|^2} = 1. +\end{align} +Der Vektor $\mathbf{u}^{-1}$ in \eqref{InverseGA} ist also tatsächlich das inverse Element im Sinne des Produktes in der geometrischen Algebra. Die geometrische Algebra leitet aus der obigen Formel \eqref{RefLinAlg} für eine Spiegelung eine einfache und intuitive Form her, welche auch für weitere Operationen erweitert werden kann. \begin{definition} - Die Spiegelungsgleichung in der geometrischen Algebra mit der Spiegelachse $\mathbf{u}$ ist definiert als + Die Abbildung der Spiegelung in der geometrischen Algebra mit dem senkrechten Vektor $\mathbf{u}$ zur Spiegelungsebene $\sigma_u$ ist \begin{align}\label{RefGA} - \mathbf{v}' = \mathbf{uvu}^{-1} + \mathbf{v} \enspace\mapsto\enspace \mathbf{v}' = -\mathbf{uvu}^{-1} \end{align} \end{definition} +Diese Abbildung muss stimmen, weil man durch die Schlussfolgerungen \eqref{uperpv} und \eqref{uparallelv} die Zusammenhänge +\begin{align} + \mathbf{uv_{\perp u}} = -\mathbf{v_{\perp u}u} \enspace\text{und}\enspace \mathbf{uv_{\parallel u}}=\mathbf{v_{\parallel u}u} +\end{align} +der geometrischen Produkte findet und somit die Abbildung aus der geometrischen Algebra \eqref{RefGA} wegen +\begin{align} + \mathbf{v}' = -\mathbf{uvu}^{-1} = -\mathbf{uv_{\perp u}u}^{-1} - \mathbf{uv_{\parallel u}u}^{-1} = -(-\mathbf{v_{\perp u}}\underbrace{\mathbf{u})\mathbf{u}^{-1}}_{1} -(\mathbf{v_{\parallel u}}\underbrace{\mathbf{u})\mathbf{u}^{-1}}_{1} = \mathbf{v_{\perp u}} - \mathbf{v_{\parallel u}} +\end{align} +gleichbedeutend zu der Definition \eqref{RefLinAlg} der Spiegelung ist. -verwendet man für $\mathbf{u}$ nur einen Einheitsvektor $\mathbf{\hat{u}}$, welcher die Länge 1 besitzt, wird die Gleichung zu +Verwendet man für $\mathbf{u}$ nur einen Einheitsvektor $\mathbf{\hat{u}}$, welcher die Länge 1 besitzt, wird die Gleichung \eqref{RefGA} zu \begin{align} - \mathbf{v'} = \mathbf{\hat{u}v\hat{u}} + \mathbf{v'} = -\mathbf{\hat{u}v\hat{u}} \end{align} vereinfacht. Im Gegensatz zu den Abbildungen in der linearen Algebra, welche in jeder anderen Dimension, durch andere Matrizen \eqref{Spiegelmatrizen} beschrieben werden müssen, ist es in der geometrischen Algebra immer der gleiche Vorgehensweise. Zudem ist diese kompakte Schreibweise in der linearen Algebra nicht möglich, da bis auf das Vektorprodukt in der dritten Dimension keine Multiplikation von Vektoren definiert ist.
\ No newline at end of file diff --git a/buch/papers/clifford/8_Rotation.tex b/buch/papers/clifford/8_Rotation.tex index 6a3251a..1d5e889 100644 --- a/buch/papers/clifford/8_Rotation.tex +++ b/buch/papers/clifford/8_Rotation.tex @@ -6,7 +6,7 @@ \section{Rotation} \rhead{Rotation} -Eine Rotation kann man aus zwei aufeinanderfolgenden Spiegelungen bilden. Das wird für einige zuerst eine verwirrende Aussage sein, da man aus den vorherig gezeigten Formeln annehmen könnte, dass die Spiegelung schon für eine Drehung ausreicht. Obwohl sich die Längen, Winkel und Volumen sich bei einer Spiegelung, wie bei einer Rotation, nicht ändert, sind sie doch verschieden, da die Orientierung bei der Spiegelung invertiert wird. Stellt man sich beispielsweise ein Objekt im Dreidimensionalen vor und spiegelt dieses an einer Fläche, dann ist es unmöglich nur durch eine Rotation (egal an welchem Punkt) das ursprüngliche Objekt deckungsgleich auf das Gespiegelte zu drehen. Hingegen ist es wiederum möglich ein zweifach gespiegeltes Objekt durch eine Drehung zu erreichen. Das liegt daran, da die Orientierung zweimal invertiert wurde. +Eine Rotation kann man aus zwei aufeinanderfolgenden Spiegelungen bilden. Das kann vielleicht zuerst eine verwirrende Aussage sein, da man aus den vorherig gezeigten Formeln annehmen könnte, dass die Spiegelung schon für eine Drehung ausreicht. Obwohl sich die Längen, Winkel und Volumen sich bei einer Spiegelung, wie bei einer Rotation, nicht ändert, sind sie doch verschieden, da die Orientierung bei der Spiegelung invertiert wird. Stellt man sich beispielsweise ein Objekt im Dreidimensionalen vor und spiegelt dieses an einer Fläche, dann ist es unmöglich nur durch eine Rotation (egal an welchem Punkt) das ursprüngliche Objekt deckungsgleich auf das Gespiegelte zu drehen. Hingegen ist es wiederum möglich ein zweifach gespiegeltes Objekt durch eine Drehung zu erreichen. Das liegt daran, da die Orientierung zweimal invertiert wurde. \\(Hier wird noch ein Bild für das Verständnis eingefügt) \begin{figure} @@ -15,19 +15,28 @@ Eine Rotation kann man aus zwei aufeinanderfolgenden Spiegelungen bilden. Das wi \draw[thin,gray!40] (-3,-1) grid (3,3); \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; \draw[<->] (0,-1)--(0,3) node[above]{$a_2$}; + \draw[line width=1.0pt,green,-stealth](2,2)--(-2,2) node[anchor=south west]{$\boldsymbol{-2v_{\parallel u}}$}; + \draw[line width=1.0pt,green,-stealth](-2,2)--(-2.828,0) node[anchor=north west]{$\boldsymbol{-2v'_{\parallel w}}$}; + \draw[blue, line width=1.0pt] (0,3)--(0,-1) node[anchor=south east]{$\sigma_u$}; + \draw[red, line width=1.0pt] (-3,1.24)--(2.21,-1) node[anchor=south]{$\sigma_w$}; \draw[line width=2pt,black,-stealth](0,0)--(2,2) node[anchor=south east]{$\boldsymbol{v}$}; - \draw[line width=1.5pt,blue,-stealth](0,0)--(0,2.5) node[anchor=south east]{$\boldsymbol{u}$}; + \draw[line width=1.5pt,blue,-stealth](0,0)--(2.5, 0) node[anchor=south east]{$\boldsymbol{u}$}; \draw[line width=2pt,black,-stealth](0,0)--(-2,2) node[anchor=south east]{$\boldsymbol{v'}$}; - \draw[line width=1.5pt,red,-stealth](0,0)--(-2.31, 0.957) node[anchor=south east]{$\boldsymbol{w}$}; + \draw[line width=1.5pt,red,-stealth](0,0)--(0.957, 2.31) node[anchor=south east]{$\boldsymbol{w}$}; \draw[line width=2pt,black,-stealth](0,0)--(-2.828,0) node[anchor=south east]{$\boldsymbol{v''}$}; \draw[line width=1.5pt,gray,-stealth](0,0)--(1,0) node[anchor=north]{$\boldsymbol{e_1}$}; - \draw[line width=1.5pt,gray,-stealth](0,0)--(0,1) node[anchor=north west]{$\boldsymbol{e_2}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(0,1) node[anchor=north east]{$\boldsymbol{e_2}$}; \coordinate (A) at (0,0); - \coordinate (B) at (0,2.5); - \coordinate (C) at (-2.31, 0.957); - \tikzset{anglestyle/.style={angle eccentricity=1.25, draw, thick, angle radius=1.25cm}} + \coordinate (B) at (2.5,0); + \coordinate (C) at (0.957, 2.31); + \tikzset{anglestyle/.style={angle eccentricity=1.25, purple, draw, thick, angle radius=1cm}} \draw pic ["$\theta$", anglestyle] {angle = B--A--C}; + \coordinate (D) at (0,0); + \coordinate (E) at (1,1); + \coordinate (F) at (-1, 0); + \tikzset{anglestyle/.style={angle eccentricity=1.25, purple, draw, thick, angle radius=1.25cm}} + \draw pic ["$2\theta$", anglestyle] {angle = E--D--F}; \end{tikzpicture} \caption{Rotation des Vektors $\textbf{v}$ um $2\theta$} \label{BildRotation} @@ -49,76 +58,84 @@ Diese Drehmatrizen gehören der speziellen orthogonalen Matrizengruppe $D\in \te \subsection{Geometrische Algebra} Da wir jetzt aus der Geometrie wissen, dass eine Rotation durch zwei Spiegelungen gebildet werden kann, können wir die Rotation mit der Formel \eqref{RefGA} einfach herleiten. \begin{satz} - Eine Rotation + Durch zwei nacheinander auf einen Vektor $\mathbf{v}$ angewendete Spiegelungen lässt sich eine Rotation \begin{align} \label{rotGA} - \mathbf{v}'' = \mathbf{wv}'\mathbf{w}^{-1} = \mathbf{w}(\mathbf{uvu}^{-1})\mathbf{w}^{-1} = (\mathbf{wu})\mathbf{v}(\mathbf{u}^{-1}\mathbf{w}^{-1}) + \mathbf{v}'' = -\mathbf{wv}'\mathbf{w}^{-1} = -\mathbf{w}(-\mathbf{uvu}^{-1})\mathbf{w}^{-1} = (\mathbf{wu})\mathbf{v}(\mathbf{u}^{-1}\mathbf{w}^{-1}) \end{align} - lässt sich durch zwei nacheinander auf einen Vektor $\mathbf{v}$ angewendete Spiegelungen beschreiben. + beschreiben. \end{satz} Die Vektoren $\mathbf{w}$ und $\mathbf{u}$ bilden hier wiederum die Spiegelachsen. Diese Formel versuchen wir jetzt noch durch Umstrukturierung zu verbessern. \subsubsection{Exponentialform} -Dazu leiten wir zuerst die Exponentialform eines Vektors her. Es wird dabei zur Vereinfachung davon ausgegangen, dass alle Vektoren $\mathbf{w}, \mathbf{u}, \mathbf{v}$ in der $\mathbf{e}_{12}$ Ebene liegen. Weitere Drehungen können in höheren Dimensionen durch Linearkombinationen von Drehungen in den $\mathbf{e}_{ij}, i\not=j$ Ebenen erreicht werden. Für die Herleitung erweitern wir nun als erstes die Polarform +Dazu leiten wir zuerst die Exponentialform eines Vektors her. Es wird dabei zur Vereinfachung davon ausgegangen, dass alle Vektoren $\mathbf{w}, \mathbf{u}, \mathbf{v}$ in der $\mathbf{e}_{1}$-$\mathbf{e}_{2}$-Ebene liegen. Weitere Drehungen können in höheren Dimensionen durch Linearkombinationen von Drehungen in den $\mathbf{e}_{i}$-$\mathbf{e}_{j}$-Ebenen $(i\not=j)$ erreicht werden. Für die Herleitung ersetzen wir als erstes in der Polarform \begin{align} \mathbf{w} = |\mathbf{w}| \left(\cos(\theta_w) \mathbf{e}_1 + \sin(\theta_w) \mathbf{e}_2\right) \end{align} -eines Vektors mit $\mathbf{e}_1^2 = 1$ beim Sinus +eines Vektors einen Faktor 1 durch $1=\mathbf{e}_1^2$ und erhalten beim Sinus \begin{align}\label{e1ausklammern} - \mathbf{w} &= |\mathbf{w}| \left(\cos(\theta_w) \mathbf{e}_1 + \sin(\theta_w) \mathbf{e}_1\mathbf{e}_1\mathbf{e}_2\right), + \mathbf{w} &= |\mathbf{w}| \left(\cos(\theta_w) \mathbf{e}_1 + \sin(\theta_w) \mathbf{e}_1\mathbf{e}_1\mathbf{e}_2\right). \end{align} -um dann $\mathbf{e}_1$ +In einem zweiten Schritt klammern wir $\mathbf{e}_1$ aus, dies ergibt \begin{align} - \mathbf{w} = |\mathbf{w}|\mathbf{e}_1\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}\right) \label{ExponentialGA} + \mathbf{w} = |\mathbf{w}|\mathbf{e}_1\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}\right). \label{ExponentialGA} \end{align} -ausklammern zu können. Die Ähnlichkeit des Klammerausdrucks zu der Eulerschen Formel bei den Komplexen Zahlen ist nun schon gut erkennbar. Versuchen wir nun mithilfe der Reihenentwicklungen +Die Ähnlichkeit des Klammerausdrucks in der Formel \eqref{ExponentialGA} zu der Eulerschen Formel bei den komplexen Zahlen ist nun schon gut erkennbar. Versuchen wir nun mithilfe der Reihenentwicklungen \begin{align} \sin(\theta_w)\mathbf{e}_{12}&=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\theta_w^{2n+1}}{(2n+1)!}}\mathbf{e}_{12} =\theta_w\mathbf{e}_{12}-{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}-\cdots \\ \cos(\theta_w)&=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\theta_w^{2n}}{(2n)!}} =1-{\frac {\theta_w^{2}}{2!}}+{\frac {\theta_w^{4}}{4!}}-\cdots \end{align} -den Zusammenhang auch hier herzustellen. Verwenden wir jetzt noch die Eigenschaft, dass $\mathbf{e}_{12}^2=-1, \enspace\mathbf{e}_{12}^3=-\mathbf{e}_{12}, \dots$, bei dem Klammerausdruck in Formel \eqref{ExponentialGA} +diesen Zusammenhang auch hier herzustellen. Setzt man diese beiden Reihenentwicklungen in \eqref{ExponentialGA} ein, erhält man \begin{align} - \cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12} &= 1+\theta_w\mathbf{e}_{12}-{\frac {\theta_w^{2}}{2!}}-{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}+{\frac {\theta_w^{4}}{4!}}+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}-\cdots\\ - &= 1 \mathbf{e}_{12}^0+\theta_w\mathbf{e}_{12}^1+{\frac {\theta_w^{2}}{2!}}\mathbf{e}_{12}^2+{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}^3+{\frac {\theta_w^{4}}{4!}}\mathbf{e}_{12}^4+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}^5+\cdots + \cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12} &= 1+\theta_w\mathbf{e}_{12}-{\frac {\theta_w^{2}}{2!}}-{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}+{\frac {\theta_w^{4}}{4!}}+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}-\cdots +\end{align} +Dies sieht noch nicht wie eine Exponentialreihe aus, da $\mathbf{e}_{12}$ nur in jedem zweiten Term auftritt. Da aber $\mathbf{e}_{12}=-1$ gibt, erhält man für +\begin{align} + e^{\theta_w\mathbf{e}_{12}} = 1 \mathbf{e}_{12}^0+\theta_w\mathbf{e}_{12}^1+{\frac {\theta_w^{2}}{2!}}\mathbf{e}_{12}^2+{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}^3+{\frac {\theta_w^{4}}{4!}}\mathbf{e}_{12}^4+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}^5+\cdots \label{ExponentialGA2} \end{align} -dann sieht man die Übereinstimmung mit der Reihenentwicklung der Exponentialfunktion +Man sieht, dass die beiden Reihen übereinstimmen. Es folgt somit +\begin{align}\label{EulerGA} + e^{\theta_w \mathbf{e}_{12}} = \cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}, +\end{align} +es gibt eine Euler-Formel mit $\mathbf{e}_{12}$ anstelle der imaginären Einheit $j$. + +Wenn man jetzt den Vektor \eqref{ExponentialGA} durch die eulersche Schreibweise \begin{align} - &e^{\theta_w\mathbf{e}_{12}}=\sum _{n=0}^{\infty }{\frac {(\theta_w\mathbf{e}_{12})^{n}}{n!}}={\frac {(\theta_w\mathbf{e}_{12})^{0}}{0!}}+{\frac {(\theta_w\mathbf{e}_{12})^{1}}{1!}}+{\frac {(\theta_w\mathbf{e}_{12})^{2}}{2!}}+{\frac {(\theta_w\mathbf{e}_{12})^{3}}{3!}}+\cdots\\ - &\Rightarrow \mathbf{w} = |w|\mathbf{e}_1 e^{\theta_w \mathbf{e}_{12}} = |w|\mathbf{e}_1\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}\right). + \mathbf{w} = |\mathbf{w}|\mathbf{e}_1e^{\theta_w\mathbf{e}_{12}} \end{align} -Man kann die Exponentialform des Vektors ähnlich wie die der komplexen Zahlen interpretieren. Der Einheitsvektor $\mathbf{e}_1$ wird um die Länge $|\mathbf{w}|$ gestreckt und um $\theta_w$ gedreht. -Bei den komplexen Zahlen würden man vom Punkt 1 anstatt $\mathbf{e}_1$ ausgehen. +ersetzt, kann die Exponentialform des Vektors ähnlich wie die der komplexen Zahlen interpretieren. Der Einheitsvektor $\mathbf{e}_1$ wird um die Länge $|\mathbf{w}|$ gestreckt und um $\theta_w$ gedreht. \subsubsection{Vektormultiplikation} -Nun werden wir das Produkt von zwei Vektoren $\mathbf{wu}$ -\begin{align} +Nun werden wir das Vektorprodukt +\begin{align} \label{VektorproduktformelGA} \mathbf{wu} = |\mathbf{w}|\mathbf{e}_1 e^{\theta_w \mathbf{e}_{12}}|\mathbf{u}|\mathbf{e}_1 e^{\theta_u \mathbf{e}_{12}} \end{align} -so umformen, dass wir eine bessere Darstellung erhalten. Wir tauschen dafür zuerst beim Vektor $\mathbf{w}$ die Reihenfolge von -$\mathbf{e}_1$ mit dem Exponentialterm $e^{\theta_w \mathbf{e}_{12}}$, indem wir bei der Gleichung \eqref{e1ausklammern}, anstatt mit $\mathbf{e}_1\mathbf{e}_1\mathbf{e}_2$ mit $\mathbf{e}_2\mathbf{e}_1\mathbf{e}_1$ erweitern +so umformen, dass wir die Drehung nur durch Exponentialterme beschreiben können. Wir tauschen dafür zuerst beim Vektor $\mathbf{w}$ die Reihenfolge von +$\mathbf{e}_1$ mit dem Exponentialterm $e^{\theta_w \mathbf{e}_{12}}$, indem wir bei der Gleichung \eqref{e1ausklammern} $1=\mathbf{e}_1^2$ an einer anderen Position \begin{align} - \mathbf{w} &= |\mathbf{w}|\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_2\mathbf{e}_1\right)\mathbf{e}_1\\ - &= |\mathbf{w}|e^{\theta_w \mathbf{e}_{21}}\mathbf{e}_1\\ - &= |\mathbf{w}|e^{-\theta_w \mathbf{e}_{12}}\mathbf{e}_1 + \mathbf{w} &= |\mathbf{w}|\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_2\mathbf{e}_1\right)\mathbf{e}_1 +\end{align} +einsetzten. Mithilfe der Formel \eqref{EulerGA} und dem Wissen, dass $\mathbf{e}_{21}= -\mathbf{e}_{12}$ können wir die Umformung +\begin{align} + |\mathbf{w}|e^{-\theta_w \mathbf{e}_{12}}\mathbf{e}_1 \end{align} -und umstrukturiert wieder in die Vektorproduktformel einsetzen +ausführen. Diese wichtige Umstrukturierung können wir wieder in die Vektorproduktformel \eqref{VektorproduktformelGA} einsetzen un erhalten \begin{align} - \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{-\theta_w \mathbf{e}_{12}}\mathbf{e}_1\mathbf{e}_1 e^{\theta_u \mathbf{e}_{12}}\\ - \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{(\theta_u-\theta_w) \mathbf{e}_{12}}. + \mathbf{wu} &= |\mathbf{w}||\mathbf{u}|e^{-\theta_w \mathbf{e}_{12}}\mathbf{e}_1\mathbf{e}_1 e^{\theta_u \mathbf{e}_{12}}\\ + &= |\mathbf{w}||\mathbf{u}|e^{(\theta_u-\theta_w) \mathbf{e}_{12}}. \end{align} -Der Term $\mathbf{u}^{-1}\mathbf{w}^{-1}$ +Das inverse Vektorprodukt \begin{align} \mathbf{u}^{-1}\mathbf{w}^{-1} = \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{(\theta_w-\theta_u) \mathbf{e}_{12}} \end{align} -kann durch die selbe Methode zusammengefasst werden. -Wenn wir den Winkel zwischen den Vektoren $\mathbf{w}$ und $\mathbf{u}$ als $\theta = \theta_w - \theta_u$ definieren erhalten wir +kann durch die selbe Methode vereinfacht werden. +Wenn wir den Winkel zwischen den Vektoren $\mathbf{w}$ und $\mathbf{u}$ als $\theta = \theta_w - \theta_u$ definieren erhalten wir als endgültige Form der Vektorprodukte \begin{align}\label{wuExpo} - \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{-\theta \mathbf{e}_{12}}\\ - \mathbf{u}^{-1}\mathbf{w}^{-1} = \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{\theta \mathbf{e}_{12}} \label{wuExpoInv} + \mathbf{wu} &= |\mathbf{w}||\mathbf{u}|e^{-\theta \mathbf{e}_{12}}\enspace\text{und}\\ + \mathbf{u}^{-1}\mathbf{w}^{-1} &= \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{\theta \mathbf{e}_{12}} \label{wuExpoInv}. \end{align} -die finale Form der Vektorprodukte. \subsubsection{Umstrukturierte Drehungsgleichung} Setzten wir nun unsere neuen Erkenntnisse in die Gleichung \eqref{rotGA} ein \begin{align} - \mathbf{v''} = (|\mathbf{w}||\mathbf{u}|e^{-\theta \mathbf{e}_{12}}) \mathbf{v}( \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{\theta \mathbf{e}_{12}}), + \mathbf{v''} = (|\mathbf{w}||\mathbf{u}|e^{-\theta \mathbf{e}_{12}})\mathbf{v}\biggl(\dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{\theta \mathbf{e}_{12}}\biggr), \end{align} erhalten wir durch die Kürzungen der Längen die vereinfachte Drehungsgleichung \begin{align} @@ -145,12 +162,12 @@ kann man sehen, dass nur der parallele Anteil $\mathbf{v_\parallel}$ des Vektors \end{align} und das Produkt der Inversen $\mathbf{u}^{-1}\mathbf{w}^{-1}$ \begin{align} - \mathbf{u}^{-1}\mathbf{w}^{-1} = (\dfrac{\mathbf{e}_1}{1^2})(\dfrac{2\mathbf{e}_2}{2^2}) = \dfrac{1}{2}\mathbf{e}_{12}. + \mathbf{u}^{-1}\mathbf{w}^{-1} = \biggl(\dfrac{\mathbf{e}_1}{1^2}\biggr) \left(\dfrac{2\mathbf{e}_2}{2^2}\right) = \dfrac{1}{2}\mathbf{e}_{12}. \end{align} Der rotierte Vektor $\mathbf{v}''$ können wir nun durch das einsetzten und auflösen der Produkte in die Gleichung \eqref{rotGA} \begin{align} - \mathbf{v}'' = (\mathbf{wu})\mathbf{v}(\mathbf{u}^{-1}\mathbf{w}^{-1}) &= (-2e_{12})(1\mathbf{e}_1 + \mathbf{e}_2 + 1\mathbf{e}_3)(\dfrac{1}{2}\mathbf{e}_{12})\\ - &= (2\mathbf{e}_2-2\mathbf{e}_1-2\mathbf{e}_{123})(\dfrac{1}{2}\mathbf{e}_{12})\\ + \mathbf{v}'' = (\mathbf{wu})\mathbf{v}(\mathbf{u}^{-1}\mathbf{w}^{-1}) &= (-2e_{12})(1\mathbf{e}_1 + \mathbf{e}_2 + 1\mathbf{e}_3)(\textstyle{\frac{1}{2}}\mathbf{e}_{12})\\ + &= (2\mathbf{e}_2-2\mathbf{e}_1-2\mathbf{e}_{123})(\textstyle{\frac{1}{2}}\mathbf{e}_{12})\\ &= -1\mathbf{e}_1 - 1\mathbf{e}_2 + 1\mathbf{e}_3 \end{align} finden. Aus dem Resultat $\mathbf{v}''= -1\mathbf{e}_1 + 1\mathbf{e}_2 + 1\mathbf{e}_3$ können wir bestätigen, dass @@ -159,11 +176,11 @@ kann man sehen, dass nur der parallele Anteil $\mathbf{v_\parallel}$ des Vektors \item sich der parallele Anteil $\mathbf{v_\parallel}'' = -1\mathbf{e}_1 - 1\mathbf{e}_2$ gedreht hat und der senkrechte Anteil $\mathbf{v_\perp}'' = 1\mathbf{e}_3$ unverändert blieb. \item der parallele Teil sich genau um $2\theta=180$° gedreht hat. $\theta$ kann übrigens durch die Umformung des Produkt $\mathbf{wu}$ in die Exponentialschreibweise \begin{align} - &\mathbf{wu} = -2\mathbf{e}_{12} = 2(0-1\mathbf{e}_{12})=2(\cos(\dfrac{-\pi}{2} + \sin(\dfrac{-\pi}{2})\mathbf{e}_{12})) = 2e^{(-\pi/2)\mathbf{e}_{12}} + &\mathbf{wu} = -2\mathbf{e}_{12} = 2(0-1\mathbf{e}_{12})=2(\cos\biggl(\dfrac{-\pi}{2}\biggr) + \sin\biggl(\dfrac{-\pi}{2}\biggr)\mathbf{e}_{12}) = 2e^{(-\pi/2)\mathbf{e}_{12}} \end{align} durch einen Vergleich mir der Formel \eqref{wuExpo} \begin{align} - \theta = -(\dfrac{-\pi}{2}) = \dfrac{\pi}{2} + \theta = -\biggl(\dfrac{-\pi}{2}\biggr) = \dfrac{\pi}{2} \end{align} ausgelesen werden. \end{itemize} diff --git a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png Binary files differnew file mode 100644 index 0000000..fb4d061 --- /dev/null +++ b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png diff --git a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png Binary files differnew file mode 100644 index 0000000..73217d3 --- /dev/null +++ b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png diff --git a/buch/papers/munkres/figures/ganzzahlige_punkte.png b/buch/papers/munkres/figures/ganzzahlige_punkte.png Binary files differnew file mode 100644 index 0000000..5689825 --- /dev/null +++ b/buch/papers/munkres/figures/ganzzahlige_punkte.png diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index c13732c..d22b57f 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -7,22 +7,37 @@ \label{munkres:section:teil1}} \rhead{Problemstellung} -Das spezielle an einem Zuordnungsproblem ist, dass es an jedem Ort nur eine Einheit angeboten bzw. nachgefragt wird. Es werden hier nicht Mengen möglichst kostenminimal von einem zum anderen -Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.B. Personen, oder Bau-Materialien auf bestimmte Orte, Stellen oder Aufgaben. +Das Spezielle an einem Zuordnungsproblem ist, dass es an jedem Ort nur eine Einheit angeboten bzw. nachgefragt wird. Es werden hier nicht Mengen möglichst kostenminimal von einem zum anderen +Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.B. Personen, oder Bau-Maschinen auf bestimmte Orte, Stellen oder Aufgaben. Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde der Munkres-Algorithmus, auch die Ungarische Methode genannt, entwickelt. Diese Methode ist ein weiteres Hauptthema dieses Kapitels. \subsection{Zuordnungsproblem an einem konkreten Beispiel \label{munkres:subsection:bonorum}} +Man hat den Fall, wo ein Bauunternehmer einen Bauingenieur beauftragt, eine optimale Transportroute für die Umplatzierung seiner Kräne zu eruieren. Das heisst, die Transportstrecke für die Umplatzierung seine Kräne +soll möglichst klein werden. +Die Frage lautet, wie sind die Kräne umzusetzen, damit deren Transportstrecke minimal wird? Bei der normalen Optimierung dürfen normalerweise beliebige reelle Werte angenommen werden $\mathbb{R}$. +Beim Beispiel mit den Kräne gibt es aber ein Problem. Bei der Suche nach der optimalen Lösung darf nur die Methode der ganzzahligen Optimierung gewählt werden $\mathbb{Z}$. Materialien kann man aufteilen, jedoch Maschinen nicht. Die Bauarbeiter auf der neuen Baustelle benötigen einen ganzen Kran und nicht nur einen halben Kran. Es muss immer ein ganzer Kran von A nach B oder gar kein Kran verschoben werden. Also 1 oder 0. +Für solche Optimierungsproblem für reelle Varianten sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art uns weise lösbar. Doch das Problem bleibt, wie in der Illustration oben ersichtlich. Es kann mit ganzzahligen Punkten kein Optimum erzielt werden. Das Ziel ist es an das Optimum so nah wie möglich heranzukommen und dies ist eine vergleichsweise träge und langsame Angelegenheit. + +\begin{figure} +\centering +\includegraphics[width=5cm]{papers/munkres/figures/ganzzahlige_punkte} +\caption{Problem der Ganzzahligkeit.} +\label{munkres:Vr2} +\end{figure} + \subsection{Zuordnungsproblem abstrakt \label{munkres:subsection:bonorum}} -Es sind alle Angebots- und Bedarfsmengen gleich 1 +In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1 \begin{equation} a_{i}=b_{j}=1 \end{equation} +Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix $\mathbb{A}$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann der Faktor Kosten mit in die Rechnung eingebracht werden. +In der Zelle dieser Matrix sind $a_{i,j}$ die Wege dargestellt, die entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet. -\subsection{alternative Darstellungen des Zuordnungsproblems +\subsection{Alternative Darstellungen des Zuordnungsproblems \label{munkres:subsection:bonorum}} \begin{equation} Netzwerk @@ -35,7 +50,7 @@ Bitpartiter Graph \end{equation} Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. -Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» +Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. \begin{figure} \centering \includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung} diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex index 9a44cd4..a3b249e 100644 --- a/buch/papers/munkres/teil2.tex +++ b/buch/papers/munkres/teil2.tex @@ -7,7 +7,7 @@ \label{munkres:section:teil2}} \rhead{Schwierigkeit der Lösung (Permutationen)} -Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine maximale Zuordnung (maximales Matching) gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. +Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. -Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer n×n-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von n Elementen gibt, also n!. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigender Permutationen. +Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer $n$×$n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigender Permutationen. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index cd47c92..874baae 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -7,7 +7,7 @@ \label{munkres:section:teil3}} \rhead{Der Munkres-Algorithmus (Ungarische Methode)} -Mit der ungarischen Methode können also lineare Optimierungsprobleme gelöst +Mit der ungarischen Methode können also Optimierungsprobleme gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der @@ -29,18 +29,90 @@ um eine $O(n^3)$-Laufzeit zu erreichen. \subsection{Besondere Leistung der Ungarischen Methode \label{munkres:subsection:malorum}} -Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem +Die Ungarische Methode ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem in polynomieller Zeit löst. Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms -wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. +wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei die "Grösse" des Problems. +\subsection{Unterschiedliche Anzahl von Quellen und Zielen +\label{munkres:subsection:malorum}} +Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. Das ist z.B dann der Fall, wenn eine 3 Mitarbeiter 4 Eignungstests abdsolvieren müssen. In diesem Fall wird in der Ungarischen Methode die Matrix künstlich mittels einer Dummy Position quadratisch ergänzt. Dummy-Positionen werden dann mit der größten vorhandenen Zahl aus der Matrix besetzt. Beispielsweise eine $4\times 3$ wird zu einer $4\times 4$ Matrix. \subsection{Beispiel eines händischen Verfahrens \label{munkres:subsection:malorum}} +Die ungarische Methode kann in einem einfachen händischen Beispiel +erläutert werden. Es gibt eine Ausgangsmatrix. Diese Matrix wird in mehreren Schritten immer +weiter reduziert. Anschließend erfolgen mehrere Zuordnungen. Hierbei ist zu beachten, dass +jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt. +Die optimale Lösung ist erreicht, wenn genau $n$ Zuordnungen gefunden +sind. + +\begin{enumerate} +\item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei +allen anderen Ziffern in der jeweiligen Zeile subtrahiert. + +\item Danach zieht man wiederum die kleinste Zahl in jeder Spalte von allen +Zahlen in der Spalte ab. + +\item Es sollen möglichst viele Nullen markiert werden, welche freistehend sind. +(Freistehend bedeutet, sowohl in der jeweiligen Zeile und Spalte nur +eine markierte Null zu haben) + +\item Jeweilige Zeilen eruieren, bei welchen keine markierte Null vorhanden sind und kennzeichnen. + +\item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls +kennzeichnen (*2) + +\item Im der selben Spalte die Markierte Null eruieren und die dazugehörige +Zeile kennzeichnen (*3) + +\item Alle Zeilen durchstreichen, welche KEINE Kennzeichnungen (*) haben + +\item Alle Spalten durchstreichen, welche EINE Kennzeichnung besitzt! (hier, *2) + +\item Kleinste Ziffer auswählen, welche nicht schon durchgestrichen sind. +(Im Beispiel ist es die Zahl 1. (Egal welche 1) + +\item Die eruierte kleinste Ziffer, wird von den nicht durchgestrichenen Ziffern +subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen) + +\item Jeweilige Zahlen eruieren, welche vorgängig doppelt durchgestrichen wurden. + +\item Kleinste eruierte Ziffer von vorhin auf die zwei markierten Ziffern addieren. + +\item Es sollen wiederum von neuem möglichst viele Nullen markiert werden, +welche freistehend sind. In diesem Schritt werden nur die markierten Nullen betrachtet. + +\item Aus allen markierten Nullen in eine eins umwandeln. + +\item Die restlichen Ziffern, durch eine Null ersetzen. + +\item Zu guter letzt soll überall wo eine 1 steht, in der Ausgangsmatrix die +dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen ergeben sich nach Summieren der Zahlen der minimalste Transportweg. +\end{enumerate} + \begin{figure} \centering -\includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres} -\caption{Händisches Beispiel des Munkres Algorithmus.} +\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png} +\caption{Händisches Beispiel des Munkres Algorithmus, minimalster Transportweg.} \label{munkres:Vr2} \end{figure} + +\subsection{Zuordnung der Kräne +\label{munkres:subsection:malorum}} + +\begin{itemize} +\item Der Kran von Baustelle A1 soll zur Baustelle B2. +\item Der Kran von Baustelle A2 soll zur Baustelle B3. +\item Der Kran von Baustelle A3 soll zur Baustelle B4. +\item Der Kran von Baustelle A4 soll zur Baustelle B1. +\end{itemize} + +\begin{figure} +\centering +\includegraphics[width=3cm]{papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png} +\caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne } +\label{munkres:Vr2} +\end{figure} + diff --git a/buch/papers/punktgruppen/crystals.tex b/buch/papers/punktgruppen/crystals.tex index 21e29c9..42008e1 100644 --- a/buch/papers/punktgruppen/crystals.tex +++ b/buch/papers/punktgruppen/crystals.tex @@ -1,8 +1,7 @@ \section{Kristalle} -%einleitung sollte noch an das ende von der Symmetrie angepasst werden -Unter dem Begriff Kristall sollte sich jeder ein Bild machen können. -Wir werden uns aber nicht auf sein Äusseres fokussieren, sondern was ihn im Inneren ausmacht. -Die Innereien eines Kristalles sind glücklicherweise relativ einfach definiert. +Eine nicht allzu häufig gestellte Frage ist, wie ein Kristall definiert ist. +Um zu klären, was ein Kristall mit Symmetrien zu tun hat, ist jedoch genau diese Frage äusserst relevant. +Glücklicherweise ist das Innere eines Kristalles relativ einfach definiert. \begin{definition}[Kristall] Ein Kristall besteht aus Atomen, welche sich in einem Muster arrangieren, welches sich in drei Dimensionen periodisch wiederholt. \end{definition} @@ -22,7 +21,7 @@ Die eingezeichneten Vektoren \(\vec{a}_1\) und \(\vec{a}_2\) sind die kleinstmö Wird ein beliebiger grauer Gitterpunkt in \ref{fig:punktgruppen:lattice} gewählt und um eine ganzzahlige Linearkombination von \(\vec{a}_1\) und \(\vec{a}_2\) verschoben, endet er zwangsweise auf einem Gitterpunkt, wenn nicht wieder am selben Ort. Im dreidimensionalen Raum können alle Gitterpunkte mit derselben Idee und einem zusätzlichen Vektor \(\vec{c}\) also \[ - \vec{r} = n_1 \vec{a}_1 + n_2 \vec{a}_2 + n_3 \vec{a}_3 = \sum_i n_i \vec{a}_i + \vec{r} = n_1 \vec{a}_1 + n_2 \vec{a}_2 + n_3 \vec{a}_3 = \sum_i n_i \vec{a}_i \] erreicht werden sofern \(n_1,n_2,n_3 \in \mathbb{Z}\) sind. Sind die Vektoren \(\vec{a}_1\), \(\vec{a}_2\), \(\vec{a}_3\) gegeben, ist ein Kristallgitter eindeutig beschrieben, weswegen sie auch als Grundvektoren bekannt sind. @@ -30,20 +29,20 @@ Sind die Vektoren \(\vec{a}_1\), \(\vec{a}_2\), \(\vec{a}_3\) gegeben, ist ein \subsection{Translationssymmetrie} Da sich das ganze Kristallgitter wiederholt, wiederholen sich auch dessen Eigenschaften periodisch mit den Grundvektoren. Sollte man sich auf einem Gitterpunkt in einem Kristall aufhalten, ist es unmöglich zu wissen, auf welchem Gitterpunkt man sich befindet, da die Umgebungen aller Punkte identisch sind. -Mit anderen Worten: Jedes Kristallgitter $ G $ ist \emph{Translationssymmetrisch} in der Translation +Mit anderen Worten: Jedes Kristallgitter $ G $ ist \emph{translationssymmetrisch} in der Translation \[ - \vec{Q}_i(G) = G + \vec{a}_i -\] wobei der Vektor $\vec{a}_i$ ein Grundvektor sein muss. + \vec{Q}_i(G) = G + \vec{a}_i, +\] +wobei der Vektor $\vec{a}_i$ ein Grundvektor sein muss. Da die Translationssymmetrie beliebig oft mit allen Grundvektoren angewendet werden kann, können wir auch sagen, dass alle Verschiebungen um eine Linearkombination -der Vektoren $\vec{a}_1$ , $\vec{a}_2$ und $\vec{a}_3$ erlaubt sind oder kurz, um $\vec{r}$. -Verschiebungen um $\vec{r}$ bewirken demnach keine Veränderungen, -solange wir ein unendlich grosses Kristallgitter verschieben. +der Vektoren $\vec{a}_1$ , $\vec{a}_2$ und $\vec{a}_3$ erlaubt sind. +Dabei sollte erwähnt werden, dass eine Translationssymmetrie nur in unendlich grossen Kristallgittern besteht. \subsection{Limitierte Kristallsymmetrien} \label{txt:punktgruppen:Translationssymmetrie} Die Translationssymmetrie ist wohl keine grosse Überraschung, wenn man die Abbildung \ref{fig:punktgruppen:lattice} betrachtet. - Was nicht direkt ersichtlich ist, dass bei beliebigen Grundvektoren nicht beliebige Symmetrien erstellt werden können. - Die geforderte Translationssymmetrie eines Kristalles schränkt weitere Symmetrien deutlich ein. + Was nicht direkt ersichtlich ist, ist dass bei beliebigen Grundvektoren nicht beliebige Symmetrien erstellt werden können. + Dies weil die Translationssymmetrie eines Kristalles weitere Symmetrien deutlich einschränkt. \begin{figure} \centering @@ -62,7 +61,7 @@ solange wir ein unendlich grosses Kristallgitter verschieben. 90\(^{\circ}\), 120\(^{\circ}\) und 180\(^{\circ}\) - erlaubt. + m\"oglich. \end{satz} \begin{proof} @@ -78,10 +77,8 @@ solange wir ein unendlich grosses Kristallgitter verschieben. Für uns bedeutet dies lediglich, dass unser zweiter Punkt \(A'\) abgedreht wird. An der neuen Position \(B\) von \(A'\) muss also auch ein Punkt des Gitters sein, um die Rotationssymmetrie zu erfüllen. \item \(B\) ist unser Name für diesen neuen Punkt. - Da auch die Eigenschaften des Kristallgittes periodisch mit dem Gitter sein müssen, dürfen wir \(C_n\) auch auf \(A'\) anwenden. - Also wenden wir \(C_n\) invertiert\footnote{Eine Rotationssymmetrie muss auch in die inverse Richtung funktionieren. - Genauere Überlegungen hierzu werden dem Leser überlassen, da sich die Autoren nicht explizit mit dieser Frage Auseinander gesetzt haben.} - auch auf \(A'\) an. + Da auch die Eigenschaften des Kristallgitters periodisch mit dem Gitter sein müssen, dürfen wir \(C_n\) auch auf \(A'\) anwenden. + Also wenden wir \(C_n^{-1}\) auch auf \(A'\) an. Dies dreht \(A\) auf einen neuen Punkt. \item \(B'\) ist kein zufälliger Name für diesen neuen Punkt, denn wir wissen, dass zwischen allen Punkten eine Translationssymmetrie bestehen muss. Die Translationssymmetrie zwischen \(B\) und \(B'\) ist hier als \(\vec{Q}'\) bezeichnet. @@ -89,14 +86,14 @@ solange wir ein unendlich grosses Kristallgitter verschieben. Mit den gegebenen Punkten lassen sich geometrische Folgerungen ziehen. Wir beginnen, indem wir die Länge der Verschiebung \(|\vec{Q}| = Q\) setzen und \(|\vec{Q}'| = Q'\). Aus Abbildung \ref{fig:punktgruppen:rot-geometry} ist ersichtlich, dass \(Q' = Q + 2x\). - Da \(\vec{Q}\) eine Translation um ein Grundvektor ist , muss \(\vec{Q}'\) ein ganzes vielfaches von \(\vec{Q}\) sein. - Demnach auch die Längen + Da \(\vec{Q}\) eine Translation um ein Grundvektor ist , muss \(\vec{Q}'\) ein ganzes Vielfaches von \(\vec{Q}\) sein. + Demnach auch die Länge \[ - Q' = nQ = Q + 2x + Q' = nQ = Q + 2x . \] - Die Strecke \(x\) lässt sich auch mit hilfe der Trigonometrie und dem angenommenen Rotationswinkel \(\alpha\) ausdrücken: + Die Strecke \(x\) lässt sich auch mit Hilfe der Trigonometrie und dem angenommenen Rotationswinkel \(\alpha\) ausdrücken: \[ - nQ = Q + 2Q\sin(\alpha - \pi/2) + nQ = Q + 2Q\sin(\alpha - \pi/2) . \] Wir können durch \(Q\) dividieren um unabhängig von der Läge des Grundvektors zu werden, was auch Sinn macht, da eine Skalierung eines Kristalles seine Symmetrieeigenschaften nicht tangiert. @@ -126,10 +123,10 @@ ein. \subsection{Kristallklassen} -Vorgehend wurde gezeigt, dass in einem zweidimensionalen Kristallgitter nicht alle Symmetrien möglich sind. +Im vorausgegangenen Abschnitt wurde gezeigt, dass in einem zweidimensionalen Kristallgitter nicht alle Symmetrien möglich sind. Mit weiteren ähnlichen Überlegungen kann gezeigt werden, dass Kristalle im dreidimensionalen Raum nur auf genau 32 Arten rein punktsymmetrische Symmetriegruppen bilden können. Diese 32 möglichen Symmetriegruppen scheinen durchaus relevant zu sein, denn sie werden unter anderem als Kristallklassen bezeichnet. - Die 32 möglichen Kristallklassen sind auf Abbildung \ref{fig:punktgruppen:Kristallkassen} zu sehen. + Die 32 möglichen Kristallklassen sind auf Abbildung \ref{fig:punktgruppen:kristallklassen} zu sehen. Die Darstellung von dreidimensionalen Punktsymmetrien wurde mit der stereographischen Projektion ermöglicht (siehe Abbildung \ref{fig:punktgruppen:stereographic-projections}), wobei die gestrichelten Klassen aus Gründen der Überschaubarkeit nicht im Detail gezeichnet wurden. @@ -137,23 +134,34 @@ Vorgehend wurde gezeigt, dass in einem zweidimensionalen Kristallgitter nicht al \centering \includegraphics[]{papers/punktgruppen/figures/projections} \caption{Kristallklassen mit zugehörigem Schönflies-Symbol} - \label{fig:punktgruppen:Kristallkassen} + \label{fig:punktgruppen:kristallklassen} \end{figure} -\subsubsection{Schönflies-Symbilok} +\subsubsection{Schönflies-Symbolik} -Jede der 32 Kristallklassen auf der Abbildung \ref{fig:punktgruppen:Kristallkassen} ist mit ihrem zugehörigen Schöönflies-Symbol bezeichnet. +Jede der 32 Kristallklassen auf der Abbildung \ref{fig:punktgruppen:kristallklassen} ist mit ihrem zugehörigen Schönflies-Symbol bezeichnet. Die Schönflies-Symbolik stammt von dem Mathematiker Arthur Moritz Schönflies, welcher sich unter anderem mit der Klasifizierung der Punktgruppen auseinandergesetzt hat. - Er hat Untergruppen gebildet, welche als Grossbuchstaben in Abbildung \ref{fig:punktgruppen:Kristallkassen} zu sehen sind. - Da nicht alle Symmetriegruppen in Kristallen möglich sind, werden nicht alle Untergruppen von Schönflies verwendet. - Es ist nur die Drehgruppe \(C\), Diedergruppe \(D\), Drehspiegelgruppe \(S\), Tetraedergruppe \(T\) und die Oktaedergruppe \(O\). - Für die eindeutige zuweisung in eine Kristallklasse werden noch identifizierende Merkmale als Subskript notiert. - Bei der Untergruppe \(C\) werden beispielsweise die möglichen Rotationssymmetrien gezeigt. - Dank Abschintt \ref{txt:punktgruppen:Translationssymmetrie} wissen wir, wieso auf \(C\) nur ganz bestimmte Subskripte folgen, weil das Subskript \(n\) von \(C_n\) zeigt, dass es sich um eine \(n\)-fache Rotationssymmetrie handelt. - Daher darf \(C_5\) auf der Abbildung \ref{fig:punktgruppen:Kristallkassen} nicht vorkommen darf, da \(360^\circ/5 = 72^\circ\) was nach Abschnitt \ref{txt:punktgruppen:Translationssymmetrie} in einem Kristall keine mögliche Rotationssymmetrie ist. - Sind im Subskript Buchstaben, definieren diese weitere Symmetrieeigenschaften der Klasse. - Wie zum Beispiel ein Inversionszentrum\footnote{Ein Objekt mit Inversionszentrum ist Punktsymmetrisch im Inversionszentrum.} \(i\) oder eine horizontale\footnote{Als Orientierungspunkt wird die Symmetrieachse höchster Ordnung (\(n\)) als vertikal definiert} Spiegelachse \(h\). - Zu beachten ist jedoch, dass manche Symmetriegruppen mit mehreren Schönflies-Symbolen beschieben werden können. + Er hat Untergruppen gebildet, welche als Grossbuchstaben in Abbildung \ref{fig:punktgruppen:kristallklassen} zu sehen sind. + \begin{itemize} + \item In Kristallen ist nur die Drehgruppe \(C\), Diedergruppe \(D\), Drehspiegelgruppe \(S\), Tetraedergruppe \(T\) und die Oktaedergruppe \(O\) zu finden. + Es gäbe auch die Ikosaedergruppe \(I\) und die Kugelgruppe \(K\), diese sind aber nicht kompatibel mit der Translationssymmetrie eines Kristalles und daher in der Kristallographie nicht relevant. + \item Dank Abschintt \ref{txt:punktgruppen:Translationssymmetrie} wissen wir, wieso in Abbildung \ref{fig:punktgruppen:kristallklassen} auf \(C\) nur ganz bestimmte Subskripte folgen. + Ist im Subskript eine Zahl \(n\) zu finden, steht dies für eine \(n\)-fache Symmetrie. + Daher darf \(C_5\) auf der Abbildung \ref{fig:punktgruppen:kristallklassen} nicht vorkommen, da \(360^\circ/5 = 72^\circ\) was nach Abschnitt \ref{txt:punktgruppen:Translationssymmetrie} keine mögliche Rotationssymmetrie eines Kristalles ist. + \item Sind im Subskript Buchstaben, definieren diese weitere Symmetrieeigenschaften der Klasse. + Für die folgenden Betrachtungen müssen wir uns Abbildung \ref{fig:punktgruppen:kristallklassen} genauer ansehen. + Dabei ist mit horizontal flach auf dem Papier gemeint. + \begin{itemize} + \item[\(h\)] bezeichnet eine horizontale Spiegelebene und + \item[\(v\)] eine Symmetrieebene, was eine Spiegelebene ist, die sich mit der Symmetrie mitdreht. + Zum Beispiel hat \(C_{3v}\) eine vertikale Spiegelebene, die durch die 3-fache Drehsymmetrie als 3 Spiegelebenen erscheinen. + \item[\(s\)] ist ein spezielles Subskript um die beiden Symmetriegruppen \(C_{1v}\) und \(C_{1h}\) zu beschreiben, weil \(C_{1v} = C_{1h}\). + \item[\(d\)] symbolisiert eine diagonale Symmetrieebene. + Es wird ersichtlich wie diagonal gemeint ist, wenn man \(D_2\) zu \(D_{2d}\) vergleicht. + \item[\(i\)] steht für ein Inversionszentrum. Hat eine Symmetriegruppe ein Inversionszentrum, bedeutet dies dass sie im Ursprung punktsymmetrisch ist. + \end{itemize} + \end{itemize} +Zu beachten ist jedoch, dass manche Symmetriegruppen mit mehreren Schönflies-Symbolen beschieben werden können. \(C_{3i}\) beschreibt genau das selbe wie \(S_6\), da eine dreifache Rotationssymmetrie mit einem Inversionszentrum einer sechsfachen Drehspiegelsymmetrie entspricht. diff --git a/buch/papers/punktgruppen/figures/projections.pdf b/buch/papers/punktgruppen/figures/projections.pdf Binary files differindex bc04313..202fc8d 100644 --- a/buch/papers/punktgruppen/figures/projections.pdf +++ b/buch/papers/punktgruppen/figures/projections.pdf diff --git a/buch/papers/punktgruppen/intro.tex b/buch/papers/punktgruppen/intro.tex index b6a72b5..1293234 100644 --- a/buch/papers/punktgruppen/intro.tex +++ b/buch/papers/punktgruppen/intro.tex @@ -1,6 +1,6 @@ \section{Einleitung} Es gibt viele Möglichkeiten sich in Kristallen zu verlieren. -Auch wen man nur die mathematischen Betrachtungsweisen berücksichtigt, +Auch wenn man nur die mathematischen Betrachtungsweisen berücksichtigt, hat man noch viel zu viele Optionen sich mit Kristallen zu beschäftigen. In diesem Kapitel wird daher der Fokus ``nur'' auf die Symmetrie gelegt. Zu Beginn werden wir zeigen was eine Symmetrie ausmacht und @@ -15,9 +15,9 @@ und sich kategorisieren lassen. Kategorien sind nicht nur für einen besseren Überblick nützlich, sondern kann man aus ihnen auch auf Physikalische Eigenschaften schliessen. Als spannendes Beispiel: Die Piezoelektrizität. -Die Piezoelektrizität ist vielleicht noch nicht jedem bekannt, -sie versteckt sich aber in diversen Altagsgegenständen -zum Beispiel sorgen sie in den meisten Feuerzeugen für die Zündung. +Piezoelektrizität ist kein weit verbreiteter Begriff, +jedoch beschreibt er ein Effekt, ohne welchen diverse Altagsgegenständen nicht besonders nützlich wären. +Wie zum Beispiel sorgt er in den allermeisten Feuerzeugen für die Zündung. Hiermit ist hoffentlich ein Funken Interesse geweckt um sich mit dem scheinbar trivialen Thema der Symmetrie auseinander zu setzten. diff --git a/buch/papers/punktgruppen/main.tex b/buch/papers/punktgruppen/main.tex index ea19421..556fc2b 100644 --- a/buch/papers/punktgruppen/main.tex +++ b/buch/papers/punktgruppen/main.tex @@ -19,6 +19,7 @@ \nocite{punktgruppen:sands-crystal} \nocite{punktgruppen:lang-elt2} \nocite{punktgruppen:ouchem} +\nocite{punktgruppen:restriction} \printbibliography[heading=subbibliography] \end{refsection} diff --git a/buch/papers/punktgruppen/piezo.tex b/buch/papers/punktgruppen/piezo.tex index 6defcdc..6ed7ee9 100644 --- a/buch/papers/punktgruppen/piezo.tex +++ b/buch/papers/punktgruppen/piezo.tex @@ -1,6 +1,6 @@ \section{Piezoelektrizität} -Die Piezoelektrizität ist per Definition spannend. -Sie beschreibt die Eigenschaft, dass gewisse Kristalle eine elektrische Spannung erzeugen, wenn machanischer Druck auf sie ausgeübt wird. +%% TODO: improve this paragraph +Die Piezoelektrizität ist die spannende Eigenschaft, dass gewisse Kristalle eine elektrische Spannung erzeugen, wenn mechanischer Druck auf sie ausgeübt wird. \begin{figure} \centering @@ -10,11 +10,11 @@ Sie beschreibt die Eigenschaft, dass gewisse Kristalle eine elektrische Spannung \end{figure} \subsection{Polarisierung} -Piezoelektrizität basiert darauf, dass zwischen den Oberflächen des Kristalles ein Ladungsungleichgewicht entsteht siehe Abbildung\ref{fig:punktgruppen:basicPiezo}. +Piezoelektrizität basiert darauf, dass zwischen den Oberflächen des Kristalles ein Ladungsungleichgewicht entsteht (siehe Abbildung\ref{fig:punktgruppen:basicPiezo}). Dieses Ungleichgewicht resultiert, -weil durch den mechanischen Druck auf der einen Oberfläche des Kristalles positiv Ione näher an die Oberfläche gelangen, -wärend auf der gegenüberliegenden Oberfläche sich mehr negative Ionen Sammeln. -Das sich die atomare Struktur eines Kristalles unter Druck genau so verformt ist nicht bei jedem Kristall gegeben. +weil durch den mechanischen Druck auf der einen Oberfläche des Kristalles positive Ionen näher an die Oberfläche gelangen, +wärend auf der gegenüberliegenden Seite dasselbe mit negativen Ionen passiert. +Es besitzt jedoch nicht jeder Kristall eine atomare Struktur welche sich unter Druck genau so verformt. Der Aufbau und somit auch die Symmetrie des Kristalles sind daher relevant für die Entstehung dieses Effektes. \begin{figure} @@ -35,49 +35,47 @@ Der Aufbau und somit auch die Symmetrie des Kristalles sind daher relevant für \end{figure} \subsection{Atomarer Aufbau} -Die Polarisation resultiert über eine gesamte Oberfläche eines Kristalles, entscheidend ist aber der atomare Aufbau. +Die Polarisation entsteht an der Oberfläche eines Kristalles, die Erklärung dazu finden wir jedoch im atomaren Aufbau. Wir wollen dazu die verschiedenen Kristallstrukturen auf Abbildung \ref{fig:punktgruppen:atomPiezo} diskutieren. -In Abbildung \ref{fig:punktgruppen:atomPiezo} gilt für alle Strukturen, dass rote Kreise Positive Ionen und blaue negative Ionen repräsentieren. -%liste oder anderes format?.. +In Abbildung \ref{fig:punktgruppen:atomPiezo} gilt für alle Strukturen, dass rote Kreise positive Ionen und blaue negative Ionen repräsentieren. Struktur \subref{fig:punktgruppen:atoms-piezo} zeigt ein piezoelektrisches Material in Ruhe. Struktur \subref{fig:punktgruppen:atoms-piezo-fv} ist dasselbe Kristallgitter, jedoch wird es senkrecht belastet. -Eingezeichnet ist auch das elektrische Feld, welches entsteht, weil mitlleren Ladungsträger weiter auseinander gerdrückt werden. -Als hilfe zur Vorstellung kann man \subref{fig:punktgruppen:atoms-piezo-fv} zwischen zwei leitende Platten setzen, so wird ersichtlich, +Eingezeichnet ist auch das elektrische Feld, welches entsteht, weil die Ladungsträger ganz links und rechts weiter auseinander gedrückt werden. +Als Hilfe zur Vorstellung kann man \subref{fig:punktgruppen:atoms-piezo-fv} zwischen zwei leitende Platten setzen, so wird ersichtlich, dass mit wachsendem Druck eine negative Ladung an die rechte Platte gedrückt wird, während sich die positiven Ionen weiter entfernen. -\subref{fig:punktgruppen:atoms-grid} ist nicht piezoelektrisch. -Dies wird ersichtlich, wenn man \subref{fig:punktgruppen:atoms-grid} unterdruck setzt und sich die Struktur zu \subref{fig:punktgruppen:atoms-grid-f} verformt. +\par +Die Struktur \subref{fig:punktgruppen:atoms-grid} ist nicht piezoelektrisch. +Dies wird ersichtlich, wenn man \subref{fig:punktgruppen:atoms-grid} unter Druck setzt und sich die Struktur zu \subref{fig:punktgruppen:atoms-grid-f} verformt. Setzt man \subref{fig:punktgruppen:atoms-grid-f} gedanklich auch zwischen zwei leitende Platten, -scheint es als würden rechts mehr Positive Ionen in die Platte gedrückt werden und links umgekehrt. -Dies ist aber nicht mehr der Fall, wenn die Struktur sich nach oben und unten periodisch wiederholt. +scheint es als würden rechts mehr positive Ionen in die Platte gedrückt werden und links umgekehrt. +Dies ist aber nicht mehr der Fall, wenn sich die Struktur nach oben und unten periodisch wiederholt. +\par Struktur \subref{fig:punktgruppen:atoms-piezo-fh} zeigt \subref{fig:punktgruppen:atoms-piezo} in unter horizontaler Belastung. Was zwischen \subref{fig:punktgruppen:atoms-piezo-fv} und \subref{fig:punktgruppen:atoms-piezo-fh} zu beobachten ist, -ist dass das entstandene Ladungsdifferenz orthogonal zu der angelegten Kraft entsteht, +ist, dass die entstandene Ladungsdifferenz orthogonal zu der angelegten Kraft entsteht, im Gegensatz zu \subref{fig:punktgruppen:atoms-piezo-fh}. -Daraus kann man schlissen, dass \subref{fig:punktgruppen:atoms-piezo} keine Rotationssymmetrie von $90^\circ$ besitzen kann, -weil die Eigenschaften ändern bei einer $90^\circ$ Drehung. -Das Fehlen dieser Rotationssymmetrie kann mit betrachten von \subref{fig:punktgruppen:atoms-piezo} bestätigt werden. +Daraus kann man schliessen, dass \subref{fig:punktgruppen:atoms-piezo} keine Rotationssymmetrie von \(90^\circ\) besitzen kann, +weil die Eigenschaften der Struktur sich bei einer \(90^\circ\) Drehung ändern. +Das Fehlen dieser Rotationssymmetrie bestätigt sich auch wenn \subref{fig:punktgruppen:atoms-piezo} als Hexagon betrachtet wird. \subsection{Punktsymmetrie} -Piezoelektrische Kristalle können nicht Punktsymmetrisch sein. +Piezoelektrische Kristalle können nicht punktsymmetrisch sein. Kristallgitter, bei welchen eine Punktspiegelung eine symmetrische Operation ist, können keine piezoelektrische Kristalle bilden. -Auf Abbildung \ref{fig:punktgruppen:atomPiezo} ist bewusst \subref{fig:punktgruppen:atoms-piezo} ein nicht Punktsymmetrischer Kristall -mit einem Punktsymmetrischen \subref{fig:punktgruppen:atoms-grid}verglichen worden. -Als vereinfachte Erklärung kann mann sich wieder das Bild vor augen führen, eines Kristalles, +Auf Abbildung \ref{fig:punktgruppen:atomPiezo} ist bewusst \subref{fig:punktgruppen:atoms-piezo} ein nicht punktsymmetrischer Kristall +mit einem punktsymmetrischen \subref{fig:punktgruppen:atoms-grid} verglichen worden. +Als vereinfachte Erklärung kann man sich wieder das Bild eines Kristalles wie \subref{fig:punktgruppen:atoms-piezo} vor Augen führen, welcher unter Druck auf der einen Seite negative und der anderen Seite positive Ionen an seine Oberfläche verdrängt. -Spiegelt man nun den Kristall um den Gitterpunkt in der mitte des Kristalles, so würden die negativen Ionen auf den Positiven auf der anderen seite landen, +Spiegelt man nun den Kristall um den Gitterpunkt in der Mitte des Kristalles, so würden die negativen Ionen auf den positiven auf der anderen Seite landen, was der Definition einer Symmetrie deutlich widerspricht. \subsection{Vom Kristall zum Feuer} -Piezoelektrizität hat durchaus nutzen im Alltag. +Piezoelektrizität hat durchaus Nutzen im Alltag. Feuerzeuge welche nicht auf dem Prinzip beruhen einen Zündstein abzuschleifen, sonder ohne Verschleiss auf Knopfdruck einen Zündfunken erzeugen, basieren auf dem Prinzip der Piezoelektrizität. -Drückt der Nutzende auf den Zündknopf spannt sich eine Feder bis zu einer Konfigurierten Spannung. -Wird vom Nutzenden weiter gedrückt entspannt sich die Feder schlagartig und beschleunigt mit der gespeicherten Energie ein Hammer, +Drückt der Nutzende auf den Zündknopf, spannt sich eine Feder bis zu einer konfigurierten Spannung. +Wird vom Nutzenden fester zugedrückt entspannt sich die Feder schlagartig und beschleunigt mit der gespeicherten Energie ein Hammer, welcher auf das Piezoelement aufschlägt. -Der augenblicklich hohe Druck sorgt an den Piezokontakten für eine eben so Kurze aber hohe elekrische Spannung. +Der augenblicklich hohe Druck sorgt an den Piezokontakten für eine eben so kurze aber hohe elektrische Spannung. Die Spannung reicht aus, um eine Funkenstrecke zu überwinden und so eine entflammbares Gas zu entzünden. -Sollten Sie also eines Tages in die Situation geraten, in welcher Sie zwei verschiedene Kristalle vor sich haben -und ein piezoelektrisches Feuerzeug bauen müssen, -wobei Sie aber wissen, dass einer eine Punktsymmetrie aufweist, -versuche sie es mit dem anderen. +Sollte der Leser eines Tages in die Situation geraten, in welcher er zwei verschiedene Kristalle vor sich hat und ein piezoelektrisches Feuerzeug bauen musst, wobei bekannt ist, dass der eine eine Punktsymmetrie aufweist, empfiehlt es sich, sich am anderen zu versuchen. diff --git a/buch/papers/punktgruppen/references.bib b/buch/papers/punktgruppen/references.bib index a29640c..05c803f 100644 --- a/buch/papers/punktgruppen/references.bib +++ b/buch/papers/punktgruppen/references.bib @@ -26,7 +26,7 @@ @book{punktgruppen:lang-elt2, title = {Elektrotechnik 2}, - author = {Hans-Dieter Lang}, + author = {Prof. Hans-Dieter Lang Ph.D}, publisher = {Fachhochschule Ostschweiz Rapperswil}, year = {2020}, month = {2}, @@ -35,10 +35,20 @@ @online{punktgruppen:ouchem, title = {Symmetry in Crystallography}, - author = {Dept. of Chemistry \& Biochemistry, Chemical Crystallography Laboratory, University of Oklahoma}, + author = {Dept. of Chemistry \& Biochemistry{,} Chemical Crystallography Laboratory{,} University of Oklahoma}, year = {2019}, month = {11}, day = {17}, url = {http://archive.today/2021.07.22-083802/http://xrayweb.chem.ou.edu/notes/symmetry.html}, urldate = {2021-07-22}, } + +@online{punktgruppen:restriction, + title = {Structure of Materials: Allowed Rotational Symmetry in Crystals}, + author = {Prof. Silvija Gradecak-Garaj{,} Massachusetts Institute of Technology (MIT)}, + year = {2020}, + month = {4}, + day = {9}, + url = {https://www.youtube.com/watch?v=Ia2eHF1ZKoI}, + urldate = {2021-07-30}, +} diff --git a/buch/papers/punktgruppen/symmetry.tex b/buch/papers/punktgruppen/symmetry.tex index 0bb4aec..2067663 100644 --- a/buch/papers/punktgruppen/symmetry.tex +++ b/buch/papers/punktgruppen/symmetry.tex @@ -22,27 +22,28 @@ Wie wir jedoch später sehen werden, ist das Konzept der Symmetrie eigentlich vi In Abbildung \ref{fig:punktgruppen:geometry-example} haben wir einige Formen, die offensichtlich symmetrisch sind. Zum Beispiel hat das Quadrat eine Gerade, an deren es gespiegelt werden kann, ohne sein Aussehen zu verändern. Regelmässige Polygone mit \(n\) Seiten sind auch gute Beispiele, um eine diskrete Rotationssymmetrie zu veranschaulichen, was bedeutet, dass eine Drehung um einen Punkt um einen bestimmten Winkel \(360^\circ/n\) die Figur unverändert lässt. -Das letzte Beispiel auf der rechten Seite ist eine unendliche Rotationssymmetrie. Sie wird so genannt, weil es unendlich viele Werte für \(\alpha \in \mathbb{R}\) gibt, die die Form unverändert lassen. +Das letzte Beispiel auf der rechten Seite ist eine unendliche Rotationssymmetrie. Sie wird so genannt, weil es unendlich viele Werte für den Drehwinkel \(\alpha \in \mathbb{R}\) gibt, die die Form unverändert lassen. Ein Objekt kann mehr als nur eine Symmetrie aufweisen. -Als Beispiel, kann das Quadrat in Abbildung \ref{fig:punktgruppen:geometry-example} nicht nur um \(\sigma\) sondern auch Diagonal gespiegelt werden oder um \(90^\circ\) gedreht werden. +Als Beispiel, kann das Quadrat in Abbildung \ref{fig:punktgruppen:geometry-example} nicht nur um \(\sigma\) sondern auch diagonal gespiegelt werden oder um \(90^\circ\) gedreht werden. Fasst man die möglichen Symmetrien zusammen, entsteht eine Symmetriegruppe. \begin{definition}[Symmetriegruppe] - \(g\) und \(h\) sein umkehrbare Operationen, die ein mathematisches Objekt unverändert lassen. + Seien \(g\) und \(h\) umkehrbare Operationen, sogenannte Symmetrieoperationen, die ein mathematisches Objekt unverändert lassen. Die Komposition \(h\circ g\) definieren wir als die Anwendung der Operationen nacheinander. - Alle möglichen Operationen bilden unter Komposition eine Gruppe, die Symmetriegruppe genannt wird. + Alle möglichen Symmetrieoperationen bilden unter Komposition eine Gruppe, die Symmetriegruppe genannt wird. \end{definition} Eine Gruppe benötigt ausserdem auch zwingend ein neutrales Element, welches wir mit \(\mathds{1}\) bezeichnen. Die Anwendung der neutralen Operation ist gleichbedeutend damit, alles unverändert zu lassen. -\(\mathds{1}\) ist auch äquivalent dazu, eine Operation anzuwenden und sie dann rückgängig zu machen (ihre Inverse anzuwenden). - Die Definition der Symmetriegruppe ist mit der Kompositionsoperation gegeben, es wird aber auch oft als Multiplikation geschrieben. +Weiterhin muss in einer Gruppe für jede Operation \(g\) auch eine inverse Operation \(g^{-1}\) vorkommen, die intuitiv rückgängig macht, was \(g\) getan hat. % intuitiv weglassen oder anstelle sinnbildlich +Somit ist \(\mathds{1}\) auch äquivalent dazu, eine Operation und dann ihre Inverse anzuwenden. + Die Definition der Symmetriegruppe ist mit der Kompositionsoperation gegeben, sie wird aber auch oft als Multiplikation geschrieben. Das liegt daran, dass in manchen Fällen die Zusammensetzung algebraisch durch eine Multiplikation berechnet wird. Die Verwendung einer multiplikativen Schreibweise ermöglicht es, einige Ausdrücke kompakter zu schreiben, z.B. durch Verwendung von Potenzen \(r^n = r\circ r \circ \cdots r\circ r\) für eine wiederholte Komposition. \begin{definition}[Zyklische Untergruppe, Erzeuger] - \(g\) sei ein Element einer Symmetriegruppe \(G\). + Sei \(g\) ein Element einer Symmetriegruppe \(G\). Alle möglichen Kompositionen von \(g\) und \(g^{-1}\) bilden eine sogenannte zyklische Untergruppe von \(G\), wobei \(g\) Erzeuger der Untergruppe genannt wird. Die von \(g\) erzeugte Untergruppe \(\langle g \rangle = \left\{ g^k : k \in \mathbb{Z} \right\}\) wird mit spitzen Klammern bezeichnet. \end{definition} @@ -51,7 +52,7 @@ durch Verwendung von Potenzen \(r^n = r\circ r \circ \cdots r\circ r\) für eine Das bedeutet, dass \(G\) die Elemente \(a, aa, aaa, \ldots\) sowie \(a^{-1}, a^{-1}a^{-1}, \ldots\) und ein neutrales Element \(\mathds{1} = aa^{-1}\) enthält. \end{beispiel} \begin{beispiel} - Als anschaulicheres Beispiel, können wir eine Zyklische Untergruppe des \(n\)-Gon formalisieren. + Als anschaulicheres Beispiel, können wir eine zyklische Untergruppe des \(n\)-Gon formalisieren. Wir bezeichnen mit \(r\) eine Drehung im Gegenuhrzeigersinn von \(360^\circ/n\) um einen Punkt. Diese Definition reicht aus, um die gesamte Symmetriegruppe \[ @@ -63,15 +64,16 @@ durch Verwendung von Potenzen \(r^n = r\circ r \circ \cdots r\circ r\) für eine In ähnlicher Weise, aber weniger interessant enthält die Reflexionssymmetriegruppe \(\langle\sigma\rangle\) nur \(\left\{\mathds{1}, \sigma\right\}\), weil \(\sigma^2 = \mathds{1}\). \end{beispiel} -Wenn wir diese Idee nun erweitern, können wir mit einem Erzeugendensystemen +Wenn wir diese Idee nun erweitern, können wir mit einem Erzeugendensystem komplexere Strukturen aufbauen. -\begin{definition}[Erzeugendensysteme] +%@Naoki Are you ok with my grammar fixes I'm not 101% shore how to use the word Erzeugendensystem? +\begin{definition}[Erzeugendensystem] Jede disktrete Gruppe kann durch eines oder mehrere ihrer Elemente generiert werden. Wir lassen \(g_1, g_2, \ldots, g_n\) erzeugenden Elemente einer Symmetriegruppe sein. - Da es mehrere Erzeuger gibt, müssen auch die sogenannte Definitionsgleichungen gegeben werden, die die Multiplikationstabelle vollständig definieren. + Da es mehrere Erzeuger gibt, müssen auch die sogenannten Definitionsgleichungen gegeben werden, die die Multiplikationstabelle vollständig definieren. Die Gleichungen sind ebenfalls in den Klammern angegeben. - Die erzeugende Elementen zusammen mit der Definitionsgleichungen bauen ein Erzeugendensysteme. + Die erzeugenden Elementen bauen zusammen mit den Definitionsgleichungen ein Erzeugendensystem. \end{definition} \begin{beispiel} Wir werden nun alle Symmetrien eines \(n\)-Gons beschreiben, was bedeutet, dass wir die Operationen \(r\) und \(\sigma\) kombinieren. @@ -98,7 +100,7 @@ Dies ist jedoch keine Voraussetzung für eine Symmetrie, da es Symmetrien gibt, \subsection{Algebraische Symmetrien} Wir haben nun unseren Operationen Symbole gegeben, mit denen es tatsächlich möglich ist, Gleichungen zu schreiben. -Die anschliesende Frage ist dann, ob wir bereits mathematische Objekte haben, mit denen wir Gleichungen schreiben, die sich auf die gleiche Weise verhalten. +Die anschliessende Frage ist dann, ob wir bereits mathematische Objekte haben, mit denen wir Gleichungen schreiben, die sich auf die gleiche Weise verhalten. Die Antwort lautet natürlich ja. Um es formaler zu beschreiben, werden wir einige Begriffe einführen. \begin{definition}[Gruppenhomomorphismus] diff --git a/buch/papers/punktgruppen/tikz/projections.tex b/buch/papers/punktgruppen/tikz/projections.tex index 64ab468..e8a4a2e 100644 --- a/buch/papers/punktgruppen/tikz/projections.tex +++ b/buch/papers/punktgruppen/tikz/projections.tex @@ -44,7 +44,7 @@ \node[classcirc] (C2h) {} node[classlabel] {\(C_{2h}\)}; & \node[classcirc] (D2) {} node[classlabel] {\(D_{2}\)}; \\ - \node[classcirc] (D3d) {} node[classlabel] {\(D_{3d}\)}; & + \node[classcirc] (D3d) {} node[classlabel] {\(C_{3v}\)}; & \node[classcirc] (C2v) {} node[classlabel] {\(C_{2v}\)}; & \node[classcirc] (D2h) {} node[classlabel] {\(D_{2h}\)}; & \node[classcirc] (D3) {} node[classlabel] {\(D_{3}\)}; & |