www.wikidata.de-de.nina.az
Eine Fixpunktiteration oder auch ein Fixpunktverfahren ist in der Mathematik ein numerisches Verfahren zur naherungsweisen Bestimmung von Losungen einer Gleichung oder eines Gleichungssystems Die Gleichung muss dazu zuerst in eine Fixpunktgleichung also in eine Gleichung der Form f x x displaystyle varphi x x mit einer Funktion f displaystyle varphi umgeformt werden Anschliessend wird eine Startnaherung x 0 displaystyle x 0 gewahlt und x 1 f x 0 displaystyle x 1 varphi x 0 berechnet Das Ergebnis wird wieder in die Funktion f displaystyle varphi eingesetzt x 2 f x 1 displaystyle x 2 varphi x 1 und so weiter Unter geeigneten Zusatzvoraussetzungen nahert sich die so erhaltene Folge x 0 x 1 x 2 displaystyle x 0 x 1 x 2 dotsc einer Losung von f x x displaystyle varphi x x und somit einer Losung des ursprunglichen Problems immer weiter an Inhaltsverzeichnis 1 Allgemeines Verfahren 2 Beispiele 3 Ein Satz zur Existenz und Eindeutigkeit 3 1 Beweis 3 2 Beispiel 4 Lineare Fixpunktverfahren 4 1 Konstruktionsidee 4 2 Konvergenz 4 3 Spezielle Verfahren 4 4 Bemerkungen 5 Nichtlineare Gleichungen 6 Literatur 7 EinzelnachweiseAllgemeines Verfahren BearbeitenGegeben seien eine Funktion f M M displaystyle varphi colon M to M nbsp die eine Menge M displaystyle M nbsp in sich selbst abbildet sowie ein Startelement x 0 M displaystyle x 0 in M nbsp Die durch das zugehorige Fixpunktverfahren erzeugte Folge x k k N 0 displaystyle x k k in mathbb N 0 nbsp in M displaystyle M nbsp ist dann iterativ definiert durch x k 1 f x k displaystyle x k 1 varphi x k nbsp fur k N 0 displaystyle k in mathbb N 0 nbsp Wenn auf der Menge M displaystyle M nbsp ein Konvergenzbegriff vorhanden ist kann man sich fragen ob diese Folge gegen einen Fixpunkt von f displaystyle varphi nbsp das heisst gegen ein x displaystyle x nbsp mit f x x displaystyle varphi x x nbsp konvergiert Der banachsche Fixpunktsatz gibt relativ allgemeine Bedingungen an unter denen das der Fall ist Ist M displaystyle M nbsp ein vollstandiger metrischer Raum also beispielsweise eine abgeschlossene Teilmenge des R n displaystyle mathbb R n nbsp oder ein Banachraum und f displaystyle varphi nbsp eine Kontraktion dann existiert in der Menge M displaystyle M nbsp genau ein Fixpunkt x displaystyle x nbsp von f displaystyle varphi nbsp und die durch das Fixpunktverfahren erzeugte Folge konvergiert fur beliebige x 0 M displaystyle x 0 in M nbsp gegen x displaystyle x nbsp Beispiele Bearbeiten nbsp Grafische Darstellung der eindimensionalen FixpunktiterationGesucht ist die positive Losung der Gleichung 2 x 2 e x displaystyle 2 x 2 e x nbsp Durch Logarithmieren erhalt man die Fixpunktgleichung ln 2 x 2 x displaystyle ln 2 x 2 x nbsp Die durch f x ln 2 x 2 displaystyle varphi x ln 2 x 2 nbsp gegebene Iterationsfunktion bildet beispielsweise das Intervall M 0 2 0 7 displaystyle M 0 2 0 7 nbsp in sich selbst ab und ist auf M displaystyle M nbsp eine Kontraktion siehe nebenstehende Abbildung Ausgehend vom Startwert x 0 0 2 displaystyle x 0 0 2 nbsp ergibt sich fur die nachsten Iterationsschritte x 1 f x 0 0 672 9 displaystyle x 1 varphi x 0 approx 0 6729 nbsp x 2 f x 1 0 436 4 displaystyle x 2 varphi x 1 approx 0 4364 nbsp x 3 f x 2 0 593 1 displaystyle x 3 varphi x 2 approx 0 5931 nbsp usw Bei der Naherung nach 20 Schritten x 20 0 537 3 displaystyle x 20 approx 0 5373 nbsp stimmen bereits die ersten vier Nachkommastellen mit der exakten Losung uberein Auch das Heron Verfahren stellt eine Fixpunktiteration dar 1 Fur a gt 0 textstyle a gt 0 nbsp hat die Funktion f x 1 2 x a x textstyle varphi x frac 1 2 cdot left x frac a x right nbsp den positiven Fixpunkt x a textstyle x sqrt a nbsp so dass f x textstyle varphi x nbsp zur numerischen Bestimmung von a textstyle sqrt a nbsp verwendet werden kann Ein Satz zur Existenz und Eindeutigkeit BearbeitenSei f a b a b R displaystyle f colon a b to a b subset mathbb R nbsp eine stetig differenzierbare Fixpunktiterationsfunktion mit f a gt a f b lt b displaystyle f a gt a f b lt b nbsp und f x 1 displaystyle f x neq 1 nbsp fur alle x displaystyle x nbsp aus a b displaystyle a b nbsp Dann existiert genau ein Fixpunkt x displaystyle x nbsp aus a b displaystyle a b nbsp mit f x x displaystyle f x x nbsp Beweis Bearbeiten Man setze F x f x x displaystyle F x f x x nbsp Dann ist F a gt 0 F b lt 0 displaystyle F a gt 0 F b lt 0 nbsp Aus dem Zwischenwertsatz folgt dass es mindestens eine Nullstelle x a b displaystyle x in a b nbsp gibt mit F x 0 displaystyle F x 0 nbsp Gabe es eine zweite Nullstelle etwa x displaystyle x nbsp dann musste es wegen F x F x displaystyle F x F x nbsp nach dem Satz von Rolle einen Punkt x ˇ displaystyle check x nbsp aus dem Intervall x x displaystyle x x nbsp geben mit F x ˇ 0 displaystyle F check x 0 nbsp was f x ˇ 1 displaystyle f check x 1 nbsp impliziert im Widerspruch zur Annahme Also ist der Fixpunkt x displaystyle x nbsp eindeutig Beispiel Bearbeiten Fur die Funktion f x x 3 1 x 3 2 displaystyle f x frac x 3 1 x 3 2 nbsp gilt auf 1 1 displaystyle 1 1 nbsp f 1 gt 0 gt 1 displaystyle f 1 gt 0 gt 1 nbsp f 1 0 lt 1 displaystyle f 1 0 lt 1 nbsp f x 3 x 2 x 3 2 2 1 displaystyle f x frac 3x 2 x 3 2 2 neq 1 nbsp fur alle x 1 1 displaystyle x in 1 1 nbsp Daraus folgt mit dem Satz oben dass f displaystyle f nbsp in 1 1 displaystyle 1 1 nbsp genau einen Fixpunkt besitzt x 0 472 2129517 displaystyle x approx 0 4722129517 nbsp Lineare Fixpunktverfahren BearbeitenKonstruktionsidee Bearbeiten Ein wichtiger Spezialfall der Fixpunktiteration sind die Splitting Verfahren Um ein lineares Gleichungssystem A x b displaystyle Ax b nbsp mit einer nichtsingularen n n Matrix A displaystyle A nbsp und einem Vektor b displaystyle b nbsp in eine Fixpunktgleichung umzuformen zerlegt man die Matrix A displaystyle A nbsp mit Hilfe einer nichtsingularen n n Matrix B displaystyle B nbsp in A B A B displaystyle A B A B nbsp Damit folgt A x b displaystyle Ax b nbsp B x A B x b displaystyle Bx A B x b nbsp x B 1 b B 1 A B x E B 1 A x B 1 b displaystyle Rightarrow x B 1 b B 1 A B x E B 1 A x B 1 b nbsp wobei E displaystyle E nbsp die Einheitsmatrix bezeichnet Das lineare Gleichungssystem A x b displaystyle Ax b nbsp ist dann aquivalent zu der Fixpunktaufgabe x f x displaystyle x varphi x nbsp mit f x E B 1 A x B 1 b displaystyle varphi x E B 1 A x B 1 b nbsp Man erhalt fur einen vorgegebenen Startvektor x 0 displaystyle x 0 nbsp folgendes Iterationsverfahren fur k 0 1 displaystyle k 0 1 ldots nbsp x k 1 E B 1 A x k B 1 b displaystyle x k 1 E B 1 A x k B 1 b nbsp und die zugehorige Iterationsmatrix lautet E B 1 A displaystyle E B 1 A nbsp Konvergenz Bearbeiten Aus dem banachschen Fixpunktsatz und weiteren Uberlegungen folgt dann dass diese Fixpunktverfahren genau dann fur jeden Startvektor x 0 displaystyle x 0 nbsp konvergieren falls der Spektralradius der Iterationsmatrix r E B 1 A max i l i E B 1 A lt 1 displaystyle rho E B 1 A max i lambda i E B 1 A lt 1 nbsp r E B 1 A displaystyle rho E B 1 A nbsp sollte moglichst klein sein da dadurch die Konvergenzgeschwindigkeit bestimmt wird Spezielle Verfahren Bearbeiten Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren zur Losung von linearen Gleichungssystemen Gauss Seidel Verfahren oder auch Einzelschrittverfahren ESV Jacobi Verfahren oder auch Gesamtschrittverfahren GSV Bemerkungen Bearbeiten Iterationsverfahren der Form x k 1 M x k v displaystyle x k 1 Mx k v nbsp k 0 1 sind linear d h xk 1 hangt linear nur von xk ab stationar d h M und v sind unabhangig von der Schrittnummer der Iteration einstufig d h nur der letzte und nicht noch weitere Naherungsvektoren werden verwendet Nichtlineare Gleichungen BearbeitenDas 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 BearbeitenWolfgang Dahmen Arnold Reusken Numerik fur Ingenieure und Naturwissenschaftler 2 Auflage Springer Verlag Berlin 2008 ISBN 978 3 540 76492 2 Martin Hermann Numerische Mathematik Band 1 Algebraische Probleme 4 uberarbeitete und erweiterte Auflage Walter de Gruyter Verlag Berlin und Boston 2020 ISBN 978 3 11 065665 7 Einzelnachweise Bearbeiten Passende Umformungen Nullstellen und Fixpunkte Nicht mehr online verfugbar In Montanuniversitat Leoben 23 Februar 2005 archiviert vom Original am 22 August 2019 abgerufen am 27 August 2019 Abgerufen von https de wikipedia org w index php title Fixpunktiteration amp oldid 233408134