Anziehungspunkt für Newtons Methode

9

Es ist bekannt, dass Newtons Methode zur Lösung nichtlinearer Gleichungen quadratisch konvergiert, wenn die Startschätzung "ausreichend nahe" an der Lösung liegt.

Was ist "ausreichend nah"?

Gibt es Literatur über die Struktur dieses Anziehungsbeckens?

iterative-method convergence nonlinear-equations David Ketcheson
quelle

Die Wurzel sollte isoliert sein (nicht mehrfach). Wenn der Hessische in der Region einheitlich bestimmt ist (konkav nach oben oder unten), sollten Sie bereit sein, loszulegen. Natürlich ist es normalerweise unpraktisch, diese Bedingungen empirisch zu garantieren oder zu testen.

Hardmath

Ich habe die Frage neulich in NA-Digest gesehen und fand sie faszinierend. Anscheinend war ich nicht der einzige :-)

Wolfgang Bangerth

8

Für eine einzelne rationale Gleichung im komplexen Bereich ist das Anziehungsbecken fraktal, das Element einer sogenannten Julia-Menge. http://en.wikipedia.org/wiki/Julia_set . Eine Theorie mit einigen netten Online-Zahlen finden Sie beispielsweise unter
http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf
http://hera.ugr.es/doi/15019160.pdf

$x^3-1=0$

Es macht daher wenig Sinn, im Detail anzugeben, was der Lösung "ausreichend nahe" liegt. Wenn man die Grenzen der zweiten Ableitungen kennt, gibt es den Newton-Kantorovich-Satz, der dem Radius einer Kugel, in der die Newtonsche Methode konvergiert, untere Grenzen gibt, aber mit Ausnahme von 1D sind diese eher pessimistisch.

Rechnerisch nützliche Grenzen können unter Verwendung von Intervallarithmetik erhalten werden; siehe z. B. meine Arbeit
Shen Zuhe und A. Neumaier, The Krawczyk Operator und Kantorovichs Theorem, J. Math. Anal. Appl. 149 (1990), 437 & ndash; 443.
http://www.mat.univie.ac.at/~neum/scan/61.pdf

Arnold Neumaier
quelle

x^{3} - 1 = 0

$x^3 - 1 = 0$

x > 0

$x > 0$

x > 1

$x > 1$

1

@hardmath: ja, aber die komplexe Gleichung wird zu zwei reellen Gleichungen in 2 Variablen, für die das Gleiche gilt.

Arnold Neumaier

4

"Ausreichend nah" ist schwer zu charakterisieren, wenn man bedenkt, dass daraus eine Klasse von Fraktalen entsteht . Newton-Methoden mit Globalisierungsstrategien wie Liniensuche und Vertrauensregion erweitern das Anziehungsbecken. Wenn eine zusätzliche Problemstruktur verfügbar ist, beispielsweise bei der Optimierung, können die für die Konvergenz erforderlichen Annahmen weiter geschwächt werden.

Jed Brown
quelle

Haben Sie aus Neugier ein Beispiel für "Wenn zusätzliche Problemstrukturen verfügbar sind, z. B. bei der Optimierung, können die für die Konvergenz erforderlichen Annahmen weiter geschwächt werden."?

vanCompute

@vanCompute In diesem Beispiel finden Sie ein Beispiel für die Optimierung, bei dem die Objektfunktion Informationen bereitstellt, die bei den Optimalitätsbedingungen erster Ordnung verloren gehen. Eine andere Form wäre das Wissen, dass eine bestimmte Fortsetzung (Pseudotransient, Parameter, Gitter usw.) immer konvergiert, aber der Rest muss möglicherweise vor Erreichen der Lösung erhöht werden, wenn man versucht, das Problem direkt zu lösen.

Jed Brown

3

Es gibt einige nützliche Ergebnisse für die Newtonsche Methode, die auf komplexe Polynome angewendet wird.

$f$

r = \frac{η}{2 d}

$r=\frac{\eta}{2d}$

η

$\eta$

f

$f$

d

$d$

f

$f$

Weitere explizite Grenzen gibt Anthony Manning in Wie man sicher sein kann, eine Wurzel eines komplexen Polynoms mit der Newtonschen Methode zu finden (Satz 1.2).

Siehe auch Wie man alle Wurzeln komplexer Polynome nach Newtons Methode von Hubbard et al.
Erfinden. Mathematik. 146 (2001), No. 1, 1–33. pdf

lhf
quelle

Angepasst von math.stackexchange.com/a/1038487/589 .

lhf

Anziehungspunkt für Newtons Methode

Antworten: