Reelle Folgen/Heron-Verfahren/2/Einführung/Textabschnitt

Heron von Alexandria (1. Jahrhundert n.C.)

Wir beginnen mit einem motivierenden Beispiel.

Beispiel

Wir wollen die Quadratwurzel einer natürlichen Zahl „berechnen“, sagen wir von $5$ . Eine solche Zahl $x$ mit der Eigenschaft $x^{2} = 5$ gibt es nicht innerhalb der rationalen Zahlen, wie aus der eindeutigen Primfaktorzerlegung folgt. Wenn $x \in R$ ein solches Element ist, so hat auch $- x$ diese Eigenschaft. Mehr als zwei Lösungen kann es aber nach Fakt nicht geben, sodass wir nur nach der positiven Lösung suchen müssen.

Obwohl es innerhalb der rationalen Zahlen keine Lösung für die Gleichung $x^{2} = 5$ gibt, so gibt es doch beliebig gute Approximationen innerhalb der rationalen Zahlen dafür. Beliebig gut heißt dabei, dass der Fehler (oder die Abweichung) unter jede gewünschte positive Schranke gedrückt werden kann. Das klassische Verfahren, um eine Quadratwurzel beliebig anzunähern, ist das Heron-Verfahren, das man auch babylonisches Wurzelziehen nennt. Dies ist ein iteratives Verfahren, d.h., die nächste Approximation wird aus den vorausgehenden Approximationen berechnet. Beginnen wir mit $a := x_{0} := 2$ als erster Näherung. Wegen

x_{0}^{2} = 2^{2} = 4 < 5

ist $x_{0}$ zu klein, d.h. es ist $x_{0} < x$ . Aus $a^{2} < 5$ (mit $a$ positiv) folgt zunächst $5 / a^{2} > 1$ und daraus $(5 / a)^{2} > 5$ , d.h. $5 / a > \sqrt{5}$ . Man hat also die Abschätzungen

a < \sqrt{5} < 5 / a,

wobei rechts eine rationale Zahl steht, wenn links eine rationale Zahl steht. Eine solche Abschätzung vermittelt offenbar eine quantitative Vorstellung darüber, wo $\sqrt{5}$ liegt. Die Differenz $5 / a - a$ ist ein Maß für die Güte der Approximation.

Beim Startwert $2$ ergibt sich, dass die Quadratwurzel $\sqrt{5}$ zwischen $2$ und $5 / 2$ liegt. Man nimmt nun das arithmetische Mittel der beiden Intervallgrenzen, also

x_{1} := \frac{2 + \frac{5}{2}}{2} = \frac{9}{4} .

Wegen ${(\frac{9}{4})}^{2} = \frac{81}{16} > 5$ ist dieser Wert zu groß und daher liegt $\sqrt{5}$ im Intervall $[5 \cdot \frac{4}{9}, \frac{9}{4}]$ . Von diesen Intervallgrenzen nimmt man erneut das arithmetische Mittel und setzt

x_{2} := \frac{5 \cdot \frac{4}{9} + \frac{9}{4}}{2} = \frac{161}{72}

als nächste Approximation. So fortfahrend erhält man eine immer besser werdende Approximation von $\sqrt{5}$ .

Allgemein ergibt sich das folgende Heron-Verfahren.

Beispiel

Beim Heron-Verfahren zur näherungsweisen Berechnung von $\sqrt{c}$ einer positiven Zahl $c$ geht man iterativ wie folgt vor. Man startet mit einem beliebigen positiven Startwert $x_{0}$ und berechnet davon das arithmetische Mittel aus $x_{0}$ und $\frac{c}{x_{0}}$ . Dieses Mittel nennt man $x_{1}$ . Es gilt

x_{1}^{2} - c = {(\frac{x_{0} + \frac{c}{x_{0}}}{2})}^{2} - c = \frac{x_{0}^{2} + 2 c + \frac{c^{2}}{x_{0}^{2}}}{4} - c = \frac{x_{0}^{2} - 2 c + \frac{c^{2}}{x_{0}^{2}}}{4} = {(\frac{x_{0} - \frac{c}{x_{0}}}{2})}^{2} \geq 0 .

