In dieser Blog-Folge zeige ich Dir, was eine Intervallschachtelung ist. Mit ihr kann man konvergente Folgen konstruieren.
Intervalle und Intervallschachtelung
Bevor ich definiere, was eine Intervallschachtelung ist, muss ich zunächst den Begriff des Intervalls einführen.
Definition
Es seien $a,b\in\R$ mit $a < b$.
Wir nennen die Menge \[ [a, b] := \{x\in\R|a\leq x\leq b\} \] das abgeschlossene Intervall von $a$ bis $b$, die Menge \[ (a, b] := \{x\in\mathbb{R}|a < x \leq b\} \] das linksoffene Intervall von $a$ bis $b$, die Menge \[ [a, b) := \{x\in\mathbb{R}|a \leq x < b\} \] das rechtsoffene Intervall von $a$ bis $b$ und die Menge \[ (a, b) := \{x\in\mathbb{R}|a < x < b\} \] das offene Intervall von $a$ bis $b$.
Ein Intervall ist also ein zusammenhängender Bereich auf dem Zahlenstrahl. Dabei ist die Zahl $a$ die linke Grenze des Bereichs und $b$ die rechte. Die verschiedenen Intervallarten unterscheiden sich dann nur noch darin, ob die beiden Intervallgrenzen zum Intervall gehören oder nicht. Bei einem abgesclossenen Intervall gehören $a$ und $b$ mit zu der Menge, die durch das Intervall definiert ist, bei einem offenen Intervall dagegen nicht.
In der Literatur findest Du auch andere Schreibweisen für offene Intervalle. Statt $(a,b)$ schreibt man auch $]a,b[$ für das offene Intervall, ebenso $[a,b[$ für das rechtsoffene und $]a,b]$ für das linksoffene Intervall.
Jetzt sind wir soweit, den Begriff der Intervallschachtelung einzuführen.
Definition
Zwei reelle Folgen $(x_n)$ und $(y_n)$ bilden eine Intervallschachtelung, wenn die folgenden Bedingungen erfüllt sind:
-
Für alle $n\in\N$ gilt: $I_n :=[x_n,y_n]\neq\emptyset$,
-
für alle $n\in\N$ gilt: $I_{n+1} \subseteq I_n$ und
-
$\displaystyle \lim_{n\rightarrow\infty} y_n-x_n=0$.
Beachte: Bedingung (i) ist äquivalent zu \[ x_n\leq y_n \text{ für alle } n\in\N \] und Bedingung (ii) ist äquivalent zu \[ x_n\leq x_{n+1} \wedge y_{n+1}\leq y_n \text{ für alle } n\in\N. \] Somit muss die Folge $(x_n)$ monoton wachsend und $(y_n)$ monoton fallend sein.
Eine Intervallschachtelung hat die folgende schöne Eigenschaft.
Satz
Gegeben sei eine Intervallschachtelung durch die Folgen $(x_n)$ und $(y_n)$.
Dann existiert genau ein $a \in \R$ mit \[ a \in [x_n,y_n] \] für alle $n \in \N$ und es gilt \[ \lim_{n\rightarrow\infty} x_n = a = \lim_{n\rightarrow\infty} y_n. \]
Beweis
Aus Bedingung (ii) für eine Intervallschachtelung folgt, dass $(x_n)$ monoton wächst und $(y_n)$ monoton fällt.
Zusammen mit Bedingung (i) folgt, dasss \[ x_1 \leq x_n \leq y_n \leq y_1 \] für alle $n\in\N$ gilt. Damit sind die Folgen auch beschränkt und somit konvergent. Es gelte \[ x:=\lim_{n\rightarrow\infty} x_n \text{ und } y:=\lim_{n\rightarrow} y_n. \]
Aus (iii) folgt dann \begin{eqnarray*} 0 & = & \lim_{n\rightarrow\infty} y_n - x_n \\ & = & \lim_{n\rightarrow\infty} y_n - \lim_{n\rightarrow\infty} x_n \\ & = & y - x, \end{eqnarray*} woraus wiederum $y=x$ folgt.
Es sei nun $a:=x = y$. Für $a$ gilt damit $x_n\leq a \leq y_n$ für alle $n\in\N$.
Man nutzt Intervallschachtelung oft, konvergente Folgen mit einem vorgegebenen Grenzwert zu konstruieren. Somit hat man dann wieder ein Berechnungsverfahren, das den vorgegebenen Grenzwert berechnet oder zumindest approximiert.
Beispiel
Für $a > 1$ konstruieren wir die Folgen $(x_n)$ und $(y_n)$ sowie eine Hilfsfolge $(z_n)$ wie folgt: \begin{eqnarray*} x_1 & = & 1\\ y_1 & = & a\\ z_n & = & \frac{1}{2}(x_n + y_n)\quad\textnormal{für } n\geq 1\\ x_n & = & \left\{ \begin{array}{ll} x_{n-1} & \textnormal{falls } z_{n-1}^2 \geq a \\[2mm] z_{n-1} & \textnormal{falls } z_{n-1}^2 < a \end{array} \right\}\quad\textnormal{für } n\geq 2 \\ y_n & = & \left\{ \begin{array}{ll} z_{n-1} & \textnormal{falls } z_{n-1}^2 \geq a \\[2mm] y_{n-1} & \textnormal{falls } z_{n-1}^2 < a \end{array} \right\}\quad\textnormal{für } n\geq 2 \end{eqnarray*}
Erläuterung: Die Folgen dienen dazu, eine Intervallschachtelung zu definieren, um mit ihr $\sqrt{a}$ zu berechnen. Für $a > 1$ gilt $1 < \sqrt{a} < a$. Daher starten wir mit dem Intervall $[1,a]$.
Dann bilden wir für das $n-1$-te Intervall $[x_{n-1},y_{n-1}]$ den Mittelpunkt $z_{n-1}$. Gilt $z_{n-1}^2 < a$, dann muss sich $\sqrt{a}$ zwischen $z_n$ und $y_{n-1}$ befinden. Daher setzen wir in diesem Fall $x_n = z_{n-1}$ und $y_n = y_{n-1}$. Das $n$-te Intervall ist dann also $[z_{n-1},y_{n-1}].$
Im anderen Fall, also wenn $z_{n-1}^2 \geq a$ gilt, wird $[x_{n-1},z_{n-1}]$ zum $n$-ten Intervall.
Damit bilden die Folgen $(x_n)$ und $(y_n)$ eine Intervallschachtelung mit \[ \lim_{n\rightarrow\infty} x_n = \lim_{n\rightarrow\infty} y_n = \sqrt{a}. \]
Solch eine Intervallschachtelung kann man natürlich leicht implementieren. Hier ein einfaches Java-Programm zur Berechnung von $\sqrt{a}$.
public class Schachtelung {
private static double EPS = 1e-15;
private static double schachtelung(double a) {
double x = 1;
double y = a;
double z;
do {
z = 0.5*(x + y);
System.out.println(z);
if (z*z < a) {
x = z;
}
else {
y = z;
}
}
while (Math.abs(y-x)>EPS);
return x;
}
public static void main(String[] args) {
double a = Double.parseDouble(args[0]);
System.out.println(schachtelung(a));
}
}
Als Genauigkeit wird $10^{-15}$ vorgegeben. Solange diese Genauigkeit nicht erreicht ist, wird weiter iteriert. Dafür werden die neuen Werte für x und y so berechnet wie in der Intervallschachtelung des letzten Beispiels. Somit konvergieren x und y gegen $\sqrt{a}$.
Beachte, dass die vorgegebene Genauigkeit nur für kleine Zahlen erreichbar ist. So terminiert dieses einfache Programm nur für Eingaben zwischen $1$ und $64$. Für $a > 65$ stehen uns in der IEEE 754 Repräsentation für Fließkommazahlen nicht genügend Nachkommastellen zur Verfügung, um eine Genauigkeit von $10^{-15}$ zu erreichen, was zu einer Endlosschleife führt. Für größere Werte müssten wir also die vorgegebene Genauigkeit herabsetzen.
Wie effizient ist dieser Algorithmus zur Wurzelberechnung, insbesondere im Vergleich zur Heronschen Folge? In jeder Iteration findet hier eine Halbierung des Intervalls $[x,y]$ statt. Somit gilt für den Fehler $f_n$ der $n+1$-ten Iteration: \[ f_{n+1} \leq \frac{1}{2} f_n. \] Anders als bei der Heronschen Folge hängt $f_{n+1}$ hier nur linear von $f_n$ ab. Wir haben also nur lineare Konvergenz. Daher benötigen wir deutlich mehr Iteration, um $\sqrt{a}$ zu berechnen. Während wir mit der Heroschen Folge beispielsweise $\sqrt{2}$ mit sechs Iterationen berechnen konnten, benötigen wir für die gleiche Aufgabe mit der Intervallschachtelung über $50$ Iterationen. Für die Berechung von Wurzeln ist die Heronsche Folge also deutlich effizienter als das hier beschriebene Verfahren auf Basis einer Intervallschachtelung.
Dafür können wir Intervallschachtelungen aber deutlich flexibler einsetzen. In einem späteren Kapitel werde ich besipeilsweise zeigen, wie wir eine Intervallschachtelung definieren können, deren Folgen gegen eine Nullstelle einer Funktion konvergieren.
Der Satz von Bolzano-Weierstraß
Zunächst führe ich den Begriff der Teilfolge ein.
Definition
Es sei $(a_n)$ eine Folge und $(n_k)_{k\in\mathbb{N}}$ eine Folge natürlicher Zahlen mit $n_1 < n_2 < \ldots$.
Dann heißt $(a_{n_k})_{k\in\mathbb{N}} = (a_{n_1},a_{n_2},a_{n_3},\ldots)$ Teilfolge der Folge $(a_n)$.
Die Folge $(n_k)$, die bestimmt, welche Folgenglieder von $(a_n)$ in die Teilfolge übernommen werden, wird auch Indexfolge genannt.
Eine Teilfolge $(a_{n_k})$ einer Folge $(a_n)$ entsteht somit durch die Auswahl bestimmter Folgenglieder von $(a_n)$. Gemäß Definition muss diese Auswahl undendlich viele Elemente umfassen und die zugehörige Indexfolge muss streng monoton sein.
Beispiel
-
Für $n_k = 2k-1$ erhalten wir die Teilfolge $a_1, a_3, a_5, a_7, \ldots$ der ungeraden Folgenglieder von $(a_n)$ und
-
dementsprechend für $n_k = 2k$ die Teilfolge $a_2, a_4, a_6, a_8,\ldots$ der geraden Folgenglieder von $(a_n)$.
-
Für $n_k=k$-te Primzahl ergibt sich die Teilfolge $a_2, a_3, a_5, a_7, a_{11},\ldots$ mit einer Primzahl als Index. Da es unendlich viele Primzahlen gibt, ist auch dies eine Teilfolge von $(a_n)$.
An dieser Stelle ließe sich jetzt noch viel zu Teilfolgen und damit verbundenen Begriffen wie Häufungspunkt und Limes Superior sagen. Auf jeden Fall genügend, um mindestens eine weitere Blog-Folge damit zu füllen. Innerhalb dieses Kurses zur Analysis werden wir Teilfolgen aber nur gelegentlich benötigen und die anderen gerade genannten Begriffe gar nicht. Daher lagere ich die etwas tiefere Behandlung von Teilfolgen und damit verbundenen Begriffen in Übungen einer späteren Blog-Folge aus. Dort kannst Du dich intensiv mit Teilfolgen auseinandersetzen. Nur eine wichtige Aussage will ich direkt hier formulieren.
Lemma
Es sei $(a_n)$ eine Folge mit \[ \lim_{n\rightarrow\infty} a_n = a. \]
Dann gilt für jede Teilfolge $(a_{n_k})$ von $(a_n)$: \[ \lim_{k\rightarrow\infty} a_{n_k} = a. \]
Demnach sind alle Teilfolgen einer konvergenten Folge wieder konvergent und sie haben den gleichen Grenzwert wie die Folge selbst. Den Beweis hierfür stelle ich Dir als Übungsaufgabe.
Übung
Beweise das vorige Lemma.
Ein äußerst wichtiger Satz in Zusammenhang mit Teilfolgen ist der Satz von Bolzano-Weierstraß.
Satz (Bolzano-Weierstraß)
Jede beschränkte, reelle Folge hat eine konvergente Teilfolge.
Der Beweis dieses Satzes ist nicht einfach, enthält aber eine Reihe von interessanten Ideen. Ein wesentlicher Bestandteil des Beweises ist die Konstruktion einer Intervallschachtelung.
Beweis
Es sei $(a_n)$ eine reelle und beschränkte Folge.
Wir werden nun induktiv eine Folge $([A_k,B_k])_{k\in\N}$ von Intervallen und eine Folge $(n_k)$ natürlicher Zahlen konstruieren, so dass die folgenden Bedingungen für alle $k\in\N$ erfüllt sind:
-
In $I_k:=[A_k,B_k]$ liegen unendlich viele Folgenglieder von $(a_n)$.
-
$[A_{k+1},B_{k+1}]\subseteq [A_k,B_k]$
-
$B_{k+1}-A_{k+1} = \frac{1}{2}(B_k-A_k)$
-
$n_{k+1} > n_k$
-
$a_{n_k}\in[A_k,B_k]$
Nach Voraussetzung ist $(a_n)$ eine reelle und beschränkte Folge. Somit existieren $A,B\in\R$ mit \[ A \leq a_n \leq B \] für alle $n\in\N$.
$k=1$: Es sei \[ A_1 := A, B_1 := B, n_1 := 1. \] Alle Folgenglieder der Folge $(a_n)$ liegen somit in dem Intervall $[A_1,B_1]$. Dies sind unendlich viele. Damit ist die Bedingung (i) für $k=1$ erfüllt.
$k\rightarrow k+1$: Es gelte die Induktionsvoraussetzung, dass das Intervall $[A_k,B_k]$ undendlich viele Folgenglieder enthält.
Es sei nun \[ M_k := \frac{A_k + B_k}{2} \] die Mitte des Intervalls $[A_k,B_k]$. Da $[A_k,B_k]$ unendlich viele Folgenglieder enthält, muss mindestens eins der beiden Intervalle $[A_k,M_k]$ und $[M_k,B_k]$ ebenfalls unendlich viele Folgenglieder von $(a_n)$ enthalten.
Es sei nun $[A_{k+1},B_{k+1}]$ solch ein Intervall mit unendlich vielen Folgengliedern.
Mit dieser Konstruktion sind die Bedingungen (i) bis (iii) erfüllt.
Da $[A_{k+1},B_{k+1}]$ unendlich viele Folgenglieder von $(a_n)$ enthält, gibt es ein $n > n_k$ mit $a_n\in [A_{k+1},B_{k+1}]$.
Es sei $n_{k+1}$ das kleinste solche $n$. Damit sind (iv) und (v) erfüllt.
Durch die Bedingungen (i) bis (iii) bilden die Folgen $(A_k)$ und $(B_k)$ eine Intervallschachtelung. Es existiert somit ein $a\in\R$, das in all diesen Intervallen liegt und es gilt \[ \lim_{n\rightarrow\infty} A_k = a = \lim_{n\rightarrow\infty} B_k \]
Nach Konstruktion gilt aber auch \[ A_k \leq a_{n_k} \leq B_k \] für alle $k\in\N$. Mit dem Sandwich-Lemma folgt \[ \lim_{n\rightarrow\infty} a_{n_k} = a. \]
Was bringt uns der Satz von Bolzano-Weierstraß? Nun, er wird in erster Linie für theoretische Herleitungen verwendet. Hierfür ist er aber ein mächtiges Werkzeug, das es uns gestattet, einen Grenzwert zu konstruieren.
Angenommen, wir haben eine Folge, von der wir beweisen wollen, dass sie konvergent ist, wir kennen aber ihren Grenzwert nicht. Dann muss diese Folge auf jeden Fall beschränkt sein, denn wir wissen ja, dass die Beschränktheit eine notwendige Bedingung für die Konvergenz ist. Also zeigen wir zunächst einmal die Beschränktheit der Folge. Der Satz von Bolzano-Weierstraß sagt uns nun, dass diese beschränkte Folge auf jeden Fall eine konvergente Teilfolge hat. Solch eine konvergente Teilfolge muss aber den gleichen Grenzwert haben wie die Folge selbst. Damit haben wir einen Grenzwert konstruiert, mit dem wir argumentieren können, den wir dann z. B. in einem Grenzwertbeweis verwenden können.
Diese Vorgehensweise werden wir beispielsweise in der nächsten Blog-Folge nutzen, um ganz allgemein zu zeigen, dass Cauchy-Folgen in den reellen Zahlen immer konvergent sind.
Teilen und Drucken