Kurs:Numerik I/Fixpunktsatz von Banach

Einführung

Der Fixpunktsatz von Banach, auch als Banachscher Fixpunktsatz bezeichnet, ist ein mathematischer Satz aus der Funktionalanalysis. Er gehört zu den Fixpunktsätzen und liefert neben der Existenz und der Eindeutigkeit eines Fixpunktes auch die Konvergenz der Fixpunktiteration. Somit ist die Aussage konstruktiv. Es wird also ein Verfahren zur Bestimmung des Fixpunktes sowie eine Fehlerabschätzung für ebendieses angegeben.

Anwendungen des Fixpunktsatzes

Mit dem Fixpunktsatz von Banach lässt sich beispielsweise die Konvergenz von iterativen Verfahren wie dem Newton-Verfahren zeigen und der Satz von Picard-Lindelöf beweisen, der Grundlage der Existenztheorie gewöhnlicher Differentialgleichungen ist.

Geschichte

Der Satz ist nach Stefan Banach benannt, der ihn 1922 zeigte.

Metrische Räume

Der Banachsche Fixpunktsatz wird allgemein für metrische Räume $(X,d)$ und ein nichtleere abschlossene Teilmenge $M\subseteq X$ bewiesen. Damit gilt dieser Satz natürlich auch für die abgeschlossene Teilmengen $M:=[a,b]\subset ℝ$ der reellen Zahlen mit der Metrik $d(x,y)=|x-y|$ oder allgemeiner auch für einen Banach-Raum mit der Metrik $d(x,y)=\Vert x-y\Vert$.

Definition - Kontraktion

Sei $(X,d)$ ein vollständiger metrischer Raum. Eine Abbildung

$\phi :X\to X$

heißt Kontraktion, wenn mit Kontraktionszahl $k\in [0,1)$ existiert, für die gilt:

$d(\phi (x),\phi (y))\le k\cdot d(x,y)$ für alle $x,y\in X$.

Fixpunktsatz von Banach

Sei $(X,d)$ ein vollständiger metrischer Raum, $M\subset X$ eine nichtleere, abgeschlossene Menge und $\phi :M\to M$ eine Kontraktion mit Kontraktionszahl $k\in [0,1)$. Dann existiert genau ein Fixpunkt $\tilde{x}\in M$, sodass für einen beliebigen Startwert $x_0\in M$, die iterativ definierte $(x_n{)}_{n\in \mathbb{N}}$ Folge mit $x_{n+1}=\phi (x_n)$ gegen den Fixpunkt $\tilde{x}\in M$ konvergiert.

Bemerkung - Ein Grenzwert beliebiger Startpunkt

Der Fixpunktsatz von Banach besagt, dass es genau einen Grenzwert $\tilde{x}\in M$ und der Startpunkt $x_0$ aus $M$ kann beliebig gewählt werden kann. Die Selbsabbildung von $\phi :M\to M$ definiert dann Folge $(x_n{)}_{n\in \mathbb{N}}$ mit $x_1:=\phi (x_0)$,..., $x_{n+1}:=\phi (x_n)$ und dann immer gegen den einen Fixpunkt konvergiert.

Beweis

Unter den obigen Voraussetzungen des Satzes muss man nun zeigen, dass

• (Existenz) ein Fixpunkt $\tilde{x}\in M$ existiert, d.h. $\phi (\tilde{x})=\tilde{x}$ gilt.
• (Eindeutigkeit) Es gibt genau einen Fixpunkt.
• (Startpunktunabhängigkeit) Die Konvergenz $\underset{n\to \mathrm{\infty }}{\lim }{x}_n=\tilde{x}$ der Iteriertenfolgen $(x_n{)}_{n\in \mathbb{N}}$ gegen $\tilde{x}$ mit $x_1:=\phi (x_0)$,..., $x_{n+1}:=\phi (x_n)$ ist unabhängig von der Wahl des Startpunktes

$x_0\in M$

Beweisschritt 1