D.h. dass $x_{1}$ mindestens so groß wie $\sqrt{c}$ ist. Auf $x_{1}$ wendet man iterativ das gleiche Verfahren an und erhält so $x_{2}$ usw. Die rekursive Definition von $x_{n + 1}$ lautet also

x_{n + 1} = \frac{x_{n} + \frac{c}{x_{n}}}{2} .

Nach Konstruktion weiß man, dass $\sqrt{c}$ in jedem Intervall $[c / x_{n}, x_{n}]$ (für $n \geq 1$ ) liegt, da aus $x_{n}^{2} \geq c$ direkt ${(\frac{c}{x_{n}})}^{2} = \frac{c^{2}}{x_{n}^{2}} \leq \frac{c^{2}}{c} = c$ folgt. Bei jedem Schritt gilt

[\frac{c}{x_{n + 1}}, x_{n + 1}] \subseteq [\frac{c}{x_{n}}, x_{n}],

d.h. das Nachfolgerintervall liegt innerhalb des Vorgängerintervalls. Dabei wird bei jedem Schritt die Intervalllänge mindestens halbiert.

Das eben beschriebene Verfahren liefert also zu jeder natürlichen Zahl $n$ eine reelle Zahl, die eine durch eine gewisse algebraische Eigenschaft charakterisierte Zahl beliebig gut approximiert. Bei vielen technischen Anwendungen genügt es, gewisse Zahlen nur hinreichend genau zu kennen, wobei allerdings die benötigte Güte der Approximation von der technischen Zielsetzung abhängt. Es gibt im Allgemeinen keine Güte, die für jede vorstellbare Anwendung ausreicht, so dass es wichtig ist zu wissen, wie man eine gute Approximation durch eine bessere Approximation ersetzen kann und wie viele Schritte man machen muss, um eine gewünschte Approximation zu erreichen. Dies führt zu den Begriffen Folge und Konvergenz.

Definition

Eine reelle Folge ist eine Abbildung

ℕ ⟶ ℝ, n ⟼ x_{n} .

Eine Folge wird zumeist als ${(x_{n})}_{n \in ℕ}$ , oder einfach nur kurz als $(x_{n})_{n}$ geschrieben. Die oben zu einem Startglied $x_{0}$ rekursiv definierten Zahlen zur Berechnung von $\sqrt{c}$ sind ein Beispiel für eine Folge. Manchmal sind Folgen nicht für alle natürlichen Zahlen definiert, sondern nur für alle natürlichen Zahlen $\geq N$ . Alle Begriffe und Aussagen lassen sich dann sinngemäß auch auf diese Situation übertragen.

Definition

Es sei ${(x_{n})}_{n \in ℕ}$ eine reelle Folge und es sei $x \in ℝ$ . Man sagt, dass die Folge gegen $x$ konvergiert, wenn folgende Eigenschaft erfüllt ist

Zu jedem positiven $ϵ > 0$ , $ϵ \in ℝ$ , gibt es ein $n_{0} \in ℕ$ derart, dass für alle $n \geq n_{0}$ die Abschätzung

| x_{n} - x | \leq ϵ

gilt. In diesem Fall heißt $x$ der Grenzwert oder der Limes der Folge. Dafür schreibt man auch

lim_{n \to \infty} x_{n} := x .

Wenn die Folge einen Grenzwert besitzt, so sagt man auch, dass sie konvergiert (ohne Bezug auf einen Grenzwert.), andernfalls, dass sie divergiert.

Man sollte sich dabei das vorgegebene $ϵ$ als eine kleine, aber positive Zahl vorstellen, die eine gewünschte Zielgenauigkeit (oder erlaubten Fehler) ausdrückt. Die natürliche Zahl $n_{0}$ ist dann die Aufwandszahl, die beschreibt, wie weit man gehen muss, um die gewünschte Zielgenauigkeit zu erreichen, und zwar so zu erreichen, dass alle ab $n_{0}$ folgenden Glieder innerhalb dieser Zielgenauigkeit bleiben. Konvergenz bedeutet demnach, dass man jede gewünschte Genauigkeit bei hinreichend großem Aufwand auch erreichen kann. Je kleiner der Fehler, also je besser die Approximation sein soll, desto höher ist im Allgemeinen der Aufwand. Statt mit beliebigen positiven reellen Zahlen $ϵ$ kann man auch mit den Stammbrüchen, also den rationalen Zahlen $\frac{1}{k}$ , $k \in ℕ_{+}$ , arbeiten, siehe Aufgabe, oder mit den inversen Zehnerpotenzen $\frac{1}{1 0^{ℓ}}$ , $ℓ \in ℕ$ .

