Das Heron-Verfahren

Grundlagen

Das Heron-Verfahren ist ein Iterationsverfahren zur Bestimmung 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 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_0 = \tfrac{z+1}{2}.

Rekursiver Algorithmus

• Lege als Startwert eine beliebige reelle Zahl x_0 > 0 fest.
• Berechne:

 
x_1 = \frac{x_0 + \frac{z}{x_0}}{2}

• Die Quadratwurzel von z ist x_1, falls |x_1 - x_0| in einer hinreichend kleinen \varepsilon-Umgebung liegt.
• Anderenfalls berechnet sie sich aus der Quadratwurzel von z und dem Startwert x_1.

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 Startwerts ergänzt werden:

Zurück zum Algorithmusbegriff.