Iterative Lösung einer nichtlinearen Gleichung

8

Ich entschuldige mich im Voraus, wenn diese Frage dumm ist. Ich muss die Wurzel von berechnen

u - f (u) = 0

$\begin{equation} u -f(u) =0 \end{equation}$

Wobei ein reeller Vektor ist und eine reelle Vektorwertfunktion ist. Ich begann mit Newtons Methode (die funktionierte), erkannte dann aber, dass eine viel einfachere Methode eine iterative Lösung wäre $u$ $f(u)$

u_{i + 1} = f (u_{i})

$\begin{equation} u_{i+1} = f(u_{i}) \end{equation}$

Dies ist viel schneller und anscheinend so genau / stabil wie Newtons Methode.

Nun die Fragen:

Ist dies der richtige Ansatz oder sollte ich eine andere Methode verwenden?
Kann man etwas über Konvergenzrate, Stabilität, Acc usw. sagen?
Ist es global konvergent?

Vielen Dank im Voraus für die Aufmerksamkeit.

iterative-method nonlinear-equations roots Gabriel Landi
quelle

3

Dies wird als Festpunktiteration bezeichnet. Ich bin mit dem Thema nicht vertraut, aber es sollte Ihnen zumindest einige neue Wörter geben, die Sie bei Google verwenden können. Wenn ich mich richtig erinnere, erscheinen Fixpunkte für eine Vielzahl von Funktionen mit einer Vielzahl von Startpunkten.

Godric Seer

1

f (u)

$f(u)$

4

f (\cdot)

$f(\cdot)$

f (u) = u - (\nabla g)^{- 1} g (u)

$f(u) = u - (\nabla g)^{-1} g(u)$

u_{i + 1} = f (u_{i})

$u_{i+1} = f(u_i)$

g (u) = 0

$g(u) = 0$

7

$q:=|f'(x^*)|<1$ $x^*$ $q$ $q$

$<1$

Arnold Neumaier
quelle

5

Das Feigenbaum-Fraktal ist ein gutes Beispiel dafür, wie seltsam die Fixpunktiteration sein kann:

http://en.wikipedia.org/wiki/Feigenbaum_fractal

http://en.wikipedia.org/wiki/File:Logistic_Bifurcation_map_High_Resolution.png

Der zweite Link zeigt das Verhalten der Fixpunktiteration, die auf die logistische Karte angewendet wird, wenn einer der Parameter variiert. Für bestimmte Werte konvergiert es, wenn auch nur linear. Für andere Werte konvergiert es zu einem Zyklus unterschiedlicher Länge. Für eine weitere Werteklasse verhält es sich völlig chaotisch.

Mit anderen Worten, das Verhalten der Fixpunktiteration hängt vollständig von der betreffenden Funktion ab. Sogar Funktionen, die ähnlich aussehen, können ein radial unterschiedliches Verhalten aufweisen.

Hinweis : Wie Jed betont, kann die Newton-Iteration ebenso seltsam sein .

Geoffrey Irving
quelle

Um fair zu sein, viele beliebte Fraktale sind die Julia-Mengen der Newton-Iteration nach einer einfachen Gleichung.

Jed Brown

4

Das Banach-Festkomma-Theorem beschreibt die Standardsituation, in der eine Festkomma-Iteration global konvergent ist. Insbesondere der Eindeutigkeitsteil des Theorems zeigt, dass Sie nur dann lokale Konvergenz erwarten können, wenn die Lösung nicht eindeutig ist.

$f^n=f\circ \ldots\circ f$ $f$

Thomas Klimpel
quelle

2

Sie können diese Referenz als nützlich erachten: Eine Homotopie zum Lösen großer, spärlicher und strukturierter Fixpunktprobleme. R. Saigal. Mathematics of Operations Research. 8, Nr. 4 (November 1983), S. 557-578.

Hirschjäger
quelle

1

Diese Methode ist korrekt und wird als "sukzessive Substitution" bezeichnet. Weitere Informationen finden Sie auf Seite 189 dieser Referenz .

Papiro
quelle

Iterative Lösung einer nichtlinearen Gleichung

Antworten: