Babylonisches Wurzelziehen

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 x0 der Iteration kann, solange er nicht gleich Null ist, beliebig festgesetzt werden, wobei zu beachten ist, dass negative Werte gegen die negative Quadratwurzel konvergieren.

Inhaltsverzeichnis

Triviales Beispiel

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

a = 9 und x0 = 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} \approx3{,}0235
x_4=\frac{\frac{257}{85} + \frac{9}{\frac{257}{85}}}{2} =\frac{\frac{257}{85} + \frac{765}{257}}{2}  =\frac{65537}{21845} \approx3{,}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 x0 = 1 gewählt. Geometrisch bedeutet dieses, dass von einem Rechteck der Seitenlänge x0 = 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 x0 = 1 ist zu klein, die andere mit y0 = 9 zu groß.

Um eine verbesserte Annäherung an die Länge einer Quadratseite zu erhalten, kann das arithmetische Mittel der Seitenlängen x0 und y0 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 x1 = 5 und y1 = 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äßt, ist die Konvergenzordnung 2.
Es gelten:
\sqrt{a} \le x_{n+1} \le 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 \ge 1) gilt:
a/x_n \le \sqrt{a} \le x_n (Einschließung), sowie
x_n-\sqrt{a} \le \frac {1}{2\sqrt{a}} (x_{n-1}-\sqrt{a})^2 (quadratische Konvergenz)

Geschichte

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

See also: Babylonisches Wurzelziehen, Algorithmus, Formelsammlung, Heron von Alexandria, Iteration, Konvergenzordnung, Newton-Verfahren, Newtonsches Näherungsverfahren, Quadratwurzel