Um die Konvergenz einer Folge nachzuweisen, stehen uns bisher die Grenzwertdefinition und Rechenregeln für Grenzwerte zur Verfügung. Häufig können wir den Grenzwert einer Folge aber nicht benennen, d. h. wir vermuten, dass eine Folge konvergent ist, wissen aber nicht, welcher Zahl sich die Folgenglieder annähern. In dieser Blog-Folge wirst Du ein erstes Kriterium kennenlernen, mit dem Du nachweisen kannst, dass eine Folge konvergent ist, ohne ihren Grenzwert zu kennen.
Monotonie
Wir betrachten als Beispiel die Folge $(a_n)$ mit \[ a_n =\left(1+\frac{1}{n}\right)^n. \] Wenn wir einen Blick auf die Folgenglieder werfen, sieht es so aus, als wäre die Folge konvergent. \[ \begin{array}{r|c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 5 & 10 & 20 & 50 & 100 & 1000\\ \hline a_n & 2 & 2.250 & 2.370 & 2.488 & 2.594 & 2.653 & 2.692 & 2.704 & 2.717 \end{array} \] Aber wie können wir die Konvergenz zeigen, wenn wir den Grenzwert nicht kennen? Bisher stehen uns dafür keine Methoden zur Verfügung.
In dieser Blog-Folge werde ich ein Kriterium vorstellen, mit der wir die Konvergenz dieser Folge nachweisen können. Für dieses Kriterium benötigen wir den Begriff der Monotonie.
Definition
Eine reelle Zahlenfolge $(a_n)$ heißt
-
monoton wachsend, wenn $a_n \leq a_{n+1}$ für alle $n\in\N$ gilt,
-
monoton fallend, wenn $a_n \geq a_{n+1}$ für alle $n\in\N$ gilt,
-
streng monoton wachsend, wenn $a_n < a_{n+1}$ für alle $n\in\N$ gilt,
-
streng monoton fallend, wenn $a_n > a_{n+1}$ für alle $n\in\N$ gilt,
-
monoton, wenn sie monoton wachsend oder monoton fallend ist.
Beispiel
-
Es gilt $n+1 > n$. Also ist $(a_n)$ mit $a_n = n$ eine streng monoton wachsende Folge.
-
Wegen $\frac{1}{n+1} < \frac{1}{n}$ ist die Folge $(b_n)$ mit $b_n = \frac{1}{n}$ streng monoton fallend.
-
Die Folge $(c_n)$ mit $c_n = \frac{(-1)^n}{n}$ ist weder monoton fallend noch monoton steigend. Also ist sie nicht monoton.
Der folgende Satz ist unser erstes Konvergenzkriterium.
Satz (Kriterium der monotonen Konvergenz)
Jede beschränkte, monotone reelle Zahlenfolge ist konvergent.Wenn es uns also gelingt zu zeigen, dass eine Folge sowohl beschränkt als auch monoton ist, dann muss sie konvergent sein. Für die Nachweise der Beschränktheit und der Monotonie müssen wir den Grenzwert der Folge nicht kennen. Wir können also ohne Kenntnis des Grenzwerts auf Konvergenz schließen.
Natürlich gibt es viele Folgen, die nicht monoton und trotzdem konvergent sind. Dementsprechend ist das Kriterium der monotonen Konvergenz ein hinreichendes Kriterium, aber kein notwendiges.
Um das Kriterium der monotonen Konvergenz zu beweisen, müssen wir auf eine der uns bekannten Möglichkeiten zum Nachweis der Konvergenz zurückgreifen. All diese benötigen einen Grenzwert. Wir müssen also aus den gegebenen Voraussetzungen einen Grenzwert konstruieren. Für eine monoton wachsende Folge gelingt uns dies mit dem Supremum. Das Supremum der Folgenglieder ist der Grenzwert!
Beweis
Ohne Beschränkung der Allgemeinheit (O. B. d. A.) sei $(a_n)$ eine monoton wachsende und beschränkte Folge. Der nachfolgende Beweis kann für monoton fallende Folgen analog geführt werden.
Es sei \[ a = \sup\{a_n | n\in\N\}, \] also das Supremum aller Folgenglieder. Da die Folge beschränkt ist, muss nach dem Vollständigkeitsaxiom dieses Supremum existieren. Wir zeigen nun, dass dieses Supremum $a$ der Grenzwert von $(a_n)$ ist.
Es sei $\epsilon > 0$ beliebig. Da $a$ das Supremum der Folgenglieder ist, existiert ein $n_0\in\N$ mit \[ a-\epsilon < a_{n_0}. \] Dies ist eine Eigenschaft des Supremums, die wir in dieser Blog-Folge bewiesen haben.
Jetzt kommt noch die Monotonie ins Spiel. Da die Folge $(a_n)$ monoton wachsend ist, muss $a_{n_0} \leq a_n$ für alle $n\geq n_0$ gelten.
Insgesamt gilt also für alle $n\geq n_0$: \[ a-\epsilon < a_{n_0} \leq a_n \leq a. \] Die Ungleichung rechts gilt, weil $a$ als Supremum auch eine obere Schranke der Folgenglieder $a_n$ ist. Daraus folgt \[ |a_n-a| < \epsilon, \] womit gezeigt ist, dass $(a_n)$ den Grenzwert $a$ hat und somit konvergent ist.
Anwendung des Monotoniekriteriums
Wir hatten oben die Folge \[ a_n = \left(1+\frac{1}{n}\right)^n \] betrachtet und vermutet, dass sie konvergent ist. Mit dem Monotoniekriterium können wir diese Hypothese beweisen. Dazu müssen wir zeigen, dass $(a_n)$ monoton und beschränkt ist. Wir beginnen mit dem Nachweis der Monotonie.
Da schon \[ a_1 = \left(1 + \frac{1}{1}\right)^1 = 2 < 2.25 = \left(1 + \frac{1}{2}\right)^2 = a_2 \] ist, kann die Folge, wenn sie monoton ist, nur monoton wachsend sein. Der Nachweis hierfür ist nicht ganz einfach und nutzt unter anderem die Bernoullische Ungleichung.
Lemma
Die Folge $(a_n)$ mit \[ a_n = \left(1+\frac{1}{n}\right)^n \] ist monoton wachsend.Beweis
Gemäß Definition bedeutet monoton wachsend \[ a_{n+1} \geq a_n \quad\text{für alle } n\in\N. \] Dies müssen wir also nachweisen.
Offensichtlich gilt $a_n > 0$ für alle $n\in\N$. Damit ergibt sich: \[ a_{n+1} \geq a_n \quad \Longleftrightarrow \quad \frac{a_{n+1}}{a_n} \geq 1. \] Für den Nachweis der Monotonie nutzen wir nun die rechte Ungleichung. \begin{eqnarray*} \frac{a_{n+1}}{a_n} & = & \frac{\left( 1 + \frac{1}{n+1} \right)^{n+1}}{\left( 1 + \frac{1}{n} \right)^n} \\ & = & \frac{\left( 1 + \frac{1}{n+1} \right)^n}{\left( 1 + \frac{1}{n} \right)^n} \left( 1 + \frac{1}{n+1} \right) \\ & = & \left(\frac{1 + \frac{1}{n+1}}{1 + \frac{1}{n}}\right)^n \frac{n+2}{n+1} \\ & = & \left(\frac{\,\,\frac{n+2}{n+1}\,\,}{ \frac{n+1}{n} }\right)^n \frac{n+2}{n+1} \\ & = & \left(\frac{(n+2)n}{(n+1)^2}\right)^n \frac{n+2}{n+1} \\ & = & \left(\frac{(n+1)^2-1}{(n+1)^2}\right)^n \frac{n+2}{n+1} \\ & = & \left(1-\frac{1}{(n+1)^2}\right)^n \frac{n+2}{n+1} \end{eqnarray*} Jetzt wenden wir die Bernoullische Ungleichung an. Mit dieser folgt: \begin{eqnarray*} & \geq & \left(1-\frac{n}{(n+1)^2}\right) \frac{n+2}{n+1} \\ & = & \frac{(n+1)^2-n}{(n+1)^2}\cdot \frac{n+2}{n+1} \\ & = & \frac{(n^2+n+1)(n+2)}{(n+1)^3} \\ & = & \frac{n^3+3n^2+3n+2}{(n+1)^3} \\ & = & \frac{(n+1)^3+1}{(n+1)^3} \\ & = & 1 + \frac{1}{(n+1)^3} \\ & > & 1 \end{eqnarray*}
Jetzt zur Beschränktheit von $(a_n)$. Diese kann man sehr leicht zeigen, wenn man vorher nachgewiesen hat, dass die Folge $(b_n)$ mit \[ b_n = \left( 1 + \frac{1}{n} \right)^{n+1} = \left( 1 + \frac{1}{n} \right) a_n \] monoton fallend ist. Dieser Nachweis erfolgt analog zum Beweis für das monotone Wachstum von $(a_n)$, weshalb ich Dir den Nachweis als Übung überlasse.
Übung
Zeige, dass die Folge $(b_n)$ mit \[ b_n = \left( 1 + \frac{1}{n} \right)^{n+1} \] monoton fallend ist.Beachte, dass \[ b_n = a_n\left(1 + \frac{1}{n}\right) \] gilt. Wegen $1 + \frac{1}{n} > 1$ folgt damit \[ a_n < b_n \] für alle $n\in\N$. Weiterhin ist $(a_n)$ monoton wachsend und $(b_n)$ monoton fallend. Somit folgt \[ a_1 \leq a_n < b_n \leq b_1 \] für alle $n\in\N$. Damit sind die Folgenglieder von $(a_n)$ durch $a_1$ und $b_1$ beschränkt.
Mit dem Monotoniekriterium folgt, dass $(a_n)$ eine konvergente Folge sein muss.
Korollar
Die Folge $(a_n)$ mit \[ a_n = \left(1 + \frac{1}{n}\right)^n \] ist konvergent.Den Grenzwert $a := \lim_{n\rightarrow\infty} (a_n)$ kennen wir aber nicht. Wir wissen aber, dass für alle $n\in\N$ die Ungleichung \[ a_n \leq a \leq b_n \] gelten muss. Damit können wir $a$ ungefähr ermitteln. Für $n=1000$ ergibt sich \[ 2.71692 \leq a \leq 2.71965 \] was eine grobe Schätzung für den Grenzwert ist.
Der tatsächliche Grenzwert ist die Eulersche Zahl, die mit dem Symbol $\e$ bezeichnet wird. Es gilt \[ \e \approx 2.718281828459045\ldots \] Wir werden die Eulersche Zahl in Kapitel 3 als Grenzwert einer anderen Folge definieren. Diese andere Folge wird deutlich schneller gegen $\e$ konvergieren als die hier betrachtete Folge $(a_n)$.
Wurzeln berechnen
Die CPU eines Computers kann nur einfache logische und arithmetische Operation ausführen, sie kann aber beispielsweise nicht direkt die Wurzel einer reellen Zahl $a \in\R_+$ bestimmen. Solch eine Wurzelberechnung muss mithilfe eines Algorithmus erfolgen. Dafür nutzt man häufig iterative Verfahren, also Verfahren, die sich dem tatsächlichen Wert von $\sqrt{a}$ immer stärker nähern.
Im Prinzip ist solch ein iteratives Verfahren nichts anderes als eine konvergente Folge. In diesem Abschnitt zeige ich Dir solch eine Folge zur Wurzelberechnung. Den Beweis, dass diese Folge tatsächlich konvergent ist, führen wir mit dem Monotoniekriterium.
Satz
Es sei $a\in\R_+$ und die Folge $(x_n)$ sei rekursiv durch \begin{eqnarray*} x_1 & = & a\\ x_n & = & \frac{1}{2}\left(x_{n-1} + \frac{a}{x_{n-1}}\right)\quad\text{für } n \geq 2\end{eqnarray*} definiert.
Dann ist die Folge $(x_n)$ konvergent mit Grenzwert $\sqrt{a}$.
Wir beweisen zunächst nur die Konvergenz von $(x_n)$. Nachdem die Konvergenz bewiesen ist, zeigen wir, dass der Grenzwert tatsächlich $\sqrt{a}$ beträgt.
Beweis der Konvergenz
Für den Beweis der Konvergenz nutzen wir das Monotoniekriterium. Wir müssen also zeigen, dass die Folge $(x_n)$ monoton und beschränkt ist.
Mittels vollständiger Induktion sieht man sofort, dass $x_n > 0$ für alle $n\in\N$ gilt: Zunächst gilt $x_1 > 0$ per Definition. Wenn wir jetzt von der Induktionsvoraussetzung $x_{n-1} > 0$ ausgehen, muss auch \[ \frac{1}{2}\left(x_{n-1} + \frac{a}{x_{n-1}}\right) > 0 \] gelten, denn alle auftretenden Terme sind positiv. Damit ist dann auch $x_n$ positiv.
Für alle $n\geq 2$ gilt damit \begin{eqnarray*} x_n^2 - a & = & \frac{1}{4}\left(x_{n-1} + \frac{a}{x_{n-1}}\right)^2 -a \\ & = & \frac{1}{4}\left(x_{n-1}^2 + 2a + \frac{a^2}{x_{n-1}^2}\right) - \frac{4a}{4} \\ & = & \frac{1}{4}\left(x_{n-1}^2 - 2a + \frac{a^2}{x_{n-1}^2}\right) \\ & = & \frac{1}{4}\left(x_{n-1} - \frac{a}{x_{n-1}}\right)^2 \geq 0. \end{eqnarray*} Diese Hilfsaussage nutzen wir jetzt zum Beweis der Monotonie. Es gilt: \begin{eqnarray*} x_n - x_{n+1} & = & x_n -\frac{1}{2}\left(x_n + \frac{a}{x_n}\right) \\ & = & \frac{1}{2}\left(x_n - \frac{a}{x_n}\right) \\ & = & \underbrace{\frac{1}{2x_n}}_{\geq 0} \underbrace{\left( x_n^2 - a\right)}_{\geq 0} \geq 0 \end{eqnarray*} Also ist $(x_n)_{n\geq 2}$ monoton fallend. Die Einschränkung ist erforderlich, weil wir in der Hilfsaussage die Rekursionformel für $x_n$ verwendet haben, die aber erst ab $n=2$ gilt. Tatsächlich kann $x_2$ größer als $x_1$ sein, nämlich wenn $0 < a < 1$ gilt. Die Einschränkung auf $(x_n)_{n\geq 2}$ ist für die Anwendung des Monotoniekriteriums aber unwesentlich, denn endlich viele Folgenglieder zu Beginn einer Folge haben keinen Einfluss auf deren Konvergenz.
Oben haben wir bereits gezeigt, dass $x_n > 0$ für alle $n\in\N$ gilt. Da $(x_n)$ für $n\geq 2$ monoton fallend ist, folgt andererseits \[ x_n \leq \max\{x_1,x_2\} \] für alle $n\in\N$. Damit ist $(x_n)$ auch beschränkt.
Mit dem Monotoniekriterium folgt, dass $(x_n)$ konvergent ist.
Beweis des Grenzwertes
Jetzt müssen wir noch zeigen, dass die Folge $(x_n)$ den Grenzwert $\sqrt{a}$ hat.
Es sei \[ x := \lim_{n\rightarrow\infty} x_n. \] Aus der Definition der Folge ergibt sich \[ x_n x_{n+1} = \frac{1}{2}\left( x_n^2 + a \right). \quad (*) \] Die Folge $(x_{n+1})$ hat natürlich den gleichen Grenzwert wie die Folge $(x_n)$, denn beide haben ja die selben Folgenglieder, nur im Index um eins verschoben. Also gilt auch \[ x = \lim_{n\rightarrow\infty} x_{n+1}. \] Jetzt wenden wir auf die Gleichung (*) Grenzwertregeln an. Dies dürfen wir, da wir ja nachgewiesen haben, dass alle beteiligten Folgen konvergent sind. Mit den Grenzwertregeln folgt \[ x^2 = \frac{1}{2}\left(x^2 + a \right) \] und damit \[ x^2 = a. \] Wegen $x_n > 0$ und somit $x\geq 0$ muss $x$ die positive Lösung der Gleichung $x^2=a$ sein. Also gilt \[ x = \lim_{n\rightarrow\infty} x_n = \sqrt{a}. \]
Die Folge $(x_n)$ ist unter dem Namen Heronsche Folge bekannt. Benannt ist sie nach dem griechischen Mathematiker Heron von Alexandria, der sie in seinem Werk Metrica beschrieb.
Die Heronsche Folge lässt sich recht einfach implementieren. Hier ein kleines Java-Programm zur Berechnung von $\sqrt{a}$.
public class Heron {
private static double heron(double a) {
double x;
double xneu = a;
int n = 1;
do {
System.out.printf("x_%d = %.16f\n", n, xneu);
x = xneu;
xneu = 0.5 * (x + a/x);
n++;
}
while (xneu != x);
return x;
}
public static void main(String[] args) {
double a = Double.parseDouble(args[0]);
System.out.printf("\nsqrt(%f) = %.16f\n", a, heron(a));
}
}
Im Java-Programm wird die Iterationsvorschrift der Heronschen Folge solange angewendet, wie sich $x_{n+1}$ und $x_n$ unterscheiden. Wenn wir im Computer exakt rechnen könnten und sowohl xneu und x reelle Zahlen wären, würde die Schleife im Programm niemals terminieren. Wir wissen aber, dass dies nicht der Fall ist, denn für die Darstellung von Zahlen steht uns im Rechner nur eine endliche Genauigkeit zur Verfügung. Wenn diese erreicht ist, werden sich xneu und x nicht mehr unterscheiden.
In der Informatik ist Effizienz eine wesentliche Eigenschaft von Rechenverfahren. Ein Informatiker versucht stets, für ein Problem ein möglichst effizientes Rechenverfahren zu finden. Wir wollen nun die Frage diskutieren, wie effizient die Heronsche Folge für die Wurzelberechnung ist.
Für die Heronsche Folge bedeutet Effizienz, dass möglichst wenige Iterationen notwendig sein sollten, um den Grenzwert mit einer vorgegebenen Genauigkeit zu erreichen. Es bezeichne \[ f_n := x_n - \sqrt{a} \] den Approximationsfehler, den wir machen würden, wenn wir $x_n$ als Approximation für $\sqrt{a}$ wählen würden. Mit dieser Definition gilt \begin{eqnarray*} \frac{1}{2x_n} f_n^2 & = & \frac{1}{2x_n}\left(x_n - \sqrt{a}\right)^2 \\ & = & \frac{1}{2x_n} \left(x_n^2 - 2x_n\sqrt{a} + a\right) \\ & = & \frac{1}{2} x_n - \sqrt{a} + \frac{a}{2x_n} \\ & = & \frac{1}{2}\left(x_n + \frac{a}{x_n}\right) - \sqrt{a} \\ & = & x_{n+1} - \sqrt{a} \\ & = & f_{n+1}, \end{eqnarray*} also \[ f_{n+1} = \frac{1}{2x_n} f_n^2. \] Weiterhin gilt $x_n \geq \sqrt{a}$, da $(x_n)$ monoton fallend ist. Hieraus ergibt sich \[ |f_{n+1}| \leq \frac{1}{2\sqrt{a}} f_n^2. \]
Wir nennen eine Folge $(a_n)$ mit Grenzwert $a$ quadratisch konvergent, wenn eine Konstante $K> 0$ existiert, mit \[ |a_{n+1}-a| \leq K\cdot |a_n-a|^2. \] Gemäß dieser Definition ist die Heronsche Folge somit eine quadratisch konvergente Folge. In der Praxis bedeutet dies, dass sich die Anzahl der korrekten Nachkommastellen bei jeder Iteration ungefähr verdoppelt. Wenn wir in Iteration $n$ beispielsweise eine Genauigkeit von $10^{-2}$ erreicht haben, können wir in Iteration $n+1$ schon mit einer Genauigkeit von ungefähr $10^{-4}$, also vier korrekten Nachkommastellen, und in Iteration $n+2$ mit einer Genauigkeit von ungefähr $10^{-8}$ und somit acht korrekten Nachkommastellen rechnen. Somit werden nur wenige Iterationen notwendig sein, um $\sqrt{a}$ soweit zu approximieren, wie es im Rechner mit der Darstellung für Gleitkommazahlen (IEEE 754) überhaupt möglich ist. Für eine Zahl wie $\sqrt{2}$ sind dies ungefähr 16 Nachkommastellen.
Die quadratische Konvergenz und die damit verbundene ungefähre Verdopplung der Anzahl der korrekten Nachkommastellen von Iteration zu Iteration sehen wir sehr schön an der Ausgabe des Java-Programms von oben für die Berechnung von $\sqrt{2}$.
x_1 = 2,0000000000000000
x_2 = 1,5000000000000000
x_3 = 1,4166666666666665
x_4 = 1,4142156862745097
x_5 = 1,4142135623746899
x_6 = 1,4142135623730950
sqrt(2,000000) = 1,4142135623730950
Es sind also nur sechs Iterationen notwendig, um $\sqrt{2}$ bis auf Maschinengenauigkeit zu berechnen.
Wegen der quadratische Konvergenz liefert die Heronsche Folge somit ein effizientes Verfahren zur Wurzelberechnung. Wir werden in der kommenden Blog-Folge mit der Intervallschachtelung ein weiteres iteratives Verfahren kennenlernen, mit dem wir ebenfalls Wurzelberechnung durchführen könnten. Im Gegensatz zur Heronschen Folge weist das Intervallschachtelungsverfahren aber nur eine lineare Konvergenz auf und benötigt daher viel mehr Iteration, um eine vorgegebene Genauigkeit zu erreichen. Dafür ist es vielfältiger verwendbar und nicht nur für Wurzelberechnungen geeignet.
Teilen und Drucken