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 $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.

(define eps 1e-04) (define runden (lambda (x eps) (let ([anzahl (round (- (/ (log eps) (log 10))))]) (/ (round (* x (expt 10 anzahl))) (expt 10 anzahl))))) (define wurzel (lambda (z x) (let ([x0 (/ (+ x (/ z x)) 2)]) (if (< (abs (- x0 x)) eps) (runden x0 eps) (wurzel z x0)))))

(wurzel 53 1)

ausführen

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

(define heron (lambda (z) (let ([x (/ (+ z 1) 2)]) (wurzel z x))))

(heron 53)

ausführen

Zurück zum Algorithmusbegriff.