Abbruchkriterien

Jeder iterative Prozeß liefert für einen Startwert im mathematischen Sinn eine unendliche Folge. Für die praktische Lösung nichtlinearer Gleichungssysteme sind jedoch nur Algorithmen von Bedeutung, die für jeden Startwert nach endlich vielen Schritten ein Resultat liefern.

Kriterien zum Abbruch eines iterativen Nullstellenverfahrens sind:

1. Das numerische Problem wurde gelöst, indem ein Näherungswert, der in der vorgegebene Toleranz liegt, gefunden wurde.

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

algebraische Gleichungen

Algebraische Gleichungen haben folgende Stuktur:

d bezeichnet den Grad des Polynoms

Zum Lösen solcher Gleichungen siehe Fundamentalsatz der Algebra

Äquivalenz

Gleichwertigkeit.

Verallgemeinerung des Anzahlbegriffs auf Mengen mit unendlich vielen Elementen (unendliche Mengen). Zwei Mengen A und B werden als gleichmächtig (äquivalent) oder von gleicher Mächtigkeit bezeichnet, wenn es eine umkehrbar eindeutige Zuordnung zwischen den Elementen von A und B gibt.

Äquivalenz von Gleichungssystemen:

Ist jede Nullstelle eines Gleichungssystemes in der Standardform (F(x)=0, auch Nullstellenform genannt), auch ein Fixpunkt in der Fixpunktform (T(x)=x) und umgekehrt, dann werden beide Systeme als äquivalent bezeichnet.

Differenzierbarkeit

Eignung einer Funktion zur Differentiation, es existiert eine Ableitung. Funktion: Veränderliche Größe, die in ihrem Wert von einer anderen abhängig ist.

Differentiation

Anwendung der Differentialrechnung.

Die Ableitbarkeit einer reelwertigen, stetigen Funktion liegt vor, wenn der Grenzwert existiert.

Dreischrittverfahren

Bei einem Dreischrittverfahren beim Lösen von nichtlinearen Gleichungen hat die Form:

Das Müller-Verfahren ist ein Dreischrittverfahren, wobei die Konvergenzordnung bei p = 1.839 liegt. Das Müller-Verfahren konvergiert damit überlinear und schneller als das Sekanten-Verfahren, welches nur ein Zweischrittverfahren ist.

Einschrittverfahren

Unter einem Einschrittverfahren versteht man ein Iterationsverfahren, bei dem der nächste Näherungswert ausschließlich vom vorhergegangenen Wert abhängig ist, wie z. B. bei der Fixpunkt-Iteration. Im Gegensatz zum Einschrittverfahren stehen das Zweischrittverfahren und das Dreischrittverfahren.

Einzugsbereich

Der Einzugsbereich E ist die Menge aller Startwerte, welche bei Anwendung eines Iterationsverfahrens, nach unendlich vielen Iterationsschritten einen gegen die Lösung konvergierenden Wert liefern. E ist eine Teilmenge vom Definitionsbereich D. Ist der gesamte Definitionsbereich Einzugsbereich einer Iteration, so spricht man von globaler Konvergenz. Umfaßt der Einzugsbereich hingegen nur eine Umgebung der Lösung, so spricht man von lokaler Konvergenz.

Fehlerabschätzung

Man unterscheidet zwischen einer A-priori-Fehlerabschätzung, mit welcher man bereits nach dem ersten Schritt der Iteration feststellen kann, wie viele Schritte maximal erforderlich sind, um eine absolute Genauigkeitsanforderung garantieren zu können, und einer A-posteriori-Fehlerabschätzung, die es gestattet, nach der Durchführung von k Schritten der Iteration den absoluten Fehler abzuschätzen.

Fundamentalsatz der Algebra

Eine algebraische Gleichung besitzt genau d Lösungen, wobei Lösungen (Nullstellen) mit ihrer Vielfachheit gezählt werden. Sind die Koeffizienten a₀,a₁,...,a_d reel, so ist mit jeder Lösung x auch deren konjugiert komplexe Zahl /x eine Lösung und zwar mit derselben Vielfachheit.

Fixpunkt

Definition:

heisst Fixpunkt der Gleichung wenn gilt:

(siehe auch Iterationsverfahren).

Fixpunktgestalt:

Um zu einem Iterationsverfahren für Gleichungssysteme zu gelangen, muß man jeweils die i-te Gleichung nach der i-ten Unbekannten auflösen.

Iterationsabbruch

Der Iterationsprozess würde theoretisch unendlich lange bestehen (da im mathematischen Sinn eine unendliche Reihe entseht). Da für die praktische Lösung nichtlinearer Gleichungen jedoch nur Algorithmen von bedeutung sind, die nach endlich vielen Schritten ein Ergebnis liefern, muß die Iteration nach einem bestimmten Zeitpunkt abgebrochen werden (Iterationsabbruch). Es ist zu beachten, daß die Iteration weder zu früh ( d. h. weiter von der gesuchten Lösung entfernt als gefordert) noch zu spät (d. h. nach dem Erreichen unnötig hoher Genauigkeit mit unnötigem Rechenaufwand) abgebrochen werden darf (siehe auch Abbruchkriterien).

Iterationsschritte

Es gibt prinzipiell Einschritt und Mehrschrittverfahren.

Man spricht von einem Einschrittverfahren wenn gilt:

Da hier der nächste Näherungswert nur von einem vorangegeangen Wert abhängt.

Man spricht von einem Mehrschrittverfahren wenn gilt:

Da hier der nächste Näherungswert nur von mehereren vorangegangenen Werten abhängt (in diesem Fall spricht man auch von einem (s+1)-Schritt- Verfahren).

Siehe auch Sekanten (2-Schritt) oder Müller (3-Schritt) Verfahren.

Iterationsprozess

Wird durch die Fixpunkt-Iteration definiert, wenn es eine nichtleere Menge bezüglich Rⁿ gibt, sodaß für alle x⁽⁰⁾ die unendliche Folge {x^(k)} ermittelt werden kann, was bedeutet, daß alle Punkte x⁽¹⁾, x⁽²⁾, x⁽³⁾,.... im Definitionsbereich der Funktion T liegen.

Jacobi- Matrix:

.

Beschreibt eine Funktion z.B. eine Fläche im 3D Raum, so kann man sich die Bedeutung der einzelnen Komponenten des Gradienten als Informationen über die Steigung in x-, y- und z- Richtung vostellen.

Liegt ein n x m Gleichungssystem vor (n Gleichungen mit m Unbekannten), so kann man eine Matrix erstellen, deren Zeilen aus n Gradienten bestehen.

Die Jacobimatrix hat die gleiche Bedeutung wie der Gradient, nur für Gleichungssysteme. Beschreiben drei Gleichungssysteme drei Flächen im 3D Raum, so kann man beispielsweise am Element in der zweiten Zeile und in der dritten Spalte die Steigung der zweiten Fläche in z- Richtung ablesen.

Jenkins-Traub-Verfahren

Ist ein dreistufiger Polyalgorithmus, mit dessen Hilfe die Nullstellen von Polynomen ermittelt werden können.

Konditionszahl

Dient dazu um Aussagen ueber die Stoerung von Berechnungen (z.B.: Datenungenauigkeiten, Auswertefehler, .....) zu machen. (:Thema Kondition von Nullstellen)

Kontraktionseffekt

Auftreten der Kontraktivitaet. (siehe Kontraktivitaet)

Kontraktivitaet

Ein Funktion

heisst kontrahierend auf

falls T dort eine Lipschitz-Bedingung

mit einer Lipschitz-Konstante (Kontraktionskonstante) 0 <= L <= 1 erfuellt.

Konvergenz

Eine unendliche Reihe a₁+a₂+a₃+.... heisst genau dann konvergent, wenn ihre Partialsummenfolge konvergiert.

Konvergenz, lokale/globale

Ist der gesamte Definitionsbereich einer Funktion Einzugsbereich einer Iteration, so spricht man von globaler Konvergenz. Umfaßt der Einzugsbereich hingegen nur eine Umgebung der Lösung, so spricht man von lokaler Konvergenz.

Konvergenzbeschleunigung

Langsam konvergente Folgen, deren Grenzwerte gesucht sind, erfordern oft einen hohen Berechnungsaufwand. Um diesen Aufwand zu senken, also die Effezienz des Verfahrens zu erhoehen gibt es Methoden zur Konvergenzbeschleunigung. (z.B.: Extrapolation, ...)

Konvergenzfaktor

Eine konvergente Folge

mit dem Grenzwert x^* hat die Konvergenzordnung p und den Kovergenzfaktor a, wenn folgendes gilt:

Im allgemeinen konvergiert eine Folge mit einer hoeheren Konvergenzordnung rascher als eine Folge niedrigerer Ordung. Zwei Spezialfaeller sind von besonderer Wichtigkeit:

p=1 lineare Konvergenz

p=2 quadratische Konvergenz

Konvergenzordnung

Eine konvergente Folge

mit dem Grenzwert x^* hat die Konvergenzordnung p und den Kovergenzfaktor a, wenn folgendes gilt:

Im allgemeinen konvergiert eine Folge mit einer hoeheren Konvergenzordung rascher als eine Folge niedrigerer Ordung. Zwei Spezialfaeller sind von besonderer Wichtigkeit:

p=1 lineare Konvergenz

p=2 quadratische Konvergenz

Koordinatenfunktion:

Laguerre-Verfahren

Spezialisiertes Iterationsverfahren zur Lösung von algebraischen Gleichungen.

Lipschitz-Konstante

Wesentliche Voraussetzung für die Anwendbarkeit des Kontraktionssatzes ist die Kenntnis einer möglichst guten, d.h. möglichst "kleinen" Lipschitz-Konstante für die Funktion. Die Gewinnung von konkreten (optimal kleinen) Lipschitz-Konstanten ist gelegentlich mit Hilfe von Computer-Algebrasystemen möglich.

Monte-Carlo-Suche

Suchverfahren nach Nullstellen. Bei einem System von n nichtlinearen Gleichungen werden mit Hilfe von gleichverteilten Zufallszahlen Punkte gesucht, die ein möglichst kleines Residuum besitzen. Diese können direkt als sehr grobe Näherung für die Lösung des Gleichungssystems verwendet werden, oder als Startwerte für Iterationsverfahren, die hinreichend nahe an der Lösung liegende Startwerte benötigen, dienen.

Nullstelle, Vielfachheit einer

Eine Nullstelle einer Funktion wird durch Angabe ihrer Vielfachheit genauer beschrieben. Läßt sich eine Funktion wie folgt faktorisieren,

wobei g(x) um x^* stetig ist, so bezeichnet man m als die Vielfachheit der Nullstelle x^*. Man beachte, daß m nicht ganzzahlig sein muß. Bei algebraischen Gleichungen ist die Vielfachheit von Nullstellen für den Fundamentalsatz der Algebra wichtig: Eine algebraische Gleichung der Ordnung n besitzt genau n Lösungen, wobei die Lösungen (Nullstellen) mit ihrer Vielfachheit gezählt werden.

Overhead

Ein Anteil des Rechenaufwandes bei einer Iteration. Setzt sich zusammen aus der Berechnung des nächsten Iterationswertes, der Überprüfung der Abbruchbedingung, etc. Der Overhead ist in den meisten Fällen für einen Vergleich von Iterationsmethoden (siehe Effizienzvergleich) nicht relevant, da es sich entweder um eine vernachlässigbare Anzahl arithmetischer Operationen (zur Berechnung des nächsten Folgengliedes) oder um einen Rechenaufwand handelt, der bei jedem Verfahren in ungefähr gleicher Größe pro Schritt erforderlich ist (Abbruchkriterien etc.).

Kontraktionssatz

Bei nichtlinearen inversen Problemen ist der Kontraktionssatz eines der wichtigsten Hilfsmittel einerseits zum Nachweis von Existenz und Eindeutigkeit der Lösung, andererseits zur Gewinnung von Iterationsverfahren zur näherungsweisen Bestimmung derselben.

Polynomgrad

Ein Polynomgrad bezeichnet die höchste vorkommende Hochzahl bezüglich x in einer algebraischen Gleichung

z.B.

d = Polynomgrad des Polynoms Pd

Der Polynomgrad ist ein wichtiger Bestandteil zum Lösen von algebraischen Gleichungen.

Siehe auch Polynom-Nullstellen

Residuum

Residuum bedeutet in der Mathematik 'Rest'.

siehe auch Residuums-Kriterium.

Sekante

Eine Gerade, die eine krumme Linie schneidet, bezeichnet man als Sekante

Skalar

Ein Skalar ist der Gegensatz zum Vektor. Er bezeichnet eine Größe ohne Richtungsangabe, das heißt eine skalare Zahl kann durch nur eine Zahl dargestellt werden.

Terminologie

Terminus=Fachausdruck

Man schreibt 'Terminolgie', wenn man einen Sachverhalt oder einen Fachausdruck näher erklären bzw. beschreiben will.

Wilkinson-Polynom

Das Wilkinsonpolynom ist ein berühmtes Beispiel des Mathematikers Wilkinson Das Polynom

hat die voneinander separierten Nullstellen 1,2,3..20. Berechnet man die ganzzahligen Polynomkoeffizienten in einer INTEGER-Arithmetik und rundet die so erhaltenen Werte auf einfache IEC/IEEE-Gleitpunktzahlen, hat das durch die Rundungsfehler gestörte Polynom 16 konjugiert komplexe Nullstellen, deren Imaginärteile deutlich von Null verschieden sind. Es muß daher eine Arithmetik mit höherer Genauigkeit verwendet werden, um eine deutliche Verbesserung zu erreichen.

Zweischrittverfahren

Ein Zweischrittverfahren beim Lösen von nichtlinearen Gleichungen hat im Gegensatz zum Einschrittverfahren die Form

Es erfordert daher spezielle Methoden der Konvergenzuntersuchung. Ein typisches Zweischrittverfahren ist das Sekanten-Verfahren.