imported>Okoska-törp: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-02-27T19:12:41Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

Eine '''Fixpunktiteration''' (oder auch ein '''Fixpunktverfahren''') ist in der [[Mathematik]] ein [[Numerische Mathematik|numerisches]] Verfahren zur näherungsweisen Bestimmung von Lösungen einer [[Gleichung]] oder eines [[Gleichungssystem]]s. Die Gleichung muss dazu zuerst in eine [[Fixpunkt (Mathematik)|Fixpunktgleichung]], also in eine Gleichung der Form
:<math>\varphi(x) = x</math>
mit einer [[Funktion (Mathematik)|Funktion]] <math>\varphi</math> umgeformt werden. Anschließend wird eine Startnäherung <math>x_0</math> gewählt und <math>x_1 = \varphi(x_0)</math> berechnet. Das Ergebnis wird wieder in die Funktion <math>\varphi</math> eingesetzt, <math>x_2 = \varphi(x_1)</math> und so weiter. Unter geeigneten Zusatzvoraussetzungen nähert sich die so erhaltene [[Folge (Mathematik)|Folge]] <math>x_0, x_1, x_2, \dotsc</math> einer Lösung von <math>\varphi(x) = x</math> und somit einer Lösung des ursprünglichen Problems immer weiter an.

== Allgemeines Verfahren ==

Gegeben seien eine Funktion <math>\varphi\colon M \to M</math>, die eine Menge <math>M</math> in sich selbst abbildet, sowie ein Startelement <math>x_0 \in M</math>. Die durch das zugehörige Fixpunktverfahren erzeugte Folge <math>(x_k)_{k \in \N_0}</math> in <math>M</math> ist dann [[Iteration|iterativ]] definiert durch
:<math>x_{k+1} = \varphi(x_k)</math>   für <math>k \in \N_0</math>.

Wenn auf der Menge <math>M</math> ein [[Grenzwert (Folge)|Konvergenzbegriff]] vorhanden ist, kann man sich fragen, ob diese Folge gegen einen Fixpunkt von <math>\varphi</math>, das heißt gegen ein <math>x^*</math> mit <math>\varphi(x^*) = x^*</math> konvergiert. Der [[Fixpunktsatz von Banach|banachsche Fixpunktsatz]] gibt relativ allgemeine Bedingungen an, unter denen das der Fall ist: Ist <math>M</math> ein [[Vollständiger Raum|vollständiger]] [[Metrischer Raum|metrischer]] Raum, also beispielsweise eine [[abgeschlossene Teilmenge]] des <math>\R^n</math> oder ein [[Banachraum]], und <math>\varphi</math> eine [[Kontraktion (Mathematik)|Kontraktion]], dann existiert in der Menge <math>M</math> genau ein Fixpunkt <math>x^*</math> von <math>\varphi</math> und die durch das Fixpunktverfahren erzeugte Folge konvergiert für beliebige <math>x_0 \in M</math> gegen <math>x^*</math>.

== Beispiele ==
[[Datei:Fixpunkt.png|rechts|miniatur|400px|Grafische Darstellung der eindimensionalen Fixpunktiteration]]
Gesucht ist die positive Lösung der Gleichung
:<math>2-x^2 = e^x</math>.
Durch [[Logarithmus|Logarithmieren]] erhält man die Fixpunktgleichung
:<math>\ln(2-x^2) = x</math>.
Die durch <math>\varphi(x) = \ln(2-x^2)</math> gegebene Iterationsfunktion bildet beispielsweise das Intervall <math>M = [0{,}2; 0{,}7]</math> in sich selbst ab und ist auf <math>M</math> eine Kontraktion (siehe nebenstehende Abbildung).

Ausgehend vom Startwert <math>x_0 = 0{,}2</math> ergibt sich für die nächsten Iterationsschritte <math>x_1 = \varphi(x_0) \approx 0{,}6729</math>, <math>x_2 = \varphi(x_1) \approx 0{,}4364</math>, <math>x_3 = \varphi(x_2) \approx 0{,}5931</math> usw. Bei der Näherung nach 20 Schritten <math>x_{20} \approx 0{,}5373</math> stimmen bereits die ersten vier Nachkommastellen mit der exakten Lösung überein.

