Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Heron-Verfahren

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''Autor: Veit Berger (2013)'''

== Grundlagen ==

Das Heron-Verfahren ist ein Iterationsverfahren zur Bestimmung der ''Quadratwurzel'' einer beliebigen reellen Zahl <math>z</math>.
Die Iterationsgleichung kann aus dem [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Newton-Verfahren|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 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 <math>x_0 = \tfrac{z+1}{2}</math>.

== Rekursiver Algorithmus ==

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

== Implementation ==

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

<code id="52a38315e828b">
(define eps 1e-04)

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

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

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

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

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

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

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