diff options
Diffstat (limited to 'buch/papers/ifs/teil2.tex')
| -rw-r--r-- | buch/papers/ifs/teil2.tex | 122 |
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} |