Heron-Verfahren

Das Babylonische Wurzelziehen (oft auch Heron-Verfahren) ist ein alter iterativer Algorithmus zur Bestimmung einer rationalen Näherung der Quadratwurzel einer Zahl. Es ist ein Spezialfall des Newton-Verfahrens.

Die Iterationsvorschrift lautet:

$x_{n+1}={\frac {x_{n}+{\frac {a}{x_{n}}}}{2}}$.

Hierbei steht $a$ für die Zahl, deren Quadratwurzel bestimmt werden soll. Der Startwert $x_{0}$ der Iteration kann, solange er nicht gleich Null ist, beliebig festgesetzt werden, wobei zu beachten ist, dass negative Werte gegen die negative Quadratwurzel konvergieren.

Triviales Beispiel

Im Folgenden ein triviales Beispiel für die Wurzel aus 9 und die Annäherung nach vier Berechnungsschritten an den wahren Wert ${\sqrt {9}}=3$:

$a=9$ und $x_{0}=1$

$x_{1}={\frac {1+{\frac {9}{1}}}{2}}={\frac {10}{2}}=5$

$x_{2}={\frac {5+{\frac {9}{5}}}{2}}={\frac {\frac {34}{5}}{2}}={\frac {34}{10}}=3{,}4$

$x_{3}={\frac {{\frac {34}{10}}+{\frac {9}{\frac {34}{10}}}}{2}}={\frac {{\frac {34}{10}}+{\frac {90}{34}}}{2}}={\frac {257}{85}}\approx 3{,}0235$

$x_{4}={\frac {{\frac {257}{85}}+{\frac {9}{\frac {257}{85}}}}{2}}={\frac {{\frac {257}{85}}+{\frac {765}{257}}}{2}}={\frac {65537}{21845}}\approx 3{,}00009$

Geometrische Veranschaulichung des Heron-Verfahrens

Der Flächeninhalt eines Quadrates kann über das Quadrat der Länge seiner Seiten berechnet werden. Die Bestimmung der Quadratwurzel einer gegebenen Zahl $a$ kann also geometrisch gedeutet werden als Bestimmung der Seitenlänge (genauer: als rationale Näherung zu ${\sqrt {a}}$) eines Quadrates mit dem Flächeninhalt $a$.

Die Idee ist nun, von einem Rechteck des Flächeninhaltes $a$ auszugehen und die Seitenlängen einem Quadrat immer weiter anzunähern.

Dazu wird ein Startwert gewählt, im obigen Fall gilt $a=9$ und als Startwert wurde $x_{0}=1$ gewählt. Geometrisch bedeutet dieses, dass von einem Rechteck der Seitenlänge $x_{0}=1$ ausgegangen wird. Die andere Seitenlänge dieses Rechtecks ergibt sich aus dem vorgegebenen Flächeninhalt: $y_{0}={\frac {9}{1}}=9$

Bei der Betrachtung ist unmittelbar ersichtlich, dass es eine geeignetere Näherung an ein Quadrat gibt, denn die eine Seitenlänge $x_{0}=1$ ist zu klein, die andere mit $y_{0}=9$ zu groß.

Um eine verbesserte Annäherung an die Länge einer Quadratseite zu erhalten, kann das arithmetische Mittel der Seitenlängen $x_{0}$ und $y_{0}$ dienen (Hier gibt es eine ganze Reihe von Möglichkeiten, das Verfahren zu verfeinern.):

$x_{1}={\frac {x_{0}+y_{0}}{2}}={\frac {9+1}{2}}=5$

Die Länge der zweiten Seite dieses neuen Näherungs-Rechtecks ergibt sich wieder durch den vorgegebenen Flächeninhalt $a$:

$y_{1}={\frac {a}{x_{1}}}={\frac {9}{5}}=1{,}8$

Die Werte $x_{1}=5$ und $y_{1}=1{,}8$ sind geometrisch gedeutet die Seitenlängen eines zweiten Näherungs-Rechtecks. Dieses und die folgenden Rechtecke lassen sich nun weiter verbessern durch erneute Bildung des arithmetischen Mittelwertes als verbesserte Näherung an die Seitenlänge eines Quadrates mit der Seitenlänge ${\sqrt {a}}$.

Konvergenz

Das Verfahren konvergiert relativ rasch innerhalb weniger Schritte. Da es sich aus dem Newtonschen Näherungsverfahren ableiten lässt, ist die Konvergenzordnung 2.
Es gelten:
${\sqrt {a}}\leq x_{n+1}\leq x_{n}(n=1,2...)$
und
$\lim _{n\to \infty }x_{n}={\sqrt {a}}$

Fehler

Für den Fehler der Heron-Folge ${x_{n}}(n\geq 1)$ gilt:
$a/x_{n}\leq {\sqrt {a}}\leq x_{n}$ (Einschließung), sowie
$x_{n}-{\sqrt {a}}\leq {\frac {1}{2{\sqrt {a}}}}(x_{n-1}-{\sqrt {a}})^{2}$ (quadratische Konvergenz)

Implementierung in Software

Das Verfahren eignet sich besonders gut zur Implementierung in Software, wird heute angesichts der breiten Verfügbarkeit numerischer Prozessorhardware aber nur noch selten benötigt. Man kommt dabei nur mit Grundrechenarten aus, s. o.

Wenn dazu noch eine Gleitkommadarstellung mit einem Zweier-Exponenten benutzt wird, wird der Ansatz relativ einfach:

• Zunächst spaltet man vom Exponenten eine gerade Anzahl ab, so dass als Exponent entweder eine 0 oder 1 übrigbleibt, die Zahl also auf das Intervall { ½ , 2 } normalisiert wird. In diesem Intervall ist die Wurzelfunktion eine nur schwach gekrümmte Kurve, lässt sich also numerisch gut behandeln.
• Als Startwert für die eigentliche Iteration gibt es mehrere Möglichkeiten, diese Kurve durch eine noch einfachere zu approximieren. Mit den komplizierteren Ansätzen lässt sich ggf. ein Iterationsschritt einsparen:
  • eine einfache Konstante (z. B. 1);
  • eine Gerade mit Steigung 1/2 und einer additiven Konstante von $(2*2^{1/4}-{\sqrt {2}})^{2}\approx 0,929683$ ;
  • eine Gerade mit optimierter Steigung und einer additiven Konstante.
• Ausgehend von dem so ermittelten Startwert führt man eine feste Anzahl von Iterationsschritten durch. Die nötige Anzahl, um die gewünschte Genauigkeit zu erreichen, lässt sich dank der obigen Fehlerabschätzung als Worst Case innerhalb des Startintervalls direkt ausrechnen. Bei 32 Bits Mantisse und dem mittleren Startansatz braucht man z. B. nur drei Schritte. Diese fest gewählte Anzahl erspart wesentlich aufwendigere Abfragen auf Erreichung der Genauigkeit. Der Ersatz der genannten Konstanten durch die Zahl 1,0 ändert daran nichts. Auch der noch kompliziertere Ansatz brächte zumindest bei dieser Genauigkeit keine Einsparung eines weiteren Iterationsschritts. Bei höheren Genauigkeitsanforderungen kann das anders aussehen.
• Zum Schluss muss man den Exponenten restaurieren, indem man die Hälfte des im ersten Schritt abgespalteten Werts wieder hinzufügt.

Geschichte

Dieses Verfahren ist auch unter dem Namen Heron-Verfahren bekannt. Es wurde nach Heron von Alexandria benannt und entstammt seiner Formelsammlung.