Processing math: 0%

Das Heron-Verfahren

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Autor: Veit Berger (2013)

Grundlagen

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

x_0 = x - \frac{f(x)}{f'(x)}
x_0 = x - \frac{x^2 - z}{2 \, x}
x_0 = \frac{2 \, x^2 - x^2 + z}{2 \, x}
x_0 = \frac{x^2 + z}{2 \, x}
x_0 = \frac{x + \frac{z}{x}}{2}

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

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

Zurück zum Algorithmusbegriff.

Persönliche Werkzeuge