Das Heron-Verfahren
(Ziegenbalg, Ziegenbalg & Zeigenbalg, 2016)
Bereits die Babylonier beschäftigten sich mit dem Lösen von quadratischen Gleichungen, was ihnen bei der Landvermessung half (Ziegenbalg, Ziegenbalg & Zeigenbalg, 2016). Dafür war es allerdings notwendig, ein Verfahren zu finden, mit dem Quadratwurzeln angenähert werden konnten. Ein bis heute gängiger Algorithmus dafür, welcher teilweise auch in der Schule angesprochen wird, ist das Heron-Verfahren.
Das Problem lautet wie folgt: Gegeben sei ein $a\in\mathbb{R}^+$. Gesucht ist ein $b\in\mathbb{R}^+$ mit $b^2 = a$. Oder anders ausgedrückt: Gesucht ist $b=\sqrt{a}$. Geometrisch interpretiert bedeutet das, dass ein Quadrat mit dem Flächeninhalt $a$ gegeben ist und dessen Seitenlänge $b$ gesucht wird. Das Heron-Verfahren findet nun eine beliebig genaue Approximation für $b$. Es basiert auf folgender Idee: Ist ein Rechteck mit Seitenlängen $x$ und $y$ und Flächeninhalt $A=xy$ gegeben, kann ein neues Rechteck konstruiert werden, das denselben Flächeninhalt besitzt, dessen Seitenlängen allerdings näher zusammenliegen als $x$ und $y$. Wird dieser Schritt anschließend iteriert, rücken die Seitenlängen immer näher zusammen, bis beide im Grenzwert gleich sind. Dann sind sie aber zwingender Maßen gleich $\sqrt{A}$. Eine Möglichkeit, dies nun zu erreichen, ist, als neue Seitenlängen
\[\frac{x+y}{2}\qquad\text{ und }\qquad \frac{A}{\frac{x+y}{2}}\]
zu wählen. Der erste Bruch ist das arithmetische Mittel der beiden Ausgangsseiten und der zweite kann umgeschrieben werden zu
\[\frac{2xy}{x +y},\]
was das harmonische Mittel von $x$ und $y$ ist. Der Flächeninhalt des neuen Rechtecks ist trivialerweise wieder $A$. Zu zeigen, dass sowohl das arithmetische als auch das harmonische Mittel echt zwischen $x$ und $y$ liegen, ist an sich jeweils eine einzeilige Rechnung, die hier nur skizziert werden soll: Erstens,
\[x< \frac{x + y}{2} \enspace\Leftrightarrow\enspace 2x < x + y \enspace\Leftrightarrow\enspace x < y\]
und analog die zweite Ungleichung. Zweitens,
\[x< \frac{2xy}{x + y} \enspace\Leftrightarrow\enspace x^2 + xy< 2xy \enspace\Leftrightarrow\enspace x(x - y) < 0\]
und analog die zweite Ungleichung.
Um nun aus der obigen Idee einen Algorithmus zur Bestimmung von $\sqrt{a}$ zu machen, werden als Ausgangsseitenlängen $x_0 = 1$ und $y_0 = a$ gewählt. Das heißt, es wird ein Rechteck mit Fläche $A = a$ betrachtet. Nach obiger Formel ergibt sich im ersten Schritt
\[x_1 = \frac{1 + a}{2}\qquad\text{ und }\qquad y_1 = \frac{2a}{1+a}.\]
Allgemein sind $x_n$ und $y_n$ gegeben und liefern im Anschluss
\[x_{n + 1}=\frac{x_n + y_n}{2}\qquad \text{ und }\qquad y_{n+1} = \frac{a}{x_{n+1}}.\]
Da sich $y_{n + 1}$ sehr einfach und direkt aus $x_{n+1}$ ergibt, wäre es für eine praktische Implementierung besser, wenn die $y$-Werte nicht separat gespeichert werden müssten – sondern nur bestimmt werden, wenn sie tatsächlich gebraucht werden. Dafür wird die Formel für $x_{n+1}$ umgeschrieben:
\[x_{n+1} = \frac{x_n + y_n}{2} = \frac{x_n + \frac{a}{x_n}}{2} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right)\]
Dies resultiert in einer rekursiv definierten Folge $(x_n)_{n\in\mathbb{N}}$, die aufgrund der obigen Überlegungen gegen $\sqrt{a}$ konvergiert.
Für eine Implementierung muss eine Abbruchbedingung definiert werden, um sicherzugehen, dass diese Folge nicht tatsächlich unendlich oft berechnet wird. Üblicherweise wird hierfür ein $\epsilon >0$ vorgegeben und die Berechnung der Folgeglieder abgebrochen, sobald $\lvert x_{n+1} - x_n\rvert \leq \epsilon$.
In Pseudocode aufgeschrieben sieht das gesamte Verfahren wie folgt aus:
Setze x_alt = 1.
Setze x_neu = 0.5 * (x_alt + a / x_alt).
Solange abs(x_neu - x_alt) > epsilon, tue:
| Setze x_alt = x_neu.
| Setze x_neu = 0.5 * (x_alt + a / x_alt).
Das Heron-Verfahren kann in folgender dynamisch-interaktiver Visualisierung getestet werden.
Anleitung: Am Schieberegler links die Quadratwurzel auswählen, die angenähert werden soll. Mit einem Klick auf den Start-Knopf das Verfahren beginnen und mit dem Reset-Knopf zum Ausgangsrechteck zurückkehren.