Riemer
[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Abbruch einer Iteration

Jeder iterative Prozeß liefert für einen Startwert

$x^{(0)}\in D^{*}$

im mathematischen Sinn eine unendliche Folge {x(k)}. Für die praktische Lösung nichtlinearer Gleichungssysteme sind jedoch nur Algorithmen von Bedeutung, die für jeden Startwert x(0) nach endlich vielen Schritten ein Resultat liefern.

Sowohl für den Entwickler als auch für den Benutzer von Software zur Lösung nichtlinearer Gleichungen ist die Wahl geeigneter Abbruchkriterien bzw. Ihrer Parameter

$\left( \tau _{abs},\tau _{rel},\tau _f,etc\right)$

eine wichtige und schwierige Aufgabe. Es müssen dabei Korrektheit und Effizienz gegeneinander abgewogen werden.

* Die Iteration darf nicht zu früh (d.h. weiter von der gesuchten Lösung entfernt als gefordert) beendet werden.

* Die Iteration soll nicht zu spät (d.h. nach dem Erreichen unnötig hoher Genauigkeit mit unnötig hohem Rechenaufwand) abgebrochen werden.

Ein zuverlässiges Programm sollte bei einer konvergenten Folge {x(k)} erkennen, ob der zuletzt berechnete Näherungswert x(k) bereits sie gewünschte Genauigkeit besitzt. Grundlage dieser Entscheidung ist ein Konvergenztest. Für schlechte Startwerte oder für Probleme, die überhaupt keine Lösung besitzen, müssen Mechanismen vorgesehen werden, die nicht konvergente Situationen erkennen und die Iteration mit der entsprechenden Information an den Anwender terminieren. Test zum Erkennen von Nicht-Konvergenz sind genauso wichtig wie Konvergenztests.


Abbruchkriterien

Die Kriterien zum Abbruch eines iterativen Nullstellenverfahrens sind:

1) Das numerische Problem wurde gelöst, indem ein Näherungswert

$\overset{\sim }{x}$ f\

ermittelt wurde, der die vorgegebene Toleranz, also z.B. eine der folgenden Ungleichungen erfüllt:

\EQN{7}{1}{}{}{\RD{\CELL{\left\| \overset{\sim }{x}-x^{\ast }\right\| \leq \tau_{abs},}}{1}{}{}{}\RD{\CELL{\left\| \overset{\sim }{x}-x^{\ast }\right\| \leq\tau _{rel}\cdot \left\| x^{\ast }\right\| }}{1}{}{}{}}

oder

$\left\| F(\overset{\sim }{x})\right\| \leq \tau _f.$

2) Das numerische Problem kann nicht gelöst werden, weil z.B. überhaupt keine Nullstelle von F existiert.


Fehler-Kriterien

In den meisten Softwareprodukten werden Schätzwerte für die Norm des Fehlers

$\left\| e\right\| =\left\| \overset{\sim }{x}-x^{*}\right\| $

als Abbruchkriterium herangezogen. Sobald z.B. eine der Ungleichungen

\EQN{7}{1}{}{}{\RD{\CELL{\left\| x^{(k+1)}-x^{(k)}\right\| &\leq &\tau_{abs},}}{1}{}{}{}\RD{\CELL{\left\| x(^{k+1)}-x^{(k)}\right\| \leq \tau_{rel}\cdot \left\| x^{(k+1)}\right\| }}{1}{}{}{}}

oder eine Mischform (zur Vermeidung von Schwierigkeiten bei

$x^{(k+1)}\approx 0$

), z.B.

$\left\| x^{(k+1)}-x^{(k)}\right\| \leq \tau _{abs}+\tau _{rel}\cdot \left\|x^{(k+1)}\right\| $

erfüllt, wird die Iteration beendet. Falls die Folge {x(k)} rasch gegen x* konvergiert, d.h. falls

$\left\| x^{(k+1)}-x_{}^{*}\right\| \ll \left\| x^{(k)}-x^{*}\right\| $

gilt, so ist

$\left\| x^{(k+1)}-x^{(k)}\right\| \approx \left\| x^{(k)}-x^{*}\right\| ,$

und aus

$\left\| x^{(k+1)}-x^{(k)}\right\| \leq \tau _{abs}$

folgt

$\left\| x^{(k+1)}-x^{*}\right\| \ll \tau _{abs}$

