Fixpunktiteration

Die Fixpunktiteration ist ein in der Mathematik gebräuchliches iteratives Verfahren zur näherungsweisen Bestimmung der Nullstellen einer Funktion ff auf einem bestimmten Intervall [a,b][a,b].

Allgemein

Jedes Fixpunktverfahren hat die Form
xk+1=φ(xk)x_{k+1} = \varphi(x_k), k=0,1,…k = 0, 1, \dots
Mit jeder weiteren Iteration nähert sich xk+1x_{k+1} der exakten Lösung x∗x^{*} an. Das Ziel ist, die Iterationsvorschrift φ\varphi so zu konstruieren, dass sie genau einen Fixpunkt x∗x^{*} besitzt, dass also schließlich gilt:
x∗=φ(x∗)x^* = \varphi(x^*).
Die Konvergenz von Fixpunktiterationen wird mittels des banachschen Fixpunktsatzes untersucht.

Lineare Fixpunktverfahren

Konstruktionsidee

Eine wichtige Art der Fixpunktiteration sind die Splitting-Verfahren. Für Fixpunkt-Probleme der Art Ax=bAx = b, wobei AA eine nicht-singuläre quadratische Matrix und bb ein Vektor ist, zerlegt man die Matrix AA mit Hilfe einer nicht-singulären n×nn\cross n-Matrix BB in
A=B+(A−B)A = B + (A - B)
und erhält so eine Fixpunktgleichung.
Damit folgt
Ax=bAx = b
(B+(A−B))x=b(B + (A - B))x = b
Bx+(A−B)x=bBx + (A - B)x = b
⇒x=B−1b−B−1(A−B)x=(E−B−1A)x+B−1b\Rightarrow x = B^{-1}b - B^{-1}(A-B)x = (E - B^{-1}A)x + B^{-1}b; EE ist die Einheitsmatrix.
Jetzt ist das lineare Gleichungssystem Ax=bAx = b äquivalent zu der Fixpunktaufgabe
x=(E−B−1A)x+B−1b=φ(x)x = (E - B^{-1}A)x + B^{-1}b = \varphi(x).
Man erhält für den vorgegebenen Startvektor x0x_{0} folgendes Iterationsverfahren
xk+1=(E−B−1A)xk+B−1b, kx_{k+1} = (E - B^{-1}A)x_k + B^{-1}b,\, k = 0, 1, ...
und die zugehörige Iterationsmatrix lautet: E−B−1AE - B^{-1} A.

Konvergenz

Aus dem banachschen Fixpunktsatz und weiteren Überlegungen folgt dann, dass diese Fixpunktverfahren genau dann für jeden Startvektor x0x_{0} konvergieren, falls der Spektralradius der Iterationsmatrix
ρ(E−B−1A)=max⁡i∣λi(E−B−1A)∣<1\rho(E - B^{-1}A) = \max_i|\lambda_i(E - B^{-1}A)| < 1.
ρ(E−B−1A)\rho(E - B^{-1}A) sollte möglichst klein sein, da dadurch die Konvergenzgeschwindigkeit bestimmt wird.

Spezielle Verfahren

Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren:

Bemerkungen

Iterationsverfahren der Form xk+1=Mxk+vx_{k+1} = Mx_k + v, k=0,1k = 0, 1, ... sind
  • linear, d.h. xk+1x_{k+1} hängt linear nur von xkx_{k} 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.

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.
 
 

So kann also die Mathematik definiert werden als diejenige Wissenschaft, in der wir niemals das kennen, worüber wir sprechen, und niemals wissen, ob das, was wir sagen, wahr ist.

Bertrand Russell

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Fixpunktiteration aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Numerische Verfahren