Heronverfahren

Das Heronverfahren ist ein rekursiver Algorithmus, der die Wurzel positiver, reeller Zahlen $x\in \mathbb {R} _{+}$ 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 $\lim _{i\rightarrow \infty }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 \mathbb {R} _{\geqslant 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\leqslant {\sqrt {x}}\leqslant 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}}\leqslant w_{1}$

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

${\frac {x}{w_{1}}}\leqslant {\sqrt {x}}\leqslant 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}}}\leqslant {\sqrt {x}}\leqslant w_{i+1}$

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

So ist das Heronverfahren entstanden.