Newton-Fraktal mit Python

[shidox]

Guten Tag liebe Python Community

Ich möchte zuerst vorweg nehmen, dass ich ein totaler Neuling in Sachen Programmierung bin. Dies ist mein erstes Projekt und darum bitte ich um Antworten, welche einigermassen verständlich für Anfänger sind. Ich wusste nicht in welches Unterforum der Beitrag gehört, darum habe ich es einfach mal im Allgemein Threat gepostet.

Mein Ziel war es, das Newton-Fraktal für die Funktion f(z)=z^3-1 darstellen zu lassen, also ein Bild zu erstellen. Dies hat eigentlich gut geklappt, jedoch gibt es noch ein Problem. Zuerst der Code:

Code: Alles auswählen

from PIL import Image


imgx = 700
imgy = 700

xmin = -2
xmax = 2
ymin = -2
ymax = 2

image = Image.new("RGB", (imgx, imgy))

for x in range(imgx):
    zx = x*(xmax-xmin)/imgx+xmin 
    for y in range(imgy):
        zy = ymax - y*(ymax-ymin)/imgy 
        z = complex(zx,zy) 

        x1 = (imgx+xmin)/(xmax-xmin)
        y1 = (imgy*ymax)/(ymax-ymin)
        zx1 = x1*(xmax-xmin)/imgx+xmin
        zy1 = ymax - y1*(ymax-ymin)/imgy

        x2 = ((-0.5)*(imgx+xmin))/(xmax-xmin)
        y2 = (imgy*(ymax-(3**(.5)/2)))/(ymax-ymin)
        zx2 = x2*(xmax-xmin)/imgx+xmin
        zy2 = ymax-y2*(ymax-ymin)/imgy

        x3 = ((-0.5)*(imgx+xmin))/(xmax-xmin)
        y3 = (imgy*(ymax+(3**(.5)/2)))/(ymax-ymin)
        zx3 = x3*(xmax-xmin)/imgx+xmin
        zy3 = ymax - y3*(ymax-ymin)/imgy
        
        z1 = complex(zx1,zy1) 
        z2 = complex(zx2,zy2)
        z3 = complex(zx3,zy3)

        n = 1

        dist1 = 5
        dist2 = 5
        dist3 = 5

        if abs(z) != 0:
            while n <= 1000 and dist1 >= 2.5 and dist2 >= 2.5 and dist3 >= 2.5:
                z = z - (z**3 - 1)/(3 * z**2)
                n = n + 1

            dist1 = abs(z-z1)
            dist2 = abs(z-z2)
            dist3 = abs(z-z3)
        
            if dist1 <= 2.5:
                image.putpixel((x,y), (0,255,0))
            if dist2 <= 2.5:    
                image.putpixel((x,y), (0,0,255))
            if dist3 <= 2.5:
                image.putpixel((x,y), (255,0,0))

image.save("Newton_Fraktal.png","PNG")

Das Bild wird erstellt und passt so eigentlich auch. Jedoch habe ich noch das Problem, dass ich bei den Werten dist1, dist2 und dist3 den Schwellenwert auf 2,5 setzen muss. Diese drei Werte sollten jedoch normalerweise zu der Null konvergieren, also ist trotzdem etwas falsch gelaufen? Ich hoffe jemand von euch kann mir bei diesem Problem behilflich sein, dass ich mich auch an weitere Newton-Fraktale wagen kann und schlussendlich an andere Fraktale.

Shidox


P.S. : Der Code ist mit Python 3.3 geschrieben

[BlackJack]

