Das Heron-Verfahren

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Autor: Veit Berger (2013)

Grundlagen

Das Heron-Verfahren ist ein Iterationsverfahren zur Bestimmung der Quadratwurzel einer beliebigen positiven reellen Zahl $z$. Die Iterationsgleichung kann aus dem Newton-Verfahren für die Nullstelle der quadratischen Funktion $f(x)=x^2-z$ hergeleitet werden:

$x_0 = x - \frac{f(x)}{f'(x)}$
$x_0 = x - \frac{x^2 - z}{2 \, x}$
$x_0 = \frac{2 \, x^2 - x^2 + z}{2 \, x}$
$x_0 = \frac{x^2 + z}{2 \, x}$
$x_0 = \frac{x + \frac{z}{x}}{2}$

Der Startwert $x$ der Iteration kann, solange er nicht Null ist, mit beliebigen positiven reellen Zahlen festgesetzt werden. Die Iteration konvergiert dann immer. Eine qualifizierte Schätzung für den Startwert erhält man aus $x = \tfrac{z+1}{2}$.

Rekursiver Algorithmus

  • Lege als Startwert eine beliebige reelle Zahl $x > 0$ fest.
  • Berechne:
$x_0 = \frac{x + \frac{z}{x}}{2}$
  • Die Quadratwurzel von $z$ ist $x_0$, falls $|x_0 - x|$ in einer hinreichend kleinen $\varepsilon$-Umgebung liegt.
  • Anderenfalls berechnet sie sich aus der Quadratwurzel von $z$ und dem neuen Startwert $x_0$.

Implementation

Zunächst ist es notwendig, eine hinreichend kleine Epsilon-Umgebung festzulegen. Der Rückgabewert wird entsprechend dieser Epsilon-Umgebung sinnvoll gerundet.

Nun kann die Berechnung mit einem sinnvollen Startwert ergänzt werden:

Zurück zum Algorithmusbegriff.

Persönliche Werkzeuge