Mathe für Nicht-Freaks: Konvergenz rekursiver Folgen beweisen

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

In diesem Kapitel werde ich dir zeigen, wie du Konvergenzbeweise für rekursive Folgen führen kannst. Hier werden wir eine gute Anwendung des Monotoniekriteriums kennenlernen.

Problemstellung

Nehme folgende Aufgabe:

Die Anwendung der Epsilon-Definition der Konvergenz ist in dieser Aufgabe schwierig. Weil die Folge $(a_n{)}_{n\in \mathbb{N}}$ rekursiv definiert ist, können wir ihren Grenzwert nicht direkt ablesen. Auch sind im Allgemeinen Abschätzungen für den Term $|a-a_n|$ mit einer reellen Zahl schwierig, weil wir keine explizite Form des Folgenglieds $a_n$ kennen.

Lösungsstrategien

In diesem Kapitel werde ich dir die folgenden zwei Lösungswege präsentieren, um die Konvergenz einer Folge zu zeigen:

1. Explizite Bildungsvorschriften: Man kann versuchen, eine explizite Bildungsvorschrift der gegebenen Folge zu bestimmen, um mit dieser das Konvergenzverhalten der Folge weiter zu untersuchen.
2. Monotoniekriterium verwenden: Wenn die rekursiv gegebene Folge konvergieren sollte, kann man versuchen, das Monotoniekriterium anzuwenden. Nachdem die Konvergenz der Folge bewiesen wurde, kann man dieses Wissen nutzen, um den Grenzwert der Folge zu bestimmen.

Lösungsweg: Explizite Bildungsvorschrift finden

Eine mögliche Lösungsstrategie ist die, eine explizite Bildungsvorschrift von $(a_n{)}_{n\in \mathbb{N}}$ zu bestimmen.

Hier bietet es sich an, die ersten Folgenglieder rekursiv auszurechnen. Dies ist generell empfehlenswert, um ein Gefühl für das Konvergenzverhalten der Folge zu bekommen. Die ersten Folgeglieder lauten:

Aufgrund dieser Liste der ersten Folgenglieder können wir vermuten, dass die Folge gegen $1$ konvergiert. Für die explizite Bildungsvorschrift müssen wir eine Zuordnungsvorschrift $n\mapsto a_n$ finden. Wir suchen also einen Term $f(x)$ für den gilt:

Wir sehen, dass der Nenner jeweils eine Potenz von $2$ ist. Außerdem ist der Zähler jeweils die Vorgängerzahl des Nenners. Es ist also

Anhand dieser Beispiele liegt die Vermutung nahe, dass wir $f(n)=\frac{2^n-1}{2^n}$ wählen können. Es sollte also gelten:

Diese Vermutung müssen wir noch beweisen. Hier bietet sich wie in vielen anderen Beispielen die vollständige Induktion an. Im Induktionsanfang haben wir:

Den Induktionsschritt von $n$ nach $n+1$ können wir nach Anwendung des Rekursionsschritts führen:

Damit haben wir $a_n=1-{\left(\frac{1}{2}\right)}^n$ gezeigt. Nun können wir das Konvergenzverhalten mit den Mitteln untersuchen, die wir bereits kennengelernt haben. Beispielsweise haben wir bereits $\underset{n\to \mathrm{\infty }}{\lim }{\left(\frac{1}{2}\right)}^n=0$ bewiesen und damit können wir die Grenzwertsätze anwenden, um die Konvergenz der Folge zu beweisen:

Alternative Möglichkeit: Folge in Teleskopreihe umformen und Bildungsvorschrift berechnen

Die explizite Bildungsvorschrift einer rekursiven Folge kann manchmal sehr kompliziert sein. In diesem Fall gibt es eine andere Möglichkeit diese zu bestimmen. Diese Methode ist insbesondere dann möglich, wenn die rekursive Bildungsvorschrift die beiden vorherigen Glieder beinhaltet. Betrachten wir das Beispiel

Betrachten wir die Differenz zweier aufeinanderfolgender Glieder $a_n$ und $a_{n-1}$, so erhalten wir

Führen wir denselben Schritt erneut durch, so erhalten wir