Konvergiert die Folge {x(k)} jedoch sehr langsam gegen x*, wenn also

$\left\| x^{(k+1)}-x^{*}\right\| \approx \left\| x^{(k)}-x^{*}\right\| $

gilt, so kann

$\left\| x^{(k+1)}-x^{(k)}\right\| $

sehr klein sein, obwohl die geforderte Genauigkeit noch bei weitem nicht erreicht ist. In diesem Fall führen die obigen Abbruchkriterien zu einem verfrühtem Terminieren.


Residuums-Kriterium

Das Residuum

$F(\overset{\sim }{x})$

liefert im Vergleich zum Fehler ein weniger kritisches Abbruchkriterium: es wird allenfalls durch Auslöschungseffekte beeinträchtigt, da

$F(\overset{\sim }{x})\approx 0$

nahe der Lösung x* gilt. Bei Funktionen mit großer Ableitung

$\left( \left\| F^{\prime }(x^{*})\right\| \gg 1\right) $

kann das Residuum sehr groß sein

$\left( \left\| F(\overset{\sim }{x})\right\| \gg \tau _f\right) $

obwohl der Fehler

$\left\| \overset{\sim }{x}-x^{*}\right\| $

bereits sehr klein ist. Es empfiehlt sich daher, nicht ausschließlich die Residuenbedingung

$\left\| F(x^{(k)})\leq \tau _f\right\| $

als Abbruchkriterium zu verwenden. Die meisten Bibliotheksprogramme beurteilen die Konvergenz nach beiden Kriterien.


Kriterien für Nicht-Konvergenz

Die Diagnose einer Divergenz der Folge {x(k)} erfolgt meist durch eines der Kriterien

$\left\| x(k)\right\| \geq x_{\max }$ $oder$ $\left\| F(x^{(k)})\right\| \geqf_{\max }$

oder nach mehrmaligem Anwachsen des Residuums, z.B.

$\left\| F(x^{(k)})\right\| >\left\| F(x^{(k-1)})\right\| >\left\|F(x^{(k-2)})\right\| .$

Sofern das Problem f(x)=0 überhaupt eine Lösung mit nichttrivialem (nichtentartetem) Einzugsbereich besitzt, deutet das 2.Kriterium auf die Wahl eines ungünstigen Startwertes x(0) hin. In diesen Fällen empfiehlt sich die Wiederholung der iterativen Nullstellenbestimmung mit einem (z.B. durch Zufallssuche ermittelten) neuen Startwert.

Außer den beiden angeführten Kriterien kann sich Nicht - Konvergenz auch durch systematisches, vor allem aber durch unsystematisches Oszillieren der Folge {x(k)} bemerkbar machen. Das Diagnostizieren eines derartigen Verhaltens wäre für ein Bibliotheksprogramm (bei dem auch die Effizienz ein wichtiges Qualitätsmerkmal ist) viel zu aufwendig. Iterationsfolgen {x(k)} mit unspezifischer Nichtkonvergenz bzw. Zu langsamer Konvergenz werden daher immer durch eine Aufwandsbeschränkung

k<kmax,

d.h. durch Vorgabe einer Maximalzahl der Iterationsschritte, terminiert.

Dieses Kriterium kann auch bei zu klein gewählten Toleranzparametern

$\tau _{abs},\tau _{rel},\tau _f$

zum Abbruch der Iteration führen. Die Situation

$\left\| x^{(k+1)}-x^{(k)}\right\| \approx eps\cdot \left\| x^{(k)}\right\| $

wird in manchen Programmen separat abgefragt und führt zur Terminierung mit einer entsprechenden Meldung. Wenn jedoch die Werte von F mit Ungenauigkeiten behaftet sind, die über dem Niveau elementarer Rundungsfehler liegen (noisy functions), und die Toleranzparameter eine Lösungsgenauigkeit vorschreiben, die aus diesem Grund nicht erreicht werden kann, so ist oft die Aufwandsbeschränkung jene Bedingung, die zum Abbruch führt.

Ein Grund für den Abbruch einer Iteration kann auch die Nichtausführbarkeit von Teilalgorithmen bestimmter Nullstellenverfahren sein. Wenn z.B. eines der linearen Gleichungssysteme, die beim Newton-Verfahren in jedem Schritt zu lösen sind, (numerisch) singulär ist, führt dies bei manchen Programmen zum Abbruch des gesamten Nullstellenverfahrens.

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]