Grenzwert rekursiver Folgen

Grenzwert rekursiver Folgen

Oberstufe
an+1=f(an), lim⁡n→∞an=a  ⇒  a=f(a)a_{n+1} = f(a_n),\ \lim_{n \to \infty} a_n = a \;\Rightarrow\; a = f(a)

Voraussetzung: ff stetig in a;a; Konvergenz von (an)(a_n) vorher nachgewiesen

ana_n
Glieder der rekursiv definierten Folge
ff
Funktion, die aus einem Glied das nächste berechnet
aa
Grenzwert der Folge, ein Fixpunkt von f
nn
Index der Folgenglieder

Konvergiert eine Folge mit a(n+1) = f(a(n)) und ist f stetig, dann ist ihr Grenzwert ein Fixpunkt von f, also a = f(a).

Erklärung

Eine rekursive Folge an+1=f(an)a_{n+1} = f(a_n) legt jedes Glied über das vorige fest. Konvergiert sie gegen aa, dann konvergiert auch (an+1)(a_{n+1}) gegen aa. Ist ff stetig, darf man den Grenzwert in ff hineinziehen:

a=lim⁡n→∞an+1=lim⁡n→∞f(an)=f(lim⁡n→∞an)=f(a)a = \lim_{n \to \infty} a_{n+1} = \lim_{n \to \infty} f(a_n) = f\left(\lim_{n \to \infty} a_n\right) = f(a)

Der Grenzwert ist also ein Fixpunkt von ff. Das Verfahren hat zwei Schritte:

  1. Konvergenz nachweisen, meist mit dem Monotoniekriterium: Monotonie und Beschränktheit per vollständiger Induktion zeigen.
  2. Fixpunktgleichung a=f(a)a = f(a) lösen und den passenden Fixpunkt auswählen. Dabei hilft: Gilt an≥ca_n \geq c für alle nn, dann auch a≥ca \geq c.

Die Gleichung a=f(a)a = f(a) sagt nur, welche Werte als Grenzwert infrage kommen. Ob die Folge überhaupt konvergiert, sagt sie nicht.

Beispiele

a1=0a_1 = 0, an+1=12an+1a_{n+1} = \frac{1}{2} a_n + 1: Die Glieder sind 0; 1; 1,5; 1,75; …0;\ 1;\ 1{,}5;\ 1{,}75;\ \ldots Per Induktion gilt an=2−22−na_n = 2 - 2^{2-n}, die Folge wächst also und ist durch 22 beschränkt. Aus a=12a+1a = \frac{1}{2} a + 1 folgt a=2a = 2.

Heron-Verfahren für 3\sqrt{3}: a1=2a_1 = 2, an+1=12(an+3an)a_{n+1} = \frac{1}{2}\left(a_n + \frac{3}{a_n}\right). Die Glieder sind 2; 1,75; 9756≈1,7321; …2;\ 1{,}75;\ \frac{97}{56} \approx 1{,}7321;\ \ldots

  • Beschränkt: an+1−3=(an−3)22an≥0a_{n+1} - \sqrt{3} = \frac{(a_n - \sqrt{3})^2}{2 a_n} \geq 0, also an≥3a_n \geq \sqrt{3} für alle nn.
  • Fallend: an+1−an=3−an22an≤0a_{n+1} - a_n = \frac{3 - a_n^2}{2 a_n} \leq 0, weil an2≥3a_n^2 \geq 3.

Die Folge konvergiert. Aus a=12(a+3a)a = \frac{1}{2}\left(a + \frac{3}{a}\right) folgt a2=3a^2 = 3, also a=±3a = \pm\sqrt{3}. Da alle Glieder positiv sind, ist a=3a = \sqrt{3}.

a1=12a_1 = \frac{1}{2}, an+1=an2a_{n+1} = a_n^2: Die Fixpunktgleichung a=a2a = a^2 hat die Lösungen 00 und 11. Die Glieder 12; 14; 116; …\frac{1}{2};\ \frac{1}{4};\ \frac{1}{16};\ \ldots fallen und sind positiv, die Folge konvergiert also. Wegen a≤a1=12a \leq a_1 = \frac{1}{2} kommt nur a=0a = 0 infrage.

Typische Fehler

  • Die Fixpunktgleichung lösen, ohne die Konvergenz zu zeigen. Bei a1=0a_1 = 0, an+1=1−ana_{n+1} = 1 - a_n liefert a=1−aa = 1 - a den Wert 12\frac{1}{2}, die Folge 0,1,0,1,…0, 1, 0, 1, \ldots pendelt aber.
  • Den falschen Fixpunkt nehmen. Beim Heron-Verfahren ist −3-\sqrt{3} ausgeschlossen, weil alle Glieder positiv sind.
  • Strikte Ungleichungen in den Grenzwert übernehmen. Aus an>0a_n > 0 folgt nur a≥0a \geq 0, wie bei an=122n−1a_n = \frac{1}{2^{2^{n-1}}} mit Grenzwert 00 im letzten Beispiel.
  • Die Stetigkeit von ff übergehen. Ohne sie darf man lim⁡\lim und ff nicht vertauschen.

Verwandte Formeln