Die Bedeutung der Fixpunktsatzein der Mathematik

Andre Uschmajew

Schulerwoche Mathematik21. August 2015

Hausdorff–Zentrum fur MathematikUniversitat Bonn

Fixpunkte

Viele Aufgaben in der Mathematik und anderen Wissenschaften lassen sichauf das Problem zuruckfuhren zu gegebenem y ein x zu finden, welches eineGleichung

f(x) = y

erfullt. Hierbei ist f eine gegebene Funktion, welche Werte x aus einer MengeX in Werte y aus einer Menge Y uberfuhrt (man schreibt f : X → Y). DieMengen X und Y mussen nicht notwendig Zahlen enthalten, sondern konnenrecht abstrakter Natur sein. Von grundlegender Bedeutung konnen dann etwadie folgenden, typisch mathematischen Fragestellungen sein:

1. Existenz. Gibt es zu gegebenem y uberhaupt ein x, welches der Gleichunggenugt?

2. Eindeutigkeit. Ist die Losung eindeutig? Wenn nicht, wieviele Losung gibtes (zu gegebenem y)?

3. Approximation. Wie konnen wir eine Losung naherungsweise berechnen?

Im dritten Punkt schreiben wir naherungsweise, da wir im Allgemeinen nichterwarten die Gleichung explizit nach x auflosen zu konnen. Wenn wir es konnten,wurden sich alle Fragen erubrigen.

Die Fixpunktsatze spielen in vielen Bereichen der Mathematik eine großeRolle, da sie vielseitige Werkzeuge zur Beantwortung einiger oder aller dieserFragen in verschiedensten Situationen liefern. Eine Grundvoraussetzung hierfurist, dass sich das Problem in eine Fixpunktgleichung umformulieren lasst. Dazunun die zentralen Definitionen.

Definition 1. Es sei X eine Menge. Eine Abbildungsvorschrift T : X→ X, wel-che also jedem x in X ein anderes Element T (x) in X zuordnet heißt Abbildung

1

Abbildung 1: Abbildung einer Menge in sich mit Fixpunkt (gestrichelt).

von X in sich oder Selbstabbildung von X.1 Erfullt ein Element x aus X dieGleichung

T (x) = x, (1)

so wird x ein Fixpunkt der Abbildung T genannt. Die Gleichung (1) heißtFixpunktgleichung. Die einfache Fixpunktiteration mit Startwert x0 ist dierekursiv definierte Folge

xn+1 = T (xn), n = 0, 1, 2 . . . (2)

Bei der einfachen Fixpunktiteration hofft man naturlich, dass die Folge irgend-wann stationar wird (d.h. xn+1 = xn, was dann einen Fixpunkt darstellt), oderdass die Folge zumindest gegen einen Fixpunkt konvergiert (d.h. fur genugendgroße n beliebig nahe an einem Fixpunkt bleibt).

Beispiel. Sei f(x) = x2 − 2. Wir betrachten die Gleichung

f(x) = x2 − 2 = 0.

Die Losungen sind naturlich x = ±√

2. Gleichbedeutend zu dieser Nullstellen-gleichung ist zum Beispiel die Fixpunktgleichung

x = x− x2 − 2

2x=

1

2

(x+

2

x

), x 6= 0.

