Globale Aspekte des kontinuierlichen Newton-Verfahrens

Immo Diener

Habilitationsschrift Göttingen Oktober 1991 Inhaltsverzeichnis

Vorwort i 1 Einführung 1 2 Newton–Blätter 8

2.1 Außerordentliche Singularitäten . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Einige Eigenschaften von Newton–Blättern . . . . . . . . . . . . . . . . . . 14

3 Die Graphen Γ^{k}(F, B) 20 4 Komplexe Newton–Flüsse 30 5 Zusammenhängende Newton-Blätter 33 6 Verallgemeinerungen 41 Literatur 44

Vorwort

Das Newton-Verfahren ist Vater und Mutter aller guten numerischen Verfahren.

Jochen Werner

Ausgangspunkt dieser Arbeit ist eine Fragestellung der globalen Optimierung: Gegeben eine differenzierbare Abbildung F : X → Y zwischen Teilmengen X, Y des IR^{n}. Bestimme Null(F, X), die Menge aller Nullstellen von F in X. Gesucht ist also letztlich ein numerisches Verfahren, das alle Nullstellen von F in einem noch zu präzisierenden Sinne approximiert.

Das klassische Hilfsmittel zur Bestimmung einer Nullstelle von F ist das Newton-Verfahren. Dabei geht man bekanntlich aus von einem Startwert x_{0}, linearisiert dort das Problem und setzt als nächste Iterierte x_{1} die Lösung des linearisierten Problems an. Dann verfährt man mit x_{1} wie zuvor mit x_{0}.

Unter geeigneten Voraussetzungen kann man die Konvergenz dieses Verfahrens gegen eine Nullstelle von F beweisen. Eine wichtige dieser Voraussetzungen ist, daß x_{0} schon “hinreichend dicht” an einer Nullstelle von F liegt. Es handelt sich also um ein lokales Verfahren.

Der Konvergenzbereich des klassischen Newton-Verfahrens läßt sich verbessern, wenn man eine Schrittweitenstrategie einführt. Daß heißt, man nimmt als nächste Iterierte nicht die Lösung des im gegenwärtigen Punkt linearisierten Problems, denn diese liegt manchmal “zu weit ab” von der gesuchten Nullstelle. Man nimmt stattdessen als nächste Iterierte eine Konvexkombination zwischen dem gegenwärtigen Aufpunkt und der Lösung des linearisierten Problems. Mit geeigneten solchen Schrittweitenstrategien läßt sich der Konvergenzbereich des Newton-Verfahrens in der Tat vergrößern.

Betrachtet man nun den Grenzfall, daß man sich in jedem Schritt nur noch “beliebig wenig” vom gegenwärtigen Aufpunkt wegbewegt, so gelangt man von der ursprünglichen Iterationsvorschrift zu einem autonomen Differentialgleichungssystem und statt der Folge der Iterierten wird nun die zugehörige Lösungstrajektorie Gegenstand der Untersuchung. Dieses Differentialgleichungssystem heißt die Newtonsche Differentialgleichung zu F:

dx/dt = −DF (x)^{−1}F (x).

Umgekehrt läßt sich das relaxierte Newton-Verfahren nun als Eulersches Verfahren zur Lösung der Newtonschen Differentialgleichung auffassen. Das mit der Integration der Newtonschen Differentialgleichung verbundene Verfahren heißt das kontinuierliche Newton-Verfahren.

Der geschilderte Zusammenhang zwischen dem relaxierten Newtonverfahren und der kontinuierlichen Version wirft die Frage auf, wie die Einzugsbereiche der Nullstellen des kontinuierlichen Verfahrens mit den Einzugsbereichen des relaxierten Verfahrens für bestimmte Schrittweitensteuerungen zusammenhängen. Dabei gehört ein Punkt x_{0} zum Einzugsbereich der Nullstelle x^{∗} bezüglich des relaxierten Verfahrens, wenn die Iterierten des in x_{0} gestarteten relaxierte Newtonverfahrens gegen x^{∗} konvergieren. Dagegen gehört x_{0} zum Einzugsbereich des kontinuierlichen Verfahrens, wenn die durch x_{0} verlaufende Trajektorie x(t) der Newtonschen Differentialgleichung für wachsende t gegen x^{∗} konvergiert. Kann man die Einzugsbereiche des relaxierten Verfahrens durch die des kontinuierlichen Verfahrens approximieren? Welche strukturellen Rückschlüsse kann man vom kontinuierlichen Verfahren auf das relaxierte ziehen?

Die Einzugsbereiche der Nullstellen des relaxierten Newtonverfahrens können, wie neuere Ergebnisse der Theorie der dynamischen Systeme zeigen, sehr wild aussehen. Dagegen lassen sich die Phasenportraits des kontinuierlichen Verfahrens, also die Familien der Integralkurven, jedenfalls für den Fall meromorpher Abbildungen auf Gebieten der komplexen Zahlenebene einigermaßen vollständig charakterisieren. Nach frühen Arbeiten von Braess [2] und Smale [22] gelang es Jongen, Jonker und Twilt [14, 23] die Newton-Flüsse für gewisse Klassen rationaler Funktionen im Komplexen graphentheoretisch zu charakterisieren. Meier [19] untersuchte in seiner Dissertation das Phasenportrait der Newtonschen Differentialgleichung für meromorphe Funktionen auf beliebigen Teilgebieten von C I. Er zeigt, in welcher Weise sich gewisse charakteristische Eigenschaften des Phasenportraits auf das relaxierte Newtonverfahren bei kleinen Schrittweiten übertragen lassen und wendet seine Ergebnisse an, um Aussagen über die Julia-Mengen der Iterationsfunktion des relaxierten Newton-Verfahrens zu gewinnen. Diese Ergebnisse wurden dann in [1] weiter ausgebaut.

Für die allgemeine Theorie des kontinuierlichen Newtonverfahrens im IR^{n} ist die Tatsache unangenehm, daß die rechte Seite der Newtonschen Differentialgleichung i.a. nicht auf dem ganzen Raum definiert ist. Man kann die Gleichung jedoch “desingularisieren”, indem man rechts statt der Inversen der Funktionalmatrix DF (x) die adjungierte Matrix D̃F(x) einsetzt. Man gelangt so zu der desingularisierten Newtonschen Differentialgleichung

dx/dt = −D̃F(x)F (x),

deren rechte Seite nun auf dem ganzen IR^{n} definiert ist. Da die kontinuierliche Newtonsche Differentialgleichung und die desingularisierte Version bis auf den Faktor det DF (x) übereinstimmen, stimmen die Phasenportraits der beiden Gleichungen in den Punkten, in denen DF (x) nicht singulär ist, überein (bis auf die Orientierung). Die Einzugsbereiche einer Nullstellen von F bezüglich des desingularisierten kontinuierlichen Verfahrens ist gegenüber dem des gewöhnlichen kontinuierlichen Verfahrens i.a. wesentlich größer. Die Erleichterung beim Übergang von der gewöhnlichen zur desingularisierten Version hat man sich aber mit einer neuen Schwierigkeit erkauft. Die rechte Seite der desingularisierten Gleichung kann nämlich auch verschwinden, ohne daß eine Nullstelle von F vorliegt. Solche Punkte nennen wir “außerordentliche Singularitäten” von F. Die Struktur der Menge dieser außerordenntlichen Singularitäten wurde für den Fall, daß F Gradient einer Funktion ist, von Jongen, Jonker und Twilt in mehreren Arbeiten untersucht. Eine Zusammenfassung der Ergebnisse wird weiter unter gegeben (siehe auch [15]).

Das desingularisierte kontinuierliche Newtonverfahren wurde 1972 von Branin in [3] angewandt, um mehrere Nullstellen einer nichtlinearen Funktion mehrerer Veränderlicher zu bestimmen. Es handelte sich dabei um den Entwurf eines elektronischen Schaltkreises mit Tunneldioden und das Newton-Verfahren konvergierte immer wieder gegen dieselbe Nullstelle. Branins Idee war, das Verfahren nicht in einer gefundenen Nullstelle abzubrechen und irgendwo anders neu aufzusetzen, sondern über die gefundene Nullstelle “hinwegzuintegrieren” und dabei das Vorzeichen der rechten Seite der desingularisierten Newtonschen Differentialgleichung herumzudrehen. Dadurch wird eine Nullstelle, die zuvor ein anziehender Fixpunkt war, zu einem abstoßenden Fixpunkt und er hoffte, beim weiteren Verfolgen der Lösungskurve auf weitere Nullstellen zu stoßen. Diese Hoffnung erfüllte sich in seinem Anwendungsfall und er war auch in weiteren Fällen erfolgreich.

Branins Arbeit regte in der Folge viele Untersuchungen dieses Verfahrens an, und man hoffte, (im Einzelfalle überprüfbare) globale Kriterien finden zu können, unter denen man etwas über das Verhalten des so “fortgesetzten” Verfahrens beweisen könnte. Leider erwies sich diese Hoffnung als trügerisch. Bis heute ist kein auf eine breite Klasse nichtlinearer Funktionen anwendbares Kriterium bekannt, das sich im konkreten Falle überprüfen ließe und garantieren würde, daß das Braninsche Verfahren, gestartet in einem Punkt x_{0}, alle Nullstellen einer Funktion F : IR^{n} → IR^{n} liefern würde.

Der Grund für die Schwierigkeit ist leicht auszumachen. Er liegt im sogenannten “Eindellargument”: Ein praktisches Verfahren stoppt nach endlich vielen Schritten, hat also die Funktion in großen Teilen des interessierenden n-dimensionalen Grundbereichs nicht untersucht. Hätte es nun alle Nullstellen von F gefunden, so könnte man doch leicht eine Funktion G angeben, die mit F in einer Umgebung des gesamten untersuchten Bereichs übereinstimmt, außerhalb dieses Bereichs aber zusätzliche Nullstellen besitzt. Diese würde das Verfahren dann nicht finden.

Eine Voraussetzung an F, die dieses Argument ausschließt, muß globaler Natur sein und lokale Modifikationen von F verbieten – zweifellos eine wesentliche Einschränkung der in Betracht kommenden Funktionenklasse, denn mit Beschränkungen wie “Sei F ein Polynom” ist, ohne Gradbeschränkung, wegen des Approximationssatzes von Weierstraß auch nicht viel gewonnen. Immerhin kann die Spezifizierung einer speziellen Struktur das Eindellargument umgehen; so liegen z.B. für den Fall gewisser Polynome theoretisch global konvergente Homotopieverfahren vor.

Übrigens gibt es intervallarithmetische Verfahren, die unter relativ schwachen Voraussetzungen garantieren, daß alle Nullstellen gefunden werden. Hier wird das Eindellargument raffiniert dadurch überlistet, daß in einige Iterationsschritte globale Informationen über den Wertebereich der Funktion einfließen, die nicht a priori vorgegeben werden müssen, sondern die sich das Verfahren selbst beschafft. Leider laufen die Intervallverfahren bisher im wesentlichen auf Teile-und-Herrsche-Verfahren hinaus und sind daher in höheren Dimensionen viel zu langsam.

Zurück zum kontinuierlichen Newton-Verfahren. Es wird nicht nur zur praktischen Berechnung von Nullstellen angewandt, sondern kommt auch als Beweishilfsmittel in Betracht, um die Existenz einer Nullstelle in einem gewissen Bereich zu zeigen. So wird, beispielsweise, das kontinuierliche Newton-Verfahren (in Fréchet-Räumen) beim Beweis des tiefliegenden Satzes von Nash und Moser über Umkehrabbildungen angewandt, und zwar um die Surjektivität der Abbildung zu zeigen. Eine ausgezeichnete Darstellung der Theorie mit vielen Anwendungsbeispielen findet man in [10].

Die Lösungstrajektorien des kontinuierlichen Newtonverfahrens haben die Eigenschaft, daß die Richtung von F auf den Trajektorien konstant ist. Beginnt man das Verfahren im Startpunkt x_{0} := x(0), dann gilt genauer:

F (x(t)) = F (x(0))e^{−t}.

Läßt sich die in x(0) beginnende Trajektorie also bis t = ∞ integrieren, so endet sie in einer Nullstelle von F. Das legt die Idee nahe, die Kurven des Verfahrens nicht durch eine Differentialgleichung zu definieren, sondern die geschilderte Eigenschaft des kontinuierlichen Newton-Verfahrens zur Grundlage einer verallgemeinerten Definition von Newton-Trajektorien zu machen. Eine Newton-Trajektorie in diesem Sinne besteht dann aus der Menge aller Punkte x, in denen F (x) eine vorgegebene Richtung hat. Dieser Ansatz soll in der vorliegenden Arbeit verfolgt werden. Er erlaubt es, globale Aussagen über den Verlauf einer Newton-Trajektorie zu machen, die im Sinne Branins durch Hinwegintegrieren über die Nullstellen von F entsteht.

Es zeigt sich, daß diese Newton-Trajektorien auf bestimmten k-dimensionalen Untermengen des IR^{n} leben, die, abgesehen von der Umgebung gewisser Ausnahmepunkte (i.a. gerade den außerordentlichen Singularitäten von F) Mannigfaltigkeiten sind. Diese Mengen werden im folgenden k-Newton-Blätter getauft. Eine Newton-Trajektorie ist dann ein 1-Newton-Blatt. Diese Mengen haben die besondere Eigenschaft, daß auf jedem Newton-Blatt alle Nullstellen von F liegen. Findet man also ein zusammenhängendes k-Newton-Blatt, dann kann man das n-dimensionale Problem, alle Nullstellen von F zu finden, auf ein k-dimensionales Problem reduzieren, nämlich auf die Suche nach den Nullstellen von F auf diesem k-Blatt. Darin liegt unter anderem die praktische Bedeutung der k-Newton-Blätter.

Im Kapitel 1 geben wir einleitende Definitionen und referieren einige grundlegende Ergebnisse zum (desingularisierten und gewöhnlichen) kontinuierlichen Newton-Verfahren, präzisieren einige Aussagen des vorliegenden Abschnitts und beweisen, daß der Einzugsbereich einer Nullstelle beim (desingularisierten und gewöhnlichen) kontinuierlichen Newton-Verfahren zusammenziehbar ist.

Kapitel 2 bringt die eigentliche präzise Definiton von Newton-Blättern und stellt einen Zusammenhang zwischen Newton-Trajektorien und einer bekannten Klasse von Homotopie-Verfahren her. Kapitel 2.1 enthält eine präzise Definition der außerordentlichen Singularitäten und stellt einige grundlegende Dinge über diese Ausnahmepunkte zusammen.

Im Kapitel 2.2 werden topologische und geometrische Ergebnisse über die Struktur von Newton-Blättern bewiesen. Zunächst wird gezeigt, daß verschiedene Newton-Blätter sich nicht tangential berühren und nicht beliebig dicht an nichtentarteten Nullstellen von F vorbeilaufen können. Dann beweisen wir, daß aufeinanderfolgende Nullstellen auf einer Newton-Trajektorie verschiedenen Index haben müssen. Daraus folgt dann, daß kompakte k-Blatt-Komponenten stets eine gerade Anzahl von Nullstellen enthalten. Sodann betrachten wir den Fall, daß es zu F kompakte (n−1)-Blatt-Komponenten gibt, auf denen keine Nullstellen von F liegen und ziehen einige Folgerungen.

Wie oben schon angedeutet, wird man i.a. kein niederdimensionales zusammenhängendes k-Blatt (im Idealfalle also eine zusammenhängende Newton-Trajektorie) finden können. Wir werden die Fragestellung daher abschwächen und im Kapitel 3 zunächst untersuchen, ob die Nullstellen einer Funktion sich wenigstens durch eine Folge zusammenhängender Newton-Blätter verbinden lassen. Dazu werden wir gewisse Graphen Γ^{k} definieren, deren Struktur widerspiegelt, wie verschiedene Newton-Blatt-Komponenten die Nullstellen verbinden. Ein erstes Ergebnis in dieser Richtung wurde für Newton-Trajektorien schon in [13] angegeben. Wir werden dieses Ergebnis wesentlich verallgemeinern und praktisch einigermaßen brauchbare Kriterien für den Zusammenhang der Graphen Γ^{k} angeben.

Im Kapitel 4 betrachten wir kurz Newton-Flüsse in der komplexen Zahlenebene und wenden die Ergebnisse des vorigen Kapitels auf diesen Fall an. Nebenbei stellen wir fest, daß komplexe Newton-Flüsse sich als Gradienten-Flüsse darstellen lassen.

Im Kapitel 5 beschäftigen wir uns mit der Frage, unter welchen Voraussetzungen man garantieren kann, daß alle k-Newton-Blätter zu F zusammenhängend sind, oder daß es wenigstens ein zusammenhängendes Newton-Blatt gibt. Für den Fall von Newton-Trajektorien hatte Branin zu dieser Frage in der oben zitierten Arbeit eine Vermutung geäußert, die sich aber als falsch erweist. Im Fall von nur zwei Dimensionen gilt sogar, bis auf triviale Ausnahmen, das Gegenteil von Branins Vermutung.

Dann untersuchen wir die Frage, unter welchen Voraussetzungen es zusammenhängende Newton-Blätter gibt. Auf dieses Problem läßt sich jede globale Version des Satzes über implizite Funktionen anwenden. Leider sind die Voraussetzungen für solche Sätze (notwendig) sehr stark, so daß sich die sich daraus ergebenden Resultate über Newton-Blätter nicht allgemein anwenden lassen. Für den Fall von nur 3 Nullstellen kann man jedoch immerhin unter leichten Zusatzvoraussetzungen bei zusammenhängendem Γ^{1} auf die Existenz einer Trajektorien-Komponente schließen, die alle Nullstellen von F enthält.

Der Leser wird sehen, daß man an verschiedenen Stellen weiter käme, wenn man ein noch allgemeineres Konzept von Newton-Trajektorien (oder Newton-Blättern) zur Hand hätte, nämlich eines für Funktionen auf einer differenzierbaren, im IR^{n} eingebetteten Mannigfaltigkeit. Man möchte gerne die in einem k-Blatt enthaltenen Newton-Trajektorien als verallgemeinerte Newton-Trajektorien einer Funktion auf diesem k-Blatt ansehen. Im Kapitel 6 betrachten wir kurz einige Möglichkeiten zu derartigen Verallgemeinerungen und diskutieren noch einige Transformationseigenschaften von Newton-Trajektorien.

Gegenüber früheren Untersuchungen des kontinuierlichen Newtonverfahrens werden in dieser Arbeit statt auf der Newtonschen Differentialgleichung beruhender analytischer Methoden hauptsächlich algebraische und topologische Methoden verwandt. Wie gezeigt wird, ermöglicht es dieser Zugang, Aussagen über die Geometrie und die Topologie der Trajektorien nicht nur “zwischen den Nullstellen”, sondern im ganzen Grundraum zu machen. Die Idee der k-Newton-Blätter liefert einen Überblick über den Verlauf einer ganzen Schar von Newton-Trajektorien und erlaubt es, das n-dimensionale Problem der Bestimmung aller Nullstellen von F auf ein k-dimensionales Problem zurückzuführen. Die sogenannten freien (n − 1)-Newton-Blätter gestatten eine geometrische Charakterisierung jener Bereiche, in denen das kontinuierliche Newton-Verfahren (das gewöhnliche und das desingularisierte) nicht gegen eine Nullstelle von F konvergieren.

Die Graphen Γ^{k} beschreiben in abstrakter Form, was in Bezug auf das Problem, alle Nullstellen von F zu bestimmen, mit Hilfe der “Verfolgung” von Newton-Trajektorien prinzipiell möglich ist. Die Ergebnisse über die Zusammenhangseigenschaften dieser Graphen kommen — im Unterschied zu früheren Untersuchungen — ohne die Voraussetzung aus, daß es keine außerordentlichen Singularitäten gebe — in der Praxis gibt es fast immer welche — und gelten nicht nur, wenn der Grundraum der ganze IR^{n} ist, sondern für nahezu beliebige Teilmengen des IR^{n}. Die Sätze über den Zusammenhang von Newton-Blättern geben Bedingungen an, unter denen die Bestimmung aller Nullstellen von F auch praktisch mit Hilfe von Kurvenverfolgungsalgorithmen möglich ist, oder unter denen man sich bei der praktischen Nullstellenbestimmung von vornherein auf ein wohlbestimmtes, zusammenhängendes k-Blatt beschränken kann.

Die in dieser Arbeit eingeführte einfache algebraische Definition von Newton-Blättern gestattet es auch, effiziente numerische Algorithmen zum Verfolgen von Newton-Trajek-torien oder zum Absuchen von k-Newton-Blättern zu entwickeln. Ein erster Ansatz, der zeigt, wie man die besondere Struktur numerisch verwerten kann, ist in [6] enthalten. Was die Aussagen über Newton-Blätter für das globale Verhalten des relaxierten Newtonverfahrens bedeuten (bzw. für eine im Sinne dieser Arbeit naheliegende desingularisierte Version desselben) läßt sich noch nicht abschließend feststellen. Die Erwartung, daß man für genügend kleine Schrittweiten in der Nähe einer bestimmten Komponente einer Newton-Trajektorie bleibt, wird höchstens gelten, wenn keine außerordentlichen Singularitäten in der Nähe der Trajektorie liegen. Wenn man z.B. weiß, daß keine Newton-Trajektorie frei ist, wird man noch nicht garantieren können, daß das relaxierte desingularisierte diskrete Newtonverfahren bei hinreichend kleiner Schrittweite von jedem Startpunkt aus gegen eine Nullstelle von F konvergiert. Dazu sind weitere Stabilitätsbetrachtungen nötig. Insbesondere wird man dazu den Grundraum nicht mehr als nahezu beliebige Teilmenge des IR^{n} wählen können.

