Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Quadratische Konvergenz des Newton-Raphson-Verfahrens
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Quadratische Konvergenz des Newton-Raphson-Verfahrens
Steinsalat
Neu Letzter Besuch: im letzten Monat
Dabei seit: 27.06.2020
Mitteilungen: 2
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-27


Hallo,

ich würde mich freuen wenn mir jemand bei der folgenden Unklarheit weiterhelfen kann.
Bei der Anwendung des multivariaten Newton-Rapson Verfahrens habe ich eine Nullstelle $x^*$ von einem polynominalen Gleichungssystem $F(x^*)=0$ bestimmt. Ich möchte jetzt den Radius $r$ der Kugel bestimmen, für die das Verfahren quadratisch gegen $x^*$konvergiert.

Ist das mit dem Satz von Kantorowitsch möglich? Die Definition des Satzes lautet (Quelle: Buch Grundwissen Mathematikstudium. Höhere Analysis, Numerik und Stochastik, S.638)

Sei $D \subset R^{m}$ offen, $D_0$ mit $D_0 \subset D$ konvex und $f : D → R^m$ stetig differenzierbar. Für $x_0 ∈ D_0$ mögen positive Konstanten r, α, β, γ , h mit den folgenden Eigenschaften existieren.

-> $U_r(x_0) \subset D_0$
-> $h:=\frac{αβγ}{2}<1$
-> $r:=\frac{α}{1-h}<1$

Für F gilt:

-> $|| F'(x) - F'(y) || \leq γ|| x - y || $ für alle $x,y ∈ D_0$, also ist F' Lipschitz-stetig mit Lipschitz-Konstante γ.
-> $|| F'(x)^{-1}|| \leq β$ und existiert.
-> $|| F'(x^0)^{-1}F(x^0)|| \leq α$

DANN ENDLICH:

=> Für alle $n>0$ gilt: $||x^n - x^*|| \leq α \frac{h^{2n-1}}{1-h^{2n}}$ und damit konvergiert das Verfahren mindestens quadratisch.

Neben der Frage ob der Satz von Kantorowitsch dafür überhaupt geeignet ist oder ich ihn missverstehe scheitere ich an der Bestimmung der Lipschitz-Konstante γ, um daraus den Radius $r$ zu bestimmen. In einem anderen Buch habe ich ein Beispiel gefunden:

$F= \begin{bmatrix}
  x_1^2 + x_2^2 - 9\\
   -x_1 + x_2^2 - 3 \\
\end{bmatrix} $ mit der zugehörigen Jacobimatrix $J = \begin{bmatrix}
   2 x_1 & 2 x_2\\
   -1 & 2 x_2\\
\end{bmatrix}$ sowie eine der Lösungen $x^*=(2,\sqrt(5))$. Die Lipschitz-konstante soll laut Musterlösung γ=4 betragen. Mir ist nicht klar wie man zu dieser Lösung gelangt (oder im Allgemeinen die Lipschitz-Konstante für polynominale Gleichungssysteme bestimmt).

Vielen Dank an jeden, der sich die Zeit nimmt mir zu helfen :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46191
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-06-29


Hi Steinsalat,
deine Jacobimatrix ist völlig falsch.
Den Satz von Kantorowitsch kann man zur Konvergenzuntersuchung verwenden.
Gruß Buri



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Steinsalat
Neu Letzter Besuch: im letzten Monat
Dabei seit: 27.06.2020
Mitteilungen: 2
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-01


Hallo Buri,

vielen Dank für deine Antwort. Du hast recht, allerdings war mein Gleichungssystem falsch. Ich habe im Latex-Modus jeweils das + vergessen. Danke für den Hinweis, ist korrigiert.

Kannst du mir sagen, wie man die Konvergenz beweist bzw. den Satz anwendet?
Konkret hapert es bei mir an der Bestimmung von $\gamma$ und ich verstehe den Unterschied zwischen $x$ und $x_0$ nicht, denn letztendlich sind ja beide aus gleichen konvexen Teilmenge $D$, oder nicht?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Steinsalat hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]