In jedem Schritt kommt also $-\frac{1}{2}$ als Vorfaktor hinzu. Nach insgesamt $n-1$ Schritten erhalten wir

Damit können wir nun noch nicht den Grenzwert berechnen, da wir „nur“ eine Bildungsvorschrift für $a_n-a_{n-1}$ und noch nicht für $a_n$ haben. Diese erreichen wir, wenn wir die (Teleskop-)Summe über $a_k-a_{k-1}$ bilden:

Auf der rechten Seite ergibt sich die geometrische Summe

Damit erhalten wir die explizite Darstellung

Mit $\underset{n\to \mathrm{\infty }}{\lim }(-\frac{1}{2}{)}^n=0$ und den Rechenregeln für Folgen gilt

Lösungsweg: Monotoniekriterium anwenden

Schritt 1: Beweis der Konvergenz

Was machen wir, wenn wir keine explizite Bildungsvorschrift der Folge finden? In manchen Fällen kann das Monotoniekriterium helfen. Dieses Kriterium lautet:

Dementsprechend reicht es aus, wenn wir die Beschränktheit und die Monotonie der Folge zeigen. Schauen wir uns zunächst die ersten Folgeglieder an, um eine Vermutung über die Eigenschaften der Folge zu bekommen:

Die Folge scheint monoton zu steigen. Außerdem sieht es so aus, als ob die Folge nach oben durch $1$ beschränkt ist.

Die Monotonie können wir induktiv beweisen. Hier zeigen wir zunächst im Induktionsanfang, dass $a_1\ge a_0$ ist:

Der Induktionsschritt von $n$ nach $n+1$ ist:

Damit ist das monotone Wachstum der Folge bewiesen. Auch die Beschränktheit der Folge nach oben durch $1$ kann mit Hilfe vollständiger Induktion gezeigt werden. Hier ist wegen $a_0=0$ der Induktionsanfang $a_0\le 1$ direkt gegeben. Im Induktionsschritt haben wir:

Damit ist die Folge $(a_n{)}_{n\in \mathbb{N}}$ nach oben durch $1$ beschränkt. Jetzt können wir auch die Konvergenz zeigen: Weil die Folge monoton steigt und nach oben beschränkt ist, konvergiert die Folge nach dem Monotoniekriterium.

Schritt 2: Grenzwert bestimmen

Um den Grenzwert der rekursiven Folge zu bestimmen, können wir die gerade bewiesene Konvergenz ausnutzen. Wir wissen so nämlich, dass es ein $a\in ℝ$ mit $\underset{n\to \mathrm{\infty }}{\lim }{a}_n=a$ gibt, wobei uns der exakte Wert von $a$ noch unbekannt ist.

Um $a$ zu bestimmen, betrachten wir den Limes $\underset{n\to \mathrm{\infty }}{\lim }{a}_{n+1}$. Auch dieser Grenzwert ist $a$ und somit erhalten wir

Der Wert $a$ muss damit die Gleichung $a=\frac{1}{2}a+\frac{1}{2}$ erfüllen. Aufgrund dieser Bedingung können wir den exakten Wert von $a$ bestimmen:

Damit ist $a=1$ der Grenzwert der Folge $(a_n{)}_{n\in \mathbb{N}}$.

Anwendungsbeispiel: Babylonisches oder Heronisches Wurzelziehen

Die ersten Folgeglieder der babylonischen Wurzelfolgen zur Berechnung von $\sqrt{2}$ mit den Startwerten $x_0=2$, $x_0=4$ und $x_0=8$.

Die Folgenglieder der babylonischen Wurzelfolge mit dem Startwert $a_0=\frac{1}{4}$.

Mit der babylonischen Wurzelfolge möchte ich dir ein Beispiel vorstellen, bei dem die Konvergenz einer rekursiven Folge mit Hilfe des Monotoniekriteriums bewiesen wird. Sie ist eine rekursiv definierte Folge, mit der sich ein Näherungswert für die Quadratwurzel einer Zahl bestimmen lässt und die von Computern zur Quadratwurzelbestimmung benutzt wird. Es gilt nämlich folgender Satz:

Übungsaufgabe

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}