Das Heron-Verfahren

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2013-11-23T22:16:51+00:00. Aktuelle Version

Grundlagen

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

x_{n+1}=\frac{x_n + \frac{z}{x_n}}{2}

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

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.

(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)))))

(wurzel 4 2)

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

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

(heron 2)

Das Heron-Verfahren

Grundlagen

Implementation

Suche