So manche in dieser Arbeit aufgeworfene Frage muß zunächst unbeantwortet bleiben. Eine für die Praxis besonders wichtige Aufgabe besteht darin, schwächere Bedingungen anzugeben, die praktisch überprüfbar sind und garantieren, daß ein bestimmtes k-Blatt (am besten eine Newton-Trajektorie) zusammenhängend ist. Auch die Frage nach den möglichen topologischen Formen kompakter Newton-Blatt-Komponenten ohne Nullstellen konnte in dieser Arbeit nicht abschließend beantwortet werden. Schließlich sei noch das Problem genannt, die möglichen Verzweigungsformen von Newton-Blättern generisch zu klassifizieren. Dies ist bisher nur für Newton-Trajektorien bei kleinen Dimensionen gelöst.

Technische Bemerkung: Die leidige Frage, wie Gleichungen, Sätze usw. zu numerieren und zu referenzieren sind, ist in dieser Arbeit folgendermaßen gelöst: Referenzen haben das Format x-y, wobei x die Nummer der Gleichung oder des Satzes usw. ist, und y die Seite, auf der die betreffende Referenz zu finden ist.

1 Einführung

Sei F : IR^{n} → IR^{n}, n ≥ 2 eine differenzierbare Abbildung. Dann besteht das klassische Newton-Verfahren zur Bestimmung einer Nullstelle von F in der Iterationsvorschrift:

x_{i+1} = x_{i} − (DF (x_{i}))^{−1}F (x_{i}),

mit einem geeignet gewählten Startwert x_{0} und der Jacobi-Matrix DF (x) im Punkt x. Um den Konvergenzbereich dieses Verfahrens zu vergrößern, arbeitet man oft nicht mit dieser, sondern einer etwas modifizierten Iterationsstrategie, dem sogenannten relaxierten Newtonverfahren:

x_{i+1} = x_{i} − h_{i}(DF (x_{i}))^{−1}F (x_{i}),  (1)

wobei die Schrittweiten h_{i} “geeignet” gewählt werden. Wählt man die h_{i} genügend klein, so läßt sich das Einzugsgebiet einer Nullstelle von F im allgemeinen gegenüber dem einfachen Newton-Verfahren vergrößern und man kann hoffen, Aussagen über die Einzugsgebiete der Nullstellen von F für kleine h_{i} zu gewinnen, indem man statt der Gleichung (1-1) die autonome Differentialgleichung

dx/dt = −DF (x)^{−1}F (x)  (2)

betrachtet, die sogenannte Newtonsche Differentialgleichung zu F. (Die Frage, ob und in wieweit die Einzugsbereiche der Nullstellen von F bezüglich des relaxierten Newton-Verfahrens für verschiedene Schrittweiten durch die Einzugsbereiche bezüglich der Differentialgleichung (2-1) approximiert werden, wurde für meromorphe Funktionen in [19] untersucht.) Gleichung (1-1) läßt sich dann als Eulersches Verfahren zur Lösung der Newtonschen Differentialgleichung auffassen. Die rechte Seite von (2-1) ist nur in den Punkten definiert, in denen DF (x) nicht singulär ist.

Für den in der Optimierung wichtigen Fall, daß F Gradient einer Funktion ist, schreiben wir die Newtonsche Differentialgleichung in der Form

dx/dt = −H_{f}^{−1}(x)∇f(x).  (3)

Dabei ist H_{f}(x) := D^{2}f(x) die Hesse-Matrix von f im Punkt x und ∇f(x) der Gradient von f im Punkt x, also der (Spalten-)Vektor Df(x)^{⊤}.

Entlang einer Trajektorie x(t) von (2-1) gilt:

\frac{d}{dt}F (x(t)) = DF (x(t)) · \frac{dx}{dt} = −F (x(t)),

woraus

F (x(t)) = F (x(0))e^{−t}

folgt. Entlang einer Trajektorie nimmt also ∥F ∥ exponentiell ab, während die Richtung von F konstant bleibt. Diese Tatsache werden wir später zum Ausgangspunkt einer erweiterten Definition von Newton-Trajektorien machen.

Die Tatsache, daß die rechte Seite von (2-1) nicht auf dem ganzen IR^{n} definiert ist, ist sowohl für die praktische Rechnung, als auch für theoretische Untersuchungen recht lästig, denn die Menge der Punkte, in denen DF (x) singulär wird, kann ziemlich wild aussehen und in der Nähe solcher Punkte wird die rechte Seite unbeschränkt. Man betrachtet daher statt der Gleichung (2-1) eine desingularisierte Form:

dx/dt = −D̃F(x)F (x).  (4)

Dabei bezeichnen wir mit Ã die zu der n × n-Matrix A adjungierte Matrix, also die Transponierte der Matrix, deren Element m_{ij} die mit dem Vorzeichenfaktor (−1)^{i+j} versehene Determinante der Matrix ist, die aus A entsteht, indem die i-te Zeile und die j-te Spalte gestrichen werden. Es gilt also für jede n × n-Matrix A:

ÃA = det(A)I,

wobei I die n × n-Einheitsmatrix sei.

Auf dem Definitionsbereich von (2-1) stimmen also die Phasenportraits von (2-1) und (4-2), abgesehen von der Orientierung überein. Wie bei der Differentialgleichung (2-1) bleibt auch auf den Lösungskurven der Differentialgleichung (4-2) die Richtung von F konstant. Das System (4-2) läßt sich also als Erweiterung des Systems (2-1) auf den ganzen IR^{n} auffassen. Das durch (4-2) gegebene Vektorfeld auf dem IR^{n} bezeichnen wir mit N (F) und die Gleichung (4-2) nennen wir die desingularisierte Newtonsche Differentialgleichung.

Im Falle F (x) = ∇f(x) schreiben wir statt (4-2)

dx/dt = −H̃_{f}(x)∇f(x),  (5)

und das zugehörige Vektorfeld auf dem IR^{n} bezeichnen wir mit N (f).

Die Nullstellen von F sind Singularitäten (Gleichgewichtspunkte) der Differentialgleichung(4-2). Wir setzen im folgenden stets voraus, daß die Nullstellen von F (die kritischen Punkte von f) nicht entartet (nicht degeneriert) sind, daß also in diesen Punkten DF (x) (bzw. H_{f}(x)) nicht singulär ist.

Wie die Linearisierung der Differentialgleichung in einer nichtentarteten Nullstelle zeigt, sind solche Singularitäten entweder anziehende (wenn det DF (x) > 0), oder abstoßende (wenn det DF (x) < 0) Fixpunkte (Knoten) von (4-2).

Neben solchen Singularitäten gibt es auch noch andere, nämlich solche, in denen F (x) ≠ 0 ist, und trotzdem D̃F(x)F (x) verschwindet. Solche Singularitäten nennen wir außerordentliche Singularitäten. Wir werden sie später noch anders charakterisieren und die Definition verallgemeinern.

Wir zitieren nun einige globale Resultate über das Verhalten der Lösungskurven zu der Differentialgleichung (4-2).

Sei M eine kompakte, zusammenhängende, 1-kodimensionale C^{∞}-Mannigfaltigkeit im IR^{n}. Dann besteht IR^{n} \M aus zwei offenen Komponenten, deren eine beschränkt ist. Wir nennen die beschränkte Komponente das Innere von M und bezeichnen sie mit M_{int}.

Definition 1 Wir sagen M erfüllt die Randbedingung bezüglich des Vektorfeldes N (F), wenn N (F) transversal zu M ist, das heißt, wenn in jedem Punkt x ∈ M der Tangentialraum T_{x}M an M in x zusammen mit dem Vektor N (F)|_{x} den ganzen IR^{n} aufspannt. M heißt dann ein globaler Rand zu N (F). Außerdem nehmen wir o.E. an, daß N (F) ins Innere von M zeigt. ◇ Abbildung 1: Lokales Phasenportrait und Trajektorien der Differentialgleichungen (2-1) und (4-2).

Zitat 1 (siehe[22]) F : IR^{n} → IR^{n} besitze keine degenerierten Nullstellen und M ⊂ IR^{n} sei ein globaler Rand zu N (F). Dann gibt es eine abgeschlossene Teilmenge Σ ⊂ M vom Maß Null in M, so daß für jeden Punkt x ∈ M \ Σ die in x beginnende Lösung von (4-2) für t → ∞ gegen eine Nullstelle von F in M_{int} konvergiert. ◇

Zum Beweis werden der Satz von Sard und die weiter unten definierte Trajektorienabbildung τ_{F} herangezogen.

Zitat 2 (siehe[15]) F : IR^{n} → IR^{n} besitze keine degenerierten Nullstellen und M ⊂ IR^{n} sei ein globaler Rand zu N (F). Außerdem enthalte M_{int} keine außerordentlichen Singularitäten von F. Dann gilt:

• M_{int} enthält keine periodischen Trajektorien der desingularisierten Newtonschen Dif-

ferentialgleichung.

• M ist diffeomorph zur Sphäre S^{n−1} ⊂ IR^{n}.

• M_{int} enthält genau eine Nullstelle von F.

◇

Wenn M_{int} außerordentliche Singularitäten enthält, gelten die Aussagen des Satzes im allgemeinen nicht mehr. Wenn F also mehr als eine Nullstelle besitzt, gibt es entweder keinen beide Nullstellen umfassenden globalen Rand zu N (F), oder aber F besitzt außerordentliche Singularitäten. Wie einfache Beispiele zeigen, kann beides in der Praxis vorkommen. Insbesondre läßt sich, wie wir noch sehen werden, das Auftreten außerordentlicher Singularitäten im allgemeinen nicht ausschließen, wenn die betrachtete Funktionenklasse nicht außerordentlich stark eingeschränkt wird.

Bekanntlich können die Einzugsbereiche von Nullstellen beim gewöhnlichen und auch beim relaxierten Newton-Verfahren selbst in einfachsten Fällen sehr wild aussehen. In der neueren Dissertation [19] bewies Meier, daß der Einzugsbereich der Nullstellen meromorpher Funktionen im Komplexen bezüglich des kontinuierlichen Newton-Verfahrens einfach zusammenhängend ist. Eine entsprechende Aussage gilt auch für den Einzugsbereich des desingularisierten kontinuierlichen Newtonverfahrens im Komplexen. Wie die Desingularisierung für meromorphe Funktionen vorgenommen werden kann, findet man in z.B. in [14]. In folgenden soll gezeigt werden, daß eine schärfere Aussage ganz allgemein gilt, und zwar sowohl für die Einzugsbereiche des kontinuierlichen Newton-Verfahrens, wie für die (i.a. viel größeren) Einzugsbereiche des desingularisierten kontinuierlichen Newton-Verfahrens. Die Einzugsbereiche sind i.a. nicht nur einfach zusammenhängend, sondern sogar zusammenziehbar.

Lemma 1 Sei ϕ : IR × M → M ein globaler Fluß auf der differenzierbaren Mannigfaltigkeit M und x^{∗} ein Fixpunkt von ϕ. Sei

B_{+}(x^{∗}) := {x ∈ M : lim_{t→∞} ϕ(t, x) = x^{∗}}

der “Einzugsbereich” des Fixpunktes x^{∗}. Weiter gelte für alle Folgen x_{n} → x^{∗} in B_{+}(x^{∗}) und t_{n} → ∞:

ϕ(t_{n}, x_{n}) → x^{∗}.

Dann ist der Einzugsbereich B_{+}(x^{∗}) zusammenziehbar. ◇

Beweis: Wir definieren eine Homotopie H : [0, 1] × B_{+}(x^{∗}) durch:

H(t, x) = \{ \begin{matrix}ϕ(t/(1 − t), x) & für (t, x) ∈ [0, 1) × B_{+}(x^{∗}) \\ x^{∗} & für (t, x) ∈ \{1\} × B_{+}(x^{∗}). \end{matrix}

Dann ist offenbar H(0, ·) die Identität auf B_{+}(x^{∗}) und H(1, ·) konstant. Wenn H also stetig ist, dann ist die Identität auf B_{+}(x^{∗}) null-homotop und folglich B_{+}(x^{∗}) zusammenziehbar.

In den Punkten von [0, 1) × B_{+}(x^{∗}) ist H offenbar stetig, weil ϕ stetig ist und die Stetigkeit in (1, x^{∗}) wird durch die Voraussetzung im Satz garantiert.

Um die Stetigkeit in (t̂, x̂) ∈ {1}×(B_{+}(x^{∗})\{x^{∗}}) zu zeigen, müssen wir für jede Folge x_{n} → x̂ und t_{n} → ∞ nachweisen:

lim_{n→∞} ϕ(t_{n}, x_{n}) = x^{∗}.

Sei U eine Umgebung von x^{∗} in B_{+}(x^{∗}), die x̂ nicht enthält. Da x^{∗} der einzige Fixpunkt von ϕ in B_{+}(x^{∗}) ist, ist für jedes x ∈ B_{+}(x^{∗}) \ {x^{∗}} die Flußlinie α_{x} : IR → M eine injektive Immersion und somit besitzt 0 ∈ IR eine Umgebung, die durch α eingebettet wird. Daraus folgt, daß die Menge

T_{U} := {t ∈ IR : ∀τ > t, x ∈ V : ϕ(τ, x) ∈ U}

auf einer genügend kleinen, zu U disjunkten Umgebung V von x̂ in B_{+}(x^{∗}) nichtleer und beschränkt ist. Sei t_{U}^{∗} > sup T_{U}. Dann liegen für genügend große n die Punkte x_{n} in V und es gilt ϕ(t_{U}^{∗}, x_{n}) ∈ U. Da das für alle Umgebungen U von x^{∗} gilt, folgt lim_{n→∞} ϕ(t_{n}, x_{n}) = x^{∗}. □

Eine entsprechende Aussage gilt natürlich für den analog definierten Einzugsbereich B_{−}(x^{∗}). Ähnlich beweist man:

Korollar 1 Sei ϕ : IR × M → M ein globaler Fluß auf der differenzierbaren Mannigfaltigkeit M, K ⊂ M und x^{∗} ∈ K ein Fixpunkt von ϕ. Sei

B_{+}(x^{∗}, K) := {x ∈ K : ∀t ≥ 0 : ϕ(t, x) ∈ K and lim_{t→∞} ϕ(t, x) = x^{∗}}

der Einzugsbereich des Fixpunktes x^{∗} bezüglich K. Weiter gelte für alle Folgen x_{n} → x^{∗} in B_{+}(x^{∗}, K) und t_{n} → ∞:

ϕ(t_{n}, x_{n}) → x^{∗}.

Dann ist der Einzugsbereich B_{+}(x^{∗}, K) zusammenziehbar. ◇

Bemerkung 1 Die Voraussetzung in Lemma 1-4, daß für alle Folgen x_{n} → x^{∗} in B_{+}(x^{∗}) und t_{n} → ∞ gelte

ϕ(t_{n}, x_{n}) → x^{∗},

ist offenbar insbesondere in folgenden Fällen erfüllt:

(1) Wenn jede Umgebung U von x^{∗} in B_{+}(x^{∗}) eine Umgebung V von x^{∗} in B_{+}(x^{∗}) enthält, so daß die Diffeomorphismen ϕ(t, ·) : M → M für t ≥ 0 die Menge V in sich abbilden.

(2) Wenn es eine stetige Funktion g : B_{+}(x^{∗}) → IR gibt, die entlang der Flußlinien ϕ(·, x) für wachsende t streng monoton wächst; wenn also, beispielsweise, für alle x ∈ B_{+}(x^{∗}) gilt: ∂/∂t(g(ϕ(t, x)))|_{t=0} > 0.

◇

Die Anwendungsmöglichkeiten von Satz 1-4 beispielsweise auf Variable-Metrik-Ver-fahren, Gradientenflüsse auf kompakten Mannigfaltigkeiten und das kontinuierliche Newton-Verfahren nach Gleichung 2-1 und Gleichung 4-2 sind offensichtlich. Wenn man die infrage kommenden Vektorfelder V (x) vermöge V (x)/(1 + ∥V (x)∥^{2}) normiert, ergeben Teil 2 der Bemerkung und Lemma 1-4:

Satz 2 Sei M eine differenzierbare (evtl. berandete) Mannigfaltigkeit mit Riemannscher Metrik, f : M → IR und ϕ der Gradienten-Fluß bezüglich der gegebenen Riemannschen Metrik. Sei x^{∗} ∈ M ein Fixpunkt von ϕ. Dann ist der Einzugsbereich von x^{∗} zusammenziehbar. ◇

Entsprechend folgt aus Teil 1 der Bemerkung und Korollar 1-5:

Satz 3 Sei K ⊂ IR^{n} nichtleer und F : IR^{n} → IR^{n} auf einer offenen Umgebung von K differenzierbar. Sei x^{∗} eine nichtdegenerierte Nullstelle von F im Innern von K. Dann sind die Einzugsbereiche B_{+}(x^{∗}, K) von F in K sowohl bezüglich der durch die Newtonsche Differentialgleichungen 2-1 als auch bezüglich der durch die desingularisierte Newtonsche Differentialgleichung 4-2 gegebenen Vektorfelder offen in B und zusammenziehbar. (Dabei nehmen wir im Falle der Differentialgleichung 4-2 an, daß das Vorzeichen der rechten Seite so gewählt wird, daß x^{∗} eine anziehender Fixpunkt ist. Sonst ist B_{+}(x^{∗}, K) = {x^{∗}} und nicht offen.) ◇

Auch andere Aussagen aus [19] lassen sich auf allgemeinere Fälle übertragen. So ist, beispielsweise, das Bild F (B_{+}(x^{∗})) des Einzugsbereiches B_{+}(x^{∗}) einer nichtentarteten Nullstelle x^{∗} einer Funktion F : IR^{n} → IR^{n} bezüglich des gewöhnlichen, wie auch des desingularisierten kontinuierlichen Newton-Verfahrens ein Sterngebiet mit Sternpunkt 0 im IR^{n}. Außerdem ist F auf dem Einzugsbereich B_{+}(x^{∗}) einer nichtentarteten Nullstelle x^{∗} bezüglich des gewöhnlichen kontinuierlichen Newton-Flusses injektiv, aber dies gilt nicht mehr für die desingularisierte Differentialgleichung. Wir wollen diese Aussagen hier nicht beweisen, da sie die Fragestellung dieser Arbeit nicht direkt berühren.

Das kontinuierliche Newton-Verfahren nach (4-2) wird in der Praxis oft angewandt, um mehrere (oder sogar alle) Nullstellen einer Funktion F : IR^{n} → IR^{n} zu bestimmen, oder um (etwa im Rahmen der globalen Optimierung) alle kritischen Punkte einer Funktion zu berechnen. Die Gleichung (4-2) ist zu diesem Zweck von Branin (vgl. [3]) anscheinend erstmalig angewandt worden. Obwohl Branin nichts über das Verfahren bewiesen hat, haben die Erfolge, die er in der Praxis damit erzielte, die Untersuchung dieses Verfahrens in den folgenden Jahren stark stimuliert. Die Trajektorien der desingularisierten Newtonschen Differentialgleichung stehen auch im Zusammenhang mit den Kurven, die gewisse Homotopieverfahren generieren (siehe Seite 8).

Um (hoffentlich) mehrere Nullstellen von F zu bestimmen, wählt man (nach Branin) einen Startpunkt x_{0} und berechnet die durch x_{0} verlaufende Trajektorie der Differentialgleichung (4-2). Wie oben schon bemerkt wurde, bleibt die Richtung von F (x(t)) auf der Lösungskurve konstant, also F (x(t)) = λ(t)F (x_{0}). Konvergiert nun x(t) gegen eine Nullstelle x^{∗} von F, so ändert man das Vorzeichen der rechten Seite in (4-2) und startet das Verfahren erneut in einem dicht bei x^{∗} gelegenen Punkt, der nicht auf x(t) liegt und in dem die Richtung von F wieder gleich F (x_{0}) ist. Einen solchen Punkt gibt es, da x^{∗} bezüglich der Differentialgleichung (4-2) ein anziehender Knoten ist. Man projiziert also gewissermaßen den letzten Schritt über die Nullstelle hinweg, ändert das Vorzeichen der rechten Seite in (4-2) und setzt das Verfahren fort. Durch die Vorzeichenänderung wird x^{∗} zu einem abstoßenden Fixpunkt und das Verfahren findet im weiteren Verlauf vielleicht weitere Nullstellen.

Diese vage Beschreibung zeigt schon, daß mit dieser Idee viele Fragen verbunden sind. Zum einen betreffen diese Fragen die numerische Implementation, zum andern die Konvergenz des theoretischen Verfahrens. Beim numerischen Verfahren läßt sich natürlich die besondere Struktur der Differentialgleichung vorteilhaft ausnutzen. Numerische Realisierungen werden zum Beispiel in [11, 9, 6] beschrieben. Es zeigt sich, daß die reine Braninsche Methode “in vielen Fällen viele Lösungen liefert”. Das hat sie mit anderen Methoden der globalen Optimierung gemein. Nur, was kann man beweisen?

In dieser Arbeit soll nun ein anderer, nicht direkt auf den Differentialgleichungen (2-1) oder (4-2) beruhender Zugang zu Newton-Trajektorien verfolgt werden. Die Tatsache, daß die Anfangsrichtung von F auf einer Trajektorie erhalten bleibt, werden wir zum Ausgangspunkt einer algebraischen Definition von Newton-Trajektorien machen. Es wird sich dabei zeigen, daß diese Beschreibungsart viele Vorteile gegenüber der Beschreibung durch Differentialgleichungen hat.

2 Newton–Blätter

Sei B ⊂ IR^{n}. Wir setzen generell voraus, daß B nichtleer sei, ohne das jedesmal zu sagen. Außerdem sei grundsätzlich n ≥ 2. Dann bezeichnen wir mit M(B) die Funktionen aus C^{r}(IR^{n}, IR), die in B nur endliche viele und nicht degenerierte kritische Punkte besitzen und die keine kritischen Punkte auf dem Rand ∂B von B besitzen.

Entsprechend sei M^{∗}(B) die Menge der Funktionen aus C^{r}(IR^{n}, IR^{n}), die in B nur endlich viele Nullstellen besitzen und keine auf dem Rand von B. Außerdem seien die Nullstellen von F in B alle nicht degeneriert. Das heißt, die Funktionalmatrix DF (x) sei in allen Nullstellen von F in B nichtsingulär.

Die Differenzierbarkeitsordnung r sei dabei “hinreichend groß”. Da wir in dieser Arbeit nicht daran interessiert sind, mit möglichst wenigen Voraussetzungen auszukommen, setzen wir einfach r = ∞. Meist reicht jedoch r = 1 oder r = 2. Manchmal brauchen wir r = n, um den Satz von Sard anwenden zu können.

Mit G(k, n) sei die Grassmann–Mannigfaltigkeit der k–kodimensionalen linearen Unterräume des IR^{n} bezeichnet. G(k, n) ist kompakt und von der endlichen Dimension k(n − k), also insbesondere folgenkompakt.

Abbildungen aus dem IR^{n} in den IR^{n} bezeichnen wir meist mit F, während wir Abbildungen aus dem IR^{n} in IR meist mit f bezeichnen. Bei F interessiert uns die Menge der Nullstellen, Null(F), und bei f die Menge der kritischen Punkte, Krit(f).

Definition 2 Sei B ⊂ IR^{n} und F ∈ C(B, IR^{n}). Sei V ein k–kodimensionaler linearer Teilraum des IR^{n}. Dann heiße die Menge

F_{V} (F, B) := {x ∈ B | F (x) ∈ V^{⊥}}

ein k–Newton–Blatt zu F, oder kurz ein k–Blatt. Ein 1–Newton–Blatt nennen wir auch eine Newton–Trajektorie zu F und bezeichnen sie manchmal mit T_{g}(F), wobei g ∈ IR^{n}\{0} den Raum V^{⊥} aufspannt.

Ist weiter f ∈ C^{1}(IR^{n}, IR), dann heiße F_{V} (f, B) := F_{V} (∇f, B) ein k–Newton–Blatt zu f, oder kurz ein k–Blatt. Ein 1–Newton–Blatt nennen wir auch eine Newton–Trajektorie zu f und bezeichnen sie manchmal mit T_{g}(f), wobei g ∈ IR^{n}\{0} den Raum V^{⊥} aufspannt.

Das 0–Blatt F_{IR^{n}}(f, B) zu f ist die Menge der kritischen Punkte von f in B, die wir mit Krit(f, B) bezeichnen. Das 0-Newton-Blatt F_{IR^{n}}(F, B) zu F ist die Menge der Nullstellen von F in B, die wir mit Null(F, B) bezeichnen. Wenn die Abhängigkeit von B klar ist, schreiben wir auch kurz F_{V} (f), F_{V} (F), T_{g}(f) und T_{g}(F), sowie Krit(f) und Null(F). ◇

Der Zusammenhang der so definierten Newton-Trajektorien mit der desingularisierten Newtonschen Differentialgleichung ist offensichtlich. Die Newton-Blätter sind gewissermaßen erste Integrale der Newtonschen Differentialgleichung. Branin meinte mit seinem Ausdruck “über Nullstellen von F wegintegrieren” gerade das Verfolgen einer Newton-Trajektorie F_{V} (F).

Wir geben nun noch eine andere Darstellung für Newton-Blätter an, um auf den Zusammenhang mit gewissen Homotopieverfahren hinzuweisen. In diesem Zusammenhang sei z.B. auf die Arbeit [7] hingewiesen, die Ausführungen zum Fall k = 1 enthält.

Sei F : IR^{n} → IR^{n} und V ein k–kodimensionaler linearer Teilraum des IR^{n}. Sei v_{1}, …, v_{k} eine Basis von V^{⊥}. Dann definieren wir eine Abbildung G_{F} : IR^{n} × IR^{k} → IR^{n} durch:

(x, λ) ↦ F (x) + ∑_{i=1}^{k} λ_{i}v_{i}.

Sei weiter π : IR^{n} × IR^{k} → IR^{n} die Projektion auf die ersten n Komponenten. Dann ist offenbar F_{V} (F) = π(G^{−1}(0)).

Die folgenden Beobachtungen sind elementar.

Bemerkung 2 Sei B ⊂ IR^{n} und F : B → IR^{n} stetig. Dann gilt:

(i) Sind V, W lineare Teilräume des IR^{n} und ist V ⊂ W, dann ist W^{⊥} ⊂ V^{⊥} und daher F_{W} (F, B) ⊂ F_{V} (F, B).

(ii) Für alle linearen Teilräume V des IR^{n} ist Null(F, B) ⊂ F_{V} (F, B).

(iii) Sind V, W lineare Teilräume des IR^{n}, dann ist (V + W)^{⊥} = V^{⊥} ∩ W^{⊥} und folglich F_{V +W} (F, B) = F_{V} (F, B) ∩ F_{W} (F, B).

◇

Durch jeden Punkt x ∈ B \ Null(F) geht genau eine Newton-Trajektorie, nämlich F_{V} (F) mit V = ⟨F (x)⟩^{⊥}. Jede solche Trajektorie enthält alle Nullstellen von F und der Durchschnitt zweier Trajektorien F_{V} (F), F_{W} (F) mit V ≠ W ist gerade gleich Null(F). Das gilt ganz allgemein, also auch, wenn Nullstellen von F degeneriert sind und auf diesen simplen Tatsachen beruht das praktische Interesse an diesen Gebilden. Ist nämlich eine Newton-Trajektorie F_{V} (F) lokal eindimensional (eine endliche Vereinigung differenzierbarer eindimensionaler Mannigfaltigkeiten) und darüberhinaus zusammenhängend, dann könnte man prinzipiell F_{V} (F) numerisch verfolgen und dabei alle Nullstellen von F bestimmen.

Die Forderung, daß die Newton-Trajektorien wirklich lokal eindimensional seien, ist praktisch keine starke Einschränkung, wie wir im nächsten Kapitel sehen werden. Das wirkliche Problem ist, daß die Newton-Trajektorien im allgemeinen mehrere Komponenten besitzen. Um alle Nullstellen von F zu bestimmen, müßte man daher auf jeder Komponente mindestens einen Startpunkt für den Verfolgungsalgorithmus finden. (Eine allgemeine Strategie dafür wurde in [4] vorgeschlagen und [6] beschreibt eine numerische Implementation.)

Es kommt vor, daß man für ein k-Newton-Blatt mit k > 1 Zusammenhang beweisen kann, aber nicht für k = 1 (vgl. zum Beispiel die Ausführungen im Anschluß an Satz 25-36). Das bedeutet in der Praxis immerhin die Reduktion eines n-dimensionalen Problems auf ein k-dimensionales und da die numerische Komplexität eines globalen Problems im allgemeinen exponentiell mit der Dimension wächst, kann eine solche Reduktion für die Praxis erheblich sein. Die Betrachtung allgemeiner k-Newton-Blätter ist also nicht nur deshalb von Interesse, weil man Newton-Trajektorien als Durchschnitte solcher Blätter erhalten kann, sondern sie besitzen auch also solche eine durchaus praktische Relevanz.

Es stellen sich verschiedene Fragen, denen wir im folgenden nachgehen werden:

• Unter welchen Bedingungen an F und V ist F_{V} (F) eine Mannigfaltigkeit?

• Unter welchen Bedingungen ist F_{V} (F) zusammenhängend?

• Gibt es Funktionen, deren k-Newton-Blätter alle zusammenhängend sind?

• Zu welchen Funktionen F gibt es zusammenhängende k-Newton-Blätter?

• Wie verhalten sich Newton-Blätter, wenn man F stört (lokal oder global)?

• Wie sehen die Topologie und die Geometrie von Newton-Blättern aus?

2.1 Außerordentliche Singularitäten

Unser Ziel ist es nun zunächst, Newton-Blätter F_{V} (F) in der Form F_{A}^{−1}(0), mit einer gewissen, von F und V anhängenden Abbildung F_{A}, darzustellen, denn diese Beschreibungsart ist für die Methoden der Topologie am besten geeignet. F_{V} (F) wird dann eine Mannigfaltigkeit sein, wenn 0 ein regulärer Wert von F_{A} ist und Verzweigungen sind durch die kritischen Punkte von F_{A} charakterisiert.

Definition 3 Sei B ⊂ IR^{n} und V ein k–kodimensionaler linearer Unterraum des IR^{n} sowie F ∈ M^{∗}(B). Sei A_{V} eine (n − k) × n–Matrix, deren Zeilen eine Basis von V bilden. Wir nennen eine solche Matrix A_{V} eine V zugeordnete Matrix. Wir betrachten nun die Abbildung F_{A} : IR^{n} → IR^{n−k} mit x ↦ A_{V} F (x). Wegen ker A_{V} = V^{⊥} ist F_{A}^{−1}(0) = F_{V} (F, IR^{n}). Auf die genaue Wahl von A kommt es dabei offenbar nicht an, solange ker A_{V} = V^{⊥} ist. In Übereinstimmung mit Definition 2-8 haben wir F_{V} (F, B) = F_{A}^{−1}(0) ∩ B.

F_{V} (F, IR^{n}) ist also eine abgeschlossene Mannigfaltigkeit, wenn für alle x ∈ F_{V} (F, IR^{n}) die Matrix A_{V} DF (x) vollen Rang dim V = n − k hat. In diesem Fall heiße F_{V} (F, IR^{n}) ein reguläres Newton–Blatt. Die Regularität hängt offenbar nicht von der speziellen Wahl der Matrix A_{V} ab, sondern nur von deren Kern.

Ein Punkt x ∈ F_{V} (F, B) in dem rangA_{V} DF (x) < dim V ist, heiße eine außerordentliche Singularität von F_{V} (F, B). Ist F_{V} (F, B) eine Newton–Trajektorie und x eine außerordentliche Singularität von F_{V} (F, B), dann nennen wir x auch einfach eine außerordentliche Singularität von F; denn x ist dann ja keine Nullstelle von F und damit liegt V =< F (x) >^{⊥} fest.

Die Menge der außerordentlichen Singularitäten von F in B bezeichnen wir mit ExS(F, B). Die Menge der außerordentlichen Singularitäten von F_{V} (F, B) werden wir mit ExS_{V} (F, B) bezeichnen. Ist F Gradient einer Funktion f, dann ist mit einer außerordentlichen Singularität von f eine solche von ∇f gemeint. Entsprechend schreiben wir ExS_{V} (f, B) und ExS(f, B).

◇

Da der Rang einer differenzierbaren Abbildung unterhalbstetig ist, sind die Mengen ExS(F, B) und ExS_{V} (F, B) abgeschlossen in B.

Die Bezeichnung “außerordentliche Singularität von F ” geht auf Branin (siehe [3]) zurück, der die Singularitäten der desingularisierten Newtonschen Differentialgleichung (4-2), in denen F nicht verschwindet, “extraneous singularities” nennt.

In der Arbeit [8] wird folgender Charakterisierungssatz für außerordentliche Singularitäten bewiesen:

Zitat 3 (siehe[8]) Sei F ∈ C^{1}(IR^{n}, IR^{n}). Dann ist x ∉ Null(F) genau dann eine außerordentliche Singularität von F, wenn der Rang der um die Spalte F (x) erweiterten Matrix DF (x) kleiner als n ist. ◇

Ähnlich kann man die außerordentlichen Singularitäten von Newton-Blättern charakterisieren. Ein Punkt x ∈ F_{V} (F, B) liegt nämlich offenbar genau dann in ExS_{V} (F, B), wenn gilt

dim(ImDF (x) ∩ V^{⊥}) + dim ker DF (x) > kodimV.

Nach dem Dimensionssatz ist

dim(ImDF (x) ∩ V^{⊥}) + dim ker DF (x) = n + k − dim(ImDF (x) + V^{⊥}).

Also ist x ∈ ExS_{V} (F, B) genau dann, wenn x ∈ F_{V} (F, B) und

dim(ImDF (x) + V^{⊥}) < n

ist. Damit folgt

Lemma 2 Sei B ⊂ IR^{n}, F ∈ M^{∗}(B, IR^{n}) und V ein k–kodimensionaler linearer Teilraum des IR^{n} und v_{1}, …, v_{k} eine Basis von V^{⊥}. Dann ist x ∈ F_{V} (F, B) genau dann eine außerordentliche Singularität von F_{V} (F, B), wenn der Rang der um die Spalten v_{1}, …, v_{k} erweiterten Matrix DF (x) kleiner als n ist:

rang[DF (x), v_{1}, …, v_{k}] < n.

Äquivalent dazu ist

ker D^{⊤}F (x) ∩ V ≠ {0}.
◇

Dabei haben wir D^{⊤}F (x) für (DF (x))^{⊤} geschrieben. Das oben zitierte Ergebnis von Gomulka ist in diesem Lemma offenbar enthalten. Die Aussage dieses Lemmas läßt sich auch leicht aus der im Anschluß an Definition 2-8 gegebenen Darstellung von Newton-Blättern erhalten.

Wenn wir V vergrößern, bleiben die Bedingungen des Lemmas offenbar erfüllt. Ist also x ∈ ExS_{V} (F, B), sowie W ⊃ V und F (x) ∈ W^{⊥}, dann liegt x auch in ExS_{W} (F, B).

Ist umgekehrt x ∈ ExS_{V} (F, B) und W ⊂ V, dann liegt F (x) automatisch in F_{W} (F, B) und es ist x ∈ ExS_{W} (F, B) genau dann, wenn ker D^{⊤}F (x) ∩ W ≠ {0} ist.

Ist x ∈ ExS_{V} (F, B) und V nicht schon in ker D^{⊤}F (x) enthalten, dann gibt es immer ein W ⊂ V, also ein F_{V} (f, B) umfassendes Newton–Blatt F_{W} (F, B), so daß x in F_{W} (F, B) liegt, aber keine außerordentliche Singularität von F_{W} (F, B) ist. Aus V ⊂ ker D^{⊤}F (x) folgt rangDF (x) ≤ kodimV.

Sei k := kodimV. Wenn k ≤ rang[DF (x), v_{1}, …, v_{k}] = n − l ist, dann kann man offenbar die Basis v_{1} …, v_{k} um l weitere Vektoren vergrößern und den Rang auf n erhöhen. Aus dem Dimensionssatz ergibt sich dabei l = dim(ker D^{⊤}F (x) ∩ V). (Sinnvoll ist das natürlich nur, wenn k + l < n ist, das heißt, wenn V nicht schon in ker D^{⊤}F (x) enthalten ist.)

Wir fassen die Ergebnisse dieser Überlegungen in folgendem Satz zusammen:

Satz 4 Sei B ⊂ IR^{n}, F ∈ M^{∗}(B) und x eine außerordentliche Singularität eines Newton-Blattes F_{V} (F, B). Dann gilt:

(i) Ist F_{W} (F, B) ein in F_{V} (F, B) enthaltenes Newton–Blatt, das x enthält, dann ist x auch eine außerordentliche Singularität von F_{W} (F, B).

(ii) Ist F_{W} (F, B) ein Newton–Blatt, das F_{V} (F, B) enthält, dann ist x genau dann eine außerordentliche Singularität von F_{W} (F, B), wenn ker D^{⊤}F (x) ∩ W ≠ {0}.

(iii) Ist kodimV < rangDF (x), dann gibt es ein F_{V} (F, B) umfassendes Newton–Blatt F_{W} (F, B), für das x keine außerordentliche Singularität ist. Dabei kann man W so wählen, daß kodimW = kodimV + dim(ker D^{⊤}F (x) ∩ V) ist.

◇

Der Fall (iii) des obigen Satzes wirft die Frage auf, wie stark der Rang von DF (x) abfallen kann. Im Falle, daß F Gradient einer Funktion f ist, ist zur Beantwortung der folgende Satz aus [13] nützlich. Dabei heißt eine Teilmenge des IR^{n} stratifiziert, wenn sie eine disjunkte, lokal-endliche Vereinigung glatter Untermannigfaltigkeiten (den Strata) des IR^{n} ist. Die Dimension einer stratifizierten Menge ist die Dimension des Stratums mit der höchsten Dimension.

Zitat 4 (siehe[13]) Es gibt eine bezüglich der starken C^{3}–Topologie offene und dichte Teilmenge H_{0} ⊂ M(IR^{n}) von C^{∞}(IR^{n}, IR), so daß die Menge H_{0}(f) ⊂ IR^{n}, auf der det H_{f}(x) verschwindet, eine abgeschlossene, stratifizierte Teilmenge des IR^{n} von einer Dimension ≤ n − 1 ist, und der Rang von H_{f}(x) für alle x ∈ IR^{n} mindestens gleich (2n + 1 − \sqrt{1 + 8n})/2 ist. ◇

Der Übersicht halber, stellen wir dieses Ergebnis in einer kleinen Tabelle zusammen:

n 2 3 4 5 6 7 8 9 10 11 12 13 14 15
min rangH_{f} 1 1 2 3 3 4 5 6 6 7 8 9 10 10
max dim ker H_{f} 1 2 2 2 3 3 3 3 4 4 4 4 4 5

Für alle n ≥ 4 gibt es also zu jeder außerordentlichen Singularität x von f ∈ H_{0} ein nichttriviales k–Blatt, für das x keine außerordentliche Singularität ist. Beispielsweise bleibt für n = 14 die durch eine außerordentliche Singularität von f ∈ H_{0} verlaufende Newton-Trajektorie auf eine fünfdimensionale Mannigfaltigkeit, ein fünfdimensionales, reguläres Newton-Blatt beschränkt.

Die Struktur der Menge ExS(f, IR^{n}) wurde für f ∈ M(IR^{n}) von Jongen, Jonker und Twilt ([15, 17]) ausführlich untersucht. Ohne weitere Annahmen über f kommt man dabei nicht aus, denn für “pathologische” Funktionen f kann diese Menge sehr wild aussehen.

Eine Teilmenge von C^{∞}(IR^{n}, R) heißt generisch, wenn sie den Durchschnitt einer abzählbaren Anzahl von C^{∞}-offenen und -dichten Teilmengen von C^{∞}(IR^{n}, IR) enthält.

Jongen, Jonker und Twilt erhielten folgendes Resultat:

Zitat 5 (siehe[15, 17]) Es gibt eine generische Teilmenge E von C^{∞}(IR^{n}, IR), so daß gilt:

• Wenn f ∈ E ist, dann ist ExS(f, IR^{n}) eine abgeschlossene stratifizierte Menge im IR^{n}, deren Dimension ≤ n − 2 ist.

• Wenn n = 2, 3 oder 4 ist, dann ist ExS(f, IR^{n}) eine abgeschlossene Untermannigfaltigkeit der Dimension n − 2 im IR^{n} (oder leer). Außerdem ist E dann C^{3}-offen in C^{∞}(IR^{n}, IR).

◇

Die Menge E in obigem Satz läßt sich durch gewisse Jet-Transversalitätsbedingungen genau charakterisieren. Für F : IR^{n} → IR^{n} lassen sich ähnliche Ergebnisse erhalten (vgl. [15]).

Für f ∈ E und n = 2 sind die außerordentlichen Singularitäten also isolierte Punkte im IR^{2}. In [17] wird auch das lokale Phasenportrait der Trajektorien der desingularisierten Newtonschen Differentialgleichung in außerordentlichen Singularitäten für die Dimensionen n = 2 und 3 analysiert. Die Ergebnisse lassen sich folgendermaßen zusammenfassen:

Zitat 6 (siehe[17]) Für alle Funktionen f aus einer generischen Teilmenge von C^{∞}(IR^{2}, IR) ist ExS(f, IR^{2}) diskret und das lokale Phasenportrait der Differentialgleichung (5-2) um eine außerordentliche Singularität x vom Sattelpunkt-Typ (x ist ein dikritischer Knoten), oder vom Zentrum-Typ.

Für alle Funktionen aus einer generischen Teilmenge von C^{∞}(IR^{3}, IR) gilt: ExS(f, IR^{3}) ist leer, oder eine abgeschlossene, eindimensionale Mannigfaltigkeit. Zu jedem Punkt x ∈ ExS(f, IR^{3}) kann man lokal eine zweidimensionale Mannigfaltigkeit M_{x} durch x wählen, so daß die lokale Trajektorie von (5-2) durch einen Punkt von M_{x} in M_{x} bleibt. Es gibt eine diskrete Teilmenge ExS_{d}(f, IR^{3}) von ExS(f, IR^{3}), so daß M_{x} die Kurve ExS(f, IR^{3}) dann und nur dann nicht transversal schneidet, wenn x in ExS_{d}(f, IR^{3}) liegt. Auf jeder Zusammenhangskomponente von ExS(f, IR^{3}) \ ExS_{d}(f, IR^{3}) ist das lokale Phasenportrait entweder vom Sattelpunkt-Typ, oder vom Zentrum-Typ. In den Punkten von ExS_{d}(f, IR^{3}) dagegen ist das lokale Phasenportrait vom Cusp-Typ. ◇

Für n = 4 läßt sich ein ähnliches Ergebnis erzielen. Für n > 4 dagegen werden die Verhältnisse anscheinend komplizierter.

Bemerkung 3 Nach obigen Überlegungen (vgl. Satz 4-12 und Zitat 4-12) können wir ein allgemeines Ergebnis dieser Art folgendermaßen formulieren:

Für alle Funktionen f aus der in Zitat 4-12 definierten offenen und dichten Teilmenge H_{0} ⊂ M(IR^{n}) gibt es durch jeden Punkt x ∈ ExS(f, IR^{n}) eine Mannigfaltigkeit M_{x} der Dimension [(1 + \sqrt{1 + 8n})/2], so daß die Trajektorien von (5-2) durch einen Punkt von M_{x} in M_{x} bleiben. ◇

Es folgt nun noch eine weitere nützliche Charakterisierung der außerordentlichen Singularitäten von F ∈ M^{∗}(IR^{n}). Dazu sei τ_{F} : IR^{n} \ Null(f) → S^{n−1} die von Smale in [22] eingeführte Trajektorienabbildung, die durch x ↦ F (x)/∥F (x)∥ definiert ist. τ_{F} ist auf den Trajektorien von (2-1) offenbar konstant. Es gilt:

Zitat 7 (siehe[22, 12]) Sei x ∉ Null(F). Dann ist x genau dann eine außerordentliche Singularität von F, wenn x ein kritischer Punkt von τ_{F} ist. ◇

Für unsere Zwecke ist die Definition τ_{F} : IR^{n} \ Null(F) → G(n − 1, n), mit x ↦ ⟨F (x)⟩ angemessener, denn das so definierte τ_{F} ist dann offenbar auf allen Newton–Trajektorien konstant. Das vorstehende Lemma gilt dann ebenso. Wenn F Gradient einer Funktion f ist, schreiben wir statt τ_{∇f} auch einfach τ_{f}.

2.2 Einige Eigenschaften von Newton–Blättern

In diesem Abschnitt stellen wir einige geometrische und topologische Eigenschaften von Newton-Blättern zusammen.

Wenn x ∉ ExS_{V} (F), dann ist F_{V} (F) lokal um x eine Mannigfaltigkeit und der Tangentialraum im Punkt x ist T_{x}F_{V} (F) = ker A_{V} DF (x). Zwei Mannigfaltigkeiten M_{1} und M_{2} im IR^{n} schneiden sich transversal in x, wenn x ∉ M_{1} ∩ M_{2}, oder wenn die Tangentialräume T_{x}M_{1}, T_{x}M_{2} an M_{1}, M_{2} in x zusammen den ganzen IR^{n} aufspannen, wenn also T_{x}M_{1} + T_{x}M_{2} = IR^{n} ist. Wenn das für jeden Punkt x ∈ IR^{n} gilt, heißen M_{1} und M_{2} transversal.

Notwendig dafür ist offenbar dim M_{1}+dim M_{2} ≥ n. Zwei Newton–Trajektorien können sich also für n > 2 nicht transversal schneiden. Andererseits zeigt der nächste Satz, daß die Tangentialräume T_{x}F_{W} (F) und T_{x}F_{V} (F) nicht ineinander liegen, wenn x keine außerordentliche Singularität ist und die Newton–Blätter nicht schon selber ineinander liegen.

Wir sagen, zwei Mengen A, B liegen schief zueinander, wenn weder A ⊂ B noch B ⊂ A gilt.

Satz 5 Seien F_{V} (F) und F_{W} (F) zwei Newton–Blätter, die zueinander schief liegen. Dann liegen auch die Tangentialräume an F_{V} (F) und F_{W} (F) in jedem Punkt der nicht zu ExS_{V +W} (F) gehört, schief zueinander. ◇

Beweis: Nach Voraussetzung gilt weder F_{V} (F) ⊂ F_{W} (F), noch F_{W} (F) ⊂ F_{V} (F). Zu zeigen ist, daß in jedem Punkt x ∉ ExS_{V +W} (F) gilt:

ker A_{W} DF (x) ⊄ ker A_{V} DF (x), und ker A_{V} DF (x) ⊄ ker A_{W} DF (x).

Nehmen wir o.E. an, es gelte ker A_{W} DF (x) ⊂ ker A_{V} DF (x). Da x ∉ ExS_{V +W} (F) ist, haben die Matrizen

( \begin{matrix}A_{W} DF (x) \\ A_{V} DF (x) \end{matrix} ) und ( \begin{matrix}A_{W} \\ A_{V} \end{matrix} )

den gleichen Rang und sind daher äquivalent. Also gibt es nichtsinguläre, quadratische Matrizen S und T, so daß gilt:

S ( \begin{matrix}A_{W} DF (x)T \\ A_{V} DF (x)T \end{matrix} ) = ( \begin{matrix}A_{W} \\ A_{V} \end{matrix} ) .

Sei etwa A_{W} z = 0, dann ist auch A_{W} DF (x)T z = 0. Aus ker A_{W} DF (x) ⊂ ker A_{V} DF (x) folgt A_{V} DF (x)T z = 0, also auch A_{V} z = 0. Folglich ist der Kern von A_{W} im Kern von A_{V} enthalten und daher F_{W} (F) ⊂ F_{V} (F). □

Insbesondere schneiden sich Newton-Blätter in nichtentarteten Nullstellen (kritischen Punkten) stets schief.

Satz 6 Sei B ⊂ IR^{n} und F ∈ M^{∗}(B). Sei x eine (nichtentartete) Nullstelle von F. Dann gibt es eine Umgebung U von x, so daß für k = 0, 1, …, n jede Komponente eines k–Blattes, die U schneidet, auch x enthält. ◇

Beweis: Dies folgt schon aus der Tatsache, daß nichtentartete Nullstellen anziehende oder abstoßende Knoten der Differentialgleichung (4-2) sind. Es soll aber noch ein anderer Beweis gegeben werden, der direkt auf unserer Definition von Newton-Blättern beruht.

Für k = 0 und k = n ist die Behauptung trivial. Sei also 1 ≤ k ≤ n − 1. Da x nichtentartet ist, gibt es eine Umgebung U von x, in der DF (x) regulär ist. Ist A_{V} eine V zugeordnete Matrix, dann hat also A_{V} DF (x) für alle x ∈ U den Rang n − k. Nach dem Satz über implizite Funktionen hat daher die Gleichung A_{V} F (x) = 0 in U eine eindeutige Auflösung. □

Wenn eine Komponente eines k–Blattes also “genügend nahe” an eine nichtentartete Nullstelle herankommt, dann geht sie auch durch diese Nullstelle. Vom nächsten Satz werden wir im folgenden mehrfach den Fall l = 1 benötigen.

Satz 7 Sei B ⊂ IR^{n}, und F ∈ M^{∗}(B). Sei F_{V} (F, B) ein k–Blatt und F_{W} (F, B) ein l–Blatt. Wenn F_{V} (F, B) ∩ F_{W} (F, B) einen Punkt aus B \ Null(F, B) enthält, dann ist

n − k − l + 1 ≤ dim(V ∩ W) ≤ min(n − k, n − l).

Ist insbesondere F_{W} (F, B) eine Newton–Trajektorie, dann ist F_{W} (F, B) ⊂ F_{V} (F, B). Eine Newton–Trajektorie, die mit einem k–Newton–Blatt einen Punkt x mit F (x) ≠ 0 gemein hat, liegt also ganz in diesem k–Blatt. ◇

Beweis: Wenn F_{V} (F) ∩ F_{W} (F) einen von den Nullstellen von F verschiedenen Punkt x enthält, dann kann F_{V} (F) ∩ F_{W} (F) nicht das 0–Blatt sein, also ist V + W ≠ IR^{n}. Folglich ist n − 1 ≥ dim(V + W). Daraus und aus dem Dimensionssatz ergibt sich n − k − l + 1 ≤ dim(V ∩ W).

Andererseits ist, trivialerweise, dim(V ∩W) ≤ dim V ≤ n−k. Damit folgt n−k−l+1 ≤ dim(V ∩ W) ≤ n − k.

Ist F_{W} (F) ein 1–Blatt, also l = 1, so folgt dim(V ∩ W) = dim V, also V ⊂ W. □

Wir nennen eine zusammenhängende Menge frei bezüglich f (bzw. F), wenn sie keinen kritischen Punkt von f (bzw. keine Nullstelle von F) enthält. Andernfalls heiße die Menge gebunden. Als erste Anwendung von Satz 7-15 beweisen wir:

Satz 8 Sei F ∈ M^{∗}(IR^{n}) und k > 0. Dann besitzt jede kompakte, freie Komponente eines k– Newton–Blattes zu F im IR^{n}, die keine außerordentlichen Singularitäten von F enthält, ein stetiges, nirgends verschwindendes tangentiales Vektorfeld. ◇

Beweis: Sei F eine solche Komponente eines Newton–Blattes. Dann geht durch jeden Punkt x auf F genau eine Newton–Trajektorie T_{F (x)}(F) und die Komponenten, die F schneiden, liegen nach Satz 7-15 ganz in F. Ein stetiges, tangentiales Einheitsvektorfeld auf F erhält man durch die normierten Tangentialvektoren an die Kurven T_{F (x)}(F) ∩ F. □

Insbesondere ist eine freie Komponente eines Newton–Blattes, auf der keine außerordentlichen Singularitäten von F liegen, niemals homöomorph zu einer Sphäre S^{2l}.

Sei F : U → IR^{n} ein glattes Vektorfeld auf einer offenen Teilmenge U des IR^{n} und x^{∗} ∈ U eine isolierte Nullstelle von F. Dann bildet die Trajektorienabbildung τ_{F} (x) = F (x)/∥F (x)∥ eine kleine Sphäre um x^{∗} in die Einheitssphäre S^{n−1} ⊂ IR^{n} ab. Den Abbildungsgrad dieser Abbildung nennt man den Index von F in derNullstelle x^{∗}. Wir schreiben dafür Index x^{∗}. Bekanntlich ist der Index einer nichtdegenerierten Nullstelle eines Vektorfeldes gleich dem Vorzeichen der Funktionaldeterminante in diesem Punkt, also

Index x^{∗} = sign det DF (x^{∗}).

Für die Klassifizierung der kritischen Punkte einer Funktion f : U → IR ist es sinnvoll, eine feinere Unterscheidung vorzunehmen, als sie durch den Index des Gradienten-Vektorfeldes in einem kritischen Punkt gegeben wäre. Man definiert daher den quadratischen Index (Morse-Index) eines nichtdegenerierten kritischen Punktes x^{∗} als die Anzahl der negativen Eigenwerte der Hesse-Matrix H_{f}(x^{∗}) := D^{2}f(x^{∗}). Für den quadratischen Index eines nichtdegenerierten kritischen Punktes schreiben wir Index_{q}x^{∗}. Damit folgt:

Satz 9 Sei B ⊂ IR^{n} und F ∈ M^{∗}(B). Sei F eine Zusammenhangskomponente einer regulären Newton–Trajektorie von F in B und seien u, v ∈ F zwei nichtdegenerierte Nullstellen von F, die in F durch keine weitere Nullstelle von F getrennt sind. Dann gilt für die Indizes der Nullstellen u und v:

Index u ≠ Index v.

Sei f ∈ M(B). Sei F eine Zusammenhangskomponente einer regulären Newton– Trajektorie von f in B und seien u, v ∈ F zwei kritische Punkte von f, die in F durch keinen weiteren kritischen Punkt getrennt sind. Dann gilt für die quadratischen Indizes der kritischen Punkte u und v:

Index_{q}u ≢ Index_{q}v (mod 2).
◇

Beweis: Nach Voraussetzung gibt es eine Trajektorie der Differentialgleichung (4-2), die u mit v verbindet. Einer der beiden Punkte u, v muß daher ein anziehender, der andere ein abstoßender Fixpunkt von (4-2) sein. Es folgt det DF (u) · det DF (v) < 0. Daraus folgt die erste Behauptung. Die zweite ergibt sich, indem man diese Schlußweise auf das Gradienten-Vektorfeld von f anwendet und die Differentialgleichung (5-2) betrachtet. □

Sei A eine Teilmenge eines topologischen Raumes und x ∈ A. Dann bezeichnen wir mit C_{x}A die Zusammenhangskomponente von A, die x enthält.

Satz 10 Sei B ⊂ IR^{n} und F ∈ M^{∗}(B). Dann enhält für k = 1, …, n − 1 jede kompakte, zum Rand von B disjunkte Komponente eines k–Blattes eine gerade Anzahl Nullstellen von F. ◇

Beweis: Im Fall k = 1 folgt die Behauptung sofort aus Satz 9-16, wenn die fragliche Komponente regulär ist. Andernfalls sei z eine Nullstelle auf der singulären, kompakten Komponente C_{z}F_{V} (F) der Newton–Trajektorie F_{V} (x). Sei U eine Umgebung von C_{z}F_{V} (F), die außer den in C_{z}F_{V} (F) enthaltenen Nullstellen keine weiteren enthält.

Nach dem Morse-Sard–Lemma hat τ_{f}(ExS(F)) das Maß Null in S^{n−1}. Also gibt es ein V′ ∈ G(1, n), so daß F_{V′}(F) regulär ist und jede Komponente, die C_{z}F_{V} (F) schneidet, ganz in U enthalten ist. Diese Komponenten von F_{V′}(F) sind kompakt und regulär, enthalten also eine gerade Anzahl Nullstellen von F. Andererseits liegen auf C_{z}F_{V} (F) genau die Nullstellen, die auch auf den in U enthaltenen Komponenten von F_{V′}(F) liegen. Deren Anzahl ist somit gerade.

Sei nun k > 1 und C_{x}F_{V} (F) eine kompakte k–Blatt-Komponente. Sei W ein linearer Unterraum des IR^{n} mit dim(W + V) = n − 1. Dann ist C_{x}F_{V} ∩ F_{W} eine Menge von kompakten Komponenten einer Newton–Trajektorie, und alle Nullstellen, die im C_{x}F_{V} (F) liegen, liegen auch in C_{x}F_{V} ∩ F_{W}. Jede Komponente dieser Menge enthält aber, wie wir eben gesehen haben, eine gerade Anzahl Nullstellen von F. Also enthält auch C_{x}F_{V} (F) eine gerade Anzahl Nullstellen. □

Das Argument im Beweis des letzten Satzes zeigt, daß für alle V aus einer dichten Menge V ⊂ G(1, n) die Newton-Trajektorien F_{V} (F, IR^{n}) eindimensionale Mannigfaltigkeiten sind, sofern F wenigstens eine Nullstelle in B besitzt. Ansonsten kann F_{V} (F, IR^{n}) auch leer sein.

Satz 11 Der Rand der beschränkten, offenen Menge U ⊂ IR^{n} sei in einer kompakten, freien Komponente K eines (n − 1)-Blattes F_{V} (F, IR^{n}) enthalten. Dann gilt:

(i) Jede Komponente von U enthält eine gerade Anzahl Nullstellen von F.

(ii) Jede Komponente K_{i} von U, die eine Nullstelle von F enthält, enthält auch eine außerordentliche Singularität von F.

(iii) Wenn \overline{U} weder Nullstellen noch außerordentliche Singularitäten enhält, dann gibt es eine stetige, fixpunktfreie Abbildung von U in U (bzw von \overline{U} in \overline{U}).

◇

Beweis: (i) Sei x eine Nullstelle in U und g ∈ S^{n−1}, g ∉ V^{⊥}. Dann kann C_{x}T_{g}(F) wegen Satz 7-15 den Rand von U nicht schneiden, ist also kompakt. Satz 10-17 liefert nun die Behauptung.

(ii) Angenommen K_{i} enhalte eine Nullstelle, aber keine außerordentliche Singularität von F. Sei M_{0} die Menge der Punkte in K_{i}, durch die eine Komponente einer Newton-Trajektorie geht, die eine Nullstelle von F in K_{i} enhält, und M_{1} die Menge der Punkte in K_{i}, durch die eine freie Komponente einer Newton-Trajektorie zu F geht. M_{0} ist als Vereinigung von Einzugsbereichen der Differentialgleichung (4-2) offen. Es ist leicht zu sehen, daß auch M_{1} offen ist (vgl. Lemma 6-28). M_{0} ist nichtleer, weil K_{i} eine Nullstelle enthält. Da K frei ist, folgt aus Korollar 15-23, daß auch M_{1} nicht leer ist. Also ist K_{i} die Vereinigung zweier offener, nichtleerer Mengen, was nicht geht.

(iii) Die desingularisierte Newtonsche Differentialgleichung (4-2) besitzt dann in U keine stationären Punkte und Trajektorien, die in U (bzw. K) starten, bleiben in U (bzw. K). Da N (F) auf einer Umgebung von \overline{U} nicht verschwindet, gibt es zu jedem x ∈ \overline{U} eine Umgebung V und eine lokale C^{∞} Koordinatentransformation, so daß x bezüglich der neuen Koordinaten y = (y_{1}, …, y_{n})^{⊤} gleich 0 ist und das Differentialgleichungssystem (4-2) lokal durch dx/dt = (1, 0, …, 0)^{⊤} gegeben ist. Es gibt folglich zu jedem x ∈ \overline{U} eine offene Umgebung W_{x} und ein t_{x} > 0, so daß für alle x ∈ W_{x} und t mit 0 < t < t_{x} gilt: ϕ_{t_{x}}(x) ≠ x. Da \overline{U} kompakt ist, läßt sich \overline{U} durch endlich viele W_{x} überdecken und daher gibt es ein t^{∗} > 0, so daß für alle x ∈ \overline{U} gilt: ϕ_{t^{∗}}(x) ≠ x. Dabei sei ϕ der durch (4-2) definierte Fluß. Die Abbildung ϕ_{t^{∗}} : U → U (bzw. \overline{U} → \overline{U}) ist stetig und fixpunktfrei. □

Da folgende Ergebnis findet sich für den Fall f ∈ M(IR^{2}) auch in [13, 15]. Es wird dort mit Hilfe des Indexsatzes von Poincaré-Hopf bewiesen.

Korollar 12 Sei F ∈ M^{∗}(IR^{2}) und F besitze keine außerordentlichen Singularitäten. Dann besitzt keine Newton-Trajektorie zu F Komponenten, die frei und kompakt sind. Das heißt, auf jeder kompakten Komponente einer Newton-Trajektorie liegen mindestens zwei Nullstellen von F. ◇

Beweis: Sei K eine kompakte Komponente einer freien Newton-Trajektorie zu F. Dann ist K diffeomorph zu einem Kreis S^{1}. Sei K_{i} die beschränkte Komponente von IR^{2} \ K vereinigt mit K. Wegen Satz 11-17 (ii) enhält K_{i} keine Nullstelle von F. Andererseits ist K_{i} homöomorph zur Kreisscheibe D^{2} und daher muß nach dem Fixpunktsatz von Brouwer jede stetige Abbildung K_{i} → K_{i} einen Fixpunkt besitzen. Anwendung von Satz 11-17 (iii) liefert einen Widerspruch. □

Es ist eine offene Frage, ob sich dieser Satz auf n Dimensionen und k-Newton-Blätter verallgemeinern läßt. Kann es, zum Beispiel, unter der Voraussetzung ExS(F, IR^{3}) = ∅ ein freies 2-Blatt im IR^{3} geben, das homöomorph zu einem Torus ist? Gilt das, falls überhaupt, auch, wenn F ein Gradient ist? Ein freies 2-Blatt in der Form eines Torus hinzubekommen ist kein Problem: Sei T : IR^{3} → IR so gewählt, daß T^{−1}(0) ein Torus ist und R : IR^{3} → IR besitze auf T^{−1}(0) keine Nullstelle. Weiter sei S : IR^{3} → IR beliebig. Sei F (x) : IR^{3} → IR^{3} durch F (x) := (T (x), R(x), S(x))^{⊤} definiert. Sei V das orthogonale Komplement des von dem Vektor (1, 0, 0)^{⊤} aufgespannten Raumes. Dann ist das 2-Blatt F_{V} (F) gleich T^{−1}(0) und dieses Blatt ist frei. Das Problem liegt also in der Vermeidung von außerordentlichen Singularitäten.

Die Aussagen der folgenden Bemerkung sollen unsere Vorstellung von Newton–Blättern abrunden. Die Beweise sind trivial. (i) gibt die Bedingungen an, unter denen sich ein k-Newton-Blatt als Durchschnitt anderer Newton-Blätter darstellen läßt. (ii) sagt aus, daß jedes k-Newton-Blatt sich für ein l < k gerade als die Vereinigung aller darin enthaltenen l-Blätter schreiben läßt. Für die Zusammenhangskomponenten der k-Blätter gilt die entsprechende Inklusion nach (iii) (natürlich) nur in einer Richtung.

Bemerkung 4 Sei B ⊂ IR^{n}, F ∈ M^{∗}(B) und F_{V} (F, B) ein k-Newton-Blatt.

(i) Genau dann gibt es ein l–Blatt F_{U}(F, B) und ein m–Blatt F_{W} (F, B), so daß sich F_{V} (F, B) als Durchschnitt F_{V} (F, B) = F_{U}(F, B) ∩ F_{W} (F, B) von F_{U}(F, B) und F_{W} (F, B) darstellen läßt, wenn die Ungleichungen l, m ≥ k und l + m − k ≤ n gelten.

(ii) Für alle l mit 1 ≤ l ≤ k gilt:

F_{V} (F, B) = ⋃_{\begin{matrix}W ⊃V \\ W ∈G(l,n) \end{matrix}} F_{W} (F, B).

(iii) Sei x eine Nullstelle von F in B. Dann gilt für alle l mit 0 ≤ l ≤ k:

C_{x}F_{V} (F, B) ⊃ ⋃_{\begin{matrix}W ⊃V \\ W ∈G(l,n) \end{matrix}} C_{x}F_{W} (F, B).

(iv) Wenn C_{x}F_{V} (F, B) eine freie k–Blatt–Komponente ist und 1 ≤ l ≤ k, dann gibt es eine freie l–Blatt–Komponente C_{x}F_{W} (F, B) ⊂ C_{x}F_{V} (F, B).

(v) Wenn l+k ≤ n ist, dann gibt es zu jedem k-Blatt F_{V} (F, B) und jedem y ∉ F_{V} (F, B) ein l–Blatt F_{W} (F, B), so daß F_{V} (F, B) ∩ F_{W} (F, B) = Null(F, B) ist und y in F_{W} (F, B) liegt.

◇

Beweis: (i) Zu zeigen ist, daß es zu jedem V ∈ G(k, n) Unterräume U ∈ G(l, n) und W ∈ G(k, n) gibt, mit V = U +W. Das ist aber klar, wenn gilt dim V ≥ dim U, dim W,also l, m ≥ k, und dim U + dim W ≥ dim V, wenn also n ≥ l + m − k ist. Die andere Beweisrichtung ist ebenso trivial.

(ii) Die “⊃”–Richtung ist klar. Um die andere Richtung zu zeigen, nehmen wir x ∈ F_{V} (F) an, also F (x) ∈ V^{⊥}. Dann gibt es ein {0} ≠ W^{⊥} ∈ G(l, n) mit F (x) ∈ W^{⊥} und W^{⊥} ⊂ V^{⊥}, also x ∈ F_{W} (F).

(iii) Seien A_{i} Teilmengen des IR^{n}. Dann gilt allgemein

C_{x} ⋃ A_{i} ⊃ ⋃ C_{x}A_{i}.

Daraus und aus (ii) folgt die Behauptung.

Die Beweise zu (iv) und (v) sind trivial. □

3 Die Graphen Γ^{k}(F, B)

Vom praktischen Gesichtspunkt aus ist natürlich die Frage wichtig, ob es zu gegebenem F eine zusammenhängende Newton-Trajektorie gibt, denn eine solche würde alle Nullstellen von F gewissermaßen “auffädeln”. Ebenso könnte man sich bei der Suche nach den Nullstellen auf eine zusammenhängende, k–dimensionale Untermannigfaltigkeit beschränken, wenn man ein zusammenhängendes k-Blatt gefunden hätte. Leider wird es in praktischen Fällen nur selten gelingen, a priori eine zusammenhängende Newton-Trajektorie zu definieren. Wir beschränken uns daher zunächst auf die Frage, ob man wenigstens alle Nullstellen von F durch ein Netz von Newton-Trajektorien, oder allgemeiner, k–Newton-Blättern, miteinander verbinden kann.

Definition 4 Sei B ⊂ IR^{n} und F ∈ C(B, IR^{n}). Dann definieren wir für k = 0, 1, …, n Graphen Γ^{k}(F, B). Die Ecken von Γ^{k}(F, B) seien die Nullstellen von F in B. Zwei Ecken u, v in Γ^{k}(F, B) seien genau dann durch eine Kante miteinander verbunden, wenn u ≠ v ist und es ein k–Newton–Blatt K zu F gibt, so daß u und v in einer Zusammenhangskomponente von K liegen. Statt Γ^{k}(F, B) schreiben wir auch Γ^{k}(F), wenn klar ist, welches B gemeint ist. ◇

Der Graph Γ^{0}(F, B) ist der total unzusammenhängende Graph mit |Null(F, B)| Ecken und keinen Kanten. Γ^{n}(F, B) ist dagegen der vollständige Graph K_{N}, bei dem jede Ecke mit jeder anderen durch eine Kante verbunden ist.

Satz 13 Sei 0 ≤ l ≤ k ≤ n. Dann ist der Graph Γ^{l}(F, B) ein aufspannender Untergraph von Γ^{k}(F, B). ◇

Beweis: Beide Graphen haben die gleiche Eckenmenge Null(F). Zu zeigen ist, daß zwei Nullstellen u, v, die auf einer l-Blatt-Komponente C_{u}F_{W} (F) liegen, auch auf einer k–Blatt-Komponente liegen. Sei V irgendein k–kodimensionaler linearer Teilraum des IR^{n}, der in W enthalten ist. Dann liegt C_{u}F_{W} (F, B) in einer Zusammenhangskomponente von F_{V} (F, B) und daher liegen auch u und v in dieser Zusammenhangskomponente. Also sind u und v in Γ^{k}(F, B) verbunden. □

In [13] definieren die Autoren einen Graphen Γ(f) für Morsefunktionen f im IR^{n}. Die Ecken dieses Graphen sind die kritischen Punkte von f und zwei Ecken u, v werden durch eine Kante verbunden, wenn es eine Trajektorie der desingularisierten Newtonschen Differentialgleichung (5-2) gibt, die u und v verbindet. Der Graph Γ(f) hängt offenbar mit unserem Graphen Γ^{1}(∇f, IR^{n}) zusammen. Beide Graphen besitzen die gleiche Eckenmenge Krit(f) und zwei Ecken, die in Γ(f) verbunden sind, sind auch in Γ^{1}(∇f, IR^{n}) verbunden. Also ist Γ(f) ein aufspannender Untergraph von Γ^{1}(∇f, IR^{n}). Außerdem besitzt Γ(f) offenbar genauso viele Zusammenhangskomponenten wie Γ^{1}(∇f, IR^{n}).

In der Arbeit [13] werden die beiden folgenden Sätze zur Struktur von Γ(f) bewiesen.

Zitat 8 (siehe[13]) Sei f ∈ C^{∞}(IR^{2}, IR) eine Morsefunktion und es sei ExS(f, IR^{2}) = ∅. Dann ist jede Komponente von Γ(f) ein Baum. (Γ(f) ist ein “Wald”.) ◇ Zitat 9 (siehe[13]) Sei f ∈ C^{∞}(IR^{n}, IR) eine Morsefunktion und es sei ExS(f, IR^{n}) = ∅. Wenn keine unbeschränkte Komponente einer Newton–Trajektorie zu f frei ist, dann ist Γ(f) zusammenhängend und wenn f wenigstens einen kritischen Punkt besitzt, dann besitzt keine Newton–Trajektoriezu f eine freie Komponente. ◇

Der erste Satz gilt nur im IR^{2}. Er folgt auch sofort aus dem (weiter unten stehenden) Lemma 8-34. Die wesentlichste Beschränkung dieser beiden Sätze ist die Forderung, daß es keine außerordentlichen Singularitäten gebe. Diese Forderung ist in der Praxis selten erfüllt, wenn f überhaupt mehr als einen kritischen Punkt hat.

Sei sei A ⊂ B ⊂ IR^{n} und F ∈ M^{∗}(B). Dann ist für 0 ≤ k ≤ n offenbar Γ^{k}(F, A) ein Teilgraph von Γ^{k}(F, B), es ist dann offenbar Null(F, A) ⊂ Null(F, B) und wenn zwei Nullstellen durch ein k-Blatt in A verbunden werden, dann auch durch das gleiche k-Blatt in B. Wenn Null(F, A) = Null(F, B) ist, dann ist Γ^{k}(F, A) sogar ein aufspannender Teilgraph von Γ^{k}(F, B). In diesem Falle folgt aus dem Zusammenhang von Γ^{k}(F, A) auch der Zusammenhang von Γ^{k}(F, B).

Zunächst ein Lemma, das grundlegend für die folgenden Überlegungen zur Struktur der Graphen Γ^{k}(F, B) ist und auch Anwendungen in der parametrischen Optimierung hat. Ein punktierter topologischer Raum (T, 0) sei im folgenden ein topologischer Raum T mit einem ausgezeichneten Punkt 0 ∈ T.

Lemma 3 Sei A ein metrischer Raum, B ⊂ IR^{n} abgeschlossen, und (T, 0) ein punktierter topologischer Raum. Sei ϕ : A → B stetig, F̂ : A × B → T stetig und F̂(x, ϕ(x)) = 0 für alle x ∈ A. Sei ψF̂ : A → P(B) definiert durch

ψF̂(x) := C_{ϕ(x)}{y ∈ B |F̂(x, y) = 0}.

Sei x^{∗} ∈ A und ψ(x^{∗}) kompakt, x_{i} → x^{∗} eine in A konvergente Folge. Dann gilt:

lim_{i→∞} sup_{z∈ψF̂(x_{i})} d(z, ψF̂(x^{∗})) = 0.

◇

Beweis:

(i) ψF̂(x^{∗}) ist nicht leer, da ϕ(x^{∗}) ∈ ψF̂(x^{∗}) ist.

(ii) Da B abgeschlossen und ψ(x^{∗}) kompakt ist, gibt es eine kompakte Umgebung K von ψF̂(x^{∗}) im R^{n}, mit

{y |F̂(x, y) = 0} ∩ K = ψF̂(x^{∗}).

(iii) Für hinreichend große i ist ψF̂(x_{i}) ∩ K nicht leer, denn da x_{i} gegen x^{∗} konvergiert und ϕ stetig ist, konvergiert ϕ(x_{i}) gegen ϕ(x^{∗}) ∈ ψF̂(x^{∗}) und da K Umgebung von ψF̂(x^{∗}) ist, liegt folglich ϕ(x_{i}) für hinreichend große i in K.

(iv) Sei y_{i} ∈ ψF̂(x_{i}) ∩ K eine Folge in K ∩ B mit

d(y_{i}, ψF̂(x^{∗})) = sup_{z∈ψF̂(x_{i})∩K} d(z, ψF̂(x^{∗})).

Eine solche Folge gibt es, denn ψF̂(x_{i}) ∩ K ist kompakt.

(v) Da B abgeschlossen ist, ist K ∩ B kompakt, also ist {y_{i}} ist eine Folge in der kompakten Menge K ∩ B, besitzt also eine gegen ein y^{∗} ∈ K ∩ B konvergente Teilfolge. O.E. konvergiere y_{i} gegen y^{∗}.

(vi) Nach Konstruktion ist für alle i:

F̂(x_{i}, y_{i}) = F̂(x_{i}, ϕ(x_{i})) = 0 ∈ T.

Da F̂ und ϕ stetig sind, folgt

F̂(x^{∗}, y^{∗}) = F̂(x^{∗}, ϕ(x^{∗})) = 0,

also

y^{∗} ∈ {y |F̂(x^{∗}, y^{∗}) = 0} ∩ K = ψF̂(x^{∗}).
□

Wenn ψF̂(x^{∗}) nicht kompakt ist, dann läßt sich die obige Folgerung

lim_{i→∞} sup_{z∈ψF̂(x_{i})} d(z, ψF̂(x^{∗})) = 0

im allgemeinen nicht ziehen. Das nächste Lemma behandelt diesen Fall. Der Beweis stützt sich auf Lemma 3-21.

Lemma 4 Sei A ein metrischer Raum, B ⊂ IR^{n} abgeschlossen, und (T, 0) ein punktierter topologischer Raum. Sei ϕ : A → B stetig, F̂ : A × B → T stetig und F̂(x, ϕ(x)) = 0 für alle x ∈ A. Definiere ψF̂ : A → P(B) durch

ψF̂(x) := C_{ϕ(x)}{y ∈ B |F̂(x, y) = 0}.

Sei x_{i} → x^{∗} eine in A konvergente Folge und es gebe eine in B konvergente Folge y_{i} → y^{∗} mit y_{i} ∈ ψF̂(x_{i}) sowie ein ϵ > 0, so daß für alle i:

d(y_{i}, ψF̂(x^{∗})) ≥ ϵ

ist. Dann besitzt {y |F̂(x^{∗}, y) = 0} mindestens zwei unbeschränkte Zusammenhangskomponenten in B. ◇

Beweis: Da F̂ und ϕ stetig sind, konvergiert F̂(x_{i}, ϕ(x_{i})) = F̂(x_{i}, y_{i}) gegen F̂(x^{∗}, ϕ(x^{∗})). Folglich liegt y^{∗} in {y ∈ B |F̂(x^{∗}, y) = 0}. Also hat, wegen d(y^{∗}, ψF̂(x^{∗})) ≥ ϵ > 0, die Menge {y ∈ B |F̂(x^{∗}, y) = 0} zwei Zusammenhangskomponenten K_{1}, K_{2} ⊂ B mit x^{∗} ∈ K_{1} und y^{∗} ∈ K_{2}.

Wenn K_{1} beschränkt wäre, dann wäre K_{1} auch kompakt. Damit wären die Voraussetzungen von Lemma 3-21 erfüllt und es ergäbe sich ein Widerspruch gegen d(y^{∗}, ψF̂(x^{∗})) ≥ ϵ > 0. Die Annahme K_{2} wäre beschränkt, führt, indem man die Rollen der Folgen x_{i} und y_{i} vertauscht, ebenso zum Widerspruch □

Im folgenden Korollar fassen wir die Ergebnisse der beiden vorstehenden Lemmata zusammen und schränken A gleich auf eine Teilmenge B′ von B ein, da wir im folgenden nur diesen Fall benötigen.

Korollar 14 Sei B ⊂ IR^{n} abgeschlossen, B′ ⊂ B, und (T, 0) ein punktierter topologischer Raum. Sei F̂ : B′ × B → T stetig und für alle x ∈ B′ gelte F̂(x, x) = 0.

Definiere ψF̂ : B′ → P(B) durch

ψF̂(x) := C_{x}{y ∈ B |F̂(x, y) = 0}.

Seien x_{i} → x^{∗} eine in B′ und y_{i} → y^{∗} eine in B konvergente Folge mit y_{i} ∈ ψF̂(x_{i}). Dann gilt

lim_{i→∞} d(y_{i}, ψF̂(x^{∗})) = 0,

oder die Menge {y |F̂(x^{∗}, y) = 0} besitzt zwei unbeschränkte Zusammenhangskomponenten. ◇

Beweis: Setze A := B′ und sei ϕ die kanonische Injektion. Dann ergibt sich die Behauptung sofort aus Lemma 3-21 und Lemma 4-22. □

Zur Vereinfachung der Schreibweise führen wir folgende Abkürzung ein:

Definition 5 Sei B ⊂ IR^{n} und F ∈ M^{∗}(B). Dann sagen wir, die Bedingung C_{k}(B) ist erfüllt, wenn kein k–Blatt zu F in B mehr als höchstens eine unbeschränkte Komponente besitzt.

Wir sagen, die Bedingung C_{k}^{∗} ist erfüllt, wenn kein k–Blatt zu F in B mehr als höchstens eine Komponente besitzt, deren Abschluß in B den Rand ∂B von B schneidet. Formal fassen wir den “Punkt ∞” als Rand von IR^{n} auf. Die Bedingungen C_{k}(IR^{n}) und C_{k}^{∗}(IR^{n}) besagen also dasselbe.

◇

Insbesondere ist die Bedingung C_{k} also erfüllt, wenn B kompakt ist. Für die Bedingung C_{k}^{∗} braucht das nicht zu gelten. Im allgemeinen ist C_{k}^{∗}(B) eine wesentlich stärkere Forderung als C_{k}(B). C_{1}(IR^{n}) ist für F = ∇f insbesondere dann erfüllt, wenn die Niveaumengen

N_{α}(f) := {x ∈ IR^{n} : f(x) ≤ α}

für alle hinreichend großen α konvex und kompakt sind.

Im nächsten Korollar formulieren wir den Spezialfall von Korollar 14-23, den wir für unsere Anwedungen benötigen:

Korollar 15 Sei B abgeschlossen, F ∈ M^{∗}(B) und die Bedingung C_{k}(B) sei erfüllt. Sei x_{i} → x^{∗} eine konvergente Folge in B, V_{i} → V^{∗} eine konvergente Folge in G(k, n) und Z ⊂ Null(F, B). Für alle i gebe es ein z_{i} ∈ Z, so daß gilt:

x_{i} ∈ C_{z_{i}}F_{V_{i}}(F, B).

Dann gibt es einen Nullstelle z^{∗} ∈ Z mit:

x^{∗} ∈ C_{z^{∗}}F_{V^{∗}}(F, B).
◇

Beweis: Da Z endlich ist, können wir o.E. annehmen (sonst Übergang zu Teilfolgen), daß es eine Nullstelle z^{∗} ∈ Z gibt, so daß für alle i gilt:

x_{i} ∈ C_{z^{∗}}F_{V_{i}}(F, B).

Wir setzen nun B′ := {x^{∗}, x_{1}, x_{2}, …} ⊂ B. Dann ist die Abbildung a : B′ → G(k, n) mit a(x_{i}) = V_{i}, a(x^{∗}) = V^{∗} stetig und es ist z^{∗} ∈ C_{x_{i}}F_{a(x_{i})}(F, B). Der punktierte Raum (T, 0) sei der IR^{n−k} mit Grundpunkt 0_{n−k}.

Sei A_{V} für jedes V ∈ a(B′) eine V zugeordnete (n−k)×n-Matrix, so daß die Zuordnung V ↦ A_{V} stetig ist. Eine solche Zuordnung gibt es: Man wähle etwa eine Orthonormalbasis von V^{∗} aus Vektoren v_{1}, …, v_{n−k} und betrachte zu gegebenem x_{i} die orthogonalen Projektionen v_{ji}, j = 1, …, n−k der v_{j} auf den Raum V_{i}. Für hinreichend große i spannen dann die v_{ji} den Raum V_{i} auf. Man bilde dann die (n − k) × n-Matrizen A_{V_{i}} deren j-Zeile der Zeilenvektor v_{ji}^{⊤} ist.

Damit ist die Abbildung F̂ : B′ × B → IR^{n−k} mit (x, y) ↦ A_{a(x)}F (y) stetig und es ist ψF̂(x) = C_{x}F_{a(x)}(F, B). Setzen wir noch y_{i} := z^{∗} für alle i, dann liefert Korollar 14-23:

d(z^{∗}, C_{x^{∗}}F_{V^{∗}}(F, B)) = 0,

also z^{∗} ∈ C_{x^{∗}}F_{V^{∗}}(F, B) und daher liegt auch x^{∗} in C_{z^{∗}}F_{V^{∗}}(F, B). □

Das nächste Lemma bereitet den darauf folgenden Satz vor und wird auch im weiteren noch benötigt.

Lemma 5 Sei B ⊂ IR^{n} abgeschlossen, F ∈ M^{∗}(B) und z^{∗} eine Nullstelle von F in B. Die Bedingung C_{k}(B) sei erfüllt. Dann ist

R(z^{∗}) := ⋃_{V ∈G(k,n)} C_{z^{∗}}F_{V} (F, B)

abgeschlossen in B. ◇

Beweis: Sei x_{i} → x^{∗} eine konvergente Folge mit x_{i} ∈ R(z^{∗}). Zu zeigen ist x^{∗} ∈ R(z^{∗}).

Jedes x_{i} liegt in einer k-Blatt-Komponente C_{z^{∗}}F_{V_{i}}(F, B) mit V_{i} ∈ G(k, n). Da G(k, n) folgenkompakt ist, gibt es eine Teilfolge der x_{i} und ein V^{∗} ∈ G(k, n), so daß die V_{i} gegen V^{∗} konvergieren und die x_{i} in C_{z^{∗}}F_{V_{i}}(F, B) liegen. Korollar 15-23 liefert nun x^{∗} ∈ C_{z^{∗}}F_{V^{∗}}(F, B), also liegt x^{∗} in R(z^{∗}). □

Wenn die Bedingung C_{k}(B) nicht erfüllt ist, braucht R(z^{∗}) dagegen nicht abgeschlossen in B zu sein:

Beispiel: Sei B := IR^{2} und f : IR^{2} → IR gegeben durch f(x, y) := x^{3}/3 − x + y^{2}. Diese Funktion besitzt die beiden nichtentarteten kritischen Punkte x^{±} = (±1, 0) und man rechnet leicht nach, daß etwa R(x^{+}) = IR^{2} \ {(x, y) ∈ IR^{2} : x = −1, y ≠ 0} ist und diese Menge ist weder offen, noch abgeschlossen. ◇

Auch beim folgenden Satz ist die Voraussetzung über die Anzahl der unbeschränkten Komponenten der k–Blätter insbesondere dann erfüllt, wenn B kompakt ist. Die Voraussetzung, daß alle Komponenten gebunden sein sollen, läßt sich allerdings am leichtesten im Fall B = IR^{n} überprüfen. Zur Definition von “frei” vergleiche Seite 15.

Satz 16 Sei B ⊂ IR^{n} abgeschlossen und zusammenhängend, F ∈ M^{∗}(B), und k ≥ 1. Wenn kein k–Blatt zu F zwei unbeschränkte Zusammenhangskomponenten besitzt und wenn keine Komponente eines k-Blattes frei ist, dann ist Γ^{k}(F, B) zusammenhängend. ◇

Beweis: Sei Γ die Menge der Ecken einer Zusammenhangskomponente des Graphen Γ^{k}(F, B). Für jede Nullstelle z von F sei, wie in Lemma 5-24 definiert:

R(z) := ⋃_{V ∈G(k,n)} C_{z}F_{V} (F, B).

Außerdem setzen wir

R := ⋃_{z∈Γ} R(z).

Wir zeigen R = B. Denn dann liegt jede Nullstelle von F auf einer k–Blatt–Komponente, die auch einen Punkt aus Γ enthält. Daraus folgt dann Γ^{k}(F, B) = Γ.

Angenommen R ≠ B. Dann gibt es, da B zusammenhängend ist, einen Randpunkt x^{∗} von R und dieser kann offenbar (wegen k ≥ 1 und Satz 6-15 ) keine Nullstelle von F sein. Da F nach Voraussetzung in B nur endlich viele Nullstellen besitzt ist auch Γ endlich und da R(z) nach Lemma 5-24 abgeschlossen ist, ist auch R abgeschlossen. Also liegt x^{∗} in R. Folglich gibt es einen Punkt z^{∗} ∈ Γ und ein V^{∗} ∈ G(k, n), so daß x^{∗} in C_{z^{∗}}F_{V^{∗}}(F, B) liegt.

Sei nun x_{i} → x^{∗} eine Folge in B \ R. Eine solche Folge gibt es, da B \ R offen in B ist und x^{∗} ein Randpunkt von B \R ist. Da F stetig ist, gibt es eine Folge V_{i} → V^{∗} in G(k, n) mit F (x_{i}) ∈ V_{i}^{⊥}. Da Γ^{k}(F, B) endlich ist und keine k-Blatt-Komponente frei ist, können wir also voraussetzen, daß es eine Nullstelle z ∈ Γ^{k}(F, B) \ Γ gibt, mit x_{i} ∈ C_{z}F_{V_{i}}(F, B) für alle i.

Korollar 15-23 liefert uns schließlich z ∈ C_{x^{∗}}F_{V^{∗}}(F, B) und daher liegt x^{∗} auch in C_{z}F_{V^{∗}}(F, B) ∩ C_{z^{∗}}F_{V^{∗}}(F, B). Also liegt z auch in C_{z^{∗}}F_{V^{∗}}(F, B) und daher auch in Γ. □

Wenn C_{k}(B) nicht erfüllt ist, läßt sich in manchen Fällen folgendes Kriterium anwenden:

Satz 17 Sei B ⊂ IR^{n} offen (!) und zusammenhängend, F ∈ M^{∗}(B), und k ≥ 1. Wenn keine unbeschränkte Komponente eines k-Blatts zu F eine außerordentliche Singularität von F enthält und keine Komponente eines k-Blattes frei ist, dann ist Γ^{k}(F, B) zusammenhängend. ◇

Beweisskizze: Man nimmt R ≠ B an und betrachtet einen Randpunkt x^{∗} ∈ B der wie im Beweis von Satz 16-25 definierten Menge R. Dann liegt x^{∗} in einer Komponente C_{z}F_{V} (F, B) eines k-Blattes durch eine Nullstelle z ∈ Null(F). Wenn diese Komponente beschränkt ist, schließt man ähnlich wie im Beweis von Satz 16-25. Wenn sie nicht beschränkt ist, enthält sie keine außerordentlichen Singularitäten und man überlegt sich, daß für dicht bei x^{∗} gelegene x und dicht bei V gelegene W ∈ G(k, n) mit x ∈ F_{W} (F, B) die (endlich vielen) Nullstellen auf C_{z}F_{V} (F, B), wegen der Offenheit von B, auch in C_{x}F_{W} (F, B) liegen. (Man betrachte die Menge {(x, V) ∈ IR^{n} × G(k, n) : x ∈ F_{V} (F)} und darauf die Abbildung π_{2} : (x, V) ↦ V) □

Bemerkung 5 Auf die Voraussetzung, daß B offen ist, kann nicht ohne weitres verzichtet werden, sonst ließen sich die verbindenden Trajektorien durch eine geeignete Struktur von B “blockieren”, wie folgendes Beispiel zeigt (siehe dazu Bild 2-27):

Sei, wie im letzten Beispiel, f(x, y) = x^{3}/3−x+y^{2}. Sei A_{1} = {(x, y) ∈ IR^{2} : x = 0, y ≤ 1} und A_{2} = {(x, y) ∈ IR^{2} : y = 1, 0 ≤ x < 1}. Setzen wir B := IR^{2} \ (A_{1} ∪ A_{2}), dann ist B zusammenhängend, ∇f ∈ M^{∗}(B). Außerdem besitzt f keine außerordentlichen Singularitäten und keine Komponente einer Newton-Trajektorie zu f ist frei. Die Bedingung C_{1}(B) ist verletzt. B ist nicht offen und Γ^{1}(f, B) ist nicht zusammenhängend. ◇

Die Voraussetzung, daß keine Komponente eines k-Blattes frei sei, ist für die Anwendung dieser Sätze lästig und läßt sich noch am ehesten im Fall B = IR^{n} nachweisen. Da B in obigen Sätzen aber ziemlich beliebig sein darf, könnte man ohne eine derartige Voraussetzung ein einmal gewähltes B durch Übergang zu einer geschickt gewählten zusammenhängenden Teilmenge B′ meist so verändern, daß die Nullstellen verbindenden Trajektorien abgeschnitten werden und Γ^{k} folglich zerfällt. Sei etwa F eine freie, reguläre (n − 1)-Blatt-Komponente, und jede Komponente von B \ F enthalte Nullstellen von F. Dann kann Γ^{1}(F, B) wegen Satz 7-15 nicht zusammenhängend sein.

Wir wollen nun sehen, ob sich nicht auch ohne die Voraussetzung, daß keine k-Blatt-Komponente frei sei, etwas über den Zusammenhang der Graphen Γ^{k} beweisen läßt. Dazu zunächst folgende Definition.

Definition 6 Wir definieren für B ⊂ IR^{n} und F ∈ M^{∗}(B):

free_{k}(F, B) := {x ∈ B |Jede k-Blatt-Komponente durch x ist frei}
free_{k}^{∗}(F, B) := {x ∈ B |Es gibt eine freie k-Blatt-Komponente durch x}

Abbildung 2: Skizze zu Bemerkung 5-26.

bound_{k}(F, B) := {x ∈ B |Es gibt eine gebundene k-Blatt-Komponente
durch x}
bound_{k}^{∗}(F, B) := {x ∈ B |Jede k-Blatt-Komponente durch x ist gebunden}
◇

Einige wichtige Eigenschaften dieser Mengen stellen wir in der folgenden Bemerkung zusammen. Die Beweise der einzelnen Punkte sind trivial.

Bemerkung 6 Sei B ⊂ IR^{n} und F ∈ M^{∗}(B). Dann gilt:

(i) free_{k}(F, B) ∪ bound_{k}(F, B) = B und free_{k}(F, B) ∩ bound_{k}(F, B) = ∅.
(ii) free_{k}^{∗}(F, B) ∪ bound_{k}^{∗}(F, B) = B und free_{k}^{∗}(F, B) ∩ bound_{k}^{∗}(F, B) = ∅.
(iii) free_{k}(F, B) ⊂ free_{k}^{∗}(F, B) und Null(F, B) ⊂ bound_{k}^{∗}(F, B) ⊂ bound_{k}(F, B).
(iv) free_{1}(F, B) = free_{1}^{∗}(F, B) und bound_{1}(F, B) = bound_{1}^{∗}(F, B).
◇

Die Mengen free_{k}(F, B) und bound_{k}(F, B), sowie free_{k}^{∗}(F, B) und bound_{k}^{∗}(F, B) bilden also eine Partition von B.

Lemma 6 Sei B ⊂ IR^{n} abgeschlossen, F ∈ M^{∗}(B) und die Bedingung C_{k}(B) (Seite 23) sei erfüllt. Dann sind free_{k}(F, B) und free_{k}^{∗}(F, B) offen in B sowie bound_{k}(F, B) und bound_{k}^{∗}(F, B) abgeschlossen in B. ◇

Beweis: Es reicht zu zeigen, daß bound_{k}(F, B) und bound_{k}^{∗}(F, B) abgeschlossen sind. Zunächst ist

bound_{k}(F, B) = ⋃_{z∈Null(F)} R(z).

Die Mengen R(z) sind nach Lemma 5-24 abgeschlossen und da Null(F) endlich ist, ist folglich auch bound_{k}(F, B) abgeschlossen.

Jetzt betrachten wir bound_{k}^{∗}(F, B). Sei x_{i} → x^{∗} eine konvergente Folge in B, mit x_{i} ∈ bound_{k}^{∗}(F, B). Zu zeigen ist x^{∗} ∈ bound_{k}^{∗}(F, B). O.E. sei x^{∗} ∉ Null(F, B).

Angenommen, es gebe ein V^{∗} ∈ G(k, n), so daß x^{∗} ∈ F_{V^{∗}}(F, B) und C_{x^{∗}}F_{V^{∗}}(F, B) wäre frei. Da F stetig ist, gibt es eine Folge V_{i} → V^{∗} in G(k, n) und gewisse Nullstellen z_{i} mit x_{i} ∈ C_{z_{i}}F_{V_{i}}(F, B). Da G(k, n) folgenkompakt und Null(F) endlich ist, können wir annehmen (Teilfolge, etc.), daß es eine Nullstelle z^{∗} gibt, so daß x_{i} in C_{z^{∗}}F_{V_{i}}(F, B) liegt. Daraus folgt mit Korollar 15-23 dann z^{∗} ∈ C_{x}^{∗}F_{V^{∗}}(F, B), im Widerspruch zur angenommenen Freiheit von C_{x^{∗}}F_{V^{∗}}(F, B). □

Der folgende Satz über den Zusammenhang der Graphen Γ^{k} kommt nun ohne die lästige Voraussetzung aus, daß es keine freien k-Blatt-Komponenten gebe. Auf die Bedingung C_{k} können wir allerdings nicht verzichten, wie einfache Gegenbeispiele zeigen.

Satz 18 Sei B ⊂ IR^{n} abgeschlossen und zusammenhängend, F ∈ M(B) und die Bedingung C_{k}(B) sei erfüllt. Dann gilt:

(i) Wenn bound_{k}(F, B) nicht zusammenhängend ist, dann ist auch Γ^{k}(F, B) nicht zusammenhängend.

(ii) Wenn bound_{k}^{∗}(F, B) zusammenhängend ist, dann ist auch Γ^{k}(F, B) zusammenhängend.

◇

Beweis:

(i) Wenn bound_{k}(F, B) nicht zusammenhängend ist, dann ist Γ^{k}(F, B) trivialerweise nicht zusammenhängend.

(ii) bound_{k}^{∗}(F, B) ⊂ B ist nach Lemma 6-28 abgeschlossen und erfüllt die Bedingung C_{k}(B), da B die Bedingung C_{k}(B) erfüllt. Also können wir Satz 16-25 anwenden und schließen, daß Γ^{k}(F, bound_{k}^{∗}(F, B)) zusammenhängend ist. Da bound_{k}^{∗}(F, B) aber alle Nullstellen von f in B enthält, ist Γ(F, bound_{k}^{∗}(F, B)) = Γ^{k}(F, B) und daher ist auch Γ^{k}(F, B) zusammenhängend. □

Hier soll noch auf eine interessante Invarianzeigenschaft bezüglich lokaler Modifikationen von F hingewiesen werden. Sei B ⊂ IR^{n}, F ∈ M^{∗}(B) und sowie V eine Teilmenge von B, die bound_{k}^{∗}(F, B) enthält. Sei weiter U eine Teilmenge von V, die keine Nullstellen von F enthält. Wenn dann bound_{k}^{∗}(F, V \ U) zusammenhängend, C_{k}(V \ U) erfüllt und V \ U abgeschlossen in R^{n} ist, dann ist Γ^{k}(F, V \ U) zusammenhängend. Also gibt es für den Zusammenhang von Γ^{k}(F, B) erforderliche Newton-Blätter schon unter den Blättern, die U nicht schneiden. Folglich ist auch Γ^{k}(G, B) zusammenhängend für alle Funktionen G ∈ M^{∗}(B), die sich von F höchstens innerhalb von U unterscheiden, aber keine Nullstellen in U haben.

Die Lücke zwischen (i) und (ii) in Satz 18-28 läßt sich im Fall k = 1 schließen:

Korollar 19 Sei B ⊂ IR^{n} abgeschlossen und zusammenhängend, F ∈ M^{∗}(B) und die Bedingung C_{1}(B) sei erfüllt. Dann besitzt Γ^{1}(F, B) dieselbe Anzahl Zusammenhangskomponenten wie bound_{1}(F, B). Insbesondere ist Γ^{1}(F, B) genau dann zusammenhängend, wenn bound_{1}(F, B) zusammenhängend ist. ◇

Beweis: Nach Bemerkung 6-27 (iv) ist bound_{1}(F, B) = bound_{1}^{∗}(F, B). Die Behauptung folgt damit sofort aus Satz 18-28 (bzw. aus dem Beweis). □

4 Komplexe Newton–Flüsse

Man kann das kontinuierliche Newton-Verfahren auch für komplexwertige Funktionen auf C I betrachten. Man geht dabei aus von dem komplexen Analogon der Gleichung (2-1):

dz/dt = −\frac{F (z)}{F′(z)}.  (6)

Der zugehörige Newton-Fluß wurde für polynomiale F zum Beispiel von Braess in [2] untersucht. Twilt untersuchte in seiner Dissertation [23] Newton-Flüsse für meromorphe Funktionen. Diese Untersuchungen wurden dann in mehreren Arbeiten von Jongen, Jonker und Twilt weitergeführt (siehe z.B. [14, 16]). Eine kurze Zusammenfassung der Ergebnisse findet man in [15].

Man kann dann die Gleichung (6-30), ähnlich wie bei der Gleichung (2-1), “regularisieren” und gelangt so zu der Differentialgleichung

dz/dt = −\overline{F′(z)}F (z),  (7)

deren rechte Seite für ganze Funktionen F auf ganz C I definiert ist. Das zugehörige Vektorfeld auf C I bezeichnen wir, wie Jongen, Jonker und Twilt, mit Ñ(F).

Um den Newton-Fluß auch für in C I meromorphe F überall zu definieren, kann man einen weiteren Regularisierungsschritt vornehmen und gelangt so zu dem Vektorfeld

\overline{N} (F)|_{z} := \{ \begin{matrix}(1 + |F (z)|^{4})^{−1}Ñ(F)|_{z} & wenn z kein Pol von F ist \\ 0 & wenn z ein Pol von F ist. \end{matrix}

Die Phasenportraits von Ñ(F) und \overline{N} (F) stimmen außerhalb der Pole von F überein.

In den oben genannten Arbeiten werden die Eigenschaften des kontinuierlichen Newton-Verfahrens im Komplexen ausführlich untersucht und interessante geometrische Eigenschaften des Phasenportraits und der maximalen Trajektorien hergeleitet. Wir werden darauf hier nicht weiter eingehen, sondern vielmehr auf einen anderen Aspekt hinweisen.

Sei F : C I → C I eine (nichtkonstante) ganze Funktion, F = u + iv, mit reellwertigen Funktionen u und v auf C I. Wir setzen z = x + iy und ordnen F zwei Abbildungen von IR^{2} nach IR^{2} zu:

R(F) := (u, v)^{⊤},

und

S(F) := (u, −v)^{⊤}.

Da für u, v die Cauchy-Riemannschen Differentialgleichungen gelten, ist S(F) Gradient einer (bis auf eine Konstante bestimmten) harmonischen Funktion s(F) : IR^{2} → IR und durch Nachrechnen stellt man leicht fest, daß gilt:

Ñ(F) = N (R(F)) = −N (s(F)) = −N (S(F)).

(N (s(F)) ist eindeutig bestimmt, obwohl s(F) nur bis auf eine Konstante bestimmt ist.) Das Studium komplexer Newton-Flüsse für ganze Funktionen kann also auf das Studium gewisser spezieller Gradienten-Newton-Flüsse (nämlich N (s(F))) im IR^{2} zurückgeführt werden (vgl. [15]).

Nun ergibt sich explizit:

Ñ(F)|_{z} = −\overline{F′(z)}F (z)
= −(u_{x} − iv_{x})(u + iv)
= −((u_{x}u + v_{x}v) + i(u_{x}v − v_{x}u))

Fassen wir |F |^{2} als Abbildung von IR^{2} nach IR auf, so erhalten wir, unter Beachtung der Cauchy-Riemannschen Differentialgleichungen, für deren Gradienten:

\frac{1}{2}∇|F |^{2} = \frac{1}{2}∇(u^{2} + v^{2}) = (uu_{x} + vv_{x}, vu_{x} − v_{x}u)^{⊤}.

Vergleich liefert also:

\frac{1}{2}∇|F (x + iy)|^{2} = −Ñ(F)|_{x+iy},

wobei wir den IR^{2} mit C I via x + iy ↔ (x, y)^{⊤} identifiziert haben. Der komplexe Newton-Fluß “ist” also eigentlich ein Gradienten-Fluß. Man kann diese Betrachtungen entsprechend erweitern und erhält:

Satz 20 Sei F im Gebiet G ⊂ C I holomorph, dann läßt sich das Vektorfeld des komplexen Newton-Flusses auf G als Gradientenfeld darstellen. ◇

Diese Eigenschaft des komplexen Newton-Vektorfeldes erhellt einige in den oben zitierten Arbeiten erhaltenen Resultate, wie bespielweise das schon von Braess in [2] erhaltene Resultat, daß die Einzugsbereiche der Nullstellen von Polynomen p bezüglich des komplexen kontinuierlichen Newton-Verfahrens unbeschränkt sind. Denn wenn wir der Einfachheit halber annehmen, daß die Nullstellen von p und p′ einfach sind, daß also die kritischen Punkte von |p|^{2} nicht entartet und die außerordentlichen Singularitäten Sattelpunkte sind, dann besitzt |p|^{2} nur nichtentartete Minima und Sattelpunkte als kritische Punkte, und keine Maxima. Die Flußlinien des Gradientenflusses, die in der Nähe eines Minimums (einer Nullstelle von p) starten und nicht nach Unendlich laufen, müssen daher gegen Sattelpunkte streben. Es gibt aber nur endlich viele Sattelpunkte und in jedem terminieren für wachsende t genau zwei Flußlinien.

Wir wollen nun die erhaltenen Sätze über den Graphen Γ^{1}(f) auf Funktionen f der Form |F (x+iy)|^{2} anwenden. Das kontinuierliche Newton–Verfahren für solche Funktionen wurde kürzlich von Twilt, Jonker und Streng in [24] für den Fall näher untersucht, daß F ein komplexes Polynom ist.

Sei also f(x, y) = |F (x + iy)|^{2}, mit einer nichtkonstanten ganzen Funktion F. Dann lassen sich die Newton–Trajektorien zu f mit einem reellen Winkel ϕ darstellen als Abschluß der Menge aller z aus C I \ N(F), für die ℜ(e^{−iϕ}F′(z)/F (z)) = 0 ist. Die kritischen Punkte von f sind die Nullstellen von F und von F′, also Krit(f) = N(F) ∪ N(F′). Den Nullstellen von F entsprechen lokale Minima von f und den Nullstellen von F′ entsprechen Sattelpunkte von f. Durch Ausrechnen bestätigt man leicht folgende Gleichung:

Ñ(F′/F)|F |^{4} = −\overline{(F′′F − F^{′2})}F′F = H̃_{f}∇f = −\frac{1}{2}(∇|F′/F |^{2})|F |^{4}.  (8)

Die außerordentlichen Singularitäten sind also die Punkte z mit F (z)F′(z) ≠ 0 und F′′(z)F (z) − F^{′2}(z) = 0. Aus der Gleichung (8-31) folgt sofort:

Lemma 7 Sei f : IR^{2} → IR von der Form f(x, y) = |F (x + iy)|^{2}, mit einer nichtkonstanten, im Gebiet G holomorphen Funktion F. Dann liegt auf jeder kompakten Komponente einer Newton-Trajektorie F_{V} (f, G) ein kritischer Punkt von f. ◇

Eine kritischer Punkt von f ist degeneriert, wenn die zugehörige Nullstelle von F oder F′ mehrfach ist. Damit folgt:

Satz 21 Sei f : IR^{2} → IR von der Form f(x, y) = |p(x + iy)|^{2} mit einem nichtkonstanten, komplexen Polynom p. Alle Nullstellen von p und p′ seien einfach. Dann ist Γ^{1}(f, IR^{2}) zusammenhängend. ◇

Die Höhenlinien einer solchen Funktion heißen “Lemniskaten” und die Geometrie dieser Kurven wird zum Beispiel in [25] und [18] im Zusammenhang mit Untersuchungen zur Lage der Nullstellen von p untersucht. Lemniskaten stehen auch in engem Zusammenhang mit dem Problem, die kritischen Punkte von Greenschen Funktionen zu bestimmen. Genaueres dazu findet man zum Beispiel in [25].

Beweis: Sei V ∈ G(1, 2). Dann hat keine Newton–Trajektorie F_{V} (f) freie Komponenten. Für kompakte Komponenten folgt dies aus Lemma 7-32 und für nichtkompakte aus der Tatsache, daß für genügend große c > 0 die Niveaumengen N_{c}(f) konvex und kompakt sind (vgl. [25]). Aus demselben Grund ist auch die Bedingung C_{1}(IR^{2}) erfüllt. Wir können also Korollar 19-29 anwenden (oder auch Satz 16-25) und erhalten die Behauptung. □

Es sei noch bemerkt, daß sich die Voraussetzung über die Einfachheit der Nullstellen von p und p′ bei näherer Betrachtung als unnötig erweist. Wir gehen darauf nicht näher ein. Auch für andere Klassen von Funktionen F lassen sich für f von der Form |F (x + iy)| mit den obigen Ergebnissen über den Zusammenhang von Γ^{1}(f) ähnliche Sätze erhalten.

5 Zusammenhängende Newton-Blätter

In [3] äußert Branin eine Vermutung, die wir in der Terminologie dieser Arbeit folgendermaßen formulieren können. Sei F : IR^{n} → IR^{n} und F besitze keine außerordentlichen Singularitäten. Dann gibt es keine freien Newton–Trajektorien und alle Newton–Trajektorien zu F sind zusammenhängend. Insbesondere liegen auf einer beliebigen Komponente einer beliebigen Newton-Trajektorie schon alle Nullstellen von F.

Diese Situation ist der Traum des Anwenders, denn dann kann er alle Nullstellen von F finden, indem er einfach in einem beliebigen Punkt x ∈ IR^{n} \ Null(F) startet und die durch diesen Punkt verlaufende Newton-Trajektorie (nach beiden “Richtungen”) numerisch verfolgt.

In [13] bewiesen die Autoren (eigentlich nur für den Fall F = ∇f, aber der Beweis gilt im allgemeinen Fall genauso), daß beim Fehlen außerordentlicher Singularitäten durch jede Nullstelle mindestens eine unbeschränkte Newton–Trajektorie geht, bei der diese Nullstelle “an einem Ende” liegt. Mit anderen Worten, durch jede Nullstelle x^{∗} gibt es eine unbeschränkte Komponente einer Newton-Trajektorie und einen Weg auf dieser Trajektorienkomponente von x^{∗} nach Unendlich, der durch keine andere Nullstelle von F passiert.

Nach Auffassung der Autoren ist die Vermutung Branins damit in einem gewissen Sinne widerlegt.

Tatsächlich ist aus Branins Formulierung nicht sicher zu entnehmen, was er genau meint. Er schreibt (siehe [3], Seite 508):

… In the absence of extraneous singular points, it seems plausible to expect not only that the method will be globally convergent but also that every trajectory will pass through all solution points of F (x) = 0. This conjecture is based on the behavior of the algorithm in two problems where extraneous singular points are known to be absent. It is also supported by the observation that the nodal points act like electric charges and the trajectories like electrostatic field lines that either terminate on charges or else pass to infinity…

In den Arbeiten [14, 15] kommen Jongen, Jonker und Twilt auf die Braninsche Vermutung zurück und interpretieren sie nun folgendermaßen:

If there are no extraneous singularities, one can find all zeros for ∇f by following (for increasing or decreasing t) a trajectory of (5-2) until one reaches a zero for ∇f and following another trajectory from this zero until on reaches another zero, and so on. In other words: in the absence of extraneous singularities, the system (5-2) provides a globally convergent method for finding all zeros for ∇f.

Diese Form ist anscheinend wesentlich schwächer, als das, was Branin im Sinne hatte. Sie bedeutet nach unserer Terminologie mindestens, daß der Graph Γ^{1}(F, IR^{n}) zusammenhängend ist, wenn F keine außerordentlichen Singularitäten besitzt. Daß das nicht richtig sein kann, ist nach den bisherigen Resultaten dieser Arbeit klar und auch Jongen, Jonker und Twilt geben ein explizites Gegenbeispiel an, nämlich f(x) := −e^{2x}/2 + e^{x} cos(y). Diese Funktion hat keine außerordentlichen Singularitäten, aber die Bedingung C_{1}(IR^{2}) ist verletzt und es gibt freie Trajektorien.

Die Braninsche Vermutung ist also falsch, auch wenn man sie in einer wesentlich schwächeren Form interpretiert.

Wir wenden uns nun der Frage zu, unter welchen zusätzlichen Voraussetzungen an F die ursprüngliche Braninsche Vermutung zu retten ist. Dazu zunächst folgendes Ergebnis:

Satz 22 Sei k > 0 und die Funktion F ∈ M^{∗}(IR^{n}) besitze wenigstens eine Nullstelle und keine außerordentlichen Singularitäten. Dann gilt: Genau dann sind alle k–Newton-Blätter zusammenhängend, wenn F die Bedingung C_{k}(IR^{n}) erfüllt. ◇

Beweisskizze: Wegen ExS(F) = ∅ sind alle k-Newton-Blätter zu F differenzierbare Mannigfaltigkeiten und eine Komponente C_{x}F_{V} (F) kann für variierende x, V nur “im Unendlichen aufspalten”. Da F nur endlich viele Nullstellen besitzt, überzeugt man sich davon, daß für genügend dicht bei x gelegene x′ und genügend dicht bei V gelegene V′ ∈ G(k, n) mit x′ ∈ F_{V′}(F) gilt:

C_{x}F_{V} (F) ∩ Null(F) ⊂ C_{x′}F_{V′}(F) ∩ Null(F).

Andererseits folgt aus Korollar 15-23 und der Bedingung C_{k}:

C_{x}F_{V} (F) ∩ Null(F) ⊃ C_{x′}F_{V′}(F) ∩ Null(F),

zusammen also

C_{x}F_{V} (F) ∩ Null(F) = C_{x′}F_{V′}(F) ∩ Null(F),

zunächst lokal, dann für alle x′, V′ mit x′ ∈ F_{V′}(F). Da Null(F) ≠ ∅ folgt daraus die Behauptung. □

Es ist angebracht, sich zu überlegen, ob der obige Satz nicht nur triviale Beispiele mit einer Nullstelle umfaßt. Klar ist, daß man zu jedem gegebenem F ein F̃ finden kann, das innerhalb einer interessierenden kompakten Menge K mit f übereinstimmt, so daß F̃ die Bedingung C_{k} erfüllt. Man braucht nur dafür zu sorgen, daß für hinreichend große ∥x∥ gilt: F (x) = x. Die Schwierigkeit liegt in der Vermeidung von außerordentlichen Singularitäten.

Für n = 2 überlegt man sich leicht, daß es Funktionen mit einem und mit zwei kritischen Punkten gibt, die die Voraussetzungen des Satzes erfüllen. Leider sind damit für n = 2 auch schon alle Beispiele erschöpft, denn es gilt:

Satz 23 Die Funktion F : IR^{2} → IR^{2} besitze keine außerordentlichen Singularitäten, und habe mindestens 3 Nullstellen. Dann gibt es eine Newton-Trajektorie T zu F, so daß nicht alle Nullstellen in einer Komponente von T liegen. ◇

Zum Beweis benötigen wir ein auch sonst nützliches Lemma:

Lemma 8 Sei F : IR^{n} → IR^{n} und U eine zusammenhängende, beschränkte offene Menge im IR^{n}, deren Rand in der Vereinigung von endlich vielen (n − 1)–Newton-Blättern enthalten ist. U enthalte keine Nullstellen von F. Dann liegt auf dem Rand von U eine gerade Anzahl Nullstellen. Wenn auf dem Rand mindestens 4 Nullstellen und keine außerordentlichen Singularitäten liegen, so enthält U eine außerordentliche Singularität von F. ◇

Beweis: Nach dem Morse–Sard–Lemma (vgl. Beweis zu 10-17) gibt es eine reguläre Newton-Trajektorie, so daß jede Komponente dieser Trajektorie, die durch eine Nullstelle auf dem Rand von U geht, mit U nichtleeren Durchschnitt hat. Diese Komponenten müssen U wieder verlassen und daher durch weitere Nullstellen auf dem Rand austreten (Satz 7-15). Die Nullstellen auf dem Rand lassen sich also paaren, und daher gibt es eine gerade Anzahl solcher Punkte.

Bezüglich der Differentialgleichung (4-2) enthält der Rand von U also mindestens zwei Attraktoren. Seien x_{1}, x_{2}, …, x_{r} die Attraktoren auf dem Rand von U. Wenn weder U noch der Rand von U außerordentliche Singularitäten enthalten, sind die in U liegenden Einzugsbereiche E_{i}, i = 1, …, r, dieser Attraktoren offen. Ebenso ist dann die Menge P der x ∈ U offen, durch die periodische Trajektorien verlaufen. Die Vereinigung von P mit den E_{i} ist gleich U und da U zusammenhängend ist muß P leer sein und es gibt nur ein E_{i}. □

Nun zum Beweis von Satz 23-34, den wir mit etwas anschaulichen Argumenten führen. Der Leser lege sich dazu eine Skizze an.

Beweis: Sei F eine Funktion ohne außerordentliche Singularitäten und mit den Nullstellen x_{1}, …, x_{k}, wobei k ≥ 3 ist. Dann sind alle Newton-Trajektorien zu F eindimensionale, differenzierbare Untermannigfaltigkeiten des IR^{2}. Die Komponenten von Trajektorien sind also unbeschränkt und diffeomorph zu IR oder kompakt und diffeomorph zu S^{1}.

Nehmen wir nun an, jede Newton-Trajektorie besitze eine Komponente, die x_{1}, …, x_{k} enthält. Nach dem zitierten Ergebnis aus der Arbeit [13] gibt es eine unbeschränkte, zu IR diffeomorphe Komponente T_{1} einer Newton-Trajektorie, so daß “links” von x_{1} keine Nullstellen liegen. O.E. liegen auf dieser Komponente rechts der Reihe nach die Nullstellen x_{2}, …, x_{k}. T_{1} zerlegt den IR^{2} in genau zwei unbeschränkte, offene Mengen, die wir mit U_{1}^{1} und U_{1}^{2} bezeichnen und deren Rand T_{1} ist.

Nun betrachten wir x_{2}. Durch x_{2} geht ebenso eine unbeschränkte Komponente T_{2} einer Newton-Trajektorie, so daß alle Nullstellen auf einer abgeschlossenen “Halbkomponente” T_{2}^{1} von T_{2} liegen. T_{2} ist nicht gleich T_{1} weil bezüglich T_{1} “links” und “rechts” von x_{2} die Nullstellen x_{1} und x_{3} liegen. O.E. liege T_{2}^{2}, die offene (bezüglich T_{2}) Halbkomponente von T_{2}, die keine Nullstellen enthält, in U_{1}^{1}. U_{1}^{1} werde von T_{2}^{2} in die beiden offenen, unbeschränkten Komponenten U_{2}^{1} und U_{2}^{2} zerlegt. O.E. sei U_{2}^{1} diejenige Komponente, deren Rand x_{1} enthält.

Wird T_{2}^{1} beginnend mit x_{2} durchlaufen, dann muß x_{1} die letzte Nullstelle sein, die durchlaufen wird, denn danach tritt T_{2}^{1} in U_{2}^{1} ein und kann diese offene Menge nicht mehr verlassen. Denn auf dem Rand von U_{2}^{1} liegen nur die Nullstellen x_{1} und x_{2}. Daraus folgt sofort, daß k gerade ist, denn nach dem Durchgang durch eine ungerade Anzahl der Punkte x_{3}, …, x_{k} verläuft T_{2}^{1} in U_{2}^{2} und x_{1} liegt nicht auf dem Rand von U_{2}^{2}.

Angenommen, T_{2}^{1} fädelt die Nullstellen in der Reihenfolge

x_{π(2)} = x_{2}, x_{π(3)}, x_{π(4)}, …, x_{π(k)}, x_{π(1)} = x_{1}

auf, wobei π eine Permutation der Zahlen von 1, 2, 3, 4, …, k ist, die 2 und 1 fest läßt. Trivialerweise ist dann π(i) − π(i + 1) ≡ 1 (mod 2), für i = 3, … k − 1.

Dann begrenzen der Teil von T_{1} zwischen x_{1} und x_{π(k)} und das Stück von T_{2}^{1} zwischen x_{π(k)} und x_{1} eine beschränkte, einfach zusammenhängende Menge U ⊂ IR^{2} deren Rand eine gerade Anzahl ≥ 4 von Nullstellen enthält. U muß daher nach Lemma 8-34 auch eine außerordentliche Singularität von f enthalten. Widerspruch.

Man kann auch einen Widerspruch erhalten, indem man ähnlich wie für x_{2} nun für x_{3} argumentiert. Wie eben folgt, daß durch x_{3} eine unbeschränkte Komponente T_{3} einer Newton-Trajektorie geht, so daß alle Nullstellen auf der abgeschlossenen Halbkomponente T_{3}^{1} von T_{3} liegen und die andere, bezüglich T_{3} offene Halbkomponente T_{3}^{2} keine Nullstellen enthält. T_{3} ist nicht gleich T_{1} und nicht gleich T_{2}, weil bezüglich T_{1} “links” und “rechts” von x_{3} die Nullstellen x_{2} und x_{4} liegen und ebenso bezüglich T_{2} die Nullstellen x_{π(π^{−1}(3)±1)} liegen. T_{3}^{2} muß in U_{2}^{2} liegen. durch Diskussion der verschiedenen Fälle überzeugt man sich davon, daß das nicht geht. □

Wir wenden uns nun der Frage zu, unter welchen Voraussetzungen es zusammenhängende Newton-Blätter gibt. Dabei würde uns eine globale Version des Satzes über implizite Funktionen weiterhelfen, den wir auf die Funktion A_{V} F (x) anwenden könnten, mit einer einem Unterraum V zugeordneten Matrix A_{V}.

Einen solchen Satz entnehmen wir [5]:

Zitat 10 (siehe[5]) Zu k ≤ n und F ∈ C^{2}(IR^{n}, IR^{k}) gebe es eine Konstante K, so daß gilt:

sup{∥(DF (x)D^{⊤}F (x))^{−1}∥ : x ∈ IR^{n}} ≤ K.

Dann ist F^{−1}(c) für alle c ∈ IR^{k} eine zusammenhängende (n − k)-dimensionale C^{1}– Mannigfaltigkeit im IR^{n}. ◇

Die unhandliche Voraussetzung dieses Satzes können wir etwas handlicher fassen:

Korollar 24 Sei k ≤ n und F ∈ C^{2}(IR^{n}, IR^{k}). Die k × k–Matrix DF (x)D^{⊤}F (x) sei gleichmäßig positiv definit auf IR^{n}. Dann ist F^{−1}(c) für alle c ∈ IR^{k} eine zusammenhängende C^{1}– Mannigfaltigkeit im IR^{n}. ◇

Damit folgt durch Anwendung von Korollar 24-36 auf A_{V} F (x):

Satz 25 Sei F_{V} (F, IR^{n}) ein k-Blatt zu F : IR^{n} → IR^{n} und A eine V zugeordnete Matrix. Dann gilt: Wenn die (n − k) × (n − k)–Matrix (ADF (x)D^{⊤}F (x)A^{⊤}) auf IR^{n} gleichmäßig positiv definit ist, dann ist das k-Blatt F_{V} (F, IR^{n}) zusammenhängend. ◇

Die Bedingung des Satzes ist recht stark, aber dennoch läßt er sich in manchen Fällen anwenden. Sei, beispielsweise, F : IR^{n} → IR^{n} und eine partielle Ableitung ∂F_{j}/∂x_{l} lasse sich auf ganz IR^{n} von 0 weg durch eine positive Konstante beschränken. Dann liefert der Satz den Zusammenhang der (n − 1)-Blätter F_{V} (F) für V = ⟨e_{j}⟩ und man kann das Problem der Suche nach den Nullstellen von F auf ein (n − 1)-dimensionales Problem zurückführen.

Der nächste Satz gibt ein Mittel an die Hand, weitere globale Versionen des Satzes über implizite Funktionen aus globalen Versionen des Satzes über Umkehrfunktionen zu erhalten.

Satz 26 Sei F : D ⊂ IR^{n} → IR^{k} und es gebe eine Abbildung G : D → IR^{n−k}, so daß die Abbildung H := (F, G) : D → H(D) ein globaler Homöomorphismus ist. Sei x_{0} ∈ D. Dann ist F^{−1}F (x_{0}) genau dann zusammenhängend, wenn H(D) ∩ {F (x_{0})} × IR^{n−k} zusammenhängend ist. ◇

Beweis: H besitzt eine Inverse H^{−1} und nach Definition von H ist F (H^{−1}(z)) = F (x_{0}) für alle z ∈ H(D) ∩ {F (x_{0})} × IR^{n−k}. Wenn diese Menge zusammenhängend ist, dann ist also auch F^{−1}F (x_{0}) zusammenhängend. Ist die Menge H(D) ∩ {F (x_{0})} × IR^{n−k} dagegen nicht zusammenhängend, dann kann auch ihr Bild F^{−1}F (x_{0}) unter H^{−1} nicht zusammenhängend sein, denn H^{−1} ist ein Homöomorphismus. □

Verwandt damit ist folgendes Ergebnis:

Satz 27 Sei f := (f_{1}, …, f_{k}) : IR^{n} → IR^{k} vom Rang k < n. Wenn es eine stetig differenzierbare Funktion f_{k+1} : IR^{n} → IR^{k} gibt, so daß f̂:= (f_{1}, …, f_{k+1}) : IR^{n} → IR^{k+1} vom Rang k + 1 ist, dann ist f^{−1}(c) für kein c ∈ f(IR^{n}) kompakt. ◇

Besitzt also zusätzlich f^{−1}(c) höchstens eine unbeschränkte Komponente, dann ist f^{−1}(c) zusammenhängend.

Beweis: M := f^{−1}(c) ist nach Voraussetzung eine C^{1}–Mannigfaltigkeit im IR^{n}. Angenommen M wäre kompakt. Dann besitzt das Problem: “Minimiere f_{k+1}(x) unter der Nebenbedingung x ∈ M” eine Lösung. Also gibt es ein x^{∗} ∈ M und Lagrange-Parameter λ_{1}, …, λ_{k} mit

∇f_{k+1}(x^{∗}) + ∑_{i=1}^{k} λ_{i}∇f_{i}(x^{∗}) = 0.

Dann aber kann f̂ in x^{∗} nicht denn Rang k + 1 haben. □

Die Frage ist, ob es zu gegebenem f : IR^{n} → IR^{k} vom Rang k immer ein solches f_{k+1} mit den verlangten Eigenschaften gibt. Wenn k = 1 ist und Df nie verschwindet, sieht man leicht, daß f^{−1}(c) nicht kompakt sein kann.

Anwendung dieses Satzes auf Newton–Trajektorien liefert

Korollar 28 Sei F ∈ M^{∗}(IR^{n}) und F_{V} (F) ein k–Newton-Blatt. Wenn für alle x ∈ IR^{n} der Rang von A_{V} DF (x) gleich k ist, dann sind für l > k alle l–Blätter, die F_{V} (F) enthalten unbeschränkt. Wenn ein solches l-Blatt nur eine unbeschränkte Komponente besitzt (wenn z.B. die Bedingung C_{l}(IR^{n}) erfüllt ist), dann ist es zusammenhängend. ◇

Der Beweis dieses Korollars ergibt sich sofort aus Satz 27-37. Als Beispiel für einen globalen Satz über inverse Funktionen sei folgender Satz genannt:

Zitat 11 (siehe[21]) Die Abbildung F ∈ C^{1}(IR^{n}, IR^{n}) ist genau dann ein C^{1}–Diffeomorphismus des IR^{n} auf sich, wenn die Jacobi-Matrix DF (x) für alle x ∈ IR^{n} nichtsingulär ist und aus ∥x∥ → ∞ auch ∥f(x)∥ → ∞ folgt. ◇

Entsprechende Versionen für Homöomorphismen zwischen Teilmengen erhält man aus einem anderen, allgemeineren Satz:

Zitat 12 (siehe[21]) Sei F : X → Y ein lokaler Homöomorphismus zwischen zusammenhängenden, lokalzusammenhängenden, lokalkompakten Hausdorff-Räumen. Dann ist F genau dann eine endliche Überlagerung, wenn das Urbild kompakter Teilmengen von Y kompakt ist. ◇

Wenn Y also zusammenziehbar ist, ist F ein globaler Homöomorphismus. Weitere globale Versionen des Satzes über inverse Funktionen für Abbildungen zwischen Teilmengen des IR^{n} findet man in [20].

Beispiel: Sei F (x, y) = y−x^{2}. Wählen wir G(x, y) = x, oder G(x, y) = xe^{2y}, dann ist die Abbildung H = (F, G) auf ganz IR^{2} definiert und dort ist überall det DH(x, y) ≠ 0. H ist also ein lokaler Homöomorphismus. Mit Hilfe von Zitat 12-38 folgt, daß H : D → H(D) für alle offenen, zusammenhängenden Mengen D ⊂ IR^{2} ein globaler Homöomorphismus ist.

Betrachten wir nun D := (−1, 1) × (−1, 1). Indem man sich das Bild des Randstückes R := {−1} × [−1, 1] ansieht, sieht man leicht, daß das Kriterium von Satz 26-37 genau für die x_{0} ∈ D mit F (x_{0}) > −1 erfüllt ist. Also ist F^{−1}(c)∩D genau dann zusammenhängend, wenn c > −1 ist.

Sei andererseits D = IR × (0, ∞) die offene obere Halbebene. Dann ist H(D) = {(x, y)^{⊤} ∈ IR^{2} | x > −y^{2}} und F^{−1}(c) ∩ D ist genau für c > 0 zusammenhängend.

Ist schließlich D = K_{r}(x_{0}) die offene Kreisscheibe vom Radius r und Mittelpunkt x_{0}, so ist F^{−1}(c) für alle c ∈ IR zusammenhängend (eventuell leer), wenn r < 1/2 ist. ◇

Als Beispiel soll gezeigt werden, wie man aus dem aus dem globalen Satz über inverse Funktionen von Palais einen globalen Satz über implizite Funktionen erhalten kann.

Satz 29 Sei k ≤ n und F ∈ C^{1}(IR^{n}, IR^{k}). Sei J eine k-elementige Teilmenge von {1, 2, …, n}. Sei D_{J}F (x) die Matrix, die aus den Spalten der Jacobi-Matrix DF (x) zu Indices aus J besteht, und für x ∈ IR^{n} sei x_{J} der Vektor mit den Komponenten von x, deren Indices in J liegen. Dann gilt:

Wenn D_{J}F (x) für alle x ∈ IR^{n} nichtsingulär ist und wenn für alle Folgen {x} mit ∥x_{J}∥ → ∞ die Beziehung ∥f(x)∥ → ∞ folgt, dann ist F^{−1}(y) für alle y ∈ IR^{k} eine zusammenhängende (n − k)–Mannigfaltigkeit im IR^{n}. ◇

Beweis: O.E. sei J = {1, 2, …, k}, und F (x)^{⊤} = (f_{1}(x), …, f_{k}(x)). Wir definieren H : IR^{n} → IR^{n} durch H_{j} : IR^{n} → IR durch H_{j} = f_{j} für j = 1, …, k, und H_{j}(x) = x_{j} für j = k + 1, …, n. Dann liefert Zitat 11-38 die Existenz einer eindeutig bestimmten, globalen Umkehrfunktion H^{−1} zu H und da H(IR^{n}) = IR^{n} konvex ist, liefert Satz 26-37 die Behauptung. □

Wir wollen diesen Ansatz, zu Aussagen über den Zusammenhang von Newton–Blättern zu gelangen, indem wir einen globalen Satz über Implizite Funktionen anwenden, hier nicht weiter verfolgen, denn bei solchen Zugängen handelt es sich auf die eine oder andere Weise immer darum, neben der Voraussetzung rangA_{V} DF (x) = dim V^{⊥} für alle x und nicht nur für x ∈ F_{V} (f), weitere Voraussetzungen nachzuweisen. Aber schon die Rangvoraussetzung ist für praktische Zwecke, jedenfalls im Fall von Newton-Trajektorien, zu einschneidend.

Satz 30 Sei B ⊂ IR^{n} abgeschlossen. Die Funktion F ∈ M^{∗}(B) besitze in B genau 3 Nullstellen und die Bedingung C_{1}^{∗}(B) sei erfüllt. Wenn dann Γ^{1}(F, B) zusammenhängend ist, dann gibt es eine Komponente einer Newton–Trajektorie zu F in B, die alle Nullstellen von F enthält. ◇

Beweis: F besitze in B genau die drei Nullstellen a, b und c. Angenommen, es gebe keine Komponente irgendeiner Newton-Trajektorie zu F in B, die a, b und c enthält.

Wie in Lemma 5-24 definieren wir für z ∈ Null(F, B):

R(z) := ⋃_{V ∈G(1,n)} C_{z}F_{V} (F, B).

Dann sind R(a), R(b) und R(c) zusammenhängend und nach Lemma 5-24 abgeschlossen, da C_{1}(B) erfüllt ist. Zwei der (nichtentarteten) Nullstellen a, b und c müssen gleichen Index haben, diese seien o.E. die Punkte a und c. Sei T (f, B) eine reguläre Newton-Trajektorie zu F in B. Dann muß wegen Satz 9-16 und der Bedingung C_{1}^{∗}(B) die Komponente C_{b}T (f, B) außer b noch genau eine weitere der Nullstellen a, c enthalten (und C_{b}T (F, B) kann ∂B nicht schneiden). Aus dem Morse–Sard–Lemma, der Bedingung C_{1}^{∗} und Korollar 15-23 folgt, daß jede Komponente C_{b}T einer Newton–Trajektorie zu F in B noch einen der Punkte a, c enhalten muß.

Wegen C_{1}^{∗}(B) ist b ein innerer Punkt von B und wegen Satz 6-15 auch ein innerer Punkt von R(b). Daher enthält R(b) auch eine (kleine) zusammenhängende, offene Umgebung U von b, so daß R(b) \ U immer noch abgeschlossen in B und zusammenhängend ist.

Nun läßt sich R(b) in der Form

R(b) = (R(b) ∩ R(a)) ∪ (R(b) ∩ R(c))

darstellen, also als Vereinigung zweier abgeschlossener, zusammenhängender Mengen. Der Durchschnitt dieser Mengen ist, nach der Annahme, daß keine Komponente einer Newton– Trajektorie a, b und c enthält, gleich {b}. Also hätten wir die zusammenhängende, abgeschlossene Menge R(b) \ U als Vereinigung zweier nichtleerer (weil Γ_{1} zusammenhängend ist), disjunkter abgeschlossener Mengen dargestellt, was nicht geht. □

Die Zahl 3 in obigem Satz läßt sich ohne weitere Voraussetzungen nicht erhöhen. In [24] geben die Autoren an, daß es im Falle f(x, y) = |p(x+iy)|^{2} mit einem komplexen Polynom p vom Grad 3 (dann hat f also i.a. 5 kritische Punkte) immer eine zusammenhängende Newton–Trajektorie gebe. Sie geben aber keinen vollständigen Beweis. Ebenfalls behauptet wird dort, daß das für komplexe Polynome vom Grad ≥ 8 i.a. falsch sei. Das folgende Beispiel zeigt, daß es schon im Falle von Polynomen vom Grad 5 nicht mehr stimmt.

Beispiel: Sei p(z) = ∏_{i=1}^{5}(z − z_{i}) mit z_{1} = −2, z_{2} = 0, z_{3} = 2, z_{4} = 1 + 2i, und z_{5} = −1 + 2.2i, und sei f(x, y) = |p(x + iy)|^{2}. Dann ist der Graph Γ^{1}(f, IR^{2}) der vollständige Graph K_{9}. Trotzdem enthält jede Newton–Trajektorie zu f mindestens 2 Komponenten und auf jeder Komponente liegen kritische Punkte von f (vgl. Lemma 7-32). In Bild 3-40 sind einige Höhenlinien der Funktion |p|^{2} zu sehen.

Abbildung 3: Einige Höhenlinien der Funktion |p(z)|^{2}.

Übrigens habe ich bei allen untersuchten Beispielen, bei denen f von der Form f(x, y) = |p(x + iy)|^{2} mit einem komplexen Polynom p ist, festgestellt, daß Γ^{1}(f, IR^{n}) ein vollständiger Graph ist. Einen Beweis oder eine Widerlegung einer solchen Vermutung habe ich nicht versucht.

Bild 4-41 zeigt die Newtontrajektorien in der Nähe der außerordentlichen Singularitäten von |p|^{2} und Bild 5-42 zeigt einige Trajektorien, an denen ablesen kann, daß Γ^{1}(|p|^{2}, IR^{2}) isomorph zum vollständigen Graphen K_{9} ist.

◇

Abbildung 4: Einige Newton-Trajektorien der Funktion |p|^{2} in der Nähe der außerordentlichen Singularitäten.

6 Verallgemeinerungen

Wir betrachten ein k-Blatt F_{V} (f) im IR^{n} mit k ≥ 2, also dim V ≤ n−2. In diesem k-Blatt liegen die r-Newton-Blätter F_{W} (f) mit W ⊃ V, W ∈ G(r, n) und nach Bemerkung 4-19 (ii) ist F_{V} (f) gerade die Vereinigung aller solchen r-Blätter F_{W}. Sei F_{V} (f) ein reguläres k-Newton-Blatt, also insbesondere eine abgeschlossene Mannigfaltigkeit im IR^{n}. Sei weiter f̂ : F_{V} (f) → IR die Restriktion von f auf F_{V} (f). Die Frage ist, ob sich die r-Blätter F_{W} (f) von f nicht als “verallgemeinerte r-Newton-Blätter” von f̂ auffassen lassen. Oder, allgemeiner, wie wären “verallgemeinerte Newton-Blätter” für Funktionen f : M → IR auf differenzierbaren Untermannigfaltigkeiten M des IR^{n} zu definieren?

Nun gilt für x ∈ F_{V} (f) ja ∇f(x) ∈ V^{⊥}. Für x ∈ F_{V} (f) sei T_{x} := T_{x}F_{V} (f) der Tangentialraum an F_{V} (f) im Punkte x und π_{x} : IR^{n} → T_{x} sei die orthogonale Projektion auf T_{x}. Dann ist ∇f̂(x) = π_{x}∇f(x) ∈ T_{x}. Folglich liegt ∇f̂(x) in π_{x}V^{⊥} für alle x ∈ F_{V} (f) und für das r-Newton-Blatt F_{W} (f) gilt: Wenn x in F_{W} (f) liegt, dann liegt ∇f̂(x) in π_{x}W^{⊥}.

Das legt für reguläre Newton-Blätter F_{V} (f) und Unterräume W ⊃ V folgende Definition nahe:

F_{V,W} (f) := {x ∈ F_{V} (f) : ∇f̂(x) ∈ π_{x}W^{⊥}}.

Abbildung 5: Newton-Trajektorien zu |p|^{2}, die zeigen, daß Γ^{1}(|p|^{2}, IR^{2}) zusammenhängend ist.

Diese Menge umfaßt im allgemeinen allerdings mehr als die Punkte von F_{W} (f). Daß dies nicht zu vermeiden ist, ist andererseits klar, denn ein “verallgemeinertes Newton-Blatt” zu f̂ muß ja alle kritischen Punkte von f̂ umfassen, und das sind neben den kritischen Punkten von f auch alle Punkte x ∈ F_{V} (f), in denen ∇f(x) senkrecht auf T_{x} steht.

Für zwei verschiedene r-kodimensionale Unterräume W_{1}, W_{2} ⊃ V erhalten wir:

F_{V,W_{1}} ∩ F_{V,W_{2}} = {x ∈ F_{V} : ∇f̂ ∈ π_{x}W_{1}^{⊥} ∩ π_{x}W_{2}^{⊥}}.

Im Schnitt zweier solcher verallgemeinerter Newton-Blätter liegen also stets die kritischen Punkte von f̂. Nur diese Punkte liegen im Schnitt, wenn für alle x ∈ F_{V} (f) gilt:

π_{x}W_{1}^{⊥} ∩ π_{x}W_{2}^{⊥} = {0}.

Das allerdings kann man zum Beispiel bei kompakten n − 1-Mannigfaltigkeiten F_{V} (f) wegen der Surjektivität der Gauß-Abbildung nicht erreichen.

Wir betrachten nun einige Transformationseigenschaften von Newton-Trajektorien. Dazu seien F, G ∈ C^{1}(IR^{n}, IR^{n}) und f ∈ C^{1}(IR^{n}, IR). Wenn G ein Homöomorphismus ist, erhalten wir

T_{g}(F ∘ G) = G^{−1}(T_{g}(F)).

Ist dagegen F ein Homöomorphismus, so ergibt sich

T_{g}(F ∘ G) = {x : G(x) ∈ F^{−1}(⟨g⟩)}.

Die Newton-Trajektorie T_{g}(F ∘ G) besteht also aus der Menge der Punkte in IR^{n} für die G(x) auf dem homöomorphen Bild der Geraden < g > unter der Abbildung F^{−1} liegt.

Für die Newton-Trajektorien von f ∘ G : IR^{n} → IR mit einem Homöomorphismus G sieht die Sache allerdings komplizierter aus. Man erhält:

T_{g}(f ∘ G) = G^{−1}({x : ∇f(x) ∈ ⟨(D^{⊤}G|_{G^{−1}(x)})^{−1}g⟩}).

Ist G ein linearer Isomorphismus, so folgt zwar

T_{g}(f) = G(T_{G^{⊤}g}(f ∘ G)),

aber im allgemeinen Fall läßt sich T_{g}(f ∘ G) nicht mehr einfach als homöomorphes Bild einer Newton-Trajektorie zu f darstellen. Der eindimensionale Unterraum des IR^{n}, in dem der Gradient zu liegen hätte, hängt jetzt vielmehr vom Aufpunkt ab.

Zu einer naheliegenden Verallgemeinerung des Konzepts von Newton-Trajektorien würde man also gelangen, wenn man die Menge der Punkte betrachtete, in denen F (x) (bzw. ∇f(x)) linear abhängig ist von einem Vektor g(x) ∈ IR^{n}. Um die Theorie dieser Arbeit auf diesen Fall übertragen zu können, müßte man das Vektorfeld g auf dem R^{n} noch parametrisieren und die Vektorfelder g_{τ} (x) betrachten und diese Parametrisierung müßte so sein, daß für feste x und τ ≠ τ′ die Vektoren g_{τ} (x) und g_{τ′}(x) nicht linear abhängig sind. Dann ist der Durchschnitt zweier so verallgemeinerter Newton-Trajektorien zu F mit verschiedenen τ gerade wieder die Menge der Nullstellen von F.

Wir wollen nun noch den Fall verallgemeinerter Newton-Trajektorien zu Funktionen auf Riemannschen Mannigfaltigkeiten kurz beleuchten. Sei also M eine n-dimensionale differenzierbare Mannigfaltigkeit mit Riemannscher Metrik, und f, g : M → IR differenzierbare Funktionen auf M. Im Sinne des eben Gesagten liegt es nun nahe, die Menge

F(f, g) := {x ∈ M : ∇f(x)∥∇g(x)}

zu betrachten, wobei die Schreibweise x∥y bedeuten soll, daß die beiden Vektoren x und y linear abhängig sind. Diese Idee wurde schon in [4] vorgeschlagen.

Die Menge F(f, g) enthält alle kritischen Punkte von f und g und wird unter geeigneten Voraussetzungen lokal eindimensional sein. Im Spezialfall M = IR^{n} und g linear erhalten wir offenbar die gewöhnlichen Newton-Trajektorien. Man kann große Teile der Theorie auf den allgemeinen Fall übertragen, wenn man mit einer stetig parametrisierten Schar g_{t} von Funktionen auf M arbeitet, so daß < ∇g_{τ} (x) > für variierende τ in jedem Punkt x ∈ M den ganzen Raum G(n − 1, n) durchläuft. Für im IR^{n+1} eingebettete M ist die auf M restringierte Funktionenschar g_{τ} (x) = τ^{⊤}x, τ ∈ S^{n} ein Beispiel, das auf die zu Anfang dieses Kapitels im Falle M = F_{V} (f) gemachte Konstruktion hinausläuft.

Anstelle von ∇g_{τ} könnte man natürlich auch ein anderes parametrisiertes tangentiales Vektorfeld auf M betrachten, oder gleich die entsprechende Konstruktion für Vektorfelder auf M betrachten. Große Teile der Theorie dieser Arbeit lassen sich auf diese allgemeinen Fälle übertragen.

Natürlich kann man alles auch noch auf k-Blätter auf Mannigfaltigkeiten verallgemeinern, aber in dieser Arbeit wollen wir uns damit begnügen, diese Möglichkeiten lediglich anzudeuten.

Literatur

[1] W. Bergweiler, F. von Haeseler, H. Kriete, H.G. Meier, and N. Terglane. Newton’s method for meromorphic functions. Preprint 31, Lehrstuhl C für Mathematik, RWTH Aachen, June 1991.

[2] D. Braess. Über den Einzugsbereich der Nullstellen von Polynomen beim Newton-Verfahren. Numerische Mathematik, 29 (1977) 123–132.

[3] F.H. Branin. A widely convergent method for finding multiple solutions of simultaneous nonlinear equations. I.B.M Journal of Research and Development, (1972) 504–522.

[4] I. Diener. Trajectory nets connecting all critical points of a smooth function. Mathematical Programming, 36 (1986) 340–352.

[5] I. Diener. On the global convergence of path-following methods to determine all solutions to a system of nonlinear equations. Mathematical Programming, 39 (1987) 181–188.

[6] I. Diener and R. Schaback. An extended continuous Newton method. Journal of Optimization Theory and Apllications, Vol. 67, Nr. 1 (1990) 57–77.

[7] C.B. Garcia and F.J. Gould. Relations between several path following algorithms and local and global Newton methods. SIAM Review, Vol. 22, Nr. 3 (1980) 263–274.

[8] J. Gomulka. Remarks on Branin’s method for solving nonlinear equations. In L.C.W. Dixon and G.P. Szegö, editors, Towards Global Optimisation, Band 1. North–Holland, Amsterdam, 1975.

[9] J. Gomulka. Two implementations of Branin’s method: Numerical experience. In L.C.W. Dixon and G.P. Szegö, editors, Towards Global Optimisation, Band 2. North– Holland, Amsterdam, 1978.

[10] R.S. Hamilton. The inverse function theorem of Nash and Moser. Bulletin of the AMS, Vol. 7, Nr 1 (1982) 65–222.

[11] J.W. Hardy. An implemented extension of Branin’s method. In L.C.W. Dixon and G.P. Szegö, editors, Towards Global Optimisation, Band 1. North–Holland, Amsterdam, 1975.

[12] M.W. Hirsch and S. Smale. On algorithms for solving f(x) = 0. Communications on Pure and Applied Mathematics, XXXII, (1979) 281–312.

[13] H.Th. Jongen, P. Jonker, and F. Twilt. On Newton flows in optimization. Methods of Operations Research, 31 (1979) 345–359.

[14] H.Th. Jongen, P. Jonker, and F. Twilt. The continuous Newton-method for meromorphic functions. In R. Martini, (Herausgeber), Geometric Approaches to Differential Equations. Lecture Notes in Mathematics, Vol. 810, Seiten 181–239. Springer Verlag, 1980.

[15] H.Th. Jongen, P. Jonker, and F. Twilt. Nonlinear Optimization in IR^{n}, Band II von Methoden und Verfahren der mathematischen Physik, Bd 32. Peter Lang Verlag, Frankfurt a.M., 1983.

[16] H.Th. Jongen, P. Jonker, and F. Twilt. The continuous, desingularized Newtonmethod for meromorphic functions. Memorandum 501, Twente University of Technology, 1985.

[17] H.Th. Jongen, P. Jonker, and F. Twilt. A note on Branin’s method for finding the critical points of smooth functions. In Parametric Optimization and Related Topics, Seiten 209–228, 1987. Int. Conf., Plaue, 1985.

[18] Morris Marden. The Geometry of the Zeros of a Polynomial in a Complex Variable. Mathematical Surveys, Number III. American Mathematical Society, 1949.

[19] Hans-Günter Meier. Diskrete und kontinuierliche Newton-Systeme im Komplexen. Dissertation, Rheinisch-Westfälische Technische Hochschule, Aachen, 1991.

[20] J.M. Ortega and W.C. Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York and London, 1970.

[21] R.S. Palais. Natural operations of differential forms. Transactions of the AMS, 92 (1959) 125–141.

[22] S. Smale. A convergent process of price adjustment and global Newton methods. Journal of Mathematical Economics, 3 (1976) 107–120.

[23] F. Twilt. Newton-flows for meromorphic functions. Dissertation, Twente University of Technology, Niederlande, 1981.

[24] F. Twilt, Jonker P., and M. Streng. Gradient Newton–flows for complex polynomials. Memorandum 764, Twente University of Technology, 1989.

[25] J.L. Walsh. The Location of Critical Points of Analytic and Harmonic Functions. Colloquium Publications, vol. XXXIV. American Mathematical Society, 1950.