Der Beweis der Aussage basiert darauf, zu zeigen, dass die Folge $(x_n{)}_{n\in \mathbb{N}}$ eine Cauchy-Folge ist, die dann aufgrund der Vollständigkeit des zugrundeliegenden Raumes konvergiert.

Zuerst gilt aufgrund der Kontraktivität

$d(x_n,x_{n+1})=d(\phi (x_{n-1}),\phi (x_n))\le k\cdot d(x_{n-1},x_n)$

Durch wiederholtes Anwenden dieser Abschätzung erhält man

$d(x_n,x_{n+1})\le k^{n}d(x_0,x_1)$ (1)

Des Weiteren folgt durch wiederholtes Abschätzen mit der Dreiecksungleichung

$d(x_n,x_{n+m})\le d(x_n,x_{n+1})+d(x_{n+1},x_{n+2})+\dots +d(x_{n+m-1},x_{n+m})$ (2)

Schätzt man die einzelnen Summenglieder der rechten Seite von (2) durch (1) ab, so erhält man

$d(x_n,x_{n+m})\le k^n(1+k+k^2+\dots +k^{m-1})d(x_0,x_1)\le \frac{k^n}{1-k}d(x_0,x_1)$

Die letzte Abschätzung folgt hier mithilfe der geometrischen Reihe, da $k<1$. Aus der Abschätzung folgt direkt, dass $(x_n{)}_{n\in \mathbb{N}}$ eine Cauchy-Folge ist. Aufgrund der Vollständigkeit existiert dann der Grenzwert

$\tilde{x}:=\underset{n\to \mathrm{\infty }}{\lim }{x}_n$

der Folge. Da $\phi$ eine Abbildung von $M$ in sich selbst ist, und $M$ abgeschlossen ist, ist $\tilde{x}$ in der Menge $M$ enthalten.

Da $\phi$ stetig ist (da kontraktiv), folgt

$\tilde{x}=\underset{n\to \mathrm{\infty }}{\lim }{x}_n=\underset{n\to \mathrm{\infty }}{\lim }\phi (x_{n-1})=\phi (\tilde{x})$,

der Grenzwert $\tilde{x}$ ist also Fixpunkt.

Angenommen, es existieren zwei Fixpunkte $\tilde{x},\tilde{y}$. Dann ist

$\phi (\tilde{x})=\tilde{x}$ und $\phi (\tilde{y})=\tilde{y}$.

Aus der Kontraktivität folgt dann

$d(\tilde{x},\tilde{y})=d(\phi (\tilde{x}),\phi (\tilde{y}))\le k\cdot d(\tilde{x},\tilde{y})$.

Da aber $k<1$ ist, muss $d(\tilde{x},\tilde{y})=0$ sein. Daher ist $\tilde{x}=\tilde{y}$.

Beweisschritt 7

Die Abbildung $\phi$ besitzt also einen eindeutig bestimmten Fixpunkt und dieser stimmt für alle Startwerte der oben angegebenen Iterationsvorschrift mit dem Grenzwert der Iteration überein.

Veranschaulichung

Veranschaulichung des Fixpunktsatzes von Banach

Eine Veranschaulichung des Satzes liefert eine Landkarte, auf der die Umgebung, in der man sich befindet, abgebildet ist. Sieht man diese Karte als Kontraktion (lat. con- „zusammen-“ und trahere „ziehen“) der Umgebung, so findet man genau einen Punkt auf der Karte, der mit dem direkt darunter liegenden Punkt in der realen Welt übereinstimmt. Es ist egal, wie groß die Landkarte ist; sie muss nur kleiner als die abgebildete Realität sein. Es ist ebenso unerheblich, wo genau sich die Landkarte befindet, solange sie innerhalb des kartografierten Bereichs liegt. In der nebenstehenden Abbildung befindet sich in der kleineren Landkarte also nach dem Fixpunktsatz von Banach genau ein Punkt, der mit dem in der realen Welt zusammenfällt.

Fehlerabschätzung der Fixpunktiteration

Für die Iterationsvorschrift

$x_{n+1}=\phi (x_n)$

gelten folgende Fehlerabschätzungen:

