Komplexe Dynamik, die Mandelbrot

KOMPLEXE DYNAMIK UND DAS
NEWTON-VERFAHREN
VON NUTZLOSER UND NÜTZLICHER MATHEMATIK
Hauptseminar: Eine Einladung in die Mathematik
Referenten: Simon Eickelkamp, Kathrin Unger
01.02.2016
2
Inhalt
 Iteration komplexer Polynome
 Die gefüllte Julia-Menge
 Die Mandelbrot-Menge
 Die Dynamik des Newton-Verfahrens
 Newton-Dynamik und Julia-Menge
 Newton-Dynamik und Mandelbrot-Menge
 Forschung am Newton-Verfahren
 Fazit
 Abbildungsverzeichnis
 Literaturverzeichnis
3
Iteration komplexer Polynome
Sei 𝑞: ℂ → ℂ ein Polynom, dessen Grad mindestens 2 ist.
Iteration von q heißt:
Wir betrachten die Folge 𝑧, 𝑞 𝑧 , 𝑞 𝑞 𝑧 , 𝑞 𝑞 𝑞 𝑧
Wir schreiben:
𝑞 °0 ≔ 𝑖𝑑
𝑞 °𝑛 ≔ 𝑞 o 𝑞°(𝑛−1) für die n-te Iterierte von q
 Wie verhält sich q bei Iteration?
