Fixpunktiteration

Möglichkeit zur Bestimmung von Nullstellen
(Weitergeleitet von Iterationsmatrix)

Eine Fixpunktiteration (oder auch ein Fixpunktverfahren) ist in der Mathematik ein numerisches Verfahren zur näherungsweisen Bestimmung von Lösungen einer Gleichung oder eines Gleichungssystems. Die Gleichung muss dazu zuerst in eine Fixpunktgleichung, also in eine Gleichung der Form

mit einer Funktion umgeformt werden. Anschließend wird eine Startnäherung gewählt und berechnet. Das Ergebnis wird wieder in die Funktion eingesetzt, und so weiter. Unter geeigneten Zusatzvoraussetzungen nähert sich die so erhaltene Folge einer Lösung von und somit einer Lösung des ursprünglichen Problems immer weiter an.

Allgemeines Verfahren

Bearbeiten

Gegeben seien eine Funktion  , die eine Menge   in sich selbst abbildet, sowie ein Startelement  . Die durch das zugehörige Fixpunktverfahren erzeugte Folge   in   ist dann iterativ definiert durch

    für  .

Wenn auf der Menge   ein Konvergenzbegriff vorhanden ist, kann man sich fragen, ob diese Folge gegen einen Fixpunkt von  , das heißt gegen ein   mit   konvergiert. Der banachsche Fixpunktsatz gibt relativ allgemeine Bedingungen an, unter denen das der Fall ist: Ist   ein vollständiger metrischer Raum, also beispielsweise eine abgeschlossene Teilmenge des   oder ein Banachraum, und   eine Kontraktion, dann existiert in der Menge   genau ein Fixpunkt   von   und die durch das Fixpunktverfahren erzeugte Folge konvergiert für beliebige   gegen  .

Beispiele

Bearbeiten
 
Grafische Darstellung der eindimensionalen Fixpunktiteration

Gesucht ist die positive Lösung der Gleichung

 .

Durch Logarithmieren erhält man die Fixpunktgleichung

 .

Die durch   gegebene Iterationsfunktion bildet beispielsweise das Intervall   in sich selbst ab und ist auf   eine Kontraktion (siehe nebenstehende Abbildung).

Ausgehend vom Startwert   ergibt sich für die nächsten Iterationsschritte  ,  ,   usw. Bei der Näherung nach 20 Schritten   stimmen bereits die ersten vier Nachkommastellen mit der exakten Lösung überein.

Auch das Heron-Verfahren stellt eine Fixpunktiteration dar.[1] Für   hat die Funktion   den (positiven) Fixpunkt  , so dass   zur numerischen Bestimmung von   verwendet werden kann.

Ein Satz zur Existenz und Eindeutigkeit

Bearbeiten

Sei   eine stetig differenzierbare Funktion mit   und   für alle   aus  . Dann existiert genau ein Fixpunkt   aus   mit  .

Man setze  . Dann ist  . Aus dem Zwischenwertsatz folgt, dass es mindestens eine Nullstelle   gibt mit  . Gäbe es eine zweite Nullstelle, etwa  , dann müsste es wegen   nach dem Satz von Rolle einen Punkt   aus dem Intervall   geben mit  , was   impliziert im Widerspruch zur Annahme. Also ist der Fixpunkt   eindeutig.

Beispiel

Bearbeiten

Für die Funktion   gilt auf  :

  •  .
  •  .
  •   für alle  .

Daraus folgt mit dem Satz oben, dass   in   genau einen Fixpunkt besitzt ( ).

Lineare Fixpunktverfahren

Bearbeiten

Konstruktionsidee

Bearbeiten

Ein wichtiger Spezialfall der Fixpunktiteration sind die Splitting-Verfahren. Um ein lineares Gleichungssystem

 

mit einer nichtsingulären n×n-Matrix   und einem Vektor   in eine Fixpunktgleichung umzuformen, zerlegt man die Matrix   mit Hilfe einer nichtsingulären n×n-Matrix   in

 .

Damit folgt

 
 
 ,

wobei   die Einheitsmatrix bezeichnet.

Das lineare Gleichungssystem   ist dann äquivalent zu der Fixpunktaufgabe   mit

 .

Man erhält für einen vorgegebenen Startvektor   folgendes Iterationsverfahren für  

 ,

und die zugehörige Iterationsmatrix lautet:  .

Konvergenz

Bearbeiten

Aus dem banachschen Fixpunktsatz und weiteren Überlegungen folgt dann, dass diese Fixpunktverfahren genau dann für jeden Startvektor   konvergieren, falls der Spektralradius der Iterationsmatrix

 .

  sollte möglichst klein sein, da dadurch die Konvergenzgeschwindigkeit bestimmt wird.

Spezielle Verfahren

Bearbeiten

Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren zur Lösung von linearen Gleichungssystemen:

Bemerkungen

Bearbeiten

Iterationsverfahren der Form  , 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.

Nichtlineare Gleichungen

Bearbeiten

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.

Literatur

Bearbeiten
  • Wolfgang Dahmen, Arnold Reusken: Numerik für Ingenieure und Naturwissenschaftler. 2. Auflage. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76492-2.
  • Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065665-7.

Einzelnachweise

Bearbeiten
  1. Passende Umformungen: Nullstellen und Fixpunkte. In: Montanuniversität Leoben. 23. Februar 2005, archiviert vom Original (nicht mehr online verfügbar) am 22. August 2019; abgerufen am 27. August 2019.