Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Heron-Verfahren

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
'''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 [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Newton-Verfahren|Newton-Verfahren]] für die Nullstelle der quadratischen Funktion $f(x)=x^2-z$ hergeleitet werden:

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

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:
  <blockquote>$x_0 = \frac{x + \frac{z}{x}}{2}$</blockquote>
* 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.

<code id="5badf754b3e71">
(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)))))
</code>

<run id="52912b57d10b0">
(wurzel 53 1)
</run>

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

<code id="546f68f63bd2c">
(define heron
  (lambda (z)
    (let ([x (/ (+ z 1) 2)])
      (wurzel z x))))
</code>

<run id="52a38315e83c5">
(heron 53)
</run>

Zurück zum [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff|Algorithmusbegriff]].