• A-priori-Fehlerabschätzung: Es ist

$d(x_n,\tilde{x})\le \frac{k^n}{1-k}d(x_1,x_0)$

• A-posteriori-Fehlerabschätzung: Es ist

$d(x_{n+1},\tilde{x})\le \frac{k}{1-k}d(x_{n+1},x_n)$

Außerdem gilt die Abschätzung

$d(x_{n+1},\tilde{x})\le k\cdot d(x_n,\tilde{x})$,

die Konvergenzgeschwindigkeit ist also linear.

Zusammenfassung des Verfahrens

Gegeben sei eine Funktion$\phi :X\to X$ auf dem metrischen Raum $(X,d)$. Zuerst muss die Menge $M\subseteq X$ bestimmt werden, für welche $\phi$ eine Kontraktion ist, d.h. $\mathrm{\exists }L<1:d(\phi (x),\phi (y))=\Vert \phi (x)-\phi (y)\Vert \le L\cdot \Vert x-y\Vert =L\cdot d(x,y)$. Ist dieses $M$ bestimmt, kann ein Startwert $x_{0}inM$ beliebeig gewählt werden. Abschließend wird $x_{n+1}=\phi (x)$ bis zum Unterschreiten der Fehlerschranke durchgeführt.

Bemerkung

In der Literatur finden sich teils von der oben angegebenen Aussage abweichende Formulierungen. Mögliche Unterschiede sind:

• Die Eigenschaft der Abbildung $\phi$, eine Kontraktion zu sein, wird stattdessen über die Lipschitz-Stetigkeit formuliert. Dann muss $\phi$ auf $M$ Lipschitz-stetig sein mit einer Lipschitz-Konstante $L=k<1$.
• Der zugrunde liegende Raum ist ein anderer. So wird der Satz teils auf Banachräumen (das heißt auf vollständigen normierten Räumen) formuliert oder auf $ℝ$. Die Aussage wie auch der Beweis bleiben identisch, es ist dann lediglich $d(x,y)=\Vert y-x\Vert$ im Falle eines normierten Raumes $(X,\Vert \cdot \Vert )$ beziehungsweise $d(x,y)=|y-x|$ im reellen Fall zu setzen.

Anwendungen

Dieser Satz wird in vielen konstruktiven Sätzen der Analysis benutzt, die wichtigsten sind:

• das inverse- und implizite-Funktionen-Theorem
• der Existenz- und Eindeutigkeitssatz von Picard-Lindelöf für gewöhnliche Differentialgleichungen

In der numerischen Mathematik spielt die Fixpunktiteration eine wichtige Rolle. Beispiele hierfür sind die Konvergenztheorien numerischer Verfahren, wie das Newton-Verfahren oder das Splitting-Verfahren.

Umkehrung

Die folgende, auch als Satz von Bessaga bekannte Aussage stellt eine Umkehrung des Fixpunktsatzes dar:

• Ist $\phi :M\to M$ eine Funktion auf einer nichtleeren Menge, so dass $\phi$ und alle Iterierten ${\phi }^n$ genau einen Fixpunkt haben, so gibt es zu jedem $k\in (0,1)$ eine vollständige Metrik $d_k$ auf $M$, so dass $\phi$ bzgl. $d_k$ eine Kontraktion mit der Kontraktionskonstanten $k$ ist.

Literatur

• Hans-Rudolf Schwarz, Norbert Köckler: Numerische Mathematik. 5., überarbeitete Auflage. Teubner, Stuttgart u. a. 2004, ISBN 3-519-42960-8.
• Vorlage:Literatur
• Vorlage:Literatur

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Fixpunktsatz%20von%20Banach
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.

Wikipedia2Wikiversity

Diese Seite wurde auf Basis der folgenden Wikipedia-Quelle erstellt:

• Fixpunktsatz von Banach https://de.wikipedia.org/wiki/Fixpunktsatz%20von%20Banach
• Datum: 27.12.2022
• Wikipedia2Wikiversity-Konverter: https://niebert.github.com/Wikipedia2Wikiversity