Zu einem $ϵ > 0$ und einer reellen Zahl $x$ nennt man das Intervall $] x - ϵ, x + ϵ [$ auch die $ϵ$ -Umgebung von $x$ . Eine Folge, die gegen $0$ konvergiert, heißt Nullfolge.

Beispiel

Eine konstante Folge $x_{n} := c$ ist stets konvergent mit dem Grenzwert $c$ . Dies folgt direkt daraus, dass man für jedes $ϵ > 0$ als Aufwandszahl $n_{0} = 0$ nehmen kann. Es ist ja

| x_{n} - c | = | c - c | = | 0 | = 0 < ϵ

für alle $n$ .

Die Folge

x_{n} = \frac{1}{n}

ist konvergent mit dem Grenzwert $0$ . Es sei dazu ein beliebiges positives $ϵ$ vorgegeben. Aufgrund des Archimedes-Axioms gibt es ein $n_{0}$ mit $\frac{1}{n_{0}} \leq ϵ$ . Insgesamt gilt damit für alle $n \geq n_{0}$ die Abschätzung

x_{n} = \frac{1}{n} \leq \frac{1}{n_{0}} \leq ϵ .

Beispiel

Wir betrachten die Folge

x_{n} = 0, 33 \dots 33

mit genau $n$ Nachkommaziffern und behaupten, dass diese Folge gegen $1 / 3$ konvergiert. Dazu müssen wir $| 0, 33 \dots 33 - \frac{1}{3} |$ bestimmen, und dafür müssen wir uns an die Bedeutung von Dezimalbrüchen erinnern. Es ist

x_{n} = 0, 33 \dots 33 = \frac{33 \dots 33}{1 0^{n}} = \frac{\sum_{j = 0}^{n - 1} 3 \cdot 1 0^{j}}{1 0^{n}}

und somit ist

\begin{matrix} | 0, 33 \dots 33 - \frac{1}{3} | & = | \frac{\sum_{j = 0}^{n - 1} 3 \cdot 1 0^{j}}{1 0^{n}} - \frac{1}{3} | \\ = | \frac{3 \cdot (\sum_{j = 0}^{n - 1} 3 \cdot 1 0^{j}) - 1 0^{n}}{3 \cdot 1 0^{n}} | \\ = | \frac{(\sum_{j = 0}^{n - 1} 9 \cdot 1 0^{j}) - 1 0^{n}}{3 \cdot 1 0^{n}} | \\ = | \frac{- 1}{3 \cdot 1 0^{n}} | \\ = \frac{1}{3 \cdot 1 0^{n}} . \end{matrix}

Wenn nun ein positives $ϵ$ vorgegeben ist, so ist für $n$ hinreichend groß dieser letzte Term $\leq ϵ$ .

Lemma

Eine reelle Folge

besitzt maximal einen Grenzwert.

Beweis

Nehmen wir an, dass es zwei verschiedene Grenzwerte $x, y$ , $x \neq y$ , gibt. Dann ist $d := | x - y | > 0$ . Wir betrachten $ϵ := d / 3 > 0$ . Wegen der Konvergenz gegen $x$ gibt es ein $n_{0}$ mit

| x_{n} - x | \leq ϵ für alle n \geq n_{0}

und wegen der Konvergenz gegen $y$ gibt es ein ${n_{0}}^{'}$ mit

| x_{n} - y | \leq ϵ für alle n \geq {n_{0}}^{'} .

Beide Bedingungen gelten dann gleichermaßen für $n \geq max {n_{0}, {n_{0}}^{'}}$ . Es sei $n$ mindestens so groß wie dieses Maximum. Dann ergibt sich aufgrund der Dreiecksungleichung der Widerspruch

d = | x - y | \leq | x - x_{n} | + | x_{n} - y | \leq ϵ + ϵ = 2 d / 3 .

◻