Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

9. Folgen

Eine (unendliche) Folge im herkömmlichen Sinn entsteht durch "Hintereinanderschreiben" von Zahlen, z.B.:

1,2,3,4,...1{,}2,3{,}4,...

Dabei ist die Reihenfolge wichtig, jede Zahl hat also ihre feste Position. Die Folge 2,1,4,3,2{,}1,4{,}3,\dots ist eine andere als 1,2,3,4,1{,}2,3{,}4,\dots

Definition

Mathematisch können wir eine Folge deshalb als Abbildung NR\mathbb{N} \to \mathbb{R} auffassen: Jeder Position wird eine Zahl zugeordnet. Die Abbildung f:n2nf: n \mapsto 2n generiert demnach die Folge der geraden Zahlen:

Die Schreibweise f:nf(n)f: n \mapsto f(n) ist für Folgen eher nicht gebräuchlich. Eher benutzt man die Indexschreibweise f:nfnf: n \mapsto f_n. Meist aber einfach (fn)nN(f_n)_{n\in\mathbb{N}} oder noch kürzer (fn)(f_n). Die Klammern vermeiden Verwechslungen mit fnf_n, was das nn-te Glied der Folge (fn)(f_n) bezeichnet.

Alternative Darstellungsmöglichkeiten

Partialsummen

Oft ist es praktischer, nicht die Folgenglieder fnf_n explizit aufzuschreiben, sondern die Differenz sn:=fnfn1s_n := f_n-f_{n-1} zwischen benachbarten Folgengliedern. Man spricht dann von einer Reihe mit Reihengliedern (sn)(s_n) und den Partialsummen:

(Man beachte, dass sich aus der Definition für den Folgenanfang f1=s1f_1=s_1 ergibt.)

Rekursiv

Speziell in der Informatik treten (bei Kostenanalysen) oft rekursiv definierte Folgen auf, bei denen jede Zahl fnf_n nach einer festen Vorschrift aus dem Vorgänger fn1f_{n-1} (oder weiteren Vorgängern) berechnet wird. Wichtig: Festlegen der Anfangs(Start)-Werte, damit die Folge überhaupt eindeutig definiert ist. Einfaches Beispiel ist z.B. das Verdoppeln: Die Vorschrift fn=2fn1f_n = 2 f_{n-1} führt auf die Folge 1,2,4,8,16,32,,1{,}2,4{,}8,16{,}32, \dots,sofern man vorher festgelegt hat, dass f1=1f_1 = 1 sein soll.

Beispiel: Die Vorschrift fn=nfn1f_n = nf_{n-1}, f1=1f_1=1 liefert dagegen die Folge 1,2,6,24,1{,}2,6{,}24, \dots, also fn=n!.f_n = n!.

Beispiel: Eine typische Anwendung von Folgen in der Informatik: die Laufzeit eines Programms für verschiedene Eingaben; etwa die Folge (an)(a_n) der Anzahl der Vergleiche, die ein Sortierprogramm zum Sortieren von nn Zahlen höchstens durchführt (Insert-Sort).

Bei Laufzeitvergleichen ist insbesondere interessant, wie sich die Laufzeiten für immer größere nn verhalten. Wachsen? Fallen? Wie stark?

Entsprechend sind folgende Eigenschaften von Folgen von praktischer Bedeutung:

Monotonie von Folgen

Eine Folge heißt monoton wachsend, wenn jedes Element größer oder gleich seinem Vorgänger ist, also fnfn1f_n \ge f_{n-1} für jedes n2n \ge 2.

Folgen mit fn>fn1f_n > f_{n-1} heißen streng monoton wachsend.

Eine Folge heißt entsprechend monoton fallend bzw. streng monoton fallend, wenn die Elemente kleiner werden, also fnfn1f_n \le f_{n-1} bzw. fn<fn1f_n < f_{n-1}.

Obere/ untere Schranken

Mindest- oder Maximallaufzeiten sind wichtig, daher sind wir an oberen/unteren Schranken für unsere Folgenelemente interessiert:

Gibt es eine Zahl CRC\in\mathbb{R} mit CfnC \ge f_n für alle nn, dann nennt man CC eine obere Schranke.

Alle Zahlen, die größer als CC sind, sind natürlich erst recht obere Schranken; am interessantesten ist daher eine kleinste obere Schranke, die heißt dann Supremum: supfn\sup f_n.

Entsprechend heißt ein cRc\in\mathbb{R} mit cfnc\le f_n für alle nn eine untere Schranke, besonders interessant ist hier eine größte untere Schranke, die heißt Infimum: inffn\inf f_n.

