aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/ifs/teil2.tex
diff options
context:
space:
mode:
authorNao Pross <np@0hm.ch>2021-06-20 19:11:28 +0200
committerNao Pross <np@0hm.ch>2021-06-20 19:11:28 +0200
commit0a850778d935434519f3b3a2a522ee37dcef073b (patch)
tree88476888a1f0a47e5813595beefe50a3f525343c /buch/papers/ifs/teil2.tex
parentRestructure (diff)
parentfix paper/ifs/references.bib (diff)
downloadSeminarMatrizen-0a850778d935434519f3b3a2a522ee37dcef073b.tar.gz
SeminarMatrizen-0a850778d935434519f3b3a2a522ee37dcef073b.zip
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'buch/papers/ifs/teil2.tex')
-rw-r--r--buch/papers/ifs/teil2.tex228
1 files changed, 199 insertions, 29 deletions
diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex
index bfd1684..143317a 100644
--- a/buch/papers/ifs/teil2.tex
+++ b/buch/papers/ifs/teil2.tex
@@ -3,38 +3,208 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Teil 2
+\section{Fraktale mit IFS
\label{ifs:section:teil2}}
\rhead{Teil 2}
-Sed ut perspiciatis unde omnis iste natus error sit voluptatem
-accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
-quae ab illo inventore veritatis et quasi architecto beatae vitae
-dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit
-aspernatur aut odit aut fugit, sed quia consequuntur magni dolores
-eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam
-est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci
-velit, sed quia non numquam eius modi tempora incidunt ut labore
-et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima
-veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam,
-nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure
-reprehenderit qui in ea voluptate velit esse quam nihil molestiae
-consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla
-pariatur?
+Wollen wir nun eine bestimmte Art anschauen, wie man Fraktale machen kann.
+Zur Veranschaulichung dieser Methode nehmen wir das Sierpinski Dreieck.
+\begin{figure}
+ \centering
+ \includegraphics[width=0.5\textwidth]{papers/ifs/images/sierpinski}
+ \caption{Sierpinski-Dreieck}
+ \label{ifs:sierpinski10}
+\end{figure}
+Wenn man das Dreieck genau anschaut, erkennt man schnell, dass es aus drei kleineren Kopien seiner selbst besteht.
+Es ist also ein Selbstähnliches Konstrukt.
+Diese Eigenschaft wollen wir uns zunutze machen.
-\subsection{De finibus bonorum et malorum
+
+Wir definieren das Dreieck mit Kantenlänge 1 als Menge $X$.
+Ausserdem bestimmen wir drei Funktionen, welche die gesamte Menge auf eine ihrer kleineren Kopien abbildet
+\begin{align*}
+ f_1(x,y)
+ =
+ \begin{pmatrix}
+ \frac{1}{2} & 0 \\
+ 0 & \frac{1}{2} \\
+ \end{pmatrix}
+ \begin{pmatrix}
+ x\\
+ y\\
+ \end{pmatrix}
+ ,\quad
+ f_2(x,y)
+ =
+ \begin{pmatrix}
+ \frac{1}{2} & 0 \\
+ 0 & \frac{1}{2} \\
+ \end{pmatrix}
+ \begin{pmatrix}
+ x\\
+ y\\
+ \end{pmatrix}
+ +
+ \begin{pmatrix}
+ \frac{1}{2} \\
+ 0
+ \end{pmatrix}
+ , \quad
+ f_3(x,y)
+ =
+ \begin{pmatrix}
+ \frac{1}{2} & 0 \\
+ 0 & \frac{1}{2} \\
+ \end{pmatrix}
+ \begin{pmatrix}
+ x\\
+ y\\
+ \end{pmatrix}
+ +
+ \begin{pmatrix}
+ \frac{1}{4} \\
+ \frac{1}{2}
+ \end{pmatrix}\\
+\end{align*}
+$f_1$ bildet das Dreieck auf das Teilstück unten links ab, $f_2$ auf das Teilstück unten rechts und $f_3$ auf das obere Teilstück.
+Wendet man alle drei Funktionen auf das Sierpinski-Dreieck an, entsteht also wieder ein Sierpinski-Dreieck.
+\begin{align*}
+ X = \bigcup\limits_{i = 1}^{3} f_i(X)
+\end{align*}
+Man kann sogar noch einen Schritt weiter gehen, und sagen: Wenn wir die Funktionen auf eine beliebige Startmenge anwenden, konvergiert die Menge gegen das Sierpinski-Dreieck.
+\begin{figure}
+ \centering
+ \subfigure[]{
+ \label{ifs:sierpconsta}
+ \includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski1}}
+ \subfigure[]{
+ \label{ifs:sierpconstb}
+ \includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski2}}
+ \subfigure[]{
+ \label{ifs:sierpconstc}
+ \includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski3}}
+ \subfigure[]{
+ \label{ifs:sierpconstd}
+ \includegraphics[width=0.25\textwidth]{papers/ifs/images/sierpinski6}}
+ \caption{Konstruktion eines Sierpinski-Dreiecks mit einem Schwarzen Quadrat als Start\\
+ (a) 1. Iteration (b) 2. Iteration (c) 3. Iteration (d) 5. Iteration}
+ \label{ifs:sierpconst}
+\end{figure}
+Im Beispiel der Abbildung \ref{ifs:sierpconst} sehen wir, wie das Bild nach jeder Iteration dem Sierpinski-Dreieck ähnlicher wird.
+Der Abstand zum Original wird immer kleiner, und konvergiert bei unendlich Iterationen gegen null.
+
+\subsection{Iterierte Funktionensysteme
\label{ifs:subsection:bonorum}}
-At vero eos et accusamus et iusto odio dignissimos ducimus qui
-blanditiis praesentium voluptatum deleniti atque corrupti quos
-dolores et quas molestias excepturi sint occaecati cupiditate non
-provident, similique sunt in culpa qui officia deserunt mollitia
-animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis
-est et expedita distinctio. Nam libero tempore, cum soluta nobis
-est eligendi optio cumque nihil impedit quo minus id quod maxime
-placeat facere possimus, omnis voluptas assumenda est, omnis dolor
-repellendus. Temporibus autem quibusdam et aut officiis debitis aut
-rerum necessitatibus saepe eveniet ut et voluptates repudiandae
-sint et molestiae non recusandae. Itaque earum rerum hic tenetur a
-sapiente delectus, ut aut reiciendis voluptatibus maiores alias
-consequatur aut perferendis doloribus asperiores repellat.
+In diesem Unterkapitel wollen wir die Erkenntnis, wie wir aus einer beliebigen Menge ein Sierpinski-Dreieck generieren können, verallgemeinern.
+
+
+$S_1,...,S_n$ sind Kontraktionen auf die Menge $D \subset \mathbb{R}^n$. Es gilt
+\begin{align}
+ |S_i(x) - S_i(y)| \leq c_i|x - y|
+\end{align}
+für jedes i mit einem $c_i < 1$. Dann existiert eine eindeutige kompakte Menge $F$ für die gilt
+\begin{equation}
+ F = \bigcup\limits_{i = 1}^{m} S_i(F)
+\end{equation}
+Weiter definieren wir die Transformation S auf kompakte Mengen ohne die leere Menge.
+\begin{equation}
+ S(E) = \bigcup\limits_{i = 1}^m S_i(E)
+\end{equation}
+Wird diese Transformation Iterativ ausgeführt, das heisst $S^0(E) = E, S^k(E) = S(S^{k-1}(E))$, und für jedes $i$ $S_i(E) \subset E$, gilt
+\begin{equation}
+ F = \bigcap\limits_{k = 1}^{\infty} S^k(E).
+\end{equation}
+In Worte gefasst bedeutet das, dass jede Gruppe von Kontraktionen iterativ ausgeführt, gegen eine eindeutige Menge konvergiert.
+Dies für jede Startmenge, solange diese ihre Transformierten wieder beinhaltet.
+Auf den Beweis wird verzichtet.
+\subsection{Beispiel: Barnsley-Farn}
+Der Barnsley-Farn, Abbildung \ref{ifs:farn}, ist ein weiteres Fraktal, welches mit einem IFS generiert werden kann.
+Wie man schnell erkennen kann, besteht der Farn aus Blättern, welche eine grosse Ähnlichkeit zum ganzen Farn haben.
+\begin{align*}
+ {S_1(x,y)}
+ =
+ \begin{pmatrix}
+ 0 & 0 \\
+ 0 & 0.16 \\
+ \end{pmatrix}
+ \begin{pmatrix}
+ x\\
+ y\\
+ \end{pmatrix}, \quad
+ {S_2(x,y)}
+ =
+ \begin{pmatrix}
+ 0.85 & 0.04 \\
+ -0.04 & 0.85 \\
+ \end{pmatrix}
+ \begin{pmatrix}
+ x\\
+ y\\
+ \end{pmatrix}
+ +
+ \begin{pmatrix}
+ 0 \\
+ 1.6
+ \end{pmatrix}\\
+ {S_3(x,y)}
+ =
+ \begin{pmatrix}
+ 0.2 & -0.26 \\
+ 0.23 & 0.22 \\
+ \end{pmatrix}
+ \begin{pmatrix}
+ x\\
+ y\\
+ \end{pmatrix}
+ +
+ \begin{pmatrix}
+ 0 \\
+ 1.6
+ \end{pmatrix}, \quad
+ {S_4(x,y)}
+ =
+ \begin{pmatrix}
+ -0.15 & 0.28 \\
+ 0.26 & 0.24 \\
+ \end{pmatrix}
+ \begin{pmatrix}
+ x\\
+ y\\
+ \end{pmatrix}
+ +
+ \begin{pmatrix}
+ 0 \\
+ 0.44
+ \end{pmatrix}\\
+\end{align*}
+In der Abbildung \ref{ifs:farncolor} sehen wir die vier Transformationen farblich dargestellt.
+$S_1$ erstellt den Stiel des Farnblattes (rot).
+Die Transformation bildet das Gesamte Blatt auf die Y-Achse ab.
+$S_2$ (grün) erstellt den Hauptteil des Farnes.
+Sie verkleinert und dreht das gesamte Bild und stellt es auf das Ende des Stiels aus $S_1$.
+$S_3$ bildet das gesamte Blatt auf das blaue Teilblatt unten Links ab.
+$S_4$ Spiegelt das Blatt und bildet es auf das magentafarbene Teilblatt ab.
+Wir führen im Zusammenhang mit dem Barnsley-Farn \cite{ifs:barnsleyfern} noch eine weitere Methode ein, um IFS auszuführen.
+Bis jetzt wurde immer davon gesprochen, die Transformationen auf die gesamte Menge anzuwenden.
+Bei komplizierteren IFS welche viele Iterationen brauchen, bis man den Attraktor erkennen kann, ist diese Methode ziemlich rechenintensiv.
+Eine Alternative ist das Chaosspiel \cite{ifs:chaos}.
+Bei dieser Methode werden die Transformationen nicht auf die Menge angewendet, sondern nur auf einen einzelnen Punkt.
+Der Startpunkt kann dabei ein beliebiger Punkt in $E$ sein.
+Es wird bei jedem Iterationsschritt nur eine Transformation, welche zufällig gewählt wurde, angewendet.
+Da, wie wir beim Barnsley-Farn gut sehen, dass nicht jede Transformation gleich viel des Bildes ausmacht, werden diese beim Chaosspiel gewichtet.
+Die Gewichtung erfolgt über den Anteil der Gesamtmasse.
+Im Fall des Barnsley-Fern wird $S_1$ in $1\%$, $S_2$ in $85\%$ und $S_3 \& S_4$ in $7\%$ der Iterationen ausgeführt.
+\begin{figure}
+ \centering
+ \makebox[\textwidth][c]{
+ \includegraphics[width=1.4\textwidth]{papers/ifs/images/farn}}
+ \caption{Barnsley-Farn}
+ \label{ifs:farn}
+\end{figure}
+\begin{figure}
+ \centering
+ \includegraphics[width=0.7\textwidth]{papers/ifs/images/farncolor}
+ \caption{Vier Transformationen des Barnsley-Farn}
+ \label{ifs:farncolor}
+\end{figure}