Angeordneter Körper/Heron-Verfahren/Motivation für Folge/Einführung/Textabschnitt

Die in Beispiel angeführte Dezimalbruchfolge wirkt vertraut, weil die Dezimalziffernentwicklung vertraut ist, und weil das das ist, was der Taschenrechner ausspuckt. Es gibt aber Folgen, die weit schneller die Quadratwurzel berechnen und die auch der Taschenrechner verwendet. Das sogenannte Heron-Verfahren (auch babylonisches Wurzelziehen genannt) ist ein typisches Beispiel dafür, dass Dezimalbruchfolgen im Allgemeinen nicht optimal sind, und es künstlich wäre, sich auf sie zu beschränken.

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 ℝ$ ein solches Element ist, so hat auch $- x$ diese Eigenschaft. Mehr als zwei Lösungen kann es aber nach Aufgabe 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 positive Schranke gedrückt werden kann. Das klassische Verfahren, um eine Quadratwurzel beliebig gut 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} := 3$ als erster Näherung. Wegen $x_{0}^{2} = 3^{2} = 9 > 5$ ist $x_{0}$ zu groß, d.h. es ist $x_{0} > \sqrt{5}$ . 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

\frac{5}{a} < \sqrt{5} < a

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

Beim Startwert $3$ ergibt sich, dass die Quadratwurzel von $5$ zwischen $5 / 3$ und $3$ liegt. Man nimmt nun das arithmetische Mittel der beiden Intervallgrenzen, also

x_{1} := \frac{3 + \frac{5}{3}}{2} = \frac{7}{3} .

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

x_{2} := \frac{\frac{15}{7} + \frac{7}{3}}{2} = \frac{47}{21}

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

Beispiel

Wir berechnen eine approximierende Folge zu $\sqrt{5}$ wie in Beispiel, allerdings mit dem Startwert $2$ . Die ersten Folgenglieder sind

2, \frac{9}{4}, \frac{161}{72}, \frac{51841}{23184}, \dots .

Der letzte Wert stimmt schon in acht Nachkommastellen mit dem wahren Wert überein.

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

Allgemein ergibt sich das folgende Heron-Verfahren.

Verfahren

Es sei $c \in K_{+}$ ein positives Element in einem angeordneten Körper. Die Heron-Folge zum positiven Startwert $x_{0}$ ist rekursiv durch

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

definiert.

Man berechnet also sukzessive das arithmetische Mittel aus $x_{n}$ und $\frac{c}{x_{n}}$ . Das Produkt dieser beiden Zahlen ist $c$ , somit ist die eine Zahl größer und die andere Zahl kleiner als $\sqrt{c}$ . Die Idee des Verfahrens liegt darin, in der Mitte dieser beiden Zahlen eine bessere Approximation zu finden. Die Folgenglieder der Heron-Folge sind offenbar stets positiv. Typischerweise startet man mit einer natürlichen Zahl als Anfangswert, die in der Größenordnung der Quadratwurzel von $c$ liegt.

Die Idee, die dem Heron-Verfahren zugrunde liegt, kann man auch so verstehen: Man möchte ein Quadrat mit dem Flächeninhalt $c$ , also mit der Seitenlänge $\sqrt{c}$ konstruieren. Man gibt sich eine approximierende Seitenlänge $x$ vor und betrachtet das Rechteck, dessen eine Seitenlänge $x$ und dessen Flächeninhalt $c$ ist. Dann muss die zweite Seitenlänge gleich $\frac{c}{x}$ sein. Wenn $x$ zu groß ist, muss $\frac{c}{x}$ zu klein sein. Für das nächste approximierende Rechteck nimmt man als eine Seitenlänge das arithmetische Mittel aus den beiden Seitenlängen des vorhergehenden Rechtecks.

Satz

Es sei $K$ ein angeordneter Körper und $c \in K_{+}$ . Es sei $x_{0}$ ein positiver Startwert und ${(x_{n})}_{n \in ℕ}$ die zugehörige Heron-Folge. Dann gelten folgende Aussagen.

Für $n \geq 1$ ist
$x_{n}^{2} \geq c$

und

${(\frac{c}{x_{n}})}^{2} \leq c .$

Die Heron-Folge ist ab dem ersten Glied fallend.

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

für $n \geq 1$ .

Für die Intervalllängen
$ℓ_{n} := x_{n} - \frac{c}{x_{n}}$

gilt die Beziehung

$ℓ_{n + 1} = \frac{1}{4 x_{n + 1}} ℓ_{n}^{2}$

und bei $c \geq 1$ gilt insbesondere

$ℓ_{n + 1} \leq \frac{1}{4} ℓ_{n}^{2} .$

Beweis

Es gilt
$\begin{matrix} x_{n}^{2} - c & = {(\frac{x_{n - 1} + \frac{c}{x_{n - 1}}}{2})}^{2} - c \\ = \frac{x_{n - 1}^{2} + 2 c + \frac{c^{2}}{x_{n - 1}^{2}}}{4} - c \\ = \frac{x_{n - 1}^{2} - 2 c + \frac{c^{2}}{x_{n - 1}^{2}}}{4} \\ = {(\frac{x_{n - 1} - \frac{c}{x_{n - 1}}}{2})}^{2} \\ \geq 0. \end{matrix}$
Somit ist
$x_{n}^{2} \geq c .$

Wegen $x_{n} \cdot \frac{c}{x_{n}} = c$ folgt nach Fakt (8), dass ${(\frac{c}{x_{n}})}^{2} \leq c$ ist.
Aufgrund von (1) ist
${(\frac{c}{x_{n}})}^{2} \leq c \leq x_{n}^{2}$

und aufgrund des strengen Wachstums des Quadrierens im positiven Teil ist

$\frac{c}{x_{n}} \leq x_{n} .$

Nach Aufgabe liegt das arithmetische Mittel stets zwischen den beiden Zahlen, also ist

$\frac{c}{x_{n}} \leq x_{n + 1} \leq x_{n} .$
Dies folgt aus (1) und (2).
Nach der Rechnung in Teil (1) ist
$x_{n + 1} - \frac{c}{x_{n + 1}} = \frac{x_{n + 1}^{2} - c}{x_{n + 1}} = \frac{1}{4 x_{n + 1}} {(x_{n} - \frac{c}{x_{n}})}^{2} .$

Bei $c \geq 1$ ist

$\frac{1}{4 x_{n + 1}} \leq \frac{1}{4 c} \leq \frac{1}{4} .$

◻

Das eben beschriebene Verfahren liefert also zu jeder natürlichen Zahl $n$ eine Folge, 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.