Hat eine Folge sowohl eine obere als auch eine untere Schranke, dann nennt man sie beschränkt

.

Konvergenz und Divergenz

Bei Folgen (und mithin auch bei Reihen) interessiert oft, was mit den Folgengliedern fnf_n im Grenzwert sehr großer nn passiert.

Der "gutmütige" Fall dabei ist, dass die Folge gegen eine Grenzwert yy konvergiert, d.h., dass für hinreichend großes nn alle Folgenglieder beliebig nahe an yy liegen:

Zur Erklärung: definiere die ϵ\epsilon-Umgebung einer Zahl yRy\in\mathbb{R}

"Beliebig nahe an yy" heißt nun, dass für jedes (noch so kleine) ϵ>0\epsilon>0 die Folgenglieder ab einem n0(ϵ)n_0(\epsilon) in Uϵ(y)U_\epsilon(y) liegen.

Es dürfen also insbesondere nur endlich viele Folgenglieder außerhalb von UϵU_{\epsilon} liegen! Für kleineres ϵ\epsilon muss man dann meist ein größeres n0(ϵ)n_0(\epsilon) nehmen.

Konvergenz heißt also:

In diesem Fall heißt yy der Grenzwert der Folge: y=limnfny=\lim_{n\to\infty}f_n.

Beispiele:

  • limn1n=0\displaystyle\lim_{n\to\infty} \frac{1}{n} = 0 (wähle n0(ϵ):=1ϵ+1n_0(\epsilon) := \lceil \frac{1}{\epsilon}\rceil +1),

  • limnn+1n=1\displaystyle\lim_{n\to\infty} \frac{n+1}{n} = 1 (umformen zu 1+1n11 + \frac{1}{n} \rightarrow 1),

  • limnn+(1)nn=1((1)nn=1n0)\displaystyle\lim_{n\to\infty} \frac{n+(-1)^n}{n} = 1\quad\left(\left|\frac{(-1)^n}{n}\right| = \frac{1}{n} \rightarrow 0 \right)

Konvergenz durch monotone, beschränkte Folgen

Ein nützlicher Satz zur Konvergenz:

SatzSatz von Bolzano-Weierstraß

Eine beschränkte und monotone (d.h. monoton wachsende oder monoton fallende) Folge reeller Zahlen ist konvergent.

Kann man nachweisen, dass eine Folge beschränkt und bis auf endlich viele Folgeglieder monoton ist, so folgt automatisch die Konvergenz. Dieser Satz liefert jedoch keine Aussage über den Grenzwert.

Häufungspunkte - limes superior und limes inferior

Die Folge (fn)(f_n) mit fn:=(1)n+1nf_n := (-1)^n + \frac{1}{n} konvergiert nicht gegen einen Grenzwert, aber die Werte 11 und 1-1 haben ähnliche Eigenschaften wie ein Grenzwert. In jeder Umgebung sind unendlich viele Folgenglieder enthalten, aber eben für beide Werte! Einen Wert mit dieser Eigenschaft (in jeder Umgebung sind unendlich viele Folgeglieder enthalten) nennt man Häufungspunkt der Folge.

Man beachte den Unterschied zwischen "nur endlich viele Folgenglieder sind außerhalb der Umgebung" (Grenzwert) und "unendlich viele Folgenglieder sind in der Umgebung" (Häufungspunkt).

Eine beschränkte Folge reeller Zahlen besitzt immer wenigstens einen Häufungspunkt. Beweis durch Intervallschachtelung: Man betrachtet das Intervall zwischen einer unteren und einer oberen Schranke, halbiert es, überlegt sich, dass in wenigstens einer Hälfte noch unendlich viele Folgenglieder liegen müssen, halbiert diese Hälfte, … Daher erzeugen wir auf diese Art und Weise eine geschachtelte Folge immer kleinerer Intervalle, deren Obergrenzen eine monoton fallende, beschränkte, also konvergente Folge bilden. Grenzwert dieser Folge ist ein Häufungspunkt!

Von besonderem Interesse bei beschränkten Folgen ist der größte Häufungspunkt, oder Limes superior der Folge. Dazu betrachten wir zunächst zu einer beschränkten Folge (fn)(f_n) die Folge (gn)(g_n) mit gn:=supmnfm.g_n := \sup_{m\geq n} f_m. Wegen der Beschränktheit von (fn)(f_n) ist auch (gn)(g_n) beschränkt, weiter ist (gn)(g_n) monoton fallend (warum?), mithin konvergent und der Grenzwert

