Heron-Algorithmus: Definition, Vorgehen & Beispiel

Der Heron-Algorithmus wird verwendet, um den Wert der Quadratwurzel von natürlichen Zahlen abzuschätzen.

Definition

Die Idee des Heron-Algorithmus ist es, für eine natürliche Zahl $$n$$​ zwei Zahlen $$x,y$$​  zu finden, für welche das Produkt gleich $$n$$​ ist, also $$x\cdot y=n$$​. Diese zwei Zahlen werden dann als Seitenlängen eines Rechtecks mit Fläche $$n$$​ interpretiert. Danach werden immer weiter Seitenlängen von Rechtecken mit Fläche $$n$$​ berechnet, sodass diese Seitenlängen gegen $$\sqrt{n}$$​  konvergieren. Wie oft die Schritte im folgenden Vorgehen wiederholt werden, kann entweder vorher definiert werden oder davon abhängig gemacht werden, wie genau die Approximation sein soll.

Vorgehen

Durch die Approximation einer neuen Seitenlänge als Mittelwert der vorherigen zwei Seitenlängen, nähern sich die Werte immer weiter dem Wert $$\sqrt{n}$$​  an. Je öfter die Schritte 2 und 3 ausgeführt werden, desto genauer wird die Approximation. 

Beispiel – Berechne eine Näherung mit dem Heron-Algorithmus.

Die Näherung von $$\sqrt{12}$$​  ,  die durch den Heron-Algorithmus in drei Schritten und mit den Anfangswerten $$6$$​ und $$2$$​ bestimmt wurde, ist damit $$3,4643$$​. Zum Vergleich ist der genaue Wert von $$\sqrt{12}$$​  auf die ersten vier Stellen gerundet $$3,4641$$​, es wurde also nach nur 3 Schritten eine gute Näherung berechnet!

Veranschaulichung der Iterationsstufen als Rechtecke der Fläche n, mit helleren Graustufen für spätere Iterationsschritte:

Hinweis: Für größere $$i$$​ , also fortgeschrittenere Iterationsstufen, nähert sich das Rechteck immer weiter einem Quadrat mit Seitenlänge $$\sqrt{n}$$.