Julia
und Mandelbrot
|
Julia
und Mandelbrot |
1 für mathematische Tiefflieger
Julia, Mandelbrot, Fraktale, Apfelmännchen - Namen und Ausdrücke, die man vielleicht schon mal gehört hat, aber wer oder was ist das?
Gaston M. Julia und Benoit B. Mandelbrot sind, bzw. waren beides Mathematikprofessoren mit - na sagen wir mal - exquisitem Arbeitsgebiet. Sie gaben sich ab mit einer Funktion, die nicht zu einer Lösung im herkömmlichen Sinn führt, die aber doch ein reproduzierbares Verhalten aufweist. Stellt man dieses Verhalten graphisch dar, so erhält man ein dreidimensionales Gebilde. Länge und Breite lassen sich auf einer Ebene auftragen, bei der Höhe weicht man auf Farben aus: Beispielweise wird ein Wert 0 als brauner Punkt dargestellt, mittlere Werte grün und ein maximaler Wert weiss. Das Bild, das auf diese Weise entsteht, ist ein Fraktal, bzw. ein Ausschnitt davon.
Die Formel für die Berechnung des Apfelmännchens sieht sehr einfach aus:
M = M^2 + C
Diese Formel darf auch so geschrieben werden:
M = M^n + C
Die Formel M = M^n + C wird viele Male in einer sogenannten Schlaufe ausgeführt. Man nimmt den Wert M, potenziert ihn, zählt einen konstanten Wert C dazu und ersetzt den vormaligen Wert M durch das Ergebnis dieser Operationen. Diesen Vorgang führt man immer und immer wieder aus, man iteriert also in einer Schlaufe, bis M einen vorgegebenen Wert erreicht. Bei jedem Schlaufendurchgang wird ein Zähler um 1 erhöht.
Es gibt Bereiche, in denen dieser Abbruchwert nie erreicht würde. Da es keinen Sinn macht, ein ganzes System in so einem Fall zu blockieren, richtet man eine Notbremse ein: Überschreitet der Zähler einen Maximalwert, wird die Schlaufe ebenfalls verlassen.
Der Wert des Zählers wird verwendet, um die Farbe des Punktes zu bestimmen. Ich sage: Der Wert wird verwendet - es müssen noch einige Operationen durchgeführt werden, bis die Nummer der Farbe vorliegt.
Die Formel muss mit Werten "gefüttert" werden, damit etwas berechnet werden kann. Ich spreche hier von einzelnen Werten, aber die bestehen jeweils aus den beiden Koordinatenwerten eines Punktes in x und y.
Bei Julia werden 2 Werte in die Formel eingesetzt. Einmal die Koordinaten des interessierenden Punktes, dann noch eine Konstante C (auch ein Koordinatenwert).
Woher diese Konstante kommt, ja, ich habe auch recht lange gebraucht, um das rauszufinden. Aber vielleicht merken sie es selbst, wenn sie einige Zeit mit dem Applet auf dieser HP spielen: http://hem.passagen.se/gweronimo/juliet.html
1.3.2
Variablen bei Mandelbrot
Bei Mandelbrot gibt es nur einen Eingangswert, die Koordinaten des interessierenden Punktes.
Der Wert, den oben erwähnte Zähler erreicht, wird zur Bestimmung der Farbe des berechneten Punktes verwendet. Da nun die Anzahl Iterationen deutlich höher ist, als die der bei mir möglichen Farbnuancen (ca. 200), muss diese Zahl verkleinert werden. Und da diese Anzahl nicht linear von Null zum Maximalwert ansteigt, wird sie logarithmiert, daneben sind aber auch die höherliegenden Farbwerte in den Paletten stark zusammengestaucht.
Ein weiterer Trick zur optimalen Farbgebung ist, zuerst einmal die niedrigste und die höchstmögliche Farbnummer im fertig gerechneten Bild zu suchen und dann die Farbwerte zwischen diesen Nummern zu verteilen.
1.5
Ausschnitt vergrössern (nur bei Mandelbrot)
Bei der "Erforschung" eines Mandelbrot-Fraktals steht die Möglichkeit des Ausschnitt festlegens und anschliessender Vergrösserung zur Verfügung. Wie das aussieht, zeigen folgende Bilder:
Ich vergrössere mal diese Grundfigur des Typs H, so dass die Darstellung das Bild ausfüllt:
Hier ist bereits ein quadratischer Ausschnitt definiert, der vergrössert werden soll:
In der Vergrösserung ist bereits wieder ein Ausschnitt markiert, der vergrössert werden soll:
Auf diese Art lassen sich weitere Ausschnitte bestimmen und vergrössern:
Beim letzten Bild ist ein Unglück geschehen: Da wurde die maximal mögliche Auflösung überschritten.
Ich mag mich noch gut an den Kommentar eines siebenmalschlauen Computer'experten' erinnern: Ich solle mir einen besseren Computer zulegen, dann könnte ich weiter auflösen. Als ob die Genauigkeit (bedeutsame Ziffern) eine Frage des Computers wären. Nein, es ist der Übersetzer (Compiler/Linker), der den geschriebenen Programmtext in Maschinensprache übersetzt.
Ich hatte da mal einen Ärger mit einem Basic- und einem Pascal-Compiler auf ein und demselben Computer. Leute um mich herum schwärmten von der Programmiersprache Pascal; Basic sei doch etwas für Doofe. Bitte, wenn ihr meint, und ich übersetzte das Basic-Programm in Pascal, kompilierte beide und liess sie laufen. Die Resultate waren bei gleichen Ausgangswerten verschieden...
Was war los: Basic definerte eine doppelt genaue Gleitkommazahl mit 15 bedeutsamen Ziffern, bei Pascal waren es nur deren 12. Womit ich wieder mal etwas gelernt hatte.
1.7
Wie genau rechnet mein System?
Auf meinem Computer ist Linux release 9 (Shrike) installiert. Die kritischen Berechnungen werden mit Gleitkommazahlen ausgeführt, die 19 bedeutsame Ziffern aufweisen. Um einen einzelnen der 1001 Punkte z.B. in einer Bildzeile zu definieren, brauch ich 3 dieser Ziffern. Damit liessen sich erst 999 Punkte definieren, aber da meine Zahlen im Computer drin nicht in Dezimalschreibweise abgelegt sind, genügen drei Dezimalstellen.
Damit verbleiben zum Vergrössern 16 Ziffern, also maximal 9'999'999'999'999'999. Zählen wir 1 dazu, dann haben wir 10'000'000'000'000'000, also 10 Billiarden mal kann ich mein Original vergrössern.
Die Zeichenfläche auf meinem Bildschirm ist etwa 25 cm breit; multipliziert mit 10 Billiarden ergibt das 25'000'000'000'000 km, 25 Billionen km. - Hilfio, wie riesengross ist das?!
Ich gehe mal hinaus in den Weltraum, dort sollte ein Papierbogen dieser Grösse Platz finden. In die Mitte setze ich die Sonne, drum herum die Planeten, der entfernteste, Pluto hat einen mittleren Abstand von rund 6 Milliarden Kilometer, seine Umlaufbahn kann problemlos auf unserem Bogen eingezeichnet werden. Und der nächste Fixstern? Alpha Centauri? Der ist ca. 4.3 Lichtjahre von uns weg, also ca. 40 Billionen Kilometer, der passt vielleicht noch knapp in eine Ecke. (hab ich mich wirklich nicht verrechnet??)
1.8 Wo sind die "schönen"
Bilder?
Die Bilder befinden sich im Saum um die primäre Mandelbrotmenge herum:
Die Region erscheint recht bescheiden, nur so einen Zehntel Millimeter rund herum. Stimmt nicht, sie ist riesengross. Man erinnere sich, Multiplikation mit 10 Billiarden, also 10'000'000'000'000'000 mal 0.1 mm ergibt 1'000'000'000 km, also eine "Autobahn" von 1 Milliarden km Breite. Und irgendwo in diesem Bereich befinden sich die gesuchten Bilder. Wo? Keine Ahnung, man suche.
Ursprünglich wollte ich mal alle möglichen Angaben zur Datei in den Namen einpacken, mit der Zeit hatte ich den Eindruck, dass das zu nichts nützt. Heute beginnt der Dateiname mit einem Grossbuchstaben, der für die Potenzierung steht: A entspricht der 2., T der 21. Potenz. Nach einem Unterstrich folgt eine fünfstellige mit Kleinbuchstaben geschriebene Laufnummer mit den "Ziffern" a bis z und nach einem weiteren Unterstrich findet man die auf eine Stelle gerundete Vergrösserung und die Anzahl der auf diese Zahl folgenden Nullen. 3E06 bedeutet also 3 millionen-fache Vergrösserung.
1.10
Bilddateien und deren Bearbeitung
Die Programme (für Julia und für Mandelbrot) erzeugen Bitmap-Dateien, d.h. jedem Bildpunkt entspricht ein Wert (Farbnummer) in der Datei, hinzu kommt eine Tabelle mit den Farbnummern entsprechenden Farbe, definiert durch 3 Werte, einen für Rot-, einen für Grün- und einen für Blauanteil.
Aus ästhetischen Gründen drehe ich manchmal ein Bild um 90 oder 180 Grad, auch erlaube ich mir, den einen oder andern störenden Fleck zu beseitigen. Sonst nichts.
Bitmap-Dateien sind unhandlich gross, es ist sinnvoll, sie in ein kompaktere Form zu wandeln. Ich verwende das Format 'CompuServe Graphics Interchange', also *.gif. Dabei entstehen Dateien, die generell etwas weniger kompakt sind als die gemäss Format 'JPEG - IFIF-kompatibel' (*.jpg), aber es entstehen dabei keine Farb-Artefakte (bei *.jpg entstehen neue Farbtöne).
Falls irgendwer auf die Idee kommt, er möchte meine Programme nachbauen, dem zeige ich nun gerne Auszüge aus meinem Quellcode. Mein Programm ist in C geschrieben und verwendet die Runtime-Library des MGR, einer Software, mit der bedienbare Oberflächen, ähnlich Windows, erstellt werden können.
Leider kann ich die Runtime-Library nicht weitergeben. Wichtig sind die Funktionen, welche die Iterationen bei den verschiedenen Potenzen bestimmen, also werden die hier erläutert.
Aus Platzgründen zeig ich hier nur eine der insgesamt 20 Funktionen. Falls jemand das ganze Modul haben möchte, dann soll er mir das mit einem Mail mitteilen, ich werde es dann als Anhang der Antwort schicken. Es sind knapp 40 kB.
Bei Mandelbrot gibt es nur ein Parameterpaar, es sind dies die Koordinaten des zu berechnenden Punktes.
Bei Julia gibt es zwei Paare von Parametern, einmal die Koordinaten des zu berechnenden Punktes und dann noch ein weiteres, für ein ganzes Juliafraktal konstant zu haltendes Koordinatenpaar.
Dieses Koordinatenpaar entspricht einem Punkt in den Randregionen eines Mandelbrot-Fraktals. Ich hab nun ein Programm geschrieben, das einerseits das Mandelbrot-, aber auch das Julia-Fraktal rechnet. Auf dem Mandelbrot-Bild wird ein Punkt gewählt:
Anschliessend wird umgeschaltet und das Julia-Fraktal gerechnet:
Nach der Berechnung kann das Fraktal "bildfüllend" nachgerechnet werden, so wie dies im obigen Bild der Fall ist.
Die Formel
M = M^2 + C
kann man auch so schreiben:
M = M^n + C
n geht bei uns von 2 bis 21. M^2 erzeugt das "Apfelmännchen" als Grundfigur, die Grundfiguren von höheren Potenzen haben keine speziellen Namen.
Dass ich bis zur 21. Potenz ging, das hat zwei (eigentlich fadenscheinige) Gründe: Dies ergibt 20 Potenzierungen, es ergibt sich daraus ein Feld mit 4 x 5 Schaltknöpfen, also eine "runde" Sache. Nicht weitergemacht hab ich wegen des Aufwandes, der mit höheren Potenzierungen rapid anwächst, und allzuviel an prinzipiell neuartigen, interessanten Bildern ist da auch nicht zu erwarten.
Zur Berechnung der Iterationszahl für die einzelnen Punkte wird bei Julia und bei Mandelbrot der gleiche Code verwendet, lediglich die Ansteuerung ist unterschiedlich.
Die Funktionen nehmen 5 Parameter entgegen.
Bei Mandelbrot sind die ersten beiden Parameter auf 0.0 gesetzt, man_x und man_y entsprechen Koordinatenwerten des interessierenden Punktes:
counts[x][y] = point[idx](0.0, 0.0, man_x, man_y, b_loops);
Bei Julia entsprechen die ersten beiden Parameter den Koordinatenwerten des Punktes, die andern beiden dem aus der Mandelbrot-Figur stammenden konstant gehaltenen Wert.
counts[x][y] = point[idx](jul_x, jul_y, man_x, man_y, j_loops);
point[]() ist ein Array von Funktionen, die jeweils den Punkt zu einer Potenz berechnen. b_loops und j_loops definieren die maximale Anzahl Schlaufenumgänge, die erlaubt sind.
Die bei der Berechnung eines Punktes verwendete Formel lautet also
M = M^n + C
wobei n 2 bis (in unserem Fall) 21 sein kann. Nun sind aber M, wie auch C komplexe Zahlen, M ist gleich (x + iy), bestehend aus dem realen Wert x und dem imaginären Anteil iy, x und y sind die (realen) Koordinatenwerte des Punktes; das gleiche gilt für C.
Der Computer kann mit imaginären Zahlen nichts anfangen, man darf aber die reale Werte von x und y gesondert behandeln, ebenso das zu y gehörende i. Nach den Berechnungen werden die Resultate der Operationen zusammengefügt.
Setzen wir mal n = 4 und berechnen (x + y)^4. Das ergibt
x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4
Wenn Werte ohne Zwischenraum aneinander gefügt werden, versteht das der Mathematiker als Multiplikation. Mit dem Zeichen ^ wird eine Potenzierung angedeutet, und eine Potenzierung bindet die Werte rechts und links vom ^ stärker, als eine Multiplikation. Den obigen Ausdruck 4x^3y ist demnach zu lesen als: 4 mal (x hoch 3) mal y.
Was als erstes schockieren mag, sind die Zahlen 4, 6, 4 bzw. 1, 4, 6, 4, 1. Es sind dies die sog. Binominalkoeffizienten, die sich jedoch einfach bestimmen lassen mit Hilfe des Pascal'schen Dreiecks:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
und so weiter.
Ein weiteres Problem stellt das i dar. Man kann es als ein Zwischending zwischen + (plus) und - (minus) betrachten, denn es gilt:
i^1 =>
i
i^2 => -
i^3 => -i
i^4 => +
und damit wird unsere Ausmultiplikation zu
x^4 + 4ix^3y - 6x^2y^2 - 4ixy^3 + y^4
Anteile mit und ohne i werden zusammgengefasst und das i ausgeklammert:
(x^4 - 6x^2y^2 + y^4) + i(4x^3y - 4xy^3)
Das i und infolge von potenziertem i gedrehte Vorzeichen sind farblich hervorgehoben.
2.5
Code der Funktion für die 4. Potenz
Ausschnitt aus dem Julia-Programm, bei Mandelbrot wird double zu long double.
/****************************************************************
*
* c a l c u l a t e _ p o i n t _ C
*
****************************************************************/
int calculate_point_C(jul_x, jul_y, man_x, man_y, loops)
double jul_x, jul_y, man_x, man_y;
int loops; /* maximum loops */ {
double x01 = jul_x,
x02 = 0.0, x03 = 0.0, /* initialize x and y variables */
x04 = 0.0,
y01 = jul_y,
y02 = 0.0,
y03 = 0.0,
y04 = 0.0, size = 0.0; /* variable to hold absolute dimension */
int count = 0; /* loop counter */
while(size <= (double)4 && count <= loops)
{
x02 = x01 * x01; x03 = x01 * x02;
x04 = x01 * x03; y02 = y01 * y01; /* avoid calculation of potencies */
y03 = y01 * y02; /* to save calculation time */
y04 = y01 * y03; /* adding up real and imaginary values */
y01 = (double)4 * x03 * y01
-(double)4 * x01 * y03 + man_y;
x01 = x04
-(double)6 * x02 * y02
+ y04 + man_x; size = x01 * x01 + y01 * y01; /* absolute dimension */ count++; /* loop counter */ } /* jump to while statement */ return count; /* return number of loops executed */ }
Note: Retournierter Wert ist mindestens 1, maximal loops.
2.6
Von der Anzahl Iterationen zur Farbe
Ich hab oben schon erwähnt, dass rund 240 Farben zur Verfügung stehen, dass aber unsere maximale Schlaufenzahl normalerweise 2400 beträgt; es kann erforderlich sein, diese Zahl zu erhöhen, dann nämlich, wenn die Ränder von Mandelbrotmengen unscharf werden.
Eine Mandelbrotmenge liegt auf unendlicher Höhe. Dadurch, dass wir eine maximale Iterationszahl festlegen, vermeiden wir ein Blockieren des Rechners, gleichzeitig muss man aber sagen, dass wir die in einer Mandelbrotmenge liegenden Punkte gar nie berechnen (können), wir können uns nur in ihre Nähe begeben. Das ist jedoch nicht schlimm, denn die Flanken eines solchen "Mandelbrotberges" werden immer steiler (extrem steiler) je näher wir an die eigentliche Mandelbrotmenge herankommen, sodass normalerweise doch ein scharfes Bild entsteht.
Einen Teil dieses Steilheitsanstieges können wir durch Logarithmieren der Schlaufenzahl kompensieren. Einfaches Logarithmieren genügt nur in den wenigsten Fällen, standardmässig verwenden wir doppelte Logarithmierung: color = log(log(counts) + 1.0). Die Addition von 1.0 verhindert, dass versucht wird, negative Werte zu logarithmieren.
Die so erhaltenen Werte müssen noch normalisiert werden, Wert = 1 wird auf die Farbe 16 gelegt (Werte von 0 bis 15 sind reserviert für die Einfärbung der Programmoberfläche), der höchste Wert auf den Wert 254 (Farbe der Mandelbrotmenge). Wert 255 ist per Definition weiss.
Trotzdem müssen die zum Einfärben des Gebildes verwendeten Paletten so gestaltet werden, dass ein Bereich zum Wechsel z.B. von rot auf grün bei höheren Farbwerten bedeutend kleiner zu halten ist, als bei niedrigeren Werten.
Ein oft durchaus erfolgreicher Trick ist, den niedrigsten Farbwert im Bild zu suchen und dann die Farbwerte zwischen diesem und dem höchsten Farbwert (entspricht der Farbe für die Mandelbrotmenge) zu verteilen.
3
Selbstkritik und Möglichkeiten
Die Wahl der Objekte und ihre Einfärbung erfolgte nach persönlichem Gutdünken, ich habe garantiert nicht jedermanns Geschmack getroffen. Ich werde weiterhin interessante Objekte suchen und auf dieser HP veröffentlichen, dies ohne Versprechen einer Besserung.
Was Einfärbungen betrifft, da bietet PaintShop Pro die Möglichkeit an, die verwendeten Farbtafeln zu ändern oder neu zu definieren, nicht unbedingt etwas einfaches, aber es funktioniert.
Ferner kann man die Objekte auch in den Proportionen verändern, alles ist erlaubt.
Man bittet, nicht auf den Mann am Klavier zu schiessen, er tut sein Bestes.