Hier ist also T (x) = 12 (x+ 2

x ) zu wahlen. Die Abbildung bildet etwa den positivenZahlenstrahl X =]0,+∞[ in sich ab. Die zugehorige einfache Fixpunktiteration

xn+1 = T (xn) =1

2

(xn +

2

xn

)heißt Heron Verfahren und wurde vermutlich bereits in der Antike zur naherungs-weisen Bestimmung der (irrationalen) Zahl

√2 verwendet. Es ist ein Spezialfall

des Newton-Verfahrens zur Bestimmung von Nullstellen (siehe Tutorium amNachmittag).

1Man beachte: weder muss jedes x ∈ X als Funktionswert auftreten, noch muss die AbildungT eineindeutig sein.

2

Beispiel?. Es sei A = [aij ]i,j=1,...,N eine quadratische Matrix mit N Zeilen undSpalten, und b = [bi]i=1,...,N ∈ RN ein Vektor mit N Eintragen. Das lineareGleichungssystem

ai1x1 + · · ·+ aiNxN = bi, i = 1, . . . , N

lautet in Matrix-Vektor-FormAx = b.

Im Prinzip konnen wir es mit dem Gauß-Algorithmus (Gauß-Elimination) explizitlosen (sofern dies uberhaupt moglich ist). Ist N aber sehr groß, so kann diesrecht aufwendig sein. Schnelle Naherungsverfahren ergeben sich als einfacheFixpunktiteration fur die aquivalenten Fixpunktgleichungen

x = x−B−1(Ax− b),

wobei B eine geeignete invertierbare Matrix ist. Die rechte Seite definiert dannein Abbildung T (x) von RN nach RN .

Beispiel?. Wir betrachten die Differentialgleichung

y′(t) = y(t) + t · ey(t), y(0) = 0.

Gesucht ist eine differenzierbare Funktion y : [0, δ[→ R, welcher dieser Gleichunggenugt. Das ist keine einfache Aufgabe, aber wir konnen sie als Fixpunktgleichungformulieren:

y(t) =

∫ t

0

y(s) + s · ey(s) ds.

Die rechte Seite definiert eine stetige Funktion z(t), wenn y selbst stetig ist.Wir konnen daher die Abbildung T (y) := z der Menge X aller stetigen Funk-tionen in sich betrachten. Die Differentialgleichung wird dann zur abstraktenFixpunktgleichung y = T (y).

1 Der Brouwersche Fixpunktsatz

Der Brouwersche Fixpunktsatz ist ein reiner Existenzsatz, und behandelt dieFrage ob stetige Abbildungen von Kugeln in sich Fixpunkte besitzen. Er hateinen mehr topologischen als analytischen Charakter und ist daher besondersfaszinierend. Wir beweisen ihn fur die Ebene.

Funktionen eines abeschlossenen Intervalls in sich

Wir beginnen zunachst jedoch mit einem anschaulichen Satz, den man deneinfachsten Fixpunktsatz nennen konnte.

Satz 1 (Einfachster Fixpunktsatz). Eine stetige Funktion T , welche das Intervall[0, 1] in sich abbildet, besitzt midestens einen Fixpunkt.

3

Abbildung 2: Einfachster Fixpunktsatz

Dabei wollen wir uns hier und im Folgenden stillschweigend mit einer anschau-lichen Vorstellung des Begriffs der stetigen Funktion begnugen, dass sich namlichbei hinreichend kleiner Anderungen der Argumente x auch die Funktionswertef(x) nur entsprechend wenig anderen. Insbesondere stellen wir uns also denGraphen einer solchen Funktion als zusammenhangende Linie vor.2 Mit dieserAnschauung im Hinterkopf genugt ein Blick auf Abbildung 2 um sich von derGultigkeit des Satzes zu uberzeugen: jede stetige Funktionskurve, welche wir indas Einheitsquadrat einzuzeichnen versuchen, muss offenbar in mindestens einemPunkt die Diagonale schneiden, und sei es auch im Anfangs- oder Endpunkt(eine Funktionskurve jedem x genau y zuweisen muss).

Ein strenger Beweis ist diese Uberlegung zwar nicht, sie enthalt aber diekorrekte Idee, die dann in entsprechend mathematisch saubere Form zu gießenware. Dies wollen wir hier nicht tun, uberlegen uns aber, dass die Aussage desSatzes gleichbedeutend mit der Ausssage ist, dass die Gleichung

f(x) := T (x)− x = 0

im Intervall [0, 1] eine Losung besitzt. Da f ebenfalls stetig ist, und nach Voraus-setzung f(0) ≥ 0 sowie f(1) ≤ 0 gilt (da T das Intervall [0, 1] in sich abbildet),ist dies aber ebenso einsichtig und Inhalt des sogenannten Zwischenwertsatzes:

Satz 2 (Zwischenwertsatz). Eine stetige Funktion f von einem Intervall [a, b]in die reellen Zahlen mit f(a) ≥ f(b) nimmt alle Funktionswerte zwischen f(b)und f(a) auch tatsachlich an.

Abbildungen der Kreisscheibe in sich3

Der niederlandische Mathematiker Luitzen Brouwer veroffentlichte 1910 denBeweis eines Fixpunktsatzes, welcher Satz 1 in beliebige Dimensionen verall-gemeinert. Wir interessieren uns hier fur den zweidimensionalen Fall. Konkret

2Die exakte Definition lautet: f ist stetig in x, wenn es zu jeder Zahl ε > 0 eine Zahl δ > 0gibt, fur welche |x− y| < δ die Beziehung |f(x)− f(y)| < ε impliziert. Ist f in jedem Punkt xdes Definitionsbereichs stetig, so heißt f stetig.

3Nach Courant, Robbins:”Was ist Mathematik?“, Springer, Berlin, 1962.

4

betrachten wir nun stetige Abbildungen (oder Transformationen) T der abge-schlossenen Einheitskreisscheibe

D2 =

{x =

(x1x2

): x21 + x22 ≤ 1

}in sich. Beispiele solcher Transformation sind etwa die Spiegelung T (x) = −x,oder die folgende Abbildung, welche die Kreisscheibe um einen Winkel φ dreht,um den Faktor 1/2 schrumpft und schließlich um 1/2 nach rechts verschiebt:

T (x) = T (x1, x2) =1

2

(cosφ · x1 − sinφ · x2sinφ · x1 + cosφ · x2

)+

(1/2

0

). (3)

Wahrend die Spiegelung den Nullpunkt als einzigen Fixpunkt besitzt, ist fur diezweite Abbildung nicht so klar, warum sie uberhaupt einen Fixpunkt besitzensollte. Interessanterweise kann man beweisen, dass dies der Fall sein muss. Diesist der beruhmte Brouwersche Fixpunktsatz.

Satz 3 (Brouwerscher Fixpunktsatz, 1910). Jede stetige Abbildung der Kreis-scheibe D2 in sich besitzt mindestens einen Fixpunkt.

Ein weiteres, vielzitiertes Beispiel ist das folgende. Ruhren wir vorsichtigKaffee in einer Tasse derart, dass die Teilchen der Oberflache auf der Oberflachebleiben, so gibt es nach diesem Satz, zumindest im Gedankenexperiment, zujedem Zeitpunkt einen Punkt auf der Oberflache, welcher sich an genau derselbenStelle wie zu Beginn befindet.

Im Gegensatz zum Satz 1 ist der Brouwersche Fixpunktsatz nicht unmittel-bar einsichtig. Seine Faszination bezieht er außerdem aus der Tatsache, dasser ein reiner Existenzsatz ist, und einen uber die weitere Vorgehensweise zurBestimmung des Fixpunkts im Unklaren lasst.4 Dies hangt damit zusammen,dass sein Beweis, wie wir unten sehen werden, durch Widerspruch gefuhrt wird.Bevor wir dazu kommen, bemerken wir jedoch, dass die Existenz eines Fixpunktsleicht aus einer Tatsache folgt, die durchaus anschaulich einsichtig ist, auch wennihr strenger Beweis ebenso schwierig ist wie der des Fixpunktsatzes selbst. DieseTatsache lautet:

Satz 4 (Retraktionssatz). Es gibt keine stetige Abbildung einer Kreisschreibe aufihren Rand (d.h. jedem Punkt der Kreisscheibe wird ein Randpunkt zugeordnet),welche die Randpunkte selbst invariant lasst.

Denn stellen wir uns anschaulich die Kreisscheibe als eine uber die Kreislinieaufgespannte, dunne Membran vor, so musste eine Transformation dieser Mem-bran auf den Randkreis, bei welcher der Rand fest eingespannt bleibt, notwendigzum Zerreißen fuhren.5

4Dies ist fur die Transformation (3) nicht wirklich der Fall, da der Banachsche Fixpunktsatzweiter unten anwendbar ist und die einfache Fixpunktiteration somit konvergiert.

5Darf man umgekehrt die Membran vorher vom Kreisrand losen, so konnte man sichvorstellen sie unendlich dunn einzurollen (oder man projiziert die Kreispunkte auf ihre x-Koordinaten) und verbogen an den Ring zu heften, was durchaus eine stetige Transformationware.

5

Abbildung 3: Transformationsvektoren T (x) − x (nicht normiert) im Beweisdes Brouwerschen Satzes. Links sind auch die zugehorigen Tangentialvektorenan den Kreis zu sehen, welche sich offenbar genau einmal um ihren relativenUrsprung drehen.Grafik aus Courant, Robbins:

”Was ist Mathematik?“, Springer, Berlin, 1962.

Mit Hilfe des Retraktionssatzes lasst sich der Fixpunktsatz leicht beweisen.Angenommen, es gabe eine fixpunktfreie stetige Transformation T der Kreis-scheibe K in sich. Dann ware stets T (x) 6= x, sodass wir fur jeden Punkt x denSchnittpunkt S(x) des von T (x) durch x verlaufenden Strahls mit dem Rand derScheibe finden konnen. Die Abbildung x 7→ S(x) ist dann eine stetige Abbildung(wie man sich uberlegen kann) der Kreisscheibe auf ihren Rand, welche dieRandpunkte unverandert lasst, im Widerspruch zum Retraktionssatz. Daher istdie Annahme, T konne keinen Fixpunkt haben, nicht haltbar.

Da wir den Retraktionssatz nicht bewiesen haben, geben wir jetzt einenweiteren semi-strengen, dafur aber unabhangigen Beweis des BrouwerschenFixpunktsatzes.

Beweis von Satz 3

Wir nehmen wieder an, es gabe eine stetige Selbstabbildung T von D2 ohneFixpunkt. Dann ist fur jedes x der Transformationsvektor T (x)−x ungleich von

Null. Wir betrachten die normierten Transformationsvektoren V (x) = T (x)−x‖T (x)−x‖ ,

wobei die Notation ‖y‖ die (Euklidische) Lange eines Vektors y bezeichne. Ist xein Randpunkt des Kreises, so zeigt der Vektor V (x) von x aus betrachtet insInnere des Kreises, siehe Abbildung 3.

Wir bezeichnen den Rand des Kreises mit S1. Bewegen wir uns von einembeliebigen Randpunkt x1 ein wenig im Uhrzeigersinn zu einem Randpunkt x2, sokann die Winkelanderung zwischen den Vektoren V (x1) und V (x2) positiv odernegativ sein, und zwar je nachdem, ob sich V (x2) nach links oder rechts (relativzu V (x1)) gedreht hat. Betrachten wir sehr viele gleichmaßig im Uhrzeigersinnauf dem Kreis angeordnete Punkte x1,x2, . . . ,xN auf dem Kreis, so konnen wirdie entsprechenden Winkelanderungen (im Bogenmaß) benachbarter Vektorensummieren (Abbildung 3 rechts). Da wir nach einer Umdrehung in der Ausgangs-lage ankommen, ist diese Summe ein ganzzahliges Vielfaches des Kreisumfangs

6

2π. Lassen wir nun die Anzahl N der Punkte gegen unendlich streben, so wirdaus der Summe ein Integral uber infinitesimale Winkelanderungen. Den Wertdieses Integrals geteilt durch 2π nennen wir den Index von S1. Der Index nimmtals Grenzwert einen ganzzahligen Wert . . . ,−2,−1, 0,+1,+2, . . . an, welcher dieAnzahl der vollstandigen positiven und negativen Umdrehungen der V (x) umden (relativen) Nullpunkt bei einem vollstandigen Kreisumlauf bilanziert.

Wir beweisen jetzt, dass stets ind(S1) = +1 gilt, und zwar unabhangig vomStartpunkt x1. Um dies zu zeigen, vergleichen wir die Drehung der Vektoren V (x)mit derjenigen der zugehorigen Tangentialvektoren an den Kreis. Letztere drehensich offenbar genau einmal um ihren (relativen) Ursprung (siehe Abbildung 3links). Ware nun der Index von Eins verschieden, mussten sich die VektorenV (x) wahrend eines Umlaufs mindestens einmal vollstandig um die Tangentedrehen. Insbesondere mussten sie die Tangente

”uberholen“ oder sich von ihr

”uberholen“ lassen. So oder so mussten also wegen der Stetigkeit des Prozesses

der Vektor V (x) und die zugehorige Tangente an x zu einem Zeitpunkt in dieselbeRichtung zeigen. Dies ist unmoglich, da die V (x) stets ins Innere des Kreiseszeigen. Folglich ist ind(S1) = +1.

Auf die gleiche Weise konnen wir einen Index fur jeden vollstandig in D2

liegenden Kreis definieren. Solche Kreise konnen durch stetige Transformationenineinander uberfuhrt werden ohne D2 zu verlassen. Da auch das Vektorfeld V (x)stetig von x abhangt, wird der Index sich bei einer solchen Transformation stetigandern. Da der Index aber, wie gesehen, fur jeden Kreis nur einen ganzzahligenWert annehmen kann, folgt daraus schon, dass er fur jeden Kreis denselben Werthat, also +1 wie ind(S1) (eine stetige Funktion mit nur ganzzahligen Werten istkonstant!). Dies ist aber fur einen hinreichend kleinen Kreis ein Widerspruch,da die normierten Vektoren V (x) aufgrund der Stetigkeit auf einer kleinenUmgebung alle in ungefahr dieselbe Richtung zeigen (Extremfall: lassen wir denKreis zu einem Punkt schrumpfen, sollte der Index Null werden). Somit war dieAnnahme, T konne keinen Fixpunkt haben, falsch.

Bemerkung. Der Brouwersche Fixpunktsatz ist nicht auf eine oder zwei Di-mensionen beschrankt, sondern gilt fur Kugeln beliebiger Dimension. Etwa imdreidimensionalen Raum: Jede stetige Abbildung der dreidimensionalen abge-schlossenen Einheitskugel in sich besitzt mindestens einen Fixpunkt. Der Beweisist jedoch ungleich schwieriger.

2 Der Banachsche Fixpunktsatz

Der Brouwersche Fixpunktsatz ist elegant und faszinierend, gibt aber keineMethode an, wie ein Fixpunkt gefunden werden kann. Hierzu sind denn auchweitere Voraussetzungen und strengere Begriffsbildungen notwendig. Der indiesem Abschnitt vorgestellte Banachsche Fixpunktsatz gibt ein Kriterium dafur,wann die einfache Fixpunktiteration (2) gegen einen Fixpunkt konvergiert undbildet als Grundlage zahlreicher numerischer Verfahren eines der wichtigstenVerbindungsstucke der mathematischen Analysis zu ihren Anwendungen.

7

Abbildung 4: Abbildung der Welt X in eine Karte innerhalb von X.

Das Landkartenproblem

Wir betrachten als Beispiel das folgende Problem. Auf einem Tisch liege eineLandkarte, welche insbesondere den Raum mit dem Tisch beinhaltet. Betrachtenwir etwa einen Tisch in diesem Horsaal, so konnte es sich um eine Karte desGebaudes, Bonns, Deutschlands oder der Welt handeln. Wir behaupten:

Auf der fixierten Karte gibt es genau einen Punkt, welcher genau uber demvon ihm markierten Punkt der Welt liegt.

Anders formuliert:

Es gibt genau einen Punkt auf der Karte, durch den man eine (unendlichdunne) Nadel stechen kann, so dass das entstandene Loch in der Karte exakt diePosition des Einstichs in den Tisch markiert.

Daruberhinaus behaupten wir, dass dieser Punkt durch folgenden Algorith-mus gefunden werden kann (genau genommen, kann er lediglich beliebig gutangenahert werden):

• Wir stechen in einen beliebigen Punkt x0 der Karte eine Nadel derart, dasssie im Tisch stecken bleibt.

• Mit einer weiteren Nadel stechen wir in denjenigen Punkt x1 der Karte,welcher die Position des Einstichs der Nadel durch x0 markiert.

• Mit einer dritten Nadel stechen wir in denjenigen Punkt x2 der Karte,welcher die Position des Einstichs der Nadel durch x1 markiert usw. usf.

Wir werden zeigen, dass die Folge xn der Nadeleinstiche fur n → ∞ danngegen einen gewunschten Punkt x∗ konvergiert. Dieser zeichnet sich geradedadurch aus, dass der Algorithmus in ihm stationar wird, das heißt, stets nurnoch denselben Punkt erzeugt.

Formulieren wir das Problem zunachst etwas mathematischer. Der von derKarte dargestellte Teil der Welt sei die Menge X. Jedem Punkt x von X entsprichtgenau ein Punkt auf der Karte. Da aber die Karte fest auf einem Tisch in Xliegt, ist dieser Punkt also (wurde man ihn etwa mit einer Nadel durchstechen)

8

insbesondere ein”realer“ Punkt T (x) in X. Auf diese Weise erhalten wir also

die SelbstabbildungT : X→ X,

welche jedem Punkt x von X den entsprechenden Punkt T (x) in X zuordnet,uber dem der zu x gehorige Kartenpunkt liegt, siehe Abbildung 4. Alle T (x)sind also insbesondere Punkte des Tisches.

Der gesuchte Punkt x∗ der Karte, welcher seine eigene Position markiert, istoffenbar durch die Fixpunktgleichung

T (x∗) = x∗

charakterisiert. Der vorgeschlagene Algorithmus erzeugt, ausgehend von einembeliebigen Startpunkt x0, Punkte gemaß der Vorschrift

xn+1 = T (xn), n = 0, 1, 2, . . . ,

entspricht als der einfachen Fixpunktiteration (2). Unsere Behauptungen lauten,dass es nur einen Fixpunkt x∗ gibt, und dass die Folge xn gegen x∗ strebt,unabhangig davon, wie wir x0 wahlen.

Einige Voruberlegungen

Ist X nicht gerade die gesamte Erdoberflache, so konnten wir uns X einfachals kreisformigen Teil einer Ebene vorstellen. Denn da die hierfur notwendigeVerzerrung der Kugeloberflache auf die Ebene eineindeutig und stetig ware,ware an der ursprunglichen Aufgabenstellung nichts geandert (Ubungsaufgabe).Die Transformation T von X auf die Karte ist offenbar stetig, und somit folgtdie Existenz eines Fixpunktes x∗ aus dem Brouwerschen Fixpunktsatz. ZurEindeutigkeit ist dabei aber noch nichts gesagt, und auch nicht zur Konvergenzder einfachen Fixpunktiteration.

Tatsachlich liegt noch eine entscheidende Zusatzeigenschaft vor: Die Abbil-dung T ist eine Kontraktion, das heißt es gibt eine Zahl 0 ≤ L < 1 (namlich denMaßstab der Karte), sodass fur beliebige zwei Punkte x,y aus X gilt:

Abstand(T (x), T (y)) ≤ L ·Abstand(x,y).

Daraus folgt aber schon, dass es hochstens einen Fixpunkt geben kann, dennzwei Fixpunkte x,y mit Abstand(x,y) 6= 0 ergaben den Widerspruch

Abstand(x,y) = Abstand(T (x), T (y)) ≤ L ·Abstand(x,y) < Abstand(x,y),

da L < 1. Wenn wir daher zeigen konnen, dass T uberhaupt einen Fixpunktbesitzt, so folgt bereits, dass es genau einen gibt.

Desweiteren genugt es zu zeigen, dass unsere durch xn+1 = T (xn) erzeug-te Naherungsfolge einen Grenzwert x∗ besitzt, also xn → x∗ (das bedeutetAbstand(xn,x∗)→ 0 fur n→∞). Denn da T stetig ist, folgt dann mit

T (x∗) = limn→∞

T (xn) = limn→∞

xn+1 = x∗, (4)

dass x∗ ein gesuchter Fixpunkt ist. Die Existenz eines Grenzwertes der Folge (2)ist die eigentliche Kernaussage des Banachschen Fixpunktsatzes, und enthalt inunserem Fall die ziemlich tiefliegende Modellannahme der Vollstandigkeit unsererWelt. Dies wird jetzt genauer erlautert.

9

Banachscher Fixpunktsatz

Um einen Eindruck der mathematischen Abstraktionsfahigkeit zu erhalten, leitenwir den Banachschen Fixpunktsatz in einem vergleichsweise allgemeinen Rahmenher. Dazu einige formale Definitionen.

Definition 2 (Abstandsmaß und metrischer Raum). Ein Abstandsmaß (oderauch eine Metrik) auf einer Menge X ist eine Funktion d(x,y), welche je zweiElementen x,y aus X eine Zahl (ihren Abstand) zuordnet, und zwar derart,dass fur alle x,y, z aus X folgendes gilt:

1. d(x,y) ≥ 0 und d(x,y) = 0 genau dann, wenn x = y,

2. d(x,y) = d(y,x),

3. d(x,y) ≤ d(x, z) + d(z,y). (”

Dreiecksungleichung“)

Eine Menge X, auf welcher ein Abstandsmaß definiert ist, heißt metrischerRaum.

Definition 3 (Cauchyfolge und Vollstandigkeit). Eine Folge (xn)n∈N in einemmetrischen Raum heißt Cauchyfolge, falls es zu jedem ε > 0 ein Nε ∈ N gibt,sodass

d(xm,xn) < ε fur alle m,n ≥ Nε.

Ein metrischer Raum heißt vollstandig, wenn jede Cauchyfolge einen Grenzwertx∗ in X besitzt.6

Der Begriff der Cauchyfolge mag zunachst schwer verstandlich und unnotigkompliziert erscheinen. Er besagt anschaulich, dass es zu jeder reellen Zahl ε > 0ein Folgenglied xn gibt, sodass alle weiteren Folgenglieder im Abstand ε zu xnverbleiben. Da hierbei ε beliebig klein sein kann, wird klar, dass die Folgengliederfur genugend große n in beliebig kleinen Umgebungen gefangen sind, und dieFolge somit einen Grenzwert haben muss, sofern die Menge X

”keine Locher“

enthalt, siehe Abbildung 5. Genau dies ist mit Vollstandigkeit gemeint.

Beispiel. Der Zahlenstrahl R ist vollstandig bzgl. des naturlichen Abstandsma-ßes d(x, y) = |x− y|.

Beispiel. Die Ebene R2 ist vollstandig bzgl. des naturlichen Abstandsmaßd(x,y) =

√(x1 − y1)2 + (x2 − y2)2.

Dass es sich um Abstandsmaße handelt, ist Ubungsaufgabe. Die Vollstandigkeitin diesen Beispielen ist nicht so einsichtig und gilt genau genommen per Definitionder reellen Zahlen selbst, worauf wir hier aber nicht weiter eingehen konnen.

Den Begriff der Kontraktion haben wir im Prinzip schon erlautert:

6Wir gehen zwar von einer intuitiven Vorstellung des Grenzwertbegriffs aus, die genaueDefinition lautet jedoch: x∗ heißt Grenzwert der Folge (xn)n∈N (bzw. (xn) konvergiert gegenx∗), falls fur jede Zahl ε > 0 ein Index Nε existiert, sodass d(xn,x∗) ≤ ε fur alle n ≥ Nε gilt.Einfacher formuliert: die Folge d(xn,x∗) der Abstande zu x∗ konvergiert gegen Null.

10

Abbildung 5: Cauchyfolge in der Ebene

Definition 4. Es sei X ein metrischer Raum mit Abstandsmaß d. Eine Abbil-dung T von X in sich heißt Kontraktion (oder kontrahierend), wenn es eineZahl 0 ≤ L < 1 gibt, sodass fur alle x,y aus X gilt:

d(T (x), T (y)) ≤ L · d(x,y).

Wir haben jetzt alle notwendigen Begriffe um den Banachschen Fixpunktsatzzu formulieren. Er bezieht sich im Vergleich zum Brouwerschen Fixpunktsatzauf kontrahierende Abbildungen.

Satz 5 (Banachscher Fixpunktsatz, 1922). Ist X ein vollstandiger, metrischerRaum, und T eine Kontraktion von X in sich, so besitzt T genau einen Fixpunktx∗ in X, und die einfache Fixpunktiteration xn+1 = T (xn) konvergiert gegendiesen Fixpunkt fur jeden Startwert x0.

Beweis. 1) Eindeutigkeit. Das Argument haben wir oben bereits gebracht: gabees zwei Fixpunkte x∗ 6= y∗, so ware

d(x∗,y∗) = d(T (x∗), T (y∗)) ≤ L · d(x∗,y∗),

was wegen 0 ≤ L < 1 den Schluss d(x∗,y∗) = 0 nach sich zieht, also x∗ = y∗(gemaß Eigenschaft 1 des Abstandsmaßes) im Widerspruch zur Annahme.

2) Existenz. Gemaß unserer Voruberlegungen weiter oben, genugt es zu zeigen,dass die Folge (xn) uberhaupt einen Grenzwert x∗ in X besitzt. Denn da T stetigist, muss dieser Grenzwert x∗ = T (x∗) erfullen (siehe (4)). Da X weiterhin alsvollstandig vorausgesetzt ist, muss fur die Existenz eines Grenzwertes lediglichgezeigt werden, dass die Folge (xn) eine Cauchyfolge ist.

Sei dazu ein ε > 0 beliebig vorgegeben. Zunachst ist

d(xn+1,xn) = d(T (xn), T (xn−1)) ≤ L · d(xn,xn−1) ≤ · · · ≤ Lnd(x1,x0).

11

Fur beliebige m > n folgt dann mit der Dreiecksungleichung (Eigenschaft 3 desAbstandsmaßes):

d(xm,xn) ≤ d(xm,xm−1) + d(xm−1,xn)

≤ d(xm,xm−1) + d(xm−1,xm−2) + d(xm−2,xn)

≤ . . .≤ d(xm,xm−1) + d(xm−1,xm−2) + · · ·+ d(xn+1,xn)

≤ Lm−1d(x1,x0) + Lm−2d(x1,x0) + · · ·+ Lnd(x1,x0)

= (Lm−1 + Lm−2 + · · ·+ Ln)d(x1,x0)

= Ln(1 + L+ L2 + · · ·+ Lm−1−n)d(x1,x0)

≤ Ln(

1

1− L

)d(x1,x0).

(5)

Die letzte Ungleichung kommt durch die geometrische Reihe zustande und isteine Ubungsaufgabe.

Der Faktor(

11−L

)d(x1,x0) in der letzten Zeile von (5) ist eine feste positive

Zahl. Der Term Ln hingegen wird fur große n immer kleiner, da L < 1. Ins-besondere gibt es ein Nε, sodass Ln < ε

( 11−L )d(x1,x0)

fur n ≥ Nε, also wird (5)

zud(xm,xn) < ε fur m > n ≥ Nε.

Dies zeigt, dass (xn) eine Cauchyfolge ist (siehe Definition 3), denn die Bedingungm > n ist unwesentlich, da man im Fall m < n einfach die Bezeichnungenvertauschen kann, und im Fall m = n sowieso d(xn,xn) = 0 gilt.

Der Beweis ist damit beendet.

Bemerkung. Die Abschatzung (5) gibt uns auch Aufschluss daruber, wieschnell die Folge (xn) gegen den Fixpunkt konvergiert. Denn lassen wir auf derlinken Seite m gegen unendlich streben, so ergibt sich aus der Stetigkeit desAbstandsmaßes (welche wiederum eine Folge der Dreiecksungleichung ist), dass

d(xn,x∗) ≤ Ln(

1

1− L

)d(x1,x0).

Man beachte, dass wir im Landkartenproblem als d den Abstand in der realenWelt gewahlt haben, welcher unabangig vom gewahlten Kartenausschnitt ist.Hingegen ist der Maßstab L umso kleiner je grosser der abgebildete Ausschnittder Welt. Es ergibt sich somit interessanterweise, dass der sich selbst markierendePunkt auf einer Weltkarte schneller gefunden werden kann, als etwa auf einemStadtplan.

Bemerkung. Ist T eine stetige Abbildung von X in sich, aber keine Kontraktion,so kann es naturlich dennoch der Fall sein, dass i) nur ein Fixpunkt existiert,und/oder dass ii) der Algorithmus xn+1 = T (xn) immer noch funktioniert. Eswird dann allerdings eventuell vom Startwert x0 abhangen.

12