Das Heron-Verfahren
Aus ProgrammingWiki
Autor: Veit Berger (2013)
Grundlagen
Das Heron-Verfahren ist ein Iterationsverfahren zur Bestimmung der Quadratwurzel einer beliebigen positiven reellen Zahl . 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.