Lösung nichtlinearer Gleichungen durch das Newtonverfahren

Neue Frage »

Tarex Auf diesen Beitrag antworten »
Lösung nichtlinearer Gleichungen durch das Newtonverfahren
Meine Frage:
Ich habe die Aufgabe bekommen die nichtlineare Gleichung zu lösen. Dabei sei z eine komplexe Variable mit z = x + iy. Dabei ist mein erstes Problem: Wo kommt das i her? Die Aufgabenstellung wird fortgefüht und es wird festgelegt, dass x der Realteil und y der Imaginärteil von z sei und daraus zwei Gleichungen entstehen:


Dieses Gleichungssystem hat drei Lösungen (in der Formel sind die "m" tiefgestellt) zm = xm + iym = (xm, ym), welche ich bestimmen muss und dann dazu den Iterationsverfahrensalgorithmus nach Newton aufstellen muss.


Meine Ideen:
Ich habe weder Ahnung wie ich überhaupt an die Aufgabe herangehen soll, noch wie ich die Lösungen bestimmen kann. Ich habe mich in den Newton Algorithmus eingelesen, jedoch verstehe ich nicht wie das mit zwei Variablen funktionieren soll. Jegliche Tipps würden mir sehr weiterhelfen. Schon mal danke im voraus!
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tarex
Dabei ist mein erstes Problem: Wo kommt das i her?

Du willst jetzt nicht im Ernst einen Einführungsvortrag über komplexe Zahlen??? geschockt
 
 
mYthos Auf diesen Beitrag antworten »

Auf Grund der Tatsache, dass EINE Lösung (reell) z1 = x1 = 1 sein muss, also z1 = 1 + 0*i, ist bekannt:

x1 = 1; y1 = 0

Finde damit die anderen zwei Lösungspaare.
Die zweite Gleichung schreibe als



und denke an den Satz vom Nullprodukt. Eliminiere dort y und setze dies in die erste Gleichung ein.
Für Newton gibt es keine Veranlassung, ausser du willst damit berechnen.
Die Lösungen für x und y können nur noch reell sein!

mY+
HAL 9000 Auf diesen Beitrag antworten »

Ich hab das so verstanden, dass die Aufgabenstellung vorschreibt, das Newtonverfahren anzuwenden. Aus Lehrzwecken kann man das schon mal an einer Gleichung mit anderweitig exakt ausrechenbaren Nullstellen durchexerzieren. Augenzwinkern

Und anscheinend soll man das auch nicht als eindimensonal komplexes, sondern zweidimensional reelles Newtonverfahren durchführen. Das bläht die Sache zusätzlich auf.
mYthos Auf diesen Beitrag antworten »

