Fixpunktiteration
aus Wikipedia, der freien Enzyklopädie
Die Fixpunktiteration ist ein in der Mathematik gebräuchliches iteratives Verfahren zur näherungsweisen Bestimmung der Nullstellen einer Funktion f auf einem bestimmten Intervall [a,b].
Inhaltsverzeichnis |
[Bearbeiten] Allgemein
Jedes Fixpunktverfahren hat die Form
, k = 0, 1, ...
Mit jeder weiteren Iteration nähert sich xk+1 der exakten Lösung x* an. Das Ziel ist, die Iterationsvorschrift 
so zu konstruieren, dass sie genau einen Fixpunkt x* besitzt, dass also schließlich gilt:
.
Die Konvergenz von Fixpunktiterationen wird mittels des banachschen Fixpunktsatzes untersucht.
[Bearbeiten] Lineare Fixpunktverfahren
[Bearbeiten] Konstruktionsidee
Eine wichtige Art der Fixpunktiteration sind die Splitting-Verfahren. Für Fixpunkt-Probleme der Art Ax = b, wobei A eine nicht-singuläre quadratische Matrix und b ein Vektor ist, zerlegt man die Matrix A mit Hilfe einer nicht-singulären n×n-Matrix B in
- A = B + (A − B)
und erhält so eine Fixpunktgleichung.
Damit folgt
- Ax = b
- (B + (A − B))x = b
- Bx + (A − B)x = b
; E ist die Einheitsmatrix.
Jetzt ist das lineare Gleichungssystem Ax = b äquivalent zu der Fixpunktaufgabe
.
Man erhält für den vorgegebenen Startvektor x0 folgendes Iterationsverfahren
- xk + 1 = (E − B − 1A)xk + B − 1b, k = 0, 1, ...
und die zugehörige Iterationsmatrix lautet: E - B-1A.
[Bearbeiten] Konvergenz
Aus dem banachschen Fixpunktsatz und weiteren Überlegungen folgt dann, dass diese Fixpunktverfahren genau dann für jeden Startvektor x0 konvergieren, falls der Spektralradius der Iterationsmatrix
- ρ(E − B − 1A) = maxi | λi(E − B − 1A) | < 1.
ρ(E − B − 1A) sollte möglichst klein sein, da dadurch die Konvergenzgeschwindigkeit bestimmt wird.
[Bearbeiten] Spezielle Verfahren
Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren:
- Gauß-Seidel-Verfahren oder auch Einzelschrittverfahren (ESV)
- Jacobi-Verfahren oder auch Gesamtschrittverfahren (GSV)
[Bearbeiten] Bemerkungen
Iterationsverfahren der Form xk + 1 = Mxk + v, k = 0, 1, ... sind
- linear, d.h. xk+1 hängt linear nur von xk ab,
- stationär, d.h. M und v sind unabhängig von der Schrittnummer der Iteration,
- einstufig, d.h. nur der letzte und nicht noch weitere Näherungsvektoren werden verwendet.
[Bearbeiten] Nichtlineare Gleichungen
Das Newton-Verfahren kann als Fixpunktiteration betrachtet werden. Allgemein wird die Konvergenz mit Hilfe des banachschen Fixpunktsatzes sichergestellt, die betrachtete Funktion muss also insbesondere im betrachteten Gebiet eine Kontraktion sein.
