Julia-Mengen

Mathematische Grundlagen

Komplexe Zahlen

Eine komplexe Zahl $z = a + bi$ setzt sich aus dem Realteil $a$ und dem Imaginärteil $b$ zusammen. $\vert z\vert = \sqrt{a^2 + b^2}$ ist der Betrag von $z$.

Im Gegensatz zu anderen Programmiersprachen unterstützt Python komplexe Zahlen:

Beschreibung	Mathematisch	Python
komplexe Zahl, Variante 1	$5 + 4i$	5 + 4j
komplexe Zahl, Variante 2	$z = a + bi$	z = complex(a, b)
Betrag	$\vert z\vert$	abs(z)

Folgen

Eine Folge von Zahlen $a_0, a_1, a_2, \ldots$ kann durch eine Anfangswert $a_0$ und eine Funktionsvorschrift $a\_{n+1} = f(a_n)$ definiert werden. Beispielsweise wird mit

$a\cdot 0 = 1, \qquad a_{n+1} = a_n + 2$

die Folge der ungeraden natürlichen Zahlen definiert.
Eine Folge heisst beschränkt, wenn die Beträge ihrer Glieder nie grösser als eine festgelegte Schranke $S$ werden:

\\vert a_n\vert < S

Beispiel: Wir verwenden die Funktionsvorschrift

$a_{n+1} = a_n^2$

Für die Anfangswerte $a_0 = 1$ und $a_0 = -1$ sind alle weiteren Folgenglieder $1$. Für Anfangswerte zwischen $-1$ und $1$ werden die Folgenglieder immer kleiner, für andere Anfangswerte immer grösser.

Anfangswert	Verhalten	Bedeutung
$\vert a_0\vert = 1$	$\vert a_n\vert$ bleibt $1$	beschränkt
$\vert a_0\vert< 1$	$\vert a_n\vert$ wird immer kleiner	beschränkt
$\vert a_0\vert > 1$	$\vert a_n\vert$ wird immer grösser	gegen unendlich

Folge von komplexen Zahlen

Nun betrachten wir eine Folge von komplexen Zahlen $z_0, z_1, z_2, \ldots$ mit der Funktionsvorschrift $z_{n+1} = f(z_n) = z_n^2$. Hier können wir das gleiche Verhalten wie oben feststellen: Die Folge ist beschränkt, wenn der Betrag des Anfangswerts nicht grösser als $1$ ist:

Anfangswert	Verhalten	Bedeutung
$\vert z_0\vert = 1$	$\vert z_n\vert$ bleibt $1$	beschränkt
$\vert z_0\vert < 1$	$\vert z_n\vert$ wird immer kleiner	beschränkt
$\vert z_0\vert > 1$	$\vert z_n\vert$ wird immer grösser	gegen unendlich

Die komplexen Zahlen $z_i$ können auch als Punkte in der zweidimensionalen Ebene interpretiert werden. Für $\vert z_0\vert = 1$ bleiben die Punkte auf dem Einheitskreis. Für $\vert z_i\vert < 1$ gehen die Punkte gegen den Ursprung und für $\vert z_0\vert > 1$ entfernen sie sich immer weiter davon.

Julia-Menge

Definition: Die Julia-Menge der komplexen Zahl $c$ ist die Menge aller Punkte $z_0$, für welche die Folge mit Startwert $z_0$ und Funktionsvorschrift $z_{n+1} = z_n^2 + c$ beschränkt ist.
Nach dieser Definition ist die Julia-Menge für $c = 0$ der Einheitskreis.
Sobald andere Werte für $c$ gewählt werden, wird die Julia-Menge zu einem Fraktal:

Julia-Menge für $c = -0.1 + 0.651i$

Programmierung

Der Algorithmus für die Darstellung einer Julia-Menge

• Für jedes Pixel des Fensters muss bestimmt werden, ob es zur Juliamenge gehört.
• Dazu müssen die Pixelkoordinaten in komplexe Zahlen umgerechnet werden.

Für jedes Pixel

Um für jedes Pixel eine Operation durchzuführen, verwenden wir zwei verschachtelte for -Schleifen:

def zeichneJulia(c):
    for x in range(0, WIDTH):
        for y in range(0, HEIGHT):
            zeichneJuliaPunkt(x, y, c)

Koordinatentransformation

Julia-Mengen befinden sich in der Nähe des Ursprungs, im Bereich $\vert z\vert < 1$. Um eine Julia-Menge in einem Fenster mit Pixelkoordinaten darzustellen, müssen die Pixelkoordinaten in die komplexe Zahlenebene transformiert werden.

Dazu wird erst der Ursprung in die Mitte des Fensters verschoben, anschliessend wird eine Skalierung vorgenommen. Für die Pixelkoordinaten x und y wird die komplexe Zahl so berechnet:

re = (x - WIDTH / 2) / skalierung
im = (y - HEIGHT / 2) / skalierung
z = complex(re, im)

Dabei beschreibt skalierung den Radius des Einheitskreises in Pixel.

Näherungsverfahren

Nun muss bestimmt werden, ob die Zahlenfolge für den Startwert $z$ beschränkt ist. Dazu wird ein Näherungsverfahren verwendet: Wir berechnen die ersten $N$ Glieder der Folge. Falls diese den Schwellwert $S$ nicht überschreiten, nehmen wir an, dass die Folge beschränkt ist. Dieses Verfahren wird mit grösserem $N$ immer genauer.

Julia-Menge mit N = 100, 500, 1000 und 5000

In Python programmieren wir diese Vorgehensweise mit Hilfe einer vorabprüfenden Schleife:

1. Setze $n$ auf $0$.
2. Wiederhole so lange wie $n < N$ und $\vert z\vert < S$:
   • berechne das $(n+1)$-te Element
   • erhöhe $n$ um $1$.

In Python sieht das so aus:

n = 0
while n < N and abs(z) < S:
    z = z * z + c
    n = n + 1

Grafische Darstellung

Ein Pixel repräsentiert eine rechteckige Fläche der komplexen Ebene, welche unendlich viele Punkte enthält. Wir betrachten die Folge aber nur für einen Punkt davon. Es ist unmöglich festzustellen, ob und wie viele Punkte der Julia-Menge in diesem Rechteck liegen. Deshalb behelfen wir uns mit einer weiteren Näherung:

Wir nehmen an, dass mehr Punkte der Juliamenge innerhalb des Pixels liegen, je länger die Folge des untersuchten Punkts innerhalb des Schwelle bleibt. Diese Schätzung stellen wir grafisch als Farbverlauf dar. Je grösser das $n$, bei welchem die Schwelle überschritten wird, desto dunkler die Farbe.

Der Bereich von $0$ bis $N$ muss also auf den Bereich $0$ bis $255$ abgebildet werden. Die einfachste Variante ist die lineare Abbildung. Bessere Resultate erhält man aber mit der Wurzelfunktion oder dem Logarithmus:

$g_1(n) = 255 - 255 \cdot \frac{n}{N}$

$g_2(n) = 255 - 255 \cdot \frac{\sqrt{n}}{\sqrt{N}}$

$g_3(n) = 255 - 255 \cdot \frac{\ln{n}}{\ln{N}}$

Abbildung von 0 bis 500 Iterationen auf einen Farbwert

Farbverlauf mit linearer Funktion, Wurzel und Logarithmus

In Python wird die Umrechnung von n in eine Farbe zum Beispiel folgendermassen programmiert:

helligkeit = 255 - int(255 * math.sqrt(n) / math.sqrt(N))
farbe = (helligkeit / 2, helligkeit / 2, helligkeit)

Schliesslich muss noch das Pixel gezeichnet werden:

screen.draw.rect(Rect(x, y, 1, 1), farbe)

Bildschirmfoto

Um ein Bildschirmfoto der aktuellen Zeichnung zu erstellen, wird das Modul pygame benötigt:

import pygame

Mit der folgenden Anweisung wird eine Kopie des aktuellen Fensterinhalts in der Datei julia.png gespeichert:

pygame.image.save(screen.surface, "julia.png")

Übung mit vorgegebenem Programm

Suchen Sie eine schöne Julia-Menge, indem Sie verschiedene Werte für $c$ ausprobieren. Experimentieren Sie ebenfalls mit dem Wert für $N$ und mit Farbverläufen. Wenn Sie eine passende Darstellung gefunden haben, dann erstellen Sie davon ein Bild in der Grösse 3200×2000 Pixel.
ACHTUNG: Vergessen Sie nicht, den Wert von SCALE entsprechend anzupassen.

import math

import pgtrun
import pygame

TITLE = "Juliamenge"
WIDTH = 500
HEIGHT = 500

skalierung = 200
hintergrundfarbe = 255, 255, 255
N = 500
S = 4


def zeichneJuliaPunkt(x, y, c):
    re = (x - WIDTH / 2) / skalierung
    im = (y - HEIGHT / 2) / skalierung
    z = complex(re, im)
    n = 0
    while n < N and abs(z) < S:
        z = z * z + c
        n = n + 1
    helligkeit = 255 - int(math.sqrt(n) * 255 / math.sqrt(N))
    farbe = (helligkeit / 2, helligkeit / 2, helligkeit)
    screen.draw.rect(Rect(x, y, 1, 1), farbe)


def zeichneJulia(c):
    for x in range(0, WIDTH):
        for y in range(0, HEIGHT):
            zeichneJuliaPunkt(x, y, c)


def draw():
    screen.fill(hintergrundfarbe)
    zeichneJulia(-0.1 + 0.651j)
    pygame.image.save(screen.surface, "julia.png")


pgtrun.go()