ist der größte Wert, für den in jeder Umgebung unendlich viele fnf_n liegen: der größte Häufungspunkt.

Zum Beweis sind zwei Eigenschaften zu zeigen:

  • In jeder Umgebung liegen unendlich viele Folgenglieder.

  • Kein größerer Wert hat diese Eigenschaft.

Dazu überlegen wir uns, dass für C:=lim supxnC := \limsup x_n einer beschränkten Folge (xn)(x_n) gilt, dass für jedes ϵ>0\epsilon>0 nur endlich viele xnx_n größer als C+ϵC+\epsilon sind.

Wären unendlich viele Glieder größer als C+ϵC+\epsilon, so könnte man daraus eine unendliche Folge definieren, mit Häufungspunkt.

Was passiert, wenn keine Konvergenz vorliegt? Divergenz:

In diesem Fall heißt die Folge divergent.

Formen der Divergenz

Es gibt zwei verschiedene Formen der Divergenz:

  • Divergenz als "Konvergenz" gegen Unendlich (++ oder -):

  • Divergenz durch mehr als einen Häufungspunkt: fn:=(1)nf_n := (-1)^n (1-1 und 11) oder gn=n(1)ng_n=n\cdot(-1)^n (++^{\infty} und -^{\infty})

Die OO-Notation, die sogenannte Landau-Symbolik, (OO wie in Oh!, nicht 00 wie in 11=01-1=0) ist ein Werkzeug, um Folgen nach ihrem Wachstumsverhalten zu klassifizieren. Für eine Folge f=(fn)f=(f_n) wird die Klasse O(f)O(f) alle Folgen enthalten, die bis auf einen konstanten Faktor nicht schneller wachsen als ff.

Wir schreiben eine Folge (fn)(f_n) jetzt kurz und einfach z.B. als n2n^2 an Stelle von nn2n\mapsto n^2.

In einer Klasse von Folgen O(n2)O(n^2) ("welche in der Ordnung von n2n^2 steigen") wollen wir Folgen zusammenfassen, mit einem bestimmten Divergenzverhalten, z.B.:

  • nn, weil nn2n\le n^2,

  • 16n216n^2, weil uns ein konstanter Faktor 16 nicht stört (nach wie vor gilt, dass sich mit doppeltem nn das fnf_n​ vervierfacht: in diesem Sinn wachsen n2n^2 und 16n216n^2 gleich schnell),

  • n2+n+1n^2+n+1, weil das kleiner ist als 3n23n^2, aber nicht 2n2^n, weil man für jedes CRC\in\mathbb{R} ein nn finden kann mit 2n>Cn22^n>C\cdot n^2

Mathematisch sieht das so aus: fnO(gn):C>0,n0N:n>n0:fnCgnf_n \in O(g_n) :\Leftrightarrow \exists C>0, n_0\in\mathbb{N}:\forall n>n_0: |f_n| \leq C\cdot g_n

Neu ist das n0n_0: Die Ungleichung muss nicht für alle Glieder gelten, sondern erst ab einem bestimmten Index (also für sehr große nn); endlich viele Ausnahmen sind erlaubt. Endlich viele Ausnahmen könnte man auch versuchen durch größeres nn zuzulassen. Geht aber nicht für gn=0g_n=0.

Unter der Voraussetzung n:gn>0\forall n:g_n>0 kann man umschreiben zu

In dieser Form ist das n0n_0 überflüssig: Die Folge fn/gn|f_n|/g_n muss beschränkt sein.

Sollte man an einem möglichst kleinen CC interessiert sein (normalerweise ist man das nicht), kann man sich auf die Suche nach dem größten Häufungspunkt der (beschränkten) Folge fn/gn|f_n|/g_n begeben: wenn man den noch um ein beliebiges ϵ>0\epsilon>0 vergrößert, hat man ja eine Zahl CC, für die nur endlich viele der Quotienten größer sind.

Eine Menge heißt abgeschlossen, wenn sie alle ihre Häufungspunkte enthält. Beispiel: nicht abgeschlossen: Q\mathbb{Q}, ]0,1[\ \rbrack0{,}1\lbrack; abgeschlossen: R\mathbb{R}, [0,1]\lbrack 0{,}1\rbrack

Eine Menge kann abgeschlossen werden, indem man all ihre Häufungspunkte hinzunimmt: QR\mathbb{Q} \rightarrow \mathbb{R}


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?