Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Heron-Verfahren

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Grundlagen ==

Das Heron-Verfahren ist ein Iterationsverfahren zur Bestummung der ''Quadratwurzel'' einer beliebigen reellen Zahl <math>z</math>.
Die Iterationsgleichung kann aus dem Newton-Verfahren für die Nullstelle der quadratischen Funktion <math>f(x)=x^2-z</math> hergeleitet werden.
Die Iterationsvorschrift lautet:

<blockquote><math>x_{n+1}=\frac{x_n + \frac{z}{x_n}}{2}</math></blockquote>

Der Startwert <math>x_0</math> der Iteration kann, solange er nicht gleich Null ist, mit beliebigen positiven reellen Zahlen festgesetzt werden. Die Iteration konvergiert dann immer. Einen qualifizierten Schätzwert für den Startwert erhält man aus <math>x_0 = \tfrac{z+1}{2}</math>.

== Implementation ==

Zum Abbruch der Iteration ist es sinnvoll, eine hinreichend kleine Epsilon-Umgebung festzulegen. Das Ergebnis der Iteration wird auf eine dieser Epsilon-Umgebung angapasste Anzahl von Dezimalstellen gerundet.

<code id="52912952ee612">
(define eps 1e-06)

(define runden
  (lambda (x eps)
    (let ([anzahl (round (- (/ (log eps) (log 10))))])
      (/ (round (* x (expt 10 anzahl))) (expt 10 anzahl)))))

(define wurzel
  (lambda (z x0)
    (let ([x1 (/ (+ x0 (/ z x0)) 2)])
      (if (< (abs (- x1 x0)) eps)
          (runden x1 eps)
          (wurzel z x1)))))
</code>

<run id="52912952ee751">
(wurzel 4 2)
</run>

Nun kann die Berechnung eines sinnvollen Startwerts ergänzt werden:

<code id="52912952ee695">
(define heron
  (lambda (z)
    (let ([x0 (/ (+ z 1) 2)])
      (wurzel z x0))))
</code>

<run id="52912952ee7d2">
(heron 2)
</run>