Heronverfahren

Das Heronverfahren ist ein rekursiver Algorithmus, der die Wurzel positiver, reeller Zahlen $x\in {ℝ}_{+}$ approximiert.

Die Rekursion lautet:

$w_0:=1$

$w_{i+1}:=\frac{\frac{x}{w_i}+w_i}{2}$ (für $i\in {\mathbb{N}}_{+}$)

Wobei $\underset{i\to \mathrm{\infty }}{\lim }{w}_i=\sqrt{x}$.

Herleitung der rekursiven Formel

Einen vollständigen Beweis gibt es auf ProofWiki: Hero's Method. Diese Erklärung soll den Gedankengang erläutern, wie man auf die Formel kommt.

Sei ein $x\in {ℝ}_{⩾1}$ von dem wir $\sqrt{x}$ bestimmen wollen. Dann nehmen wir in Schritt eins an, die Wurzel sei $w_0:=1$, also $w_0^2\approx x$ Dann ist folgende Unleichung offensichtlich:

$w_0=1⩽\sqrt{x}⩽x$

Das war nun wirklich schlecht geschätzt, wir haben $\sqrt{x}$ damit aber zumindest schonmal eingekesselt. Eine bessere Schätzung ($w_1$) wäre sicherlich der Durchschnitt der beiden Grenzen, also genau die Mitte zwischen 1 und $x$:

$w_1:=\frac{1+x}{2}$

Mit einem kurzen Beweis findet man heraus:

$\sqrt{x}⩽w_1$

Daraus und mit $\frac{x}{\sqrt{x}}=\sqrt{x}$ folgt $\frac{x}{w_1}⩽\sqrt{x}$. Also haben wir erneut zwei Grenzen für $\sqrt{x}$ gefunden:

$\frac{x}{w_1}⩽\sqrt{x}⩽w_1$

Nun können wir mit $w_2:=\frac{\frac{x}{w_1}+w_1}{2}\approx \sqrt{x}$ wieder den Durchschnitt bilden und die Quadratwurzel noch besser approximieren.

Aus dieser Beobachtung erwächst die Vermutung, dass ganz allgemein, alle Folgenmitglieder $w_{i+1}:=\frac{\frac{x}{w_i}+w_i}{2}$ (für $i\in {\mathbb{N}}_{+}$) die Eigenschaft haben:

$\frac{x}{w_{i+1}}⩽\sqrt{x}⩽w_{i+1}$

Der verlinkte Beweis zeigt, dass diese Folge tatsächlich konvergiert, auch für $x\in {ℝ}_{+}$ und diese Eigenschaft immer erfüllt ist.

So ist das Heronverfahren entstanden.