Facharbeit von René Rondot
1 1
Inhalt
2
Einführung
Es war schon immer das Ziel der Naturwissenschaften, Ursache und Wirkung
in Zusammenhang zu bringen. Es gibt viele Naturphänomene, bei denen das
problemlos möglich ist (zum Beispiel läßt sich leicht voraussagen,
daß ein Stein, den man fallenläßt nach unten fällt).
Es gibt jedoch auch Phänomene, bei denen das nicht so einfach möglich
ist. Als anschauliches Beispiel kann man das Wetter beobachten. Jeder weiß
aus eigener Erfahrung, daß sich das Wetter des nächsten Tages nicht
mit absoluter Sicherheit voraussagen läßt. Aber auch ein einfacheres
Beispiel wie der Wurf eines Würfels reicht zur Demonstration eines zufälligen
oder stochastischen Phänomens. Bis vor einiger Zeit ging man davon
aus, daß sich solche Situationen zumindest prinzipiell berechnen lassen,
wenn man nur genügend Daten sammelt und verarbeitet. Um beim Beispiel
des Würfelns zu bleiben: Es dürfte durchaus möglich sein, mit
großem technischen Aufwand den Wurf eines Würfels so zu organisieren,
daß das Ergebnis mit Sicherheit zu berechnen ist. Dieser Standpunkt
ist jedoch im Laufe dieses Jahrhunderts, vor allem in den letzten Jahren,
immer mehr ins Wanken gekommen. Man entdeckte, daß selbst einfache deterministische
Systeme aus nur wenigen Teilen ein stochastisches Verhalten erzeugen können.
Dieses Zufallsverhalten ist prinzipieller Natur und läßt sich auch
durch immer weiteres Sammeln von Informationen nicht berechnen. Man nennt
dieses Zufallsverhalten, das zwar noch von einem Rest an Ordnung durchdrungen
ist und nach festen Gesetzen entsteht, dessen Verlauf aber nicht vorhersagbar
ist deterministisches Chaos. Mittlerweile hat sich herausgestellt,
daß dieses Chaos in vielen Bereichen der Naturwissenschaften vorkommt.
In der Physik findet es sich zum Beispiel bei der Schwingung von Doppelpendeln,
bei verschiedenen Strömungen, bei Planetenbahnen in Doppelsternsystemen
oder sogar bei einem tropfenden Wasserhahn. In der Biologie ist es vor allem
bei der Entwicklung von Populationen vertreten, deren Schwankungen teilweise
recht chaotisch sind. Sogar in der Kriegsforschung wird mit Modellen aus der
Chaosforschung gearbeitet und die Medizin findet das Chaos in EKGs von Patienten
mit Herzflimmern. In der Mathematik wird das Wesen dieser Vorgänge untersucht
und man stellt fest, daß es sich durchweg um Rückkopplungsvorgänge
handelt. Untersucht man Modelle solcher Rückkopplungen anhand der Iteration
von Funktionen, findet man selbst dort ein Chaos – ein Begriff, der
in der Mathematik sonst eher ungewöhnlich ist. Daß sich daraus
dann auch noch bunte Bilder ergeben und man durch reines Experimentieren mathematische
Entdeckungen machen kann, dürfte so manchen, der nur die “trockene”
Schulmathematik kennt, dann vollends überraschen.
3 Grundlagen
3.1
Iteration reeller Funktionen
Iterieren einer Funktion heißt:
- Zu gegebenem Startwert x0 den Funktionswert x1 =
f (x0) berechnen.
- Den Wert x1 als neuen Startwert betrachten und Schritt 1 wiederholen.
Beispiel:
f(x) = λ · x, λ > 0
x
1 = f(x
0) = λ · x
0
x
2 = f(x
1) = f(λ · x
0) = λ
· λ · x
0 = λ² · x
0
x
3 = f(x
2) = f(λ² · x
0) =
λ² · λ · x
0 = λ³ · x
0
...
Allgemein:
x
1 = f(x
0)
x
2 = f(x
1) = f ° f(x
0)
...
x
n = f(x
n-1) = f ° f ° ... ° f(x
0)
= f
n(x
0)
Beispiele:
f(x) =
x
0 = 2, x
1 =
,
x
2 =
,
..., x
n =
Für n → ∞ konvergiert diese Folge nach 0.
f(x) = 3x divergiert für n → ∞ nach +∞.
f(x) = x + c divergiert abhängig von c nach +∞ oder -∞.
f(x) = x² zeigt folgendes Verhalten:
Das Verhalten dieser Funktion ist also abhängig vom Startwert.
3.2 Graphische Iteration
Der Graph einer Funktion f(x) wird zur graphischen Iteration in ein Koordinatensystem
eingetragen. Man beginnt mit einem Startwert für x und geht in der Zeichnung
nach oben (oder unten), bis man auf den Graphen trifft. An der y-Achse läßt
sich dann f(x) ablesen, das man als nächsten Ausgangswert einsetzt. Der
Wert muß also wieder an der x-Achse abgetragen werden. Dazu verwendet
man die 1. Winkelhalbierende, deren Gleichung bekanntlich y=x ist. Von dem
Punkt auf dem Graphen mit den Koordinaten (x|f(x)) geht man nach rechts (oder
links), bis man auf die Winkelhalbierende stößt. Die Koordinaten
sind dann (f(x)|f(x)). Von dort aus geht man wieder senkrecht bis zum Graphen
und wieder waagerecht zur Winkelhalbierenden und so weiter. Der Vorgang kann
beliebig oft wiederholt werden.
3.3 Begriffe
Die Definitionen sind im Wesentlichen aus [1] übernommen.
3.3.1 Orbit:
Der Orbit O
x eines Punktes x ist die Folge der Iterierten von
x:
O
x := { x, f(x), f(f(x)), ..., f
n(x), ... }
Der Grenzwert eines Orbits (falls existent) ist definiert als Grenzwert der
Folge der Iterierten von x:
3.3.2 Fixpunkt:
Ein Punkt x heißt Fixpunkt der Periode 1 (oder einfach Fixpunkt)
von f, wenn gilt f(x) = x (damit gilt auch fn(x) = x für alle
n) und Fixpunkt der Periode k, wenn gilt fk(x) = x.
Ein Punkt x heißt Fast-k-Fixpunkt von f, wenn gilt fk+1(x)=
fk(x) aber fn+1(x) ≠ fn(x) für
alle n < k (Spezialfall: Fast-0-Fixpunkte sind genau die Fixpunkte von
f).
Bildlich gesehen ist ein Fixpunkt der Periode 1 ein Punkt auf dem Graphen,
von dem man “nicht mehr wegkommt”, auch wenn man noch so oft iteriert.
Da die Gerade y=x (1. Winkelhalbierende) genau diese Bedingung erfüllt,
findet man solche Fixpunkte immer an den Schnittpunkten der Funktion mit der
ersten Winkelhalbierenden. Ein Fixpunkt höherer Periode wird zwar wieder
verlassen, aber nach einer bestimmten Zahl weiterer Iterationen wieder erreicht.
3.3.3 Attraktor
und Repellor:
Ein Fixpunkt x heiß Attraktor (anziehender Fixpunkt), wenn es eine
Umgebung Uδ(x) gibt, so daß für alle y ε Uδ
gilt: Der Grenzwert des Orbits Oy ist x.
Ein Fixpunkt x heiß Repellor (abstoßender Fixpunkt), wenn es eine
Umgebung Uδ(x) gibt, so daß für alle y ε Uδ
gilt: Der Grenzwert des Orbits Oy ist nicht aus Uδ(x).
Graphisch gesehen bewegt man sich mit jeder Iteration weiter auf einen Attraktor
zu, bis man ihn evtl. erreicht. Von einem Repellor bewegt man sich immer weiter
weg.
Für einen attraktiven Fixpunkt p heißt das maximale Intervall der
x-Werte, deren Orbit nach p konvergiert, Einzugsbereich des Attraktors p.
Wird eine Funktionenfamilie (abhängig z. B. vom Parameter µ) betrachtet,
so heißt für einen Fixpunkt p das maximale µ-Intervall, für
das p ein Attraktor ist, der Stabilitätsbereich des Attraktors p.
3.4 Hauptsätze
Die Funktion f(x) sei beliebig oft stetig differenzierbar (stetig differenzierbar
heißt, daß die Ableitungen stetig sind). Weiter sei der Punkt
p Fixpunkt der Periode n⊂N, also f
n(p) = p.
Satz 1: Wenn gilt | (f
n)’(p) | < 1, dann ist p
Attraktor.
Beweis (nach [1]):
Für die Periode 1: f(p) = p und | f’(p) | < 1.
Erste Iteration:
Wegen der Stetigkeit von f’(x) gibt es für alle x in einem hinreichend
kleinen Intervall U = ] p - ε, p + ε [ ein A < 1 mit | f’(x)
| < A. Mit f(p) = p und x ⊂ U ergibt sich | f(x) - p | = | f(x) -
f(p) |.
Nach Anwendung des Mittelwertsatzes
[1]
ergibt sich daraus folgende Gleichung:
| f(x) - f(p) | = | f’(ξ) | · | x - p |
Dabei ist ξ eine Stelle zwischen x und p. Also gilt f’(ξ)
< A < 1.
Insgesamt folgt daraus: | f(x) - p | = | f(x) - f(p) | < A | x - p | <
A · ε < ε.
Wegen | f(x) - p | < ε gilt f(x) ⊂ U und wegen | f(x) - p |
< | x - p | liegt f(x) sogar näher an p als x.
Bei den weiteren Iterationen ergibt sich | f
n(x) - p | < A
n
| x - p |. Daraus folgt wegen A < 1 die Existenz des angegebenen Grenzwertes.
Satz 2: Wenn gilt | (f
n)’(p) | > 1, dann ist p
Repellor.
Der Beweis verläuft analog zu dem des ersten Hauptsatzes.
4
Die logistische Funktion
Ein Anwendungsbeispiel für die Iteration ist die Untersuchung der
Entwicklung von Tierpopulationen. In einem Räuber-Beute-Modell schwankt
die Anzahl der Räuber und der Beutetiere immer entgegengesetzt. Um diese
Entwicklung zu beschreiben braucht man eine Funktion, die nicht ins Unendliche
wächst und bei der die Population auch nicht ausstirbt. Pierre-Francois
Verhulst (1804-1849) fand folgende Funktion:
fµ(x )= x + µ x (1-x) mit µ > 0 (logistische
Funktion)
Betrachtet man das Verhalten dieser Funktion bei der Iteration, so läßt
sich ein interessantes Verhalten feststellen: Je nach Wert des Parameters
µ hat diese Funktion entweder einen Fixpunkt, mehrere Fixpunkte oder
gar keinen.
Die Funktion läßt sich zur weiteren Betrachtung vereinfachen, indem
a = µ + 1 gesetzt wird. Es ergibt sich folgende (quadratische) Funktion:
fa(x) = a x (1-x).
Man beobachtet jetzt für verschiedene Intervalle von a ein unterschiedliches
Verhalten bei der Iteration.
4.1 Der Bereich
0 < a < 1
Es gibt zwei Fixpunkte der Periode 1, nämlich den Ursprung 0 und p
=
< 0. Der Ursprung ist Attraktor, der Punkt p Repellor.
Beweis:
Mit f’(0) = a < 1 und f’(p) = 2- a > 1 ist nach den beiden
Hauptsätzen der Beweis erbracht.
4.2 Der Fall a
= 1
Die Parabel liegt unterhalb der 1. Winkelhalbierenden und hat nur einen
Punkt mit ihr gemeinsam, nämlich den Punkt (0|0). Dieser Punkt ist also
der einzige Fixpunkt der Funktion. Für 0 < x < 1 ist der Fixpunkt
anziehend, anderenfalls abstoßend.
Beweis:
Weil f’(0) = 1 ist, können die beiden Hauptsätze nicht zum
Beweis herangezogen werden. Der einfachste Beweis führt in diesem Fall
über die graphische Iteration durch ausprobieren. Man kann leicht erkennen,
daß bei Startwerten im Bereich 0 < x0 < 1 die graphische
Iteration treppenförmig auf den Ursprung zuläuft.
Der Punkt 1 bleibt, wie bei a < 1 abstoßender fast-1-Fixpunkt, das
heißt, bei einem x-Wert von 1 landet man nach einer Iteration direkt
auf dem Ursprung und bleibt dort auch nach weiteren Iterationen stehen.
Eine graphische Iteration für a=1 also für f(x) = x (1-x) führt
nach 20 Iterationsschritten mit dem Startwert x0 = 0,5 zu folgendem
Bild:
Abb. 4.1: Iteration für a=1.0 mit Startwert 0.25
4.3 Der Bereich
1 < a < 3
In diesem Bereich ist nur das Intervall [0,1] für x interessant, weil
für x < 0 und x > 1 stets
gilt.
Es ergeben sich zwei Fixpunkte der Periode 1, da sich Parabel und Diagonale
zweimal schneiden.
Der Ursprung ist Repellor, der Punkt p=
ist Attraktor.
Abb. 4.2: Iteration für a=1.6 und x0=0.15 Abb. 4.3:
Iteration für a=2.8 und x0=0.25
Wenn 1 < a ≤ 2 ist, beobachtet man eine treppenstufenförmige
Annäherung an den Attraktor, wenn 2 < a < 3 ist ergibt sich eine
Spirale.
4.4 Der Bereich
a > 3
In diesem Bereich wird die Dynamik wesentlich komplizierter. Es gibt dramatische
Veränderungen.
Auch hier sind die Punkte 0 und p noch Fixpunkte der Periode 1, jedoch mit
abstoßendem Charakter.
Hier gibt es jetzt jedoch auch Fixpunkte der Periode 2, das heißt es
gibt zwei Punkte auf der Funktion, auf die man immer wieder abwechselnd gelangt.
Um diese zu finden, muß die Funktion f
2(x) = f(f(x)) = a
2
x ( 1 - x ) ( 1 - ax ( 1- x) ) untersucht werden. Man muß also die Lösung
zu f
2(x) = x finden. Es ergeben sich zwei reelle voneinander verschiedene
Lösungen für a > 3. Wenn a sogar größer als 1 +
= 3,449... wird, gibt es Fixpunkte der Periode 4. Es hat also eine Periodenverdopplung
stattgefunden.
In der folgenden Abbildung sind nur die 100. bis 200. Iteration dargestellt,
die ersten 100 Iterationen wurden zwecks besserer Übersicht ausgeblendet,
so daß das Einpendeln nicht erscheint.
Abb. 4.4: Graphische Iteration für a=3.4 (links) bzw.3.5 (rechts)
mit Startwert 0.1 nach 200 Iterationen (davon 100 unsichtbar). Periodenlänge
ist 2 bzw. 4.
5
Das Feigenbaum-Diagramm
Wenn man a schrittweise erhöht, bemerkt man noch weitere Periodenverdopplungen.
Um dies anschaulich darzustellen wechselt man das Koordinatensystem. Auf der
x-Achse trägt man den Parameter a auf und auf der y-Achse die x-Werte
der Attraktoren. Die entstehende Grafik nennt man nach ihrem “Erfinder”
Mitchell J. FEIGENBAUM Feigenbaum-Diagramm. Bei jeder Periodenverdopplung
gabelt sich der Graph, man spricht daher auch von einer Bifurkation
(lat. furka = Heugabel).
Diese Zahlen lassen sich von Hand schon nur noch schwer errechnen. Wenn die
Perioden eine Länge von 8 und mehr erreichen, ist die Rechnung schon
extrem aufwendig. Um das gesamte Feigenbaum-Diagramm wie oben dargestellt
zu erstellen, ist schon ein enormer Rechenaufwand nötig. Was liegt also
näher, als den Rechenknecht Computer darauf anzusetzen. Dabei läßt
man den Rechner eine bestimmte Zahl von Iterationen durchführen (je mehr
es sind, desto genauer wird das Bild), bei denen er noch nichts zeichnet (wieder
um das Erscheinen des Einpendelns zu verhindern). Danach läßt man
ihn wiederum eine bestimmte Anzahl Iterationen durchführen, bei denen
er jeweils den x-Wert in das Diagramm einzeichnet. Die hier gezeigte Abbildung
entstand mit dem in Anhang A abgedruckten PASCAL-Programm mit 1000 unsichtbaren
und 100 sichtbaren Iterationen.
Abb. 5.1: Feigenbaum-Diagramm im Bereich a=0 bis a=4 mit Kennzeichnung
der ersten beiden Bifurkationen bei a=3 und a=1+.
5.1 Die Feigenbaum-Konstante
Feigenbaum fand auch eine wichtige Konstante, die nach ihm benannt wurde.
Die Feigenbaum-Konstante δ berechnet sich folgendermaßen (wenn
man die i-te Bifurkation als b
i bezeichnet):
Auf den ersten Blick ist das bloß ein Zahl, die das Verhalten der logistischen
Funktion bei der Iteration beschreibt. Feigenbaum zeigte jedoch durch seine
Forschungen, daß diese Zahl universell ist und auch bei anderen Funktionen
auftaucht. Die Zahl konnten nur mit dem Computer ermittelt werden. Oscar E.
LANFORD fand zwar 1982 einen mathematischen Beweis, kam aber auch nicht ohne
Computer aus [1].
Auch der Abstand zwischen den einzelnen “Gabelzinken” (bezeichnet
als d
i für die i-te Bifurkation) ergibt eine ähnliche
(ebenfalls universelle) Konstante, wenn man sie in folgendes Verhältnis
setzt:
5.2 Das Chaos
Bei der logistischen Funktion beobachtet man Bifurkationen bis a=3.5699...
. Dieser Wert wird als b
∞ bezeichnet und läßt
sich nur durch Ausprobieren finden. Wenn a> b
∞ wird, wird
das Verhalten bei der Iteration chaotisch, wie auch im Feigenbaum-Diagramm
leicht zu erkennen ist. Die Werte springen wild durcheinander und das Verhalten
scheint absolut unverhersagbar zu werden. Eine graphische Iteration in diesem
Bereich läßt dies gut erkennen:
Abb. 5.2: Graphische Iteration für a=3.8 mit Startwert 0.6 nach
100 Iterationen
Abb. 5.3: Dieselbe graphische Iteration nach 5000 Iterationen
In den Abbildungen erkennt man deutlich, daß nach einer großen
Anzahl von Iterationen fast jeder Wert der Funktion einmal erreicht worden
ist. Das Verhalten ist also absolut chaotisch und es ist kein Attraktor zu
erkennen.
Betrachtet man das Feigenbaum-Diagramm genau, so fällt ein weißer
Bereich um a=3.84 auf. In diesem Bereich scheint sich tatsächlich wieder
eine Ordnung zu ergeben. Für a=3.84 ist die Periodenlänge = 3. Gut
zu erkennen ist dies auf einer Ausschnittsvergrößerung des Bereiches
3.84 bis 3.852:
Abb. 5.4: Feigenbaum-Diagramm im Bereich a=3.84 bis a=3.852.
Führt man für a=3.84 eine graphische Iteration durch, läßt
sich diese Periode tatsächlich erkennen.
Abb. 5.5: Iteration für a=3.84 mit Startwert 0.1
nach 200 Iterationen (davon 100 unsichtbar)
Interessanterweise findet man in diesem Bereich mit 3 eine ungerade Periodenlänge,
während der erste Bifurkationsbereich nur gerade Periodenlängen
aufzuweisen hatte (außer der 1). Nach der ersten folgenden Bifurkation
wird diese aber (notwendigerweise) wieder gerade. An anderen Stellen im Feigenbaum-Diagramm
finden sich jedoch nach dem Satz von A. N. SARKOWSKII auch Periodenlängen
für alle n⊂
Ð [1].
Streckt man den Ausschnitt des Feigenbaum-Diagrammes auch in y-Richtung, so
macht man eine verblüffende Entdeckung: Man erhält (fast) dasselbe
Bild wie vor der Vergrößerung (siehe Abb. 5.6 und 5.7). Diese Phänomen
nennt man Selbstähnlichkeit.
Abb. 5.6: Feigenbaum-Diagramm im Intervall Abb. 5.7: Feigenbaum-Diagramm
im Intervall
[0.45;0.55] für y, [3.84;3.856] für a [0.0;1.0] für y, [2.8;4.0]
für a
6
Selbstähnlichkeit fraktaler Punktmengen
6.1 Definition
der Selbstähnlichkeit (aus [1])
Eine Punktmenge M heißt selbstähnlich, wenn man endlich viele
echte Teilmengen Ti M mit ∪Ti = M finden kann,
so daß für alle i gilt M = αi (Ti).
Dabei sind αi Ähnlichkeitsabbildungen.
6.2 Selbstähnlichkeitsdimension
Die klassische Definition der Dimension lautet:
.
Dabei ist N die Anzahl der Substitutionsabschnitte und k der Skalierungsfaktor.
An einem Beispiel für 3-Dimensionalität sei dies hier kurz gezeigt.
Ein Würfel der Seitenlänge 4 cm besteht aus 64 Würfel der Seitenlänge
1 cm. Der Skalierungsfaktor ist also k=4, die Anzahl der Würfel ist N=64.
Die Dimension ist also
d kann auch keine natürliche Zahl sein. Man spricht dann von einer fraktalen
Punktmenge. Diese Formel läßt sich noch folgendermaßen umformen:
Daraus ergibt sich:
Als Beispiel wird im Folgenden das Sierpinski-Dreieck betrachtet.
6.3 Das Sierpinski-Dreieck
Abb. 6.1: Entstehung des Sierpinski-Dreiecks (aus [4])
Die Konstruktionsvorschrift für das nach Waclaw SIERPINSKI benannte Dreieck
lautet folgendermaßen:
Ausgangspunkt ist ein gleichseitiges Dreieck. Man wiederholt die folgenden
Schritte:
- die Mittelpunkte der Dreieckseiten geradlinig miteinander verbinden
- das mittlere der auf diese Weise gebildeten Dreiecke entfernen
Dieses Verfahren wird bei jedem Schritt auf alle noch vorhandenen Dreiecke
angewendet (s. Abb. 6.1).
Das Ergebnis ist ein “durchlöchertes” Dreieck, das einige
bemerkenswerte Eigenschaften hat.
6.3.1 Fläche
des Sierpinski-Dreiecks
Bezeichnet man den Flächeninhalt der Ausgangsfläche mit A und
die Flächeninhalte des Sierpinski-Dreiecks nach der i-ten Durchführung
mit F
i, läßt sich der Flächeninhalt der “fertigen”
Figur (also nach unendlich vielen Entfern-Vorgängen) berechnen:
F
2 = A - δ
2 (δ
2 ist die Fläche,
die entfernt wird, und damit
A)
F
2 =
A
F
3 = F
2 – 3 · δ
3 (δ
3
=
δ
2)
F
3 = F
2 -
δ
2 =
F
4 = F
3 – 3² · δ
4 =
Allgemein gilt:
F
n =
Betrachtet man die Fläche nach unendlich vielen Schritten ergibt sich
ein erstaunliches Ergebnis:
Es bleibt also keine Fläche übrig!
6.3.2 Länge
des Randes des Sierpinski-Dreiecks
Wenn man keine Dreiecksseiten mehrfach zählt und von einem Ausgangsrand
von R
1 = U ausgeht läßt sich der Rand nach n Schritten
folgendermaßen berechnen:
R
2 = R
1 +
R
1 =
(weil die Seitenlängen immer halbiert werden)
R
3 = R
2 +
R
2 =
Daraus folgt allgemein:
R
n = R
n-1 +
R
n-1 =
Betrachtet man auch hier den Grenzwert nach unendlich vielen Schritten darf
man sich erneut wundern:
Der Rand wird also unbegrenzt immer länger.
6.3.3 Dimension
des Sierpinski-Dreiecks
Wie in den beiden vorherigen Kapiteln gezeigt wurde, hat das Sierpinski-Dreieck
keine Fläche, aber einen unendlich langen Rand. Das heißt, es ist
mehr als eindimensional, aber weniger als zweidimensional. Es hat also eine
gebrochene (
fraktale) Dimension.
Nach der Formel für die Selbstähnlichkeitsdimension (das Sierpinski-Dreieck
ist selbstähnlich) berechnet sich die Dimension folgendermaßen:
Anzahl der Substitutionsabschnitte: N = 3 (aus einem Dreieck werden drei)
Skalierungsfaktor: k = 2 (die Seitenlängen sind dann halb so lang)
=
6.4 Die Sierpinski-Pyramide
Die Konstruktionsvorschrift ist ähnlich der des Sierpinski-Dreiecks:
Ausgangspunkt ist ein regulärer Tetraeder. Man wiederholt die folgenden
Schritte:
- die Mittelpunkte der Seiten geradlinig miteinander verbinden
- den entstehenden Oktaeder entfernen
Dieses Verfahren wird bei jedem Schritt auf alle noch vorhandenen Tetraeder
angewendet.
Abb. 6.2: Sierpinski-Pyramide (aus [1])
Das Ergebnis ist eine durchlöcherte Pyramide (s. Abb. 7.1).
Berechnet man die Dimension der Sierpinski-Pyramide, macht man die erstaunliche
Entdeckung, daß diese nicht fraktal ist, sondern ganzzahlig, wie sich
aus folgender Rechnung ergibt:
Anzahl der Substitutionsabschnitte: N = 4 (aus einem Tetraeder werden vier)
Skalierungsfaktor: k = 2 (die Seitenlängen sind dann halb so lang)
=
Erstaunlicherweise ist die Sierpinski-Pyramide also zweidimensional. Stellt
man einige Überlegungen zu Volumen, Oberfläche und Rand der Pyramide
an, läßt sich dies auch geometrisch erschließen. Ich verzichte
hier auf eine weitere detaillierte Rechnung und stelle fest: Das Volumen geht
gegen null, das heißt, die Dimension ist kleiner als 3. Der Rand wird
unendlich lang, das heißt die Dimension ist größer als 1.
Die Oberfläche bleibt überraschenderweise konstant, wie man leicht
am Bild erkennt, also ist die Dimension tatsächlich 2.
7
Die fraktale Dimension
7.1 Die Küstenlinie
Englands
Abb. 7.1: Approximation mit fester Zirkelweite (aus [1])
Ein interessantes und beliebtes Beispiel für die Dimensionsberechnung
ist die Küstenlinie Englands. Diese ist zwar nicht selbstähnlich,
aber auch sehr zerklüftet. Hat sie also möglicherweise auch eine
fraktale Dimensionszahl? Auf dem Weg zur Beantwortung dieser Frage, muß
erst einmal die Länge der Küste Englands ermittelt werden. Hierbei
macht man eine erstaunliche Entdeckung: die Küste Englands ist unendlich
lang. Diese Ergebnis erhält man, wenn man durch rein empirisches Vorgehen
die Küste Englands abmißt. Dazu verwendet man einen Stechzirkel
der Öffnungsweite r. Man approximiert die geschlängelte Küste
also durch einen Polygonzug mit lauter gleich langen Seiten (s. Abb. 7.1).
Je kleiner man die Zirkelöffnung wählt, um so länger wird die
Küste (das heißt, die Küste wird natürlich nicht länger,
aber man erhält ein größeres Meßergebnis), weil ja auch
kleinere Buchten abgezirkelt werden. Wenn r die Länge einer Polygonseite
angibt und N(r) ihre Anzahl, dann gilt für die Gesamtlänge des Polygonzuges
L(r) = r N(r). Trägt man die Funktion L(r) in ein doppeltlogarithmisches
Koordinatensystem ein und verbindet die Punkte durch ein Gerade, so kann man
deren Steigung angeben. Lewis F. RICHARDSON (1881-1953) ermittelte für
die Küste Englands m ≈ -0.23. Betrachtet man den Grenzwert der
Funktion für r → 0 so ergibt sich, daß x = ln r → -∞
und y = ln L(r) → +∞, also L → +∞. Die Küste
Englands (und natürlich jede andere Küste) ist also unendlich lang
bzw. ihre Länge nicht meßbar. Will man jetzt die Dimension berechnen,
muß man sich etwas einfallen lassen. Zuerst geht man vom einfachsten
Fall aus, nämlich einer Küstenlinie in Form einer Geraden. m ist
dann 0, weil bei Veränderung von r die Länge L konstant bleibt.
Die Dimension (nach dem klassischen Dimensionsbegriff) ist dann 1. Die Definition,
die jetzt festgelegt wurde setzt m = 1 – d. Die Küste Englands
hat dann die Dimension d ≈ 1.23. Diese Dimension ist eine gebrochene
Zahl, also ist die Küste Englands ein Fraktal.
7.2 Allgemeine
Formel
Durch einige Umformungen der erhaltenen Formeln kommt man auf folgende
allgemeine Formel für die fraktale Dimension d
f:
8
Mandelbrot- und Julia-Mengen
Erweitert man die in Kapitel 3 und 4 benutzen Verfahren auf den Körper
" der komplexen Zahlen und veranschaulicht
diese in der Gaußschen Zahlenebene ergeben sich weitere interessante
Zusammenhänge und Entwicklungen bis hin zum sogenannten “Apfelmännchen”,
dem Wahrzeichen der Chaos-Forscher und dem bekanntesten Fraktal überhaupt.
Die im Kapitel 3.1 vorgestellte Iteration reeller Funktionen wird jetzt mit
komplexen Funktionen durchgeführt. Die im Folgenden betrachtete Funktion
ist die spezielle quadratische Funktion:
fc(z) = z² + c mit z, c ⊂ ".
8.1 Mandelbrot-Mengen
Zum Berechnen der Mandelbrot-Menge (benannt nach Benoit B. MANDELBROT)
hält man z fest und wählt dann für c verschiedene Werte, also
verschiedene Punkte der Gauß-Ebene. Weil c variiert, spricht man auch
von der c-Ebene.
Mit z
0 = 0 ergibt sich eine relativ einfache Rechnung. Die Iterationen
gestalten sich dann so:
c
1 = f
c(0) = c, c
2 = f
c (c
1)
= c
2 + c, c
3 = f
c(c
2) = c
4
+ 2c
3 + c
2 + c , ...
Beispiel: c = 2i
c
2 = -4 + 2i, c
3 = 12 – 14i, c
4 = -52
– 344 i, ...
Für die Mandelbrot-Menge ist jetzt relevant, ob diese Folge divergiert
oder konvergiert. Um dies zu entscheiden betrachtet man anstelle der Zahlen
c
n = x
n + i y
n deren Beträge |c
n|
=
. Es entsteht dann eine Folge reeller Zahlen, deren Divergenz oder Konvergenz
man wie üblich bestimmen kann. Im Beispiel sieht diese Folge so aus:
|c
1| =2, |c
2| =
, |c
3| =
, |c
4| =
Diese Folge ist eindeutig divergent. Nimmt man der Reihe nach die Punkte c
der Zahlenebene und markiert Punkte der Nichtdivergenz schwarz. Allerdings
ist diese Aufgabe viel zu aufwendig, um sie von Hand zu erledigen. Es muß
also wieder einmal der Computer als Rechenknecht dienen. Das Vorgehen ist
ähnlich wie beim Feigenbaum-Diagramm. Man läßt den Computer
eine bestimmte Anzahl von Iterationen durchführen und überprüft
dann, ob die Folge eine bestimmte Grenze nicht überschreitet. Das Verfahren
ist zwar streng genommen ungenau, aber die einzige realistische Möglichkeit.
Die Menge der gefundenen Punkte wird als
Mandelbrot-Menge bezeichnet
(dies gilt auch für andere komplexe Funktionen). In der Schreibweise
der Mengenlehre sieht ihre Definition so aus:
M = { c ⊂
" | |c
n|
< A, n ≤ N } (realistische Mandelbrot-Menge)
oder im Idealfall (nach unendlich vielen Iterationen):
M = { c ⊂
" |
|c
n|
∞ } (ideale Mandelbrot-Menge)
A ist also bei der realistischen Mandelbrot-Menge die Grenze für c, an
der der Punkt als divergent angesehen wird und N die Zahl der Iterationen,
bei der er als konvergent erscheint. Mit dem in Anhang B abgedruckten Programm
ergab sich dieses Bild:
Abb. 8.1: Mandelbrot-Menge berechnet mit A=2 und N=20
Das Apfelmännchen hat eine ganze Reihe mathematischer Eigenschaften,
die teilweise bewiesen sind, teilweise aber auch nicht. Aufgrund des begrenzten
Umfangs dieser Facharbeit, beschränke ich mich hier darauf, die einfachste
Eigenschaft (nämlich die Symmetrie) zu beweisen und einige weitere Eigenschaften
anzugeben.
Satz: Das Apfelmännchen ist zur reellen Achse symmetrisch.
Beweis (nach [1]):
Betrachtet man einen Punkt c = x + iy der c-Ebene, der Element der Mandelbrot-Menge
ist, so gilt
|c
n|
∞. Der Punkt, der bezüglich der x-Achse “gegenüber”
liegt, heißt komplex konjugierter Punkt
Ç
= x – iy. Nach einer Iteration ergeben sich für c und
Ç
die folgenden Werte:
f
c(c) = c
2 + c = (x
2 – y
2
+ x) + i (2xy + y)
f
c(
Ç)
=
Ç2
+
Ç
= (x
2 – y
2 + x) – i (2xy + y)
Es ist also |f
c(c)| = |f
c(
Ç)|.
durch vollständige Induktion gelangt man über |f
n(c)|
= |f
n(
Ç)|
zu
|f
n(c)| =
|f
n(
Ç)|
und damit ist
Ç
⊂ M.
Als weitere Eigenschaft läßt sich angeben, daß M in eine
Kreisscheibe mit dem Mittelpunkt 0 und dem Radius 2 eingebettet ist (Beweis
siehe [1]). Außerdem ist der Hauptkörper des Apfelmännchens
durch eine kardiodenförmige Kurve begrenzt. Die Gleichung der Randkurve
ist (nach [1]) c =
, mit t ⊂
3.
8.2 Ausschnittsvergrößerungen
des Apfelmännchens
Ähnlich wie beim Feigenbaum-Diagramm lassen sich auch bei der Mandelbrot-Menge
Ausschnittsvergrößerungen durchführen, die zu immer neuen
Bildern führen, in denen auch das Apfelmännchen immer wieder auftaucht,
aber auch andere Strukturen wie Äste, Schnecken, Spiralen, Seepferdchen
usw. Zeitler und Neidhardt schreiben in [1]:
“Man sollte den Rand des Apfelmännchens selber mit dem ‚Mikroskop‘
absuchen. Da dieser Rand unendlich lang ist, kann man Neuland beschreiten
und noch nie gesehene Bilder erzeugen. Selber Forscher sein! Es lohnt sich!”
Und damit die Ergebnisse wirklich “schön” werden, wendet
man einen Trick an, um die Bilder von Schwarz/Weiß zur Farbe zu bringen.
In dem Bereich, in dem normalerweise keine Punkte gesetzt werden, werden jetzt
farbige Punkte gesetzt, deren Farbe vom Wert für N abhängt, bei
dem es zur Divergenz kommt. Das gesamte Apfelmännchen selbst sieht dann
so aus:
Abb. 8.2: Mandelbrot-Menge im Bereich x⊂[-2.5;1.59], y⊂[-1.5;1.5]
8.3 Julia-Mengen
Zur Erzeugung der nach dem französischen Mathematiker Gaston JULIA
benannten Julia-Mengen geht man ebenso vor, wie bei den Mandelbrot-Mengen,
verändert jedoch nicht den Wert für c, sondern den für z.
Die Definition der Julia-Menge sieht also so aus:
J
c = { z ⊂
" |
|z
N|
∞ } (ideale Julia-Menge)
J
c = { z ⊂
" ||z
N|
< A } (realistische Julia-Menge)
Auch die Julia-Mengen haben interessante Eigenschaften, von denen ich jedoch
hier auch nur die Symmetrie beweisen werde.
Satz: Jede Julia-Menge ist zum Ursprung punktsymmetrisch.
Beweis (nach [1]):
Ausgangspunkt ist z ⊂ J
c. Es gilt dann
|f
n(z)|
∞. Der Punkt, der bezüglich des Ursprungs zu z symmetrisch liegt
ist –z. Nach der ersten Iteration ergibt sich f
c(z) = z
2
+ c = (-z)
2 + c = f
c(-z). Weiter ergibt sich dann |f
n(z)|
= |f
n(-z)| und damit
|f
n(z)| =
|f
n(-z)|
∞. Weil z⊂ J
c ist dann auch –z ⊂ J
c.
Für verschiedene c ergeben sich ziemlich unterschiedliche Punktmengen,
deshalb verwendet man hier auch den Index c am Buchstaben J. A. Douady beschreibt
die Julia-Mengen so: “Es gibt eine unglaubliche Vielzahl von Julia-Mengen:
Einige sehen aus wie dicke Wolken, andere wie dorniges Gestrüpp, wieder
andere wie Funken, die nach der Explosion eines Feuerwerkskörpers in
der Luft schweben. Eine sieht aus wie ein Kaninchen, viele haben Schwänze
wie Seepferdchen.” (aus [1]). Der eigenen Phantasie und Experimentierfreude
sind keine Grenzen gesetzt.
Auch hier seien wieder einige schöne oder aussagekräftige Beispiele
dargestellt:
Abb. 8.7: c = 0.279225 + i · 0.539797
Abb. 8.8: c = -0.095775 + i · 0.652297
Wie man erkennen kann, sind manche Julia-Mengen zusammenhängend, manche
unzusammenhängend. Daraus ergibt sich ein interessanter Zusammenhang
zwischen Mandelbrot- und Julia-Mengen. Die Julia-Mengen J
c, deren
Parameter in der Mandelbrot-Menge enthalten ist, sind zusammenhängend.
Wie bei der Mandelbrot-Menge, kann man auch bei der Julia-Menge etwas Farbe
ins Spiel bringen, indem man die Anzahl der Iterationen mit unterschiedlichen
Farben darstellt:
Abb. 8.9: c = -0.5125 + i · 0.56875
Abb. 8.10: c = 0
Wie man sehen kann, gibt es auch “langweilige” Julia-Mengen (Abb.
8.10), die beispielsweise Kreisform haben. Natürlich lassen sich auch
von Julia-Mengen Ausschnittsvergrößerungen anfertigen. Dabei macht
man manche überraschende Entdeckung, zum Beispiel ein Apfelmännchen
in einer Julia-Menge!
Abb. 8.11: c = -0.75 im Bereich [-0.20;0.19];[0.58;0.88]
9
Fraktale Bildkompression – eine Anwendung
Eine Anwendung dieser Kenntnisse über Fraktale und vor allem Selbstähnlichkeit
ist die fraktale Bildkompression. Das Prinzip dieser Art von Kompression beruht
darauf, daß es in fast jedem Bild Elemente gibt, die durch andere Teile
nach Skalierung angenähert werden können. Als Ergebnis erhält
man also eine Menge von Transformationen, die man wiederholt auf ein beliebiges
Anfangsbild anwendet und damit das Originalbild annähert. Eine interessante,
nicht unbekannte Eigenschaft, ist die, daß sich das Bild beliebig vergrößern
läßt, indem man die Iterationstiefe erhöht. diese Idee stammt
von M. Barnsley, der wußte, daß es möglich ist, durch fraktale
Algorithmen realistische Landschaften zu erzeugen, und den Vorschlag machte,
ähnliche Algorithmen für vorgegebene Bilder zu verwenden. Es könnten
dann für jeden Ausschnitt des Bildes nur die für den Algorithmus
notwendigen Parameter gespeichert werden. Die Dekompression ist dann kein
Problem, die Suche nach passenden Algorithmen ist jedoch nicht ganz einfach.
Als Beispiel muß einmal wieder das Sierpinski-Dreieck dienen. Um dieses
aus einem leeren Ausgangsbild zu erzeugen, verwendet man die folgenden drei
Transformationen:
Insgesamt ist dann
.
Geht man von einer beliebigen Ausgangsmenge A(0)={(x,y) | 0>x>1, 0>y>1}
aus und setzt A(n)=W(A(n-1)), dann wird jeder Punkt der Menge A(n) auf drei
Punkte der Menge A(n+1) abgebildet. die ersten vier Iterationen sehen dann
so aus:
Abb. 9.1: Entwicklung des Sierpinski-Dreiecks aus der Transformation W
(aus [7])
Läßt man n gegen unendlich gehen entsteht (unabhängig von
A(0)) das Sierpinski-Dreieck. Nach häufiger Anwendung der Transformationen
wird das Ausgangsbild A(0) zu einem Punkt der Zielmenge. Wenn man komplexere
Transformationen einsetzt, lassen sich auch realistischere Bilder erzeugen:
Abb. 9.2: Entstehung eines Farnblattes durch Ähnlichkeits-Transformationen
(aus [7])
Um dieses Prinzip tatsächlich auf beliebige Bilder anwenden zu können,
muß man es etwas erweitern. Man verwendet dazu das PIFS (partitioned
iterated function system), bei dem die Transformation W nicht auf das gesamte
Bild sondern auf einen Ausschnitt angewendet wird.
Die Kompression geschieht dann also in zwei Schritten:
- Unterteilung des Bildes in größtmögliche Bereiche.
- Suche nach Transformationsparametern für jeden Bereich.
Es müssen also die einzelnen Bereiche und für jeden Bereich die
Transformationsparameter gespeichert werden. Wie groß das Bild nach
der Kompression ist, hängt also vor allem davon ab, in wie viele Bereich
man das Bild unterteilen muß.
Das derzeit beste Kompressionsverfahren kommt von der University of Bath in
Großbritannien. Die “hybrid image compression with implicit fractal
terms”-Systeme kommen dank komplexerer Basis-Funktion und vorbestimmter
Einteilung ohne Suche aus und sind daher sehr schnell.
Anhang
A
Program Feigenbaum_4;
{ Zeichnet ein Feigenbaum-Diagramm
in einem festgelegten Bereich für den
Parameter a
(c) 1997 by René Rondot
}
Uses Graph;
Const Anfang : Real = 0; {
Startwert für a }
xSkal = 150; {
Skalierung in x-Richtung }
Var x,m : Real;
i : Word;
s : String;
gr : Integer;
Procedure KOS;
Begin
Line(0,400,640,400);
Line(25,0,25,410);
m:=Anfang;
Repeat
m:=m+0.5;
SetLineStyle(SolidLn,0,1);
Line(round((m-Anfang)*xSkal)+25,395,round((m-Anfang)*xSkal)+25,405);
SetLineStyle(DottedLn,0,1);
Line(round((m-Anfang)*xSkal)+25,0,round((m-Anfang)*xSkal)+25,395);
Str(m:2:1,s);
OutTextXY(round((m-Anfang)*xSkal),405,s);
Until m>=4;
m:=0;
SetLineStyle(SolidLn,0,1);
Repeat
m:=m+0.1;
Line(25,round((1-m)*400),30,round((1-m)*400));
Str(m:2:1,s);
outtextxy(0,round((1-m)*400)-4,s);
Until m>=1.1;
End;
Begin
gr := 0;
InitGraph(gr,gr,'E:\BP\BGI'); KOS;
m:=Anfang;
Repeat
m:=m+0.001; {
Schrittweite }
x:=0.1; {
Startwert }
For i:= 1 to 1000 do x := m * x * (1-x); {
unsichtbare Iterationen }
For i:= 1 to 100 do {
sichtbare Iterationen }
Begin
x := m * x * (1-x);
PutPixel(round((m-Anfang)*xSkal)+25,round((1-x)*400),15);
End;
Until m > 3.999;
Readln;
End.
Anhang
B
Program Mandelbrot_1;{
Darstellung der Mandelbrot-Menge für fc(z) = z2
+ c
(c) 1997 by René Rondot
}Uses Graph,crt;Type Komplex
= Record R,I : Extended; End;
Var z,c : Komplex;
g,N : Integer;
{ Prozeduren für komplexe Zahlen
}
Procedure KompMul(c,d : Komplex; Var cd
: Komplex);
Begin
cd.R := c.R * d.R - c.I * d.I;
cd.I := c.R * d.I + c.I * d.R;
End;
Procedure KompAdd(c,d : Komplex; Var cd
: Komplex);
Begin
cd.R := c.R + d.R;
cd.I := c.I + d.I;
End;
Function KompBetr(c : Komplex) : Extended;
Begin
KompBetr := sqrt (c.R*c.R+c.I*c.I);
End;
Procedure KOS;
Begin
Line(320,0,320,480);
Line(0,240,640,240);
Line(520,235,520,245);
Line(315,40,325,40);
Line(315,440,325,440);
End;
Begin
g:=0; InitGraph(g,g,'E:\BP\BGI'); KOS;
c.I := -2;
Repeat
c.R := -2;
Repeat
z.I := 0; z.R := 0; N := 0;
Repeat
KompMul(z,z,z); KompAdd(z,c,z);
Inc(N);
Until (KompBetr(z) > 2) or (N>20);
if N>20 Then PutPixel(Round(c.R*200+320),240-Round(200*c.I),15);
c.R := c.R + 0.005;
Until c.R >= 1;
c.I := c.I + 0.005;
Until c.I >= 1;
Readln;
End.
Anhang
C
Literaturverzeichnis:
- Herbert Zeitler und Wolfgang Neidhardt: Fraktale und Chaos – Eine
Einführung, Wissenschaftliche Buchgesellschaft Darmstadt, 1993
- Karl-Heinz Becker und Michael Dörfler: Dynamische Systeme und Fraktale,
Friedrich Vieweg Verlag Braunschweig, 1989
- H.-O. Peitgen u.a.: Chaos – Ein Arbeitsbuch, Ernst Klett Schulbuchverlag
Stuttgart 1992
- H.-O. Peitgen u.a.: Fraktale – Ein Arbeitsbuch, Ernst Klett Schulbuchverlag
Stuttgart 1992
- Günter Hellwig: Höhere Mathematik I – Eine Einführung,
Bibliographisches Institut Mannheim 1971
[6] Internet-Seite der University of Bath (http://dmsun4.bath.ac.uk)
[7] Internet-Seite der Universität Saarbrücken (
http://www.uni-sb.de)
[8] GEO 7/1985, Artikel “Das Chaos” auf Seite 36 von R. Breuer
Die Abbildungen 8.2 bis 8.10 wurden mit dem Freeware-Programm WinFract v18.21,
(c) 1990, 1993 The Stone Soup Group erstellt.
[1] Der Mittelwertsatz lautet
folgendermaßen [5]: f sei in [a,b] stetig und in (a,b) differenzierbar.
Dann gibt es wenigstens ein Zahl ξ ⊂ (a,b) mit f’(ξ)
=
.
Nach Umformung ist f’(ξ) · (b - a) = f(b) - f(a)