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:

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

Der Startwert <math>x</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 = \tfrac{z+1}{2}</math>.

== Rekursiver Algorithmus ==

* Lege als Startwert eine beliebige reelle Zahl <math>x > 0</math> fest.
* Berechne:
  <blockquote><math>x_0 = \frac{x + \frac{z}{x}}{2}</math></blockquote>
* Die Quadratwurzel von <math>z</math> ist <math>x_0</math>, falls <math>|x_0 - x|</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_0</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="546f68f63bc98">
(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 x)
    (let ([x0 (exact->inexact (/ (+ 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 Startwerts 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]].