MATHEMATISCHES INSTITUT DER UNIVERSITÄT MÜNCHEN Dr. W. Spann, G. Kleen WS 2022/2023

Programmieren II für Studierende der Mathematik

Aufgabe 7

Das Konvergenzverhalten des komplexen Newton-Verfahrens zur Bestimmung von Nullstellen analytischer Funktionen f : ℂ → ℂ

z_{0} ∈ ℂ, z_{k+1} = z_{k} − \frac{f(z_{k})}{f′(z_{k})} (k ∈ ℕ_{0})

soll für Startwerte z_{0} im Rechteck {z ∈ ℂ : a ≤ Re z ≤ b, c ≤ Im z ≤ d} untersucht werden.

(a) Starten Sie dazu das Verfahren auf einem homogenen rechteckigen Gitter mit M ·N Punkten und brechen Sie die Iteration jeweils ab, wenn |z_{k+1} − z_{k}| ≤ ε|z_{k}|. Speichern Sie den so gefundenen Wert z_{k} in einem Vektor komplexer Zahlen ab, allerdings nur dann, wenn er von früher abgespeicherten Werten um mindestens D > 0 abweicht. In einem anderen Vektor soll festgehalten werden, wie oft Konvergenz gegen jeden dieser abgespeicherten Werte eingetreten ist. Reservieren Sie sich die Komponente 0 dieses Vektors für den Fall, dass numerisch keine Konvergenz beobachtet wird, d.h. eine vorgegebene Iterationsschranke itmax überschritten wird. Geben Sie die berechneten Grenzwerte mit den Häufigkeitswerten aus und drucken Sie, wie oft numerisch Divergenz beobachtet wurde.

(b) Zur graphischen Darstellung des Einzugsbereichs der einzelnen Nullstellen können Sie das Format P6 oder P3 (sehr speicheraufwendig!) einer PPM-Datei verwenden (man 5

ppm oder https://de.wikipedia.org/wiki/Portable Anymap). Erstellen Sie einen Vek-

tor mit mindestens 7 vordefinierten Farben (P6: Darstellung des RGB-Wert mit 3 Byte) und speichern Sie den der Nullstelle entsprechenden Farbwert in der PPM-Datei. Für Nichtkonvergenz soll die Farbe weiß verwendet werden. Konvertieren Sie die PPM-Datei in eine JPG- oder GIF-Datei, z.B. mit dem Kommando convert aus ImageMagick, oder verwenden Sie gimp (GNU Image Manipulation Program) zum Anzeigen der Datei unter Windows.

Verwenden Sie bei der Programmierung möglichst eine Funktion für das Newtonverfahren mit Parametern für f und f′, und eine Klasse zur Durchführung der Nullstellenberechnung auf dem Gitter, deren Konstruktor u.a. die Gitterdaten und Funktionszeiger auf f und f′ initialisiert. Eine weitere Komponentenfunktion soll die Berechnungen auf dem Gitter durchführen, den Häufigkeitsvektor erstellen und ausgeben, und die Ausgabedatei befüllen.

Rechnen Sie folgende Beispiele mit ε = 10^{−12} und itmax = 200 und geeigneten einzulesenden Werten für a, b, c, d, M, N und D (z.B. −4 4 −4 4 500 500 0.001)

(i) f(z) = z^{3} − 1

(ii) f(z) = z^{3} + 3z^{2} − i

(iii) f(z) = z^{5} − 2iz^{4} − 13z^{3} + 14iz^{2} + 24z − 1

(iv) f(z) = e^{z}(z^{3} − 1)

Bearbeitungszeitraum: bis Donnerstag, 21.12.2022, 16^{00}