@shidox: Warum musst Du den Wert denn auf 2.5 setzen? Und vor allem was hat das in der ``while``-Schleife zu suchen? Die Werte `dist1` bis `dist3` werden innerhalb der ``while``-Schleife überhaupt gar nicht verändert, also macht es auch keinen Sinn bei jedem Schleifendurchlauf dagegen zu testen. Das Ergebnis dieses Teilausdrucks ist ja bei jedem Durchlauf zwingend das selbe. Nur `n` verändert sich. Und bei der Art *wie* es sich verändert ist eigentlich eine ``for``-Schleife die naheliegende Wahl. Da `n` selbst nicht verwendet wird kann man auch den Namen `_` benutzen, der per Konvention oft verwendet wird bei Namen die man aus syntaktischen Gründen angeben muss, die aber nicht verwendet werden.

Und wenn man diese Teilbedingung aus der ``while``-Schleife heraus nimmt, sieht der Code an der Stelle ziemlich komisch aus:

Code: Alles auswählen

            z1 = complex(zx1, zy1)
            z2 = complex(zx2, zy2)
            z3 = complex(zx3, zy3)

            dist1 = 5
            dist2 = 5
            dist3 = 5
     
            if abs(z):
                if dist1 >= 2.5 and dist2 >= 2.5 and dist3 >= 2.5:
                    for _ in range(1000):
                        z = z - (z**3 - 1) / (3 * z**2)
         
                dist1 = abs(z - z1)
                dist2 = abs(z - z2)
                dist3 = abs(z - z3)
           
                if dist1 <= 2.5:
                    image.putpixel((x, y), (0, 255, 0))
                if dist2 <= 2.5:    
                    image.putpixel((x, y), (0, 0, 255))
                if dist3 <= 2.5:
                    image.putpixel((x, y), (255, 0, 0))

Wenn man zu dem ``if`` kommt, dann sind die `dist*`-Werte alle grösser als 2.5 denn sie wurden kurz davor ja auf 5 gesetzt. Damit ist die ``if``-Bedingung immer wahr und man kann sie sich komplett sparen. Und *dann* kann man sich auch das setzen auf 5 sparen, denn diese 5en werden nie irgendwo benutzt. Was hast Du Dir dabei denn gedacht? Das hier macht genau das selbe:

Code: Alles auswählen

            z1 = complex(zx1, zy1)
            z2 = complex(zx2, zy2)
            z3 = complex(zx3, zy3)
     
            if abs(z):
                for _ in range(1000):
                    z = z - (z**3 - 1) / (3 * z**2)
         
                dist1 = abs(z - z1)
                dist2 = abs(z - z2)
                dist3 = abs(z - z3)
           
                if dist1 <= 2.5:
                    image.putpixel((x, y), (0, 255, 0))
                if dist2 <= 2.5:    
                    image.putpixel((x, y), (0, 0, 255))
                if dist3 <= 2.5:
                    image.putpixel((x, y), (255, 0, 0))

[shidox]

Achso okey, wie gesagt, bin komplett neu. Wenn ich den Wert höher oder tiefer setze ist das Bild nur schwarz, was für mich keinen Sinn ergibt..
Mit den 5en hab ich mir eig. nichts Grosses überlegt. Zuerst hatte ich die nicht, dann kam ne Fehlermeldung, dass die drei Variablen nicht vorhanden sind und so hab ich sie halt vorher kurz auf 5 gesetzt.
Danke für die Hilfe
Das Problem mit den Werten auf 2.5 ist aber immer noch so ein Problem..

& so läuft die for-Schleife doch immer bis "_" auf 1000 ist. Wenn "dist1/2/3" jedoch schon einen Wert unter diesen 'kuriosen' 2.5 erreicht hat, könnte die Schleife schon aufhören. Das bedeutet doch einen extremen Rechenverlust, oder nicht?

[BlackJack]

@shidox: `dist1` bis `dist3` haben in der Schleife überhaupt keinen Wert, weder über noch unter 2.5, denn die gibt es vor und in der Schleife gar nicht, die werden nach der Schleife überhaupt erst definiert. Wenn Du eine Bedingung setzen möchtes die die Schleife auch vor den vollen 1000 Rechenschritten abbrechen kann, dann muss das natürlich eine Bedingung sein die sich auf irgend etwas bezieht was *in* der Schleife berechnet wird und sich damit von Durchlauf zu Durchlauf auch verändert.

