Heron-Verfahren zur Wurzelberechnung

Das Heron-Verfahren (auch bekannt als Babylonisches Wurzelziehen) ist ein iteratives Verfahren zur näherungsweisen Bestimmung der Quadratwurzel einer Zahl.
Die Iterationsvorschrift lautet:
xn+1=12⋅(xn+qxn)x_{n+1}= \dfrac 1 2 \cdot \left(x_n + \dfrac{q}{x_n}\right).(1)
Es bezeichnet qq die Zahl, deren Quadratwurzel bestimmt werden soll und x0x_0 den Startwert der Iteration. Letzterer kann eine beliebige von Null verschiedene Zahl sein. Ist x0<0x_0<0, so konvergent das Verfahren jedoch gegen die negative Quadratwurzel −q\uminus\sqrt q.
 
 

Beispiel

HFunk.png
Grafische Veranschaulichung der ersten Iterationsschritte
Zur näherungsweisen Berechnung Wurzel aus 99 verwenden wir den Startwert x0=1x_0=1
x1=12⋅(1+91)=102=5x_1=\dfrac1 2\cdot \left(1 + \dfrac{9}{1}\right) =\dfrac{10}{2}=5
x2=12⋅(5+95)=12⋅(345)x_2=\dfrac1 2\cdot \left(5 + \dfrac{9}{5}\right) =\dfrac1 2\cdot \left(\dfrac {34}{5}\right) =3410=\dfrac{34}{10} =175=3,4=\dfrac {17} 5 = 3{,}4
x3=12⋅(175+9175)=12⋅(175+4517)x_3=\dfrac1 2\cdot \left(\dfrac {17} 5 + \dfrac{9}{\dfrac {17} 5}\right) =\dfrac1 2\cdot \left(\dfrac{17}{5} + \dfrac{45}{17}\right)=12⋅51485=25785≈3,0235=\dfrac1 2\cdot\dfrac {514}{85}=\dfrac{257}{85} \approx3{,}0235
x4=12⋅(25785+925785)x_4=\dfrac1 2\cdot \left(\dfrac{257}{85} + \dfrac{9}{\dfrac{257}{85}}\right) =12⋅(25785+765257)=\dfrac1 2\cdot \left(\dfrac{257}{85} + \dfrac{765}{257}\right) =12⋅13107421845=\dfrac1 2\cdot \dfrac{131074}{21845} =6553721845≈3,00009155=\dfrac{65537}{21845} \approx3,00009155
Wie wir erkennen können, konvergiert das Verfahren in unserem Beispiel recht gut, schon im 4. Iterationschritt ist das Ergebnis 33 auf vier Stellen nach dem Komma angenähert.
Im folgenden Formular finden Sie weitere Iterationsschritte aufgelistet und sie können mit den Werten experimentieren.

Herleitung aus dem Newtonverfahren

Wir betrachten die Funktion f(x)=x2−qf(x)=x^2-q. Die Nullstellen dieser Funktion sind q\sqrt q und −q-\sqrt q, daher liefert und das Newtonverfahren, wenn es auf ff angewandt wird, eine Wurzel von qq. Die allgemeine Iterationsvorschrift des Newtonverfahrens lautet: xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\dfrac {f(x_n)}{f^\prime (x_n)}. Wir erhalten mit f′(x)=2xf^\prime (x)=2x dann:
xn+1=xn−xn2−q2xnx_{n+1}=x_n-\dfrac{x_n^2-q}{2x_n} =2xn2−xn2+q2xn=\dfrac{2x_n^2 -x_n^2+q}{2x_n}=12⋅(xn+qxn)=\dfrac 1 2 \cdot \left(x_n + \dfrac{q}{x_n}\right),
also die obige Iterationsvorschrift (1).
Zu Konvergenzüberlegungen siehe Satz C7VC und folgende.

Geometrische Veranschaulichung

Wir definieren yn=qny_n=\dfrac q n. Setzen wir die in die Iterationsvorschrift (1) ein so ergibt sich
xn+1=12⋅(xn+yn)x_{n+1}=\dfrac 1 2\cdot (x_n+y_n),(2)
und die ursprüngliche Vorschrift ist als arithmetisches Mittel zweier Größen dargestellt. Da yn+1y_{n+1} nur von qq und nicht von xnx_n abhängt, liegt nun folgende Interpretation nahe. Wenn xnx_n die Seite eines Rechtecks mit dem Flächeninhalt qq ist, so muss die andere Seite genau die Länge yn=qny_n=\dfrac q n haben. Da xnx_n gegen die Wurzel q\sqrt q konvergent, nähern sich die Rechtecke in den einzelnen Iterationsschritten immer mehr einem Quadrat an.
Beim Übergang von einem Rechteck zum nächsten ergibt sich eine Seite als arithmetisches Mittel der beiden Ausgangsseiten. Die Länge der zweiten Seite ist genau so gewählt, dass wieder ein flächengleiches Rechteck entsteht. Mit fortlaufender Iteration nähern sich diese Rechtecke immer mehr einem Quadrat an.

Verallgemeinerung des Verfahrens

Dieses Verfahren kann man leicht verallgemeinern, um die mm-te Wurzel zu berechnen. Die Iterationsvorschrift analog wie oben aus dem Newtonverfahren für die Funktion f(x)=xm−qf(x)=x^m-q hergeleitet werden:
xn+1=(m−1)xnm+qm⋅xnm−1x_{n+1}= \dfrac{(m-1) x_n^m + {q}}{m\cdot x_n^{m-1}}.

Es gibt jedoch noch einen anderen Grund für die hohe Wertschätzung der Mathematik; sie allein bietet den Naturwissenschaften ein gewisses Maß an Sicherheit, das ohne Mathematik nicht erreichbar wäre.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Wurzeln