Fixpunktiteration

Wie zeigt man, dass die Folge

\(x_{n+1}=1+\dfrac{1}{x_n}, \quad x_0=1 \)

konvergiert? Man trifft diese Aufgabe bisweilen in Analysis vor der Differentialrechnung. Leider ist sie an dieser Stelle nur umständlich zu lösen und taugt höchstens als Hartnäckigkeitstest. Ohne anständiges Werkzeug können halt die einfachsten Aufgaben schwierig werden.

Die Software Euler kann einen sogenannten „Webplot“ erzeugen. Das Kommando dazu ist

>fwebplot(„1+1/x“,0.5,2.5,1,10);

Man sieht, dass die Iteration um den Fixpunkt

\(x = f(x) = 1 + \dfrac{1}{x} \)

alterniert.

Leider ist anscheinend auch die Nutzung von Software verpönt, so dass man die Sache also rein analytisch angehen muss, ohne einen Hinweis zu haben. Erfahrungsgemäß verwenden Studenten nicht einmal einen Taschenrechner, um eine Idee zu bekommen, was da passiert. In der Klausur ist ja auch kein Taschenrechner erlaubt.

Wenn man also nichts außer der Analysis hat, dann sollte man wenigstens gute Methoden verwenden. f ist nämlich stetig, und wenn x ein Grenzwert der Iteration ist, so muss also gelten

\(x = \lim x_{n+1} = \lim (1+\dfrac{1}{x_n}) = 1 + \dfrac{1}{\lim x_n} = 1 + \dfrac{1}{x} \)

Daraus erhält man sofort

\(x = \dfrac{1 + \sqrt{5}}{2} \)

wenn man beachtet, dass die Iteration immer im Positiven bleibt, so dass x>0 sein muss. Um zu zeigen, dass dies tatsächlich der Grenzwert ist, verwendet man immer den Mittelwertsatz der Differentialrechung.

\(x_{n+1}-x = f(x_n)-f(x) = f'(\xi_n) (x-x_n) = – \dfrac{1}{\xi_n^2} (x-x_n) \)

Man sieht nun leicht ein, dass die Differenz das Vorzeichen wechselt, und immer kleiner wird. Damit ist die Folge der geraden Glieder streng monoton wachsend und kleiner als x, und die Folge der ungeraden streng monoton fallend und größer als x. Beide Folgen konvergieren also. Um zu zeigen, dass sie tatsächlich gegen x konvergieren, kann man nun verwenden, dass ab n=3

\(|x_{n+1} – x| \le \dfrac{1}{x_3^2} |x_n-x| \)

ist, und dies eine echte Kontraktion ergibt. Damit hat man sogar die geometrische Konvergenzrate erkannt.

In Fällen von einseitiger Konvergenz kann man statt dessen einfach argumentieren, dass die Folge nur gegen x konvergieren kann. Ein Beispiel ist

\(x_{n+1} = \dfrac{1}{2} \left( x_n + \dfrac{2}{x_n} \right), \quad x_0=2 \)

was streng monoton fallend gegen die Wurzel aus 2 konvergiert. Zugegebenermaßen ist hier die Argumentation mit der Ableitung nicht ganz so einfach. Man muss induktiv zeigen, dass die Folge tatsächlich rechts von Wurzel 2 bleibt.

In keinem dieser Fälle ist es aber notwendig, die Ausdrücke algebraisch auszurechen, und komplexe, einfallsreiche Abschätzungen zu verwenden, wie man das so gerne in Musterlösungen sieht.

Übrigens kann man mit demselben Trick oft die Monotonie einer Folge beweisen. Es gilt nämlich für eine Fixpunktiteration

\(x_{n+2}-x_{n+1} = f'(\xi_n) (x_{n+1}-x_n) \)

Wenn die Ableitung überall positiv ist, so bleibt das Vorzeichen der Differenz gleich.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.