, … 𝑓ü𝑟 𝑧 ∈ ℂ
4
Iteration komplexer Polynome
Die Folge (𝑞°𝑛 𝑧 )𝑛∈ℤ nennt man den Orbit von z.
beschränkter Orbit:
- wenn z ein Fixpunkt oder allgemeiner ein
periodischer Punkt von q ist
(𝑞 𝑧 = 𝑧 𝑜𝑑𝑒𝑟 𝑞°𝑛 𝑧 = 𝑧 𝑓ü𝑟 𝑒𝑖𝑛 𝑛 ∈ ℕ)
- wenn 𝑞°𝑛 𝑧 einen Grenzwert < ∞ besitzt
unbeschränkter Orbit:
wenn 𝑞°𝑛 𝑧 → ∞ für 𝑛 → ∞
5
…verschiedene
invariante
Mengen
lassen Aussagen über Dynamik von
verschiedenen Orbits treffen!
(Menge 𝐾 ⊂ ℂ invariant, wenn q(K) ⊂ K)
6
Gefüllte Julia-Menge
Benannt nach Gaston Julia (1893 - 1978; einer der Gründer der komplexen
Dynamik im frühen 20. Jahrhundert)
𝑲 𝒒 ≔ { 𝑧 ∈ ℂ: der Orbit von z unter Iteration von q ist beschränkt}
Abb.1: Julia-Menge eines quadratischen Polynoms
7
Gefüllte Julia-Menge
Komplement der Julia-Menge
=
Menge der entkommenden Punkte von q
𝑰 𝒒 ≔ 𝑧 ∈ ℂ: der Orbit von z geht unter Iteration von q gegen ∞
Für jedes Polynom q gilt: ℂ = K(q) ∪ 𝐼(𝑞)
(benannt nach Pierre Fatou (1878-1929); daher auch FatouMenge; wichtiger Pionier der komplexen Dynamik)
8
Gefüllte Julia-Menge
Gefüllte Julia-Menge von q:
𝐾 𝑞 ≔ { 𝑧 ∈ ℂ: der Orbit von z unter Iteration von q ist beschränkt}
Menge der entkommenden Punkte von q:
𝐼 𝑞 ≔ {𝑧 ∈ ℂ: der Orbit von z geht unter Iteration von q gegen ∞}
Abb. 2: gefüllte Julia-Menge verschiedener quadratischer Polynome
9
Gefüllte Julia-Menge
Abb. 3: Karte von Julia-Mengen zur Funktion 𝑧 → 𝑧 2 + 𝑐
10
Die gefüllte Julia-Menge
Überlegungen zur Struktur dieser Mengen:
1. Sind alle unzusammenhängenden Mengen K(q)
homöomorph zueinander?
2. Hat K(q) innere Punkte (d.h. enthält K(q) offene
Mengen)?
11
Die gefüllte Julia-Menge
Überlegungen zur Struktur dieser Mengen:
3. Kann der Rand von K(q) positives Maß haben,
insbesondere in dem Fall, wenn K(q) keine inneren
Punkte hat?
4. Wie kann man entscheiden, ob die gefüllte JuliaMenge eines bestimmten Polynoms q
zusammenhängend ist?
12
Die gefüllte Julia-Menge
1. Sind alle unzusammenhängenden Mengen
K(q)
homöomorph zueinander?
Wenn q Grad 2 hat, gilt:
Ist die gefüllte Julia-Menge eines quadratischen Polynoms
unzusammenhängend, so ist sie eine Cantor-Menge und
zwei Cantor-Mengen in einem metrischen Raum sind stets
homöomorph.
Cantor-Menge: kompakt, total unzusammenhängend, keine isolierten Punkte
13
Die gefüllte Julia-Menge
2. Hat
K(q) innere Punkte (d.h. enthält K(q) offene
Mengen)?
Wenn K(q) innere Punkte enthält, so nennt man jede
Zusammenhangskomponente des Inneren von K(q) eine
Fatou-Komponente.
Jede Fatou-Komponente wird durch q surjektiv auf eine
andere Fatou-Komponente abgebildet.
𝑈𝑞 ≔ 𝐾(𝑞)\J(𝑞)
14
Die gefüllte Julia-Menge
K(q) positives Maß haben,
insbesondere in dem Fall, wenn K(q) keine inneren
3. Kann der Rand von
Punkte hat?
• Jahrzehntelang ungelöst!
• „vor kurzem“ zeigten Xavier Buff und Arnaud Chéritat,
dass dies passieren kann!
15
Die gefüllte Julia-Menge
4.
Wie kann man entscheiden, ob die gefüllte Julia-Menge
eines bestimmten Polynoms q zusammenhängend ist?
Satz: Die Menge K(q) ist genau dann zusammenhängend,
wenn die Orbits aller kritischen Punkte von q
beschränkt sind (und sie ist eine Cantor-Menge, falls
alle kritischen Orbits unter Iteration gegen unendlich
konvergieren).
16
Die Mandelbrot-Menge
(benannt nach Benoît Mandelbrot (1924 - 2010))
Sei 𝑞𝑐 𝑧 = 𝑧 2 + 𝑐, wobei 𝑐 ∈ ℂ und 𝑧 = 0 (Startwert)
Dann ist die Mandelbrot-Menge M die Menge der
Parameter c, für die 𝐾𝑐 ≔ 𝐾 𝑞𝑐 zusammenhängend ist.
… M ist eine Art „Inhaltsverzeichnis“ im Buch der
(zusammenhängenden) quadratischen Julia- Mengen…
 man kann jetzt Aussagen über Mengen von K(q) machen!
17
Die Mandelbrot-Menge
Abb. 4: Mandelbrot-Menge M im Raum der iterierten komplexen
Polynome 𝑧 → 𝑧 2 + 𝑐
18
Die Mandelbrot-Menge
 Komplizierte Struktur