Wenn das Bild schwarz bleibt, dann trifft keines der ``if``\s zum Punkte setzen zu. Dann sind `dist1` bis `dist3` alle grösser als der Vergleichswert den Du dort einsetzen. An der Stelle solltest Du mal eine Vermutung anstellen welchen Wertebereich `z` annehmen kann und wie sich der Wert innerhalb der Schleife entwickelt und dann diese Vermutung *überprüfen* in dem Du Dir die Werte mal ausgeben lässt ob die sich tatsächlich so verhalten wie Du das erwartest.

[Sirius3]

Hast Du Dir schonmal angeschaut, welche Nullstellen z1,z2,z3 Du berechnet hast? Jedenfalls nicht die Nullstellen von z^3-1. Die ganzen Zeilen 21-38 sind übrigens unabhängig von den Schleifenvariablen und können deshalb vor die for-Schleifen gezogen werden.

Da Du einen Algorithmus zum Finden von Nullstellen, brauchst Du sie erst gar nicht selbst berechnen, sondern kannst die gefundenen Zahlen in einer Liste speichern.

[shidox]

okey, ich werde mal die nullstellen prüfen und das ergebnis der schleife auch anzeigen lassen. mal schauen was da rauskommt.
wie würde das denn mit der liste gehen ? hab da keine idee wie ich das umsetzen könnte..

Änderung: Alles klar, das Problem mit den 2.5 war rein mathematisch mein Fehler bei der Berechnung der Nullstellen. Danke für die Hilfe !
Das mit der Liste wäre allerdings noch gut, wenn man bedenkt dass die Anzahl Nullstellen dem Grad des Polynoms entsprechen. Wie würde man so etwas umsetzen? :K

[Sirius3]

Ein erster Schritt wäre, statt »dist1«, »dist2«, »dist3« immer auszurechnen, in einer for-Schleife alle Nullstellen durchzugehen und die Distanz zu z als Abbruchkriterium zu nehmen. Was Du brauchst ist eine Liste mit Nullstellen, eine Liste mit Farben und »zip«.

Immer 1000 Iterationsschritte zu gehen, um die Nullstelle zu berechnen, ist aber ein bißchen viel. Welche Bedingung ist denn erfüllt, wenn z eine Nullstelle Deines Polynoms ist?

[shidox]

Das Polynom hat ja genau 3 Nullstellen und jenachdem zu welcher dieser Nullstellen ein Punkt mit dem Newton-Verfahren konvergiert, wird dieser rot/grün/blau eingefärbt.
Das mit der Liste hab ich immer noch nicht ganz begriffen, denn wie hilft mir eine Liste mit Annäherungen weiter, wenn es halt trotzdem nur Annäherungen sind und ich nicht von Anfang an weiss, zu welcher Nullstelle ein Punkt konvergieren wird?
Jo, normalerweise gehe ich nun so um die 30 Iterationsschritte und das klappt wunderbar.
Hmm.. Also wenn z schon von Anfang an die Nullstelle ist, dann verändert sich diese Zahl während der Iterations einfach nicht.
Also am Schluss will ich eig. ein Programm haben, das die Punkte, die schneller konvergieren z.B. hellrot einfärbt und die, die langsam konvergieren dunkelrot einfärbt und das bei allen 3 Farben. Zudem wäre eben diese Liste noch von Vorteil, aber ich verstehe halt noch nicht wie du das meinst.. :K

Was noch zu den verschiedenen Farbtönen gehört : Dafür wäre es ja gut, wenn die Iterarion abbricht sobald eine bestimmte Annäherung erreicht wird. Dann könnte man die Anzahl Iterationen zählen lassen und so den Farbwert bestimmen, aber hier scheitert mein Vorhaben auch noch an der Umsetzung .. :K