« vorheriger Beitrag  · nächster Beitrag »

24.10.08 · 19:17 Uhr

Topologie von Flächen XXXVII

Kategorie: Naturwissenschaften  ·  Kommentare: 3

Gebe eine Zahl unter 20 in den Taschenrechner ein und drücke abwechselnd wiederholt auf die Tasten exp und 1/x. Die Ergebnisse pendeln sich auf 0,56714.. ein.

Zum Beispiel mit Startwert 10:
nach den ersten beiden Schritten hat man 0.000045399
nach den nächsten beiden 0.999954601
nach zwei weiteren 0.367896142
nach zwei weiteren 0.692189066
nach den nächsten beiden dann 0.500479286
und danach 0.606240027
als nächstes 0.545397699
danach dann 0.579611226, 0.560116082, 0.57114276, 0.564879547, 0.568428611, ..

Oder mit Startwert 5:
nach den ersten beiden Schritten hat man 0.006737946
nach den nächsten beiden 0.993284702
nach zwei weiteren 0.370358174
nach zwei weiteren 0.690486971
nach den nächsten beiden dann 0.501331875
und danach 0.605723374
als nächstes 0.54679553
danach dann 0.579447883, 0.56020758, 0.571090504, 0.564909067, 0.568411831, ..

(Das Beispiel stammt aus einem Skript von C.Brand.)

Was steckt dahinter, was hat man hier eigentlich berechnet?

Wie sich zeigen wird: die Lösung von 1/exp(x)=x,
mit anderen Worten den Fixpunkt der Funktion f(x)=1/exp(x).

f:[0,20]-->[0,20] definiert durch
f(x)=1/exp(x)
hat nach der 1-dimensionalen Version des Brouwerschen Fixpunktsatzes einen Fixpunkt, wie jede stetige Funktion. Wie man diesen tatsächlich berechnen kann, hatten wir in den letzten beiden Wochen besprochen. (Im 1-dimensionalen Fall ist es natürlich einfacher.)

f ist aber nicht nur stetig, sondern sogar "kontrahierend" (abstände-verringernd). Und für kontrahierende Abbildungen gibt es ein effizienteres Verfahren zur Berechnung von Fixpunkten: man starte mit einem beliebigen Startwert und wende immer wieder f an. (Das ist genau das, was wir oben im Beispiel gemacht haben.) Die so produzierte Folge konvergiert gegen den Fixpunkt (d.h. nähert ihn beliebig gut an).

Im Beispiel: die Folge x, f(x), f(f(x)), f(f(f(x))),... nähert sich dem Fixpunkt von f, d.h. der (eindeutigen) Lösung der Gleichung 1/exp(x)=x.
Wir haben also berechnet, daß 0.56.. die Lösung dieser Gleichung ist.

Fixpunktsätze sind oftmals das Mittel der Wahl, um zu zeigen, dass ein kompliziertes Gleichungssystem Lösungen hat, wenn man nicht in der Lage ist, "auf direktem Wege" eine zu finden.
Aufgrund des Erfolgs, den man mit einem solchen Vorgehen hat, gibt es auch entsprechend viele Varianten von Fixpunktsätzen und artverwandten Konzepten, die einem die Lösbarkeit diverser Gleichungen sichern.
Die Methode, die wir hier eben benutzt haben, geht auf den Beweis des Banach'schen Fixpunktsatzes zurück: für kontrahierende Abbildungen gibt es einen eindeutigen Fixpunkt, und diesen kann man berechnen als Grenzwert der Folge x, f(x), f(f(x)), f(f(f(x))),...

Ein anderes Beispiel, das schon den Babyloniern bekannt war, ist die Berechnung der Wurzel aus 2. Natürlich könnte man diese mit dem Zwischenwertsatz näherungsweise berechnen (vgl. TvF 35). Eleganter (und vor allem effizienter) ist aber Heron's Verfahren:

Die Wurzel aus 2 ist natürlich die Lösung von x²=2 und diese Gleichung kann man auf scheinbar kompliziertere Weise auch schreiben als x=0.5(x+2/x).
(Wer's nachprüfen will: die zweite Gleichung gibt 2x=x+2/x, also x=2/x, also x²=2.)
Man will also den Fixpunkt von f(x)=0.5(x+2/x) bestimmen.

f ist kontrahierend. (Leichte Rechnung: |f(x) - f(y)| = |(x-y)/2+1/x-1/y| = |(x - y)/2+(y-x)/xy| = |(x - y)/2 + (y - x)/(xy)| = |x - y||1/2 - 1/(xy)| < 1/2 |x - y| für x, y ≥ 1.)

Daraus folgt - mit dem Banach'schen Fixpunktsatz - daß f genau einen Fixpunkt in
{x ∈ IR: x ≥ 1} besitzt. Das ist dann die Wurzel aus 2. Und berechnen kann man ihn, indem man die Funktion iteriert (d.h. mit irgendeinem Wert startet und immer wieder f anwendet).
Wenn man z.B. mit 1 anfängt, bekommt man:
1, 3/2=1.5, 17/12=1.4166.., 577/408=1.4142..
also recht gute Näherungen für die Wurzel aus 2. (Heron selbst hatte übrigens nur den Näherungswert 17/12 berechnet.)

Auf ähnliche Weise kann man natürlich auch Quadratwurzeln irgendwelcher anderer Zahlen berechnen. Einige Beispiele werden hier vorgerechnet.

Heron von Alexandria

Allgemein funktioniert dieses Verfahren für alle kontrahierenden Funktionen, d.h. es muß gelten: |f(x) - f(y)| < L |x - y| für irgendeine Zahl L zwischen 0 und 1. Wenn diese Bedingung gilt, dann wird die Folge x, f(x), f(f(x)), f(f(f(x))),... gegen den (eindeutigen) Fixpunkt von f konvergieren, egal welchen Startpunkt x man wählt.

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36

 

Autor: Thilo· 3 Kommentare· Permalink· Trackback-URL

Tags: banach· fixpunkt· heron· iteration· kontrahierend· quadratwurzel