Unbeantwortete Fragen:
1.
Lässt sich die Topologie der Mandelbrot-Menge einfach
beschreiben?
2.
Sei c ein innerer Punkt von M. Enthält die gefüllte Julia-Menge von
𝑞𝑐 notwendigerweise einen inneren Punkt?
3.
Ist der Rand von M eine Kurve? Wie groß ist sein Flächeninhalt?
19
Dynamik des Newton-Verfahrens
• Motivation: Wichtigkeit des Findens der Nullstellen von
Funktionen für Mathematik und Wissenschaft
• „Ist x* eine einfache Nullstelle von f (d. h. f(x*) = 0 und
f‘(x*) ≠ 0), dann konvergiert der Newton-Orbit aller
hinreichend nahe an x* liegenden Punkte gegen x*: Es
gibt ε > 0 derart, dass alle x0 mit |x0 − x*| < ε die
Eigenschaft xn → x* haben.“
• Folge der Näherungen konvergiert sehr schnell gegen
Nullstelle
20
Dynamik des Newton-Verfahrens
• Nf: Nf (x)= x – f(x)/f‘(x)
• Bzw. Np: Np (x)= x – p(x)/p‘(x), wenn f = p ein Polynom
• Rationale Funktion  Julia-Menge anwendbar
•
Abb.6: Versch. Darstellungen der Dynamikebene der Np eines typischen komplexen Polynoms (hier deg(p) = 7).
21
Dynamik des Newton-Verfahrens
• Bassin: Für eine Nullstelle α von p sei Bα das Bassin von
α, also die Menge aller z ∈ ℂ, die unter Iteration von Np
gegen α konvergieren.
• Vereinigung aller Bassins sind die sogenannten „guten
Startwerte“, d.h. mit denen man eine Nullstelle mit der
Newton-Iteration findet
 alle anderen werden „schlechte Startwerte“ genannt
22
Dynamik des Newton-Verfahrens
• Es stellen sich nun die folgenden 4 Fragen:
• 1. Konvergieren fast alle Punkte in ℂ unter Iteration von
Np gegen eine Nullstelle von p?
• 2. Kann es offene Mengen von Punkten in ℂ geben, die
unter Iteration von Np nicht gegen irgendeine Nullstelle
von p konvergieren?
23
Dynamik des Newton-Verfahrens
• 3. Sei p ein Polynom vom Grad d ≥ 2, von dem wir nur
wissen, dass alle Nullstellen von p in der komplexen
Einheitsscheibe D liegen. Wie können wir Startpunkte
finden, so dass uns die Newton-Iteration alle Nullstellen
liefert?
• 4. Wie oft muss man von passenden Startpunkten
iterieren, um alle Nullstellen mit einer bestimmten
Genauigkeit ε > 0 zu finden?
24
Dynamik des Newton-Verfahrens
Schlechte Punkte:
• Falls deg(p) = 2 und p hat zwei Nullstellen
 schlechte Punkte liegen auf Mittelhalbierenden zwischen den
Nullstellen
• Wenn deg(p) ≥ 3 gibt es immer schlechte Startwerte
25
Dynamik des Newton-Verfahrens
Ränder des Bassins:
• Rand jedes Bassins ist abgeschlossen, nicht leer und
schneidet kein Bassin einer Nullstelle
Kein Punkt auf dem Rand eines Bassins konvergiert gegen
Nullstelle
• Ränder aller Bassins sind stets gleich
 Dieser gemeinsame Rand ist die Julia-Menge von Np