Wäre ja auch ein Unding, das SO zu lösen ... (SO'n Quark noch nicht gesehen!)

Er kann ja eh das Newton-Verfahren anwenden, wenn's sein muss, eindimensional, nicht zweidimensional.

in die erste Gleichung, es folgt



So, jetzt!
Achtung beim Startwert, der Wendepunkt kann Probleme verursachen.
Z.B. x1 = -1 wählen.

mY+
Tarex Auf diesen Beitrag antworten »
Lösung nichtlinearer Gleichungen durch das Newtonverfahren
Zitat:
Original von mYthos
Auf Grund der Tatsache, dass EINE Lösung (reell) z1 = x1 = 1 sein muss, also z1 = 1 + 0*i, ist bekannt:

x1 = 1; y1 = 0

Finde damit die anderen zwei Lösungspaare.
Die zweite Gleichung schreibe als



und denke an den Satz vom Nullprodukt. Eliminiere dort y und setze dies in die erste Gleichung ein.
Für Newton gibt es keine Veranlassung, ausser du willst damit berechnen.
Die Lösungen für x und y können nur noch reell sein!

mY+


Danke für die Antwort. Das mit dem x1 =1; y1=0 habe ich verstanden. Nach meiner Rechnung müsste das zweite Paar dann x2=-0,5; y2= sein. Jetzt stehe ich wieder aufm Schlauch. Wie kann man dann die dritte Lösung berechnen.
Ich entschuldige mich hier nochmals für meine Unwissenheit.
mYthos Auf diesen Beitrag antworten »

ist die einzige reelle Lösung, dazu gibt es zwei y-Werte.

Denn aus , so muss ebenfalls betragen.

Somit ist



--------------------------

Wie du siehst, ist zur Lösung kein Näherungsverfahren nötig. Wer hat denn solches verlangt und weshalb?

mY+
Steffen Bühler Auf diesen Beitrag antworten »

Vielleicht soll's ja eine Einführung in Fraktale werden. Das ist nämlich ein Klassiker:

[attach]41233[/attach]

Viele Grüße
Steffen
HAL 9000 Auf diesen Beitrag antworten »

Hier auch noch die inhaltliche Erläuterung was es mit der Punktfärbung in dem Bild von Steffen auf sich hat. Die Farbzuordnung stellt also dar, zu welcher der drei möglichen Wurzeln das Newtonverfahren konvergiert, abhängig vom gewählten komplexen Startwert der Folge.
Tarex Auf diesen Beitrag antworten »

Zitat:
Original von mYthos
ist die einzige reelle Lösung, dazu gibt es zwei y-Werte.

Denn aus , so muss ebenfalls betragen.

Somit ist



--------------------------

Wie du siehst, ist zur Lösung kein Näherungsverfahren nötig. Wer hat denn solches verlangt und weshalb?

mY+


Und auch danke für die Antwort. Da hätte ich eigentlich auch echt selbst drauf kommen können...

Das ganze ist eine Hausaufgabe um das Näherungsverfahren zu verstehen.

Jetzt gleich mal zum Näherungsverfahren, damit ich sicher bin, dass ich das verstanden habe: die Gleichung lautet dabei ja: xn - (f(xn)/f'(xn)
xn ist dabei der Startwert für die ganze Sache. Jetzt hier gleich mal eine Frage: Was genau muss ich bei der Wahl von xn1 beachten?
Wenn dann weitergerechnet wird, wird xn immer durch das Ergbnis der vorherigen Rechnung ersetzt. Hab ich das richtig verstaden? Und am Ende nähert es sich dann immer mehr der eigentlichen Nullstelle an.
Steffen Bühler Auf diesen Beitrag antworten »

In der Tat, die Vorschrift heißt

Und hier ist

Das ergibt somit

Du fängst also mit einem beliebigen an, berechnest daraus und so weiter. Je nach Startwert wird diese Folge dann mehr oder weniger schnell in eine der drei Lösungen konvergieren, falls sie überhaupt konvergiert.

Wenn der Startwert bereits in der Nähe einer Lösung liegt, ist alles in Ordnung. Das sieht man an meiner Grafik. Aber wehe, wenn in der Nähe der drei Grenzverläufe begonnen wird! Man könnte meinen, auf der "Grenzlinie" selbst konvergiert es nicht, außerhalb in die nächstgelegene Lösung. Beileibe nicht! Es existiert gar keine gerade Grenzlinie! Hier gilt "wenn zwei sich streiten, freut sich der dritte". Siehst Du, dass an der Grenze zwischen Grün und Blau plötzlich auch Startwerte existieren, die in die dritte Lösung Rot konvergieren? Das ist das Faszinierende an diesem Fraktal. Probier's mal aus.

Viele Grüße
Steffen
HAL 9000 Auf diesen Beitrag antworten »

Um zu ergänzen, was beim Newtonverfahren so alles passieren kann:

(a) Es gibt hinreichende (!) Kriterien an einen Startwert für die Konvergenz des da startenden Newton-Verfahrens gegen eine bestimmte Nullstelle, siehe z.B. hier.

(b) Für alle anderen Startwerte lässt sich meist zunächst wenig sagen: Möglicherweise bewegt sich die Folge nach mehr oder weniger vielen Schritten in einen Bereich, der durch (a) erfasst wird. Es kann aber auch passieren, dass die Folge periodisch zwischen mehreren Häufungspunkten (besser gesagt: deren Umgebungen) hin- und herwechselt, und und und...

Nicht bei allen Funktionen sind alle diese Szenarien möglich. Beim hier betrachteten etwa schätze ich mal, dass man mit Ausnahme einer Menge vom Maß 0 (dem eigentlichen Fraktal) sonst immer nach einer endlichen Anzahl Schritte in Szenario (a) landet - aber sicher bin ich mir da nicht, Steffen darf mich da gern korrigieren. Augenzwinkern
Steffen Bühler Auf diesen Beitrag antworten »

Wir haben uns ja neulich erst darüber unterhalten. smile

Es könnte vielleicht gezeigt werden, dass für ganzzahlige Exponenten (hier 3) grundsätzlich Szenario a zutrifft, während nichtganzzahlige Exponenten Bereiche ergeben, in denen die Folge oszilliert, also in einen Zyklus mündet. Den Beweis überlasse ich aber gerne anderen zur Übung. Augenzwinkern
HAL 9000 Auf diesen Beitrag antworten »

Tja, "neulich" ist relativ: Es war vor 18 Monaten, und ich habe es komplett verdrängt. smile
mYthos Auf diesen Beitrag antworten »

Das Newton-Verfahren ausgerechnet an diesem komplexen Beispiel zu demonstrieren, erklären und zu verstehen sollen, finde ich nicht gerade glücklich.
Da hätte der Lehrer zuerst eher eine Standard-Einführung geben sollen.

Abgesehen davon ist die Behandlung mit den Fällen und Fraktalen hier interessant (wie auch der andere diesbezügliche ältere Thread).

@Tarex
Du hast es richtig verstanden.
Allerdings kommt der Wahl des Startwertes eine große Bedeutung zu, damit das Verfahren konvergiert.
Es gibt genug Gründe (w.o. auch beschrieben), weshalb das Verfahren fehlschlagen kann.
Z.B. kann ein Wendepunkt in der Nähe der Nullstelle zum Störfaktor werden.

Günstig ist es, zuerst von der Funktion eine kleine Wertetabelle zu erstellen ("kleine" KurvDisskuss).
Dort, wo bei den Funktionswerten ein VZW (Vorzeichenwechsel) eintritt, ist eine Nullstelle zu erwarten. Den Startwert möglichst nahe der Nullstelle wählen (x-Wert des kleineren absoluten Funktionswertes)!

Wir haben das Thema in diesem Board auch schon oft behandelt, siehe dir das mal an!

Anwendung des Newton-Verfahrens

https://www.matheboard.de/thread.php?pos...257#post1184257

und viele weitere ...

mY+
Steffen Bühler Auf diesen Beitrag antworten »

Hochinteressant fand ich damals diesen Thread:
Startwert Newton Verfahren

Selbst bei einer einfachen kubischen Funktion im Reellen ist nicht für jeden Startwert vorhersagbar, ob dieser zur Konvergenz führt.
HAL 9000 Auf diesen Beitrag antworten »

Zumindest bei den kubischen Funktionen hier im Thread sowie dem von dir eben verlinkten Thread scheint es ja so zu sein, dass das Newtonverfahren für fast jeden Startwert konvergiert. Manchmal braucht es eine kleine "wilde" Fahrt endlicher Länge, aber es findet sich.

Ausnahmestellen sind auf jeden Fall die mit sowie jene Startwerte, die nach endlich vielen Newtonschritten auf ein solches führen - insgesamt sind das höchstens abzählbar viele. Bei allen anderen reellen Startwerten sieht es nach Konvergenz aus (beweisen kann ich das nicht). Das mag damit zusammenhängen, dass beides kubische Funktionen mit nur jeweils einer reellen Nullstelle sind. verwirrt
Tarex Auf diesen Beitrag antworten »

Erst einmal danke nochmals für die zahlreichen und besonders hilfreichen Antworten hier!

Ich hab das Newton-Verfahren nun verstanden. Jetzt hat die Aufgabe, die mir gestellt wurde, jedoch meiner Meinung nach impliziert, dass ich das Newton-Verfahren auf das Gleichungssystem mit den beiden Unbekannten x,y anwende. Ich habe jetzt noch nachgelesen und herausgefunden, dass es eine relativ einfache Formel dafür gibt. Zur Erklärung:
Vektor a = Vektor mit den Startwerten
J = Invertierte Jakobi-Matrix
Vektor f = Vektor mit den berechneten Funktionswerten zu den jeweiligen Startwerten
Die Formel wäre dann ja: a+J*f

Jedoch bräuchte ich hier nochmal eure Hilfe. Am Ende der Berechnung erhalte ich ja einen Vektor mit zwei Werten. Wenn ich es richtig verstanden habe, dann sind dies die entsprechend neuen Startwerte für die nächste Iteration, oder? Und nochmal zu den ersten Startwerten: Ich habe jetzt schon verschiedene ausprobiert, aber irgendwie geht x weder gegen 1 noch gegen 0,5 und y ebenfalls nicht gegen eine der vorher berechneten Lösungen. Entweder habe ich jetzt noch ein Fehler in meiner Rechnung oder meine Startwerte sind einfach schlecht gewählt. Noch eine letzte Frage: Woher weiß ich nach wie vielen Iterationsdurchläufen ich denn aufhören kann?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tarex
Am Ende der Berechnung erhalte ich ja einen Vektor mit zwei Werten. Wenn ich es richtig verstanden habe, dann sind dies die entsprechend neuen Startwerte für die nächste Iteration, oder?

Ja klar, so funktioniert das bei einer solchen Rekursion.

Zitat:
Original von Tarex
Ich habe jetzt schon verschiedene ausprobiert, aber irgendwie geht x weder gegen 1 noch gegen 0,5 und y ebenfalls nicht gegen eine der vorher berechneten Lösungen.

Da ist es jetzt sinnlos zu spekulieren - zuerst solltest du mal präsentieren, wie die Rekursion bei dir konkret aussieht. D.h., was hast du bei der Jacobi-Matrix, deren Inverser usw. alles herausbekommen? Meine Vermutung geht dahin, dass bereits da noch irgend ein Fehler lauert.

Anmerkung: Tatsächlich ist diese zweidimensionale Rechnung nicht wirklich nötig. Benutzt man das komplexe Newtonverfahren mit angewandt auf die holomorphe Funktion , so bekommt man letztendlich haargenau dieselbe Formel, und das ohne dass man sich mit Jacobi-Matrizen und deren Inversen herumplagen muss. Augenzwinkern


Zitat:
Original von Tarex
Woher weiß ich nach wie vielen Iterationsdurchläufen ich denn aufhören kann?

Ich nehme an, du hast die Diskussion hier nicht wirklich verfolgt, sie ist ja auch sehr in Richtung Fraktale abgedriftet. Zunächst mal dies: Es gibt hinreichende Kriterien, aus denen man i.d.R. Intervalle ableiten kann, wo darin liegende Startwerte zur Konvergenz des Verfahrens führen,
ich hatte oben einen passenden Wiki-Link dazu angegeben. Meistens beinhalten diese Kriterien dann auch eine Abschätzung für den Abstand der Iterierten von der Nullstelle. Je nachdem, wie genau du es haben willst, kannst du damit dann das Verfahren nach geeigneter Schrittzahl abbrechen. Das Newton-Verfahren an sich hat quadratische Konvergenz, d.h., ist man erstmal im "Einzugsbereich" der Nullstelle, dann geht es ganz schnell: Jede zusätzliche Iteration verdoppelt ungefähr die Stellenzahl der richtigen Ziffern.
Tarex Auf diesen Beitrag antworten »

Edit (mY+): Vollzitat entfernt. Sh. meinen Beitrag unten.

Also meine nicht invertierte Jakobi-Matrix hat die Form:
Die invertierte Jakobi-Matrix:

Und scheinbar hab ich deinen Artikel zu den Startwerten übersehen. Ich werde nochmal nachschauen!

Im Anhang habe ich nochmal ein Bild von dem Java-Programm hinzugefügt, welches ich mir für die Berechnung geschrieben habe (mir ist dabei durchaus bewusst, dass man mit diesem keine Preise für Schönheit oder ähnliches Gewinnen kann). Dabei sind x und y meine Startwerte. a1 und a2 die Funktionswerte dieser Startwerte und J die Matrix als Array (der Einfachheit halber). Mit faktor ist dabei der Faktor gemeint, mit welchem die invertierte Jakobi-Matrix berechnet wird (sprich das 1/9x...).
[attach]45304[/attach]
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tarex
Also meine nicht invertierte Jakobi-Matrix hat die Form:
Die invertierte Jakobi-Matrix:

Wie befürchtet, da geht es schon los mit den Fehlern: Wir haben



als vektorwertige Funktion, auf deren Nullstellensuche wir Newton anwenden wollen. Die zugehörige Jacobi-Matrix ist abweichend von deiner Darstellung nämlich



mit Determinante und inverser Matrix

.
Tarex Auf diesen Beitrag antworten »

Edit (mY+): Vollzitat entfernt. Sh. meinen Beitrag unten.

Vielen Dank! Scheinbar hab ich dabei grundlegend was nicht verstanden. Ich werde das gleich mal ändern.
mYthos Auf diesen Beitrag antworten »
Bitte keine Vollzitate (Voll-Quotas)
Bitte drücke zum Antworten NICHT den Zitat-Button, sondern jenen zum Antwort erstellen!
Die Vollzitate werde ich zur besseren Übersicht entfernen.

mY+
Tarex Auf diesen Beitrag antworten »

Edit (mY+): Vollzitat entfernt. Sh. meinen Beitrag w.o.

Hab jetzt alles entsprechend der Jakobi-Matrix in meinem Programm angepasst. Als Startwerte habe ich jetzt einfach mal 1 und -1 genommen und bekomme dann folgende Wert raus:
[attach]45305[/attach]

Aber irgendwie kann das ja nicht stimmen. Leider finde ich meinen Fehler auch gerade mal wieder nicht...
HAL 9000 Auf diesen Beitrag antworten »

Die Newtoniteration lautet nicht , sondern

,

also MINUS !!!


P.S.: Effizienz mag hier keine Rolle spielen, aber i.d.R. ist die Implementation von x*x schneller als Math.pow(x,2), zumindest in kompilierten C++.
Tarex Auf diesen Beitrag antworten »

Hammer Bei dem ganzen Zeug hier, habe ich echt ein Brett vorm Kopp. Das war wieder sowas einfaches, dass ich übersehen habe. An dieser Stelle muss ich mich nochmals für meine Dummheit entschuldigen. Und großes Dankeschön nochmal an Alle!

P.S.: Jetzt kommen auch wenigstens sinnvolle Werte raus...
HAL 9000 Auf diesen Beitrag antworten »

Einfacher wäre gewesen, gleich komplex zu rechnen: mit ergibt mit dann

.

Setzt man da ein, bekommt man und das bedeutet getrennt nach Real- und Imaginärteil

.

Auch wenn es vielleicht auf den ersten Blick nicht so aussieht: Es ist dieselbe Rekursion wie oben. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »