aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/ifs/teil2.tex
diff options
context:
space:
mode:
authormichael-OST <75078383+michael-OST@users.noreply.github.com>2021-06-24 09:53:05 +0200
committerGitHub <noreply@github.com>2021-06-24 09:53:05 +0200
commit716a1e2103b10e8fc1e2a32035f3e45bc3eccb54 (patch)
tree69a91574b751adf30bfffe9e6544e0b86cfefbd8 /buch/papers/ifs/teil2.tex
parentseveral changes (diff)
parentMerge pull request #25 from LordMcFungus/master (diff)
downloadSeminarMatrizen-716a1e2103b10e8fc1e2a32035f3e45bc3eccb54.tar.gz
SeminarMatrizen-716a1e2103b10e8fc1e2a32035f3e45bc3eccb54.zip
Merge branch 'AndreasFMueller:master' into master
Diffstat (limited to 'buch/papers/ifs/teil2.tex')
-rw-r--r--buch/papers/ifs/teil2.tex122
1 files changed, 84 insertions, 38 deletions
diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex
index 143317a..fd10634 100644
--- a/buch/papers/ifs/teil2.tex
+++ b/buch/papers/ifs/teil2.tex
@@ -14,13 +14,13 @@ Zur Veranschaulichung dieser Methode nehmen wir das Sierpinski Dreieck.
\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.
+Es besteht aus drei kleineren Kopien von sich selbst.
+Es ist also ein Selbstähnliches Gebilde.
Diese Eigenschaft wollen wir uns zunutze machen.
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
+Ausserdem bestimmen wir drei Funktionen
\begin{align*}
f_1(x,y)
=
@@ -63,13 +63,15 @@ Ausserdem bestimmen wir drei Funktionen, welche die gesamte Menge auf eine ihrer
\begin{pmatrix}
\frac{1}{4} \\
\frac{1}{2}
- \end{pmatrix}\\
+ \end{pmatrix},
\end{align*}
+welche die gesamte Menge auf eine ihrer kleineren Kopien abbildet.
$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.
+Wendet man alle drei Funktionen auf das Sierpinski-Dreieck an
\begin{align*}
- X = \bigcup\limits_{i = 1}^{3} f_i(X)
+ X = \bigcup\limits_{i = 1}^{3} f_i(X),
\end{align*}
+entsteht also wieder ein Sierpinski-Dreieck.
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
@@ -90,37 +92,44 @@ Man kann sogar noch einen Schritt weiter gehen, und sagen: Wenn wir die Funktion
\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.
+Der Abstand zum Original wird immer kleiner, und konvergiert gegen null.
\subsection{Iterierte Funktionensysteme
-\label{ifs:subsection:bonorum}}
-In diesem Unterkapitel wollen wir die Erkenntnis, wie wir aus einer beliebigen Menge ein Sierpinski-Dreieck generieren können, verallgemeinern.
+\label{ifs:subsection:IteratedFunktionensysteme}}
+In diesem Abschnitt 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
+$S_1,\dots,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
+für jedes i mit einem $c_i < 1$.
+Der Banachsche Fixpunktsatz besagt, dass für solche Kontraktionen ein Eindeutiges $A$ existiert, für das $S(A) = A$ gilt.
+Den Beweis kann man in \cite{ifs:Rousseau2012} nachlesen.
+Hat man nicht nur eine sondern mehrere Kontraktionen, dann existiert eine eindeutige kompakte Menge $F$ für die gilt
\begin{equation}
- F = \bigcup\limits_{i = 1}^{m} S_i(F)
+ F = \bigcup\limits_{i = 1}^{m} S_i(F).
\end{equation}
-Weiter definieren wir die Transformation S auf kompakte Mengen ohne die leere Menge.
+Weiter definieren wir die Transformation S auf kompakte Mengen $E$ ohne die leere Menge
\begin{equation}
- S(E) = \bigcup\limits_{i = 1}^m S_i(E)
+ S(E) = \bigcup\limits_{i = 1}^m S_i(E).
+ \label{ifs:transformation}
\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
+Wird diese Transformation Iterativ ausgeführt, das heisst $S^0(E) = E, S^k(E) = S(S^{k-1}(E))$, gilt
\begin{equation}
F = \bigcap\limits_{k = 1}^{\infty} S^k(E).
+ \label{ifs:ifsForm}
\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.
+Diese Menge ist auch als Attraktor eines IFS bekannt.
+Der Beweis für die Existenz eines eindeutigen Attraktors ist in \cite{ifs:fractal-geometry} beschrieben.
+
\subsection{Beispiel: Barnsley-Farn}
-Der Barnsley-Farn, Abbildung \ref{ifs:farn}, ist ein weiteres Fraktal, welches mit einem IFS generiert werden kann.
+Der Barnsley-Farn, Abbildung \ref{ifs:farn}, ist ein Beispiel eines 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)}
+Die vier affinen Transformationen
+\begin{align}
+ & {S_1(x,y)}
=
\begin{pmatrix}
0 & 0 \\
@@ -129,9 +138,9 @@ Wie man schnell erkennen kann, besteht der Farn aus Blättern, welche eine gross
\begin{pmatrix}
x\\
y\\
- \end{pmatrix}, \quad
+ \end{pmatrix}, \quad &
{S_2(x,y)}
- =
+ &=
\begin{pmatrix}
0.85 & 0.04 \\
-0.04 & 0.85 \\
@@ -145,7 +154,7 @@ Wie man schnell erkennen kann, besteht der Farn aus Blättern, welche eine gross
0 \\
1.6
\end{pmatrix}\\
- {S_3(x,y)}
+ & {S_3(x,y)}
=
\begin{pmatrix}
0.2 & -0.26 \\
@@ -159,9 +168,9 @@ Wie man schnell erkennen kann, besteht der Farn aus Blättern, welche eine gross
\begin{pmatrix}
0 \\
1.6
- \end{pmatrix}, \quad
+ \end{pmatrix}, \quad &
{S_4(x,y)}
- =
+ &=
\begin{pmatrix}
-0.15 & 0.28 \\
0.26 & 0.24 \\
@@ -175,26 +184,51 @@ Wie man schnell erkennen kann, besteht der Farn aus Blättern, welche eine gross
0 \\
0.44
\end{pmatrix}\\
-\end{align*}
-In der Abbildung \ref{ifs:farncolor} sehen wir die vier Transformationen farblich dargestellt.
-
+ \label{ifs:farnFormel}
+\end{align}
+, welche für die konstruktion des Farns benötigt werden sind in der Abbildung \ref{ifs:farncolor} farblich dargestellt.
+Das gesamte Farnblatt ist in der schwarzen Box.
+Auf diese werden die Transformationen angewendet
$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.
+$S_4$ spiegelt das Blatt und bildet es auf das magentafarbene Teilblatt ab.
+\subsection{Erzeugung eines Bildes zu einem IFS}
+Es gibt zwei verschiedene Methoden um das Bild zu einem IFS zu erzeugen.
+Die erste Methode ist wahrscheinlich die intuitivste.
+Wir beginnen mit einm Startbild, zum Beispiel ein Schwarzes Quadrat, und bilden dieses mit den affinen Transformationen des IFS ab.
+Das neue Bild, dass entsteht, ist die nächste Iterierte.
+Dieses wird wieder mit den Transformationen abgebildet.
+Wir wiederholen den letzten schritt, bis wir zufrieden mit der neusten Iterierten sind.
+
+Diesen Vorgang haben wir beim Sierpinski-Dreieck in Abbildung \ref{ifs:sierpconst} gebraucht.
+In Abbildung \ref{ifs:sierpinski10} ist die zehnte Iterierte zu sehen.
+Weitere Iterationen hätten in dieser Darstellungsgrösse kaum mehr einen Unterschied gemacht.
+
-Wir führen im Zusammenhang mit dem Barnsley-Farn \cite{ifs:barnsleyfern} noch eine weitere Methode ein, um IFS auszuführen.
+Die zweite Methode ist das Chaosspiel \cite{ifs:chaos}.
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.
+Bei komplizierteren IFS welche viele Iterationen brauchen, bis man den Attraktor erkennen kann, ist die erste Methode ziemlich rechenintensiv.
+Beim Chaosspiel 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.
+Da, wie wir beim Barnsley-Farn gut sehen, nicht jede Transformation gleich viel des Bildes ausmacht, werden diese beim Chaosspiel gewichtet.
+Je mehr eine Transformation kontrahiert, desto weniger Punkte braucht es um die resultierende Teilabbildung darzustellen.
+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.
+Wir sehen auch in Abbildung \ref{ifs:farncolor} gut, dass der rote Stiel, $S_1$, einiges weniger Punkte braucht als der grüne Hauptteil des Blattes, $S_2$.
+
+In Abbildung \ref{ifs:farnNoWeight} wurden die vier gleich stark gewichtet.
+Man sieht, dass trotzt gleich vieler Iterationen wie in Abbildung \ref{ifs:farn}, der Farn nicht so gut abgebildet wird.
+
+Am besten sieht man den Effekt einer schlechten Gewichtung in Abbildung \ref{ifs:farnrightWeight}.
+Hier wurde $S_4$, welches für das rechte untere Teilblatt zuständig ist, mit nur $1\%$ statt $7\%$ gewichtet.
+Man sieht, wie sich der Mangel an Punkten auf die anderen Abbildungen das Farnblattes auswirkt.
+In jeder Kopie des ganzen Farns fehlen die Punkte für dieses rechte untere Teilblatt.
+
+
+
\begin{figure}
\centering
\makebox[\textwidth][c]{
@@ -204,7 +238,19 @@ Im Fall des Barnsley-Fern wird $S_1$ in $1\%$, $S_2$ in $85\%$ und $S_3 \& S_4$
\end{figure}
\begin{figure}
\centering
- \includegraphics[width=0.7\textwidth]{papers/ifs/images/farncolor}
- \caption{Vier Transformationen des Barnsley-Farn}
+ \includegraphics[width=\textwidth]{papers/ifs/images/farncolor2}
+ \caption{Vier Transformationen des Barnsley-Farn in unterschiedlichen Farben}
\label{ifs:farncolor}
\end{figure}
+
+\begin{figure}
+ \centering
+ \subfigure[]{
+ \label{ifs:farnNoWeight}
+ \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnnotweight}}
+ \subfigure[]{
+ \label{ifs:farnrightWeight}
+ \includegraphics[width=0.45\textwidth]{papers/ifs/images/farnrightwight}}
+ \caption{(a) Chaosspiel ohne Gewichtung (b) $S_4$ zu wenig gewichtet}
+ \label{ifs:farnweight}
+\end{figure}