26
Dynamik des Newton-Verfahrens
Umformulierung der 1. und 2. Frage:
• 1. Konvergieren fast alle Punkte in ℂ unter Iteration von
Np gegen eine Nullstelle von p?
• 2. Kann es offene Mengen von Punkten in ℂ geben, die
unter Iteration von Np nicht gegen irgendeine Nullstelle
von p konvergieren?
„Liegt jeder Punkt z ∈ ℂ, der nicht gegen eine Nullstelle
von p konvergiert, in dem gemeinsamen Rand aller
Bassins? Und kann dieser gemeinsame Rand positives
Maß haben?“
27
Newton-Dynamik und Julia-Menge
• „Für jedes quadratische Polynom q gibt es ein kubisches
Polynom p, so dass die Menge der schlechten Startwerte
für die Newton-Dynamik von Np eine Kopie der gefüllten
Julia-Menge von q enthält.“
• Abb. 7
28
Newton-Dynamik und Julia-Menge
• die meisten schlechten Startwerte gehören zu solchen
kleinen Kopien von gefüllten Julia-Mengen quadratischer
Polynome (alle anderen bilden eine Nullmenge)
Wir müssen für die „nützlichen“ Fragen über die NewtonDynamik die „nutzlose“ Theorie der iterierten Polynome
kennen!
29
Newton-Dynamik und Julia-Menge
• Liegt jeder Punkt z
∈ ℂ, der nicht gegen eine Nullstelle
von p konvergiert, in dem gemeinsamen Rand aller
Bassins? Und kann dieser gemeinsame Rand positives
Maß haben?“
• Es gibt Polynome p derart, dass der Rand des Bassins
einer Nullstelle, positives Maß hat (also keine vereinzelte
Punkte darstellt), da dieser Rand eine Kopie des Rands
der gefüllten Julia-Menge eines quadratischen Polynoms
enthält, deren Maß positiv ist. Also: Es konvergieren nicht
fast alle Punkte in ℂ unter Iteration von Np gegen eine
Nullstelle von p.
30
Newton-Dynamik und Julia-Menge
• Es konnte sogar gezeigt werden, dass Frage 2 eintritt und
somit der „schlechteste Fall“ Realität ist
• Da gefüllte Julia-Menge von quadratischen Polynomen
offene Mengen enthalten kann, können
Newtonabbildungen offene Mengen „schlechter
Startwerte“ haben
31
Newton-Dynamik und Julia-Menge
• Aufgrund dieser Antwort kam es zu einer 5. Frage:
• 5. Wie klassifiziere man die Polynome p (mit beliebigem
Grad), deren Newtonabbildungen Np offene Mengen
schlechter Startwerte besitzen?
• Auch hierfür die angeblich „nutzlose“ Theorie über die
Dynamik iterierter Polynome herangezogen
32
Newton-Dynamik und Julia-Menge
• In allen Graden d ≥ 3 sind (bis auf eine Nullmenge) alle
„schlechten“ Startwerte in kleinen Kopien von JuliaMengen bestimmter Polynome enthalten, und für deren
Klassifikation benötigt man eine Klassifikation aller
iterierten Polynome.
33
Newton-Dynamik und Mandelbrot-Menge
Überlegung: Wann haben die kubischen Polynome unter
Iteration von 𝑁𝑝 offene Mengen schlechter Startwerte?
𝑝 𝑧 = 𝑐 𝑧 − 𝛼1 𝑧 − 𝛼2 𝑧 − 𝛼3 mit 𝑐, 𝛼𝑖 ∈ ℂ
…
𝑝λ 𝑧 = 𝑧 𝑧 − 1 𝑧 − λ
 Man muss nur den einzigen Punkt 𝑧 ∈ ℂ \ {𝛼1 , 𝛼2 , 𝛼3 } mit
𝑁 ′ λ 𝑧 = 0 unter Iteration betrachten
 konvergiert er nicht, so gibt es für dieses λ offene Mengen
schlechter Startwerte!
34
Newton-Dynamik und Mandelbrot-Menge
Abb. 8: Die λ − Ebene kubischer Polynome 𝑝λ 𝑧
 Zum Verstehen der „schlechten kubischen Polynome“ muss
man bereits die Mandelbrotmenge verstehen!
35
Forschung am Newton-Verfahren
• Problem: Selbst wenn fast alle Startwerte gegen
irgendeine Nullstelle konvergieren, ist noch nicht klar, wie
man auf diese Weise alle Nullstellen finden soll
• Ziel: Newton-Verfahren zu einen „richtigen“ Algorithmus
machen und ein „Rezept“ der folgenden Form zu erhalten:
„Gegeben sind ein Polynom p vom Grad d ≥ 2 und eine Fehlertoleranz
ε > 0. Wähle die Startwerte z(1), . . . , z(k) mit k ≥ d (X) und iteriere die
Newtonabbildung an diesen Punkten, bis die folgende Bedingung gilt
(X). Dann gibt es d Punkte auf den iterierten Orbits (X), so dass jede
der d Nullstellen von p von einem von ihnen höchstens Abstand ε hat.“
36
Forschung am Newton-Verfahren
• Hauptproblem (u.a.) ist, dass ein Orbit zn =Np◦n(z0) einen
Punkt z erreichen könnte, in dem p‘(z) sehr nahe an 0 ist,
so dass Np(z) = z − p(z)/p‘(z) nahe an ∞ ist, und es
anschließend lange dauert, bis der Orbit wieder die
Gegend der Nullstellen erreicht. Daher ist die Dynamik
schwer zu kontrollieren.
• Methoden der komplexen Dynamik (insbesondere die
„nutzlosen“ Teile der Theorie) können helfen, das
Verfahren zu verbessern
37
Forschung am Newton-Verfahren
„Gegeben sei ein (auf eine bestimmte Weise normiertes)
Polynom vom Grad d ≥ 2. Dann kann man eine recht kleine
Menge von k = 1.11*d*log² (d) Startwerten z(1), z(2), . . . ,
z(k) angeben, so dass es für jede Nullstelle α von p
mindestens einen Startwert gibt, der unter Iteration von Np
gegen α konvergiert.“
• Hängt nur vom Grad und nicht vom Polynom selbst ab
38
Forschung am Newton-Verfahren
• Dies führt zur Beantwortung von Frage 3:
• 3. Sei p ein Polynom vom Grad d ≥ 2, von dem wir nur
wissen, dass alle Nullstellen von p in der komplexen
Einheitsscheibe D liegen. Wie können wir Startpunkte
finden, so dass uns die Newton-Iteration alle Nullstellen
liefert?
Man kann die Menge der Startwerte explizit aufschreiben;
die Punkte sind auf log d konzentrischen Kreisen um den
Ursprung gleichverteilt. Die Anzahl der Punkte lasst sich
sogar deutlich auf etwa d*(log log d)² reduzieren, wenn
man einige von ihnen zufällig verteilt!
39
Rückblick
• Probleme/Erkenntnisse der „nutzlosen“ Theorie über
Dynamik iterierter Polynome dargelegt
 (gefüllte) Julia-Menge und Mandelbrot-Menge
• Anwendung auf und Erkenntnisse über die Dynamik des
Newton-Verfahrens aufgezeigt
40
Fazit
• Grundstein für auf Newton-Verfahren basierenden Algorithmus
gelegt
• Frage 4 immer noch offen (Vermutung, dass auch hier die
gleichen Ansätze zur Lösung führen)
(4. Wie oft muss man von passenden Startpunkten iterieren, um alle
Nullstellen mit einer bestimmten Genauigkeit ε > 0 zu finden?)
 Newton-Verfahren möglicherweise doch ein besserer
Algorithmus, als man immer dachte?
 Kein Teil der Mathematik sollte als „nützlich“ oder „nutzlos“
eingestuft werden!
… „Wir bauen alle gemeinsam am „Haus“ der Mathematik“…
41
Abbildungsverzeichnis
Abbildung 1:
https://de.wikipedia.org/wiki/Julia-Menge#/media/File:Julia-set_z2%2Bc_-0.742_0.1_5000.jpg
Abbildung 2:
D. Schleicher; M. Lackmann (Hrsg.): Eine Einladung in die Mathematik. 2013, S. 215, Abb. 1.
Abbildung 3:
https://de.wikipedia.org/wiki/Julia-Menge#/media/File:Julia-Teppich.png
Abbildung 4:
D. Schleicher; M. Lackmann (Hrsg.): Eine Einladung in die Mathematik. 2013, S. 218. Abb. 2.
Abbildung 5:
http://media05.myheimat.de/2008/01/30/105986_web.jpg?1201722910
Abbildung 6:
D. Schleicher; M. Lackmann (Hrsg.): Eine Einladung in die Mathematik. 2013, S. 220.
Abbildung 7:
D. Schleicher; M. Lackmann (Hrsg.): Eine Einladung in die Mathematik. 2013, S. 222.
Abbildung 8:
D. Schleicher; M. Lackmann (Hrsg.): Eine Einladung in die Mathematik. 2013, S. 224..
42
Literaturverzeichnis
• D. Schleicher; M. Lackmann (Hrsg.): Eine Einladung in
die Mathematik. 2013, S. 213-228.

Download Report