Auch das [[Heron-Verfahren]] stellt eine Fixpunktiteration dar.<ref>{{Internetquelle |url=http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html |titel=Passende Umformungen: Nullstellen und Fixpunkte |werk=[[Montanuniversität Leoben]] |datum=2005-02-23 |zugriff=2019-08-27 |archiv-url=https://web.archive.org/web/20190822114648/http://institute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/skripts05/node17.html |archiv-datum=2019-08-22 |offline=ja }}</ref> Für <math display="inline">a > 0</math> hat die Funktion <math display="inline">\varphi(x) = \frac{1}{2}\cdot\left(x + \frac{a}{x}\right)</math> den (positiven) Fixpunkt <math display="inline">x = \sqrt{a}</math>, so dass <math display="inline">\varphi(x)</math> zur numerischen Bestimmung von <math display="inline">\sqrt{a}</math> verwendet werden kann.

== Ein Satz zur Existenz und Eindeutigkeit ==

Sei <math>f\colon [a,b] \to [a,b]\subset\R</math> eine [[stetig]]
[[differenzierbar]]e Funktion mit <math>f(a)>a, f(b)<b</math> und
<math>f'(x)\ne 1</math> für alle <math>x</math> aus <math>(a,b)</math>.
Dann existiert genau ein Fixpunkt <math>x^*</math> aus
<math>(a,b)</math> mit <math>f(x^*)=x^*</math>.

=== Beweis ===
Man setze <math>F(x):=f(x)-x</math>. Dann ist <math>F(a)>0,
F(b)<0</math>. Aus dem [[Zwischenwertsatz]] folgt, dass es mindestens
eine Nullstelle <math>x^*\in [a,b]</math> gibt mit
<math>F(x^*)=0</math>. Gäbe es eine zweite [[Nullstelle]], etwa
<math>x^{**}</math>, dann müsste es wegen <math>F(x^*)=F(x^{**})</math>
nach dem [[Satz von Rolle]] einen Punkt <math>\check x </math> aus dem
Intervall <math>(x^*,x^{**})</math> geben mit <math>F'(\check x) =
0</math>, was <math>f'(\check x)=1</math> impliziert im Widerspruch zur
Annahme. Also ist der Fixpunkt <math>x^*</math> eindeutig.

=== Beispiel ===
Für die Funktion <math>f(x)=\frac{x^3-1} {x^3-2}</math> gilt auf <math>
[-1, +1]</math>:

* <math>f(-1) > 0 > -1 </math>.
* <math>f(+1)=0<1</math>.
* <math>f'(x)=\frac {-3x^2} {(x^3-2)^2} \ne 1</math> für alle <math> x
\in (-1,+1)</math>.

Daraus folgt mit dem Satz oben, dass <math> f</math> in
<Math>(-1,+1)</math> genau einen Fixpunkt besitzt
(<math>x^*\approx 0{,}4722129517</math>).

== Lineare Fixpunktverfahren ==
=== Konstruktionsidee ===
Ein wichtiger Spezialfall der Fixpunktiteration sind die [[Splitting-Verfahren]]. Um ein [[lineares Gleichungssystem]]
:<math>Ax = b</math>
mit einer [[Reguläre Matrix|nichtsingulären]] ''n×n''-[[Matrix (Mathematik)|Matrix]] <math>A</math> und einem [[Vektor]] <math>b</math> in eine Fixpunktgleichung umzuformen,
zerlegt man die Matrix <math>A</math> mit Hilfe einer nichtsingulären ''n×n''-Matrix <math>B</math> in
:<math>A = B + (A - B)</math>.

Damit folgt
:<math>Ax = b</math>
:<math>Bx + (A - B)x = b</math>
:<math>\Rightarrow x = B^{-1}b - B^{-1}(A-B)x = (E - B^{-1}A)x + B^{-1}b</math>,
wobei <math>E</math> die [[Einheitsmatrix]] bezeichnet.

Das lineare Gleichungssystem <math>Ax=b</math> ist dann äquivalent zu der Fixpunktaufgabe <math>x = \varphi(x)</math> mit
:<math>\varphi(x) = (E - B^{-1}A)x + B^{-1}b</math>.
Man erhält für einen vorgegebenen Startvektor <math>x_0</math> folgendes Iterationsverfahren für <math>k = 0,1,\ldots</math>
:<math>x_{k+1} = (E - B^{-1}A)x_k + B^{-1}b</math>,
und die zugehörige '''Iterationsmatrix''' lautet: <math>E - B^{-1}A</math>.

=== Konvergenz ===
Aus dem [[Fixpunktsatz von Banach|banachschen Fixpunktsatz]] und weiteren Überlegungen folgt dann, dass diese Fixpunktverfahren genau dann für jeden Startvektor <math>x_0</math> konvergieren, falls der [[Spektralradius]] der Iterationsmatrix

:<math>\rho(E - B^{-1}A) = \max_i|\lambda_i(E - B^{-1}A)| < 1</math>.
<math>\rho(E - B^{-1}A)</math> sollte möglichst klein sein, da dadurch die [[Konvergenzgeschwindigkeit]] bestimmt wird.

=== Spezielle Verfahren ===
Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren zur Lösung von linearen Gleichungssystemen:
* [[Gauß-Seidel-Verfahren]] oder auch '''Einzelschrittverfahren''' (ESV)
* [[Jacobi-Verfahren]] oder auch '''Gesamtschrittverfahren''' (GSV)

=== Bemerkungen ===
Iterationsverfahren der Form <math>x_{k+1} = Mx_k + v</math>, k = 0, 1, ... sind
* '''linear''', d. h. x<sub>k+1</sub> hängt linear nur von x<sub>k</sub> 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 [[Fixpunktsatz von Banach|banachschen Fixpunktsatzes]] sichergestellt, die betrachtete Funktion muss also insbesondere im betrachteten Gebiet eine [[Kontraktion (Mathematik)|Kontraktion]] sein.

== Literatur ==
* Wolfgang Dahmen, Arnold Reusken: ''Numerik für Ingenieure und Naturwissenschaftler.'' 2. Auflage. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76492-2.
*[[Martin Hermann (Mathematiker)|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 ==
<references />

[[Kategorie:Numerische Mathematik]]

Fixpunktiteration - Versionsgeschichte

imported>Okoska-törp: /* growthexperiments-addlink-summary-summary:2|0|0 */