www.wikidata.de-de.nina.az

Heron Verfahren Das Heronsche Näherungsverfahren oder babylonische Wurzelziehen ist ein Rechenverfahren zur Berechnung e

Heron-Verfahren

Das Heron-Verfahren, Heronsche Näherungsverfahren oder babylonische Wurzelziehen ist ein Rechenverfahren zur Berechnung einer Näherung der Quadratwurzel einer reellen Zahl . Hierbei wird die Zahl als Flächeninhalt eines Rechtecks aufgefasst (z. B. mit Seitenlängen und ). Dieses Rechteck wird dann schrittweise in ein flächengleiches Quadrat transformiert, indem man in jedem Rechenschritt die längere Seite der vorherigen Rechtecks verkürzt und seine kürzere Seite so verlängert, so dass der Flächeninhalt erhalten bleibt. Die verkürzte neue längere Seite berechnet sich dabei als Mittelwert der beiden Seiten des vorherigen Rechtecks (siehe Grafik rechts). Das Verfahren ist nach dem griechischen Mathematiker Heron von Alexandria benannt, der es in seinem Werk Metrica beschrieb. Allerdings wurde es schon über 1000 Jahre früher von den Babyloniern benutzt.

Berechnung von mit dem Heronverfahren

Geometrische Veranschaulichung des Heron-Verfahrens Bearbeiten

Die ersten 4 Schritte zur Berechnung der Wurzel aus 9 mit dem Heron-Verfahren

Dem Heron-Verfahren liegt die Idee zu Grunde, dass ein Quadrat mit Flächeninhalt eine Seitenlänge von hat. Ausgangspunkt des Verfahrens ist ein beliebiges Rechteck mit Flächeninhalt . Schritt für Schritt wird das Seitenverhältnis des Rechtecks so geändert, dass sich seine Form immer mehr der eines Quadrats annähert, während der Flächeninhalt gleich bleibt. Die Seitenlängen des Rechtecks sind die Näherungswerte für .

Im ersten Schritt wird eine beliebige Seitenlänge für das Rechteck gewählt. Damit dieses den gewünschten Flächeninhalt hat, wird die zweite Seitenlänge mit der Formel

berechnet. Als Beispiel soll die Wurzel aus 9 berechnet werden. Für die eine Seitenlänge wird der Wert 9 gewählt, sodass sich die andere Seitenlänge zu 1 berechnet. Das erste Rechteck hat deshalb die folgende Form.

Die Ähnlichkeit dieses Rechteckes mit einem Quadrat ist gering. Das kommt auch dadurch zum Ausdruck, dass die Seitenlängen 1 und 9 sehr schlechte Näherungen für die Wurzel aus 9 sind.

Um eine bessere Annäherung an ein Quadrat zu erhalten, muss die lange Seite gekürzt und die kurze Seite verlängert werden. Als neue Länge der langen Seite wird der Mittelwert

der beiden bisherigen Seitenlängen genommen. Die Länge der anderen Seite berechnet sich wie oben zu

Im Beispiel ergibt sich als Mittelwert die Seitenlänge 5. Die dazugehörige kurze Seite hat eine Länge von 1,8.

Auch hier ist die Ähnlichkeit zu einem Quadrat noch gering. Allerdings ist das neue Rechteck im Vergleich zum vorhergehenden kompakter.

Der beschriebene Ablauf wird in jedem weiteren Schritt des Heron-Verfahrens wiederholt. Der Mittelwert der Seitenlängen eines Rechtecks entspricht der Länge der langen Seite des neuen Rechtecks und die Länge der kurzen Seite lässt sich daraus jeweils wie oben beschrieben berechnen. Im Beispiel entstehen so in den nächsten zwei Schritten die folgenden beiden Rechtecke.

Das letzte Rechteck ist schon annähernd quadratisch. Die Seitenlänge 3,024 liegt entsprechend nah bei 3, dem exakten Wert von .

Heron-Verfahren als Spezialfall des Newton-Verfahrens Bearbeiten

Heron-Verfahren zur Berechnung von mit drei verschiedenen Startwerten

Die Iterationsgleichung des Heron-Verfahrens kann aus dem Newton-Verfahren für die Nullstelle der quadratischen Funktion hergeleitet werden. Mit folgt aus der Rekursionsformel des Newton-Verfahrens die Iterationsvorschrift:

Der Startwert der Iteration kann, solange er nicht gleich Null ist, beliebig festgesetzt werden, die Iteration konvergiert immer. Zu beachten ist, dass bei negativen Startwerten die Iteration gegen die negative Quadratwurzel konvergiert. Eine qualifizierte Schätzung für den Startwert erhält man aus der Taylorreihen-Entwicklung der binomischen Reihe um 1, deren zwei erste Glieder diese Gleichung liefern:

Das Heron-Verfahren gehört zu den Fixpunktverfahren. Setzt man , so gilt für den Fixpunkt (der die Bedingung erfüllt) mit der (positiven) Lösung .

Beispiel Bearbeiten

Die Folgenglieder der babylonischen Wurzelfolge mit dem Startwert .

Im folgenden einfachen Beispiel wird die Wurzel aus 9 als Annäherung mit drei Berechnungsschritten an den wahren Wert gezeigt. Mit wird der Startwert für die Iteration berechnet und in die Iterationsvorschrift eingesetzt:

Konvergenz Bearbeiten

Das Verfahren lässt sich folgendermaßen als rekursiv definierte Folge ausdrücken:

Es handelt sich dabei um eine rein positive Folge. Man kann nun zeigen, dass für alle das -te Folgenglied ist. Dazu zeigt man die äquivalente Ungleichung :

Weiter zeigt man, dass eine monoton fallende Folge ist:

Durch die gezeigte Beschränktheit und Monotonie muss die Folge konvergieren, und zwar von oben gegen die gesuchte Wurzel:

Da sich das Heron-Verfahren aus dem Newtonschen Näherungsverfahren ableiten lässt und die zu berechnende Nullstelle einfach ist, ist die Konvergenzordnung 2.

Das Verfahren konvergiert sehr schnell, wenn bereits eine gute Näherung vorliegt. Die Zahl der richtigen Stellen wird mit jedem Schritt etwa verdoppelt. Wenn die erste Näherung jedoch schlecht ist, sind viele Schritte für eine gute Näherung nötig.

Wenn zum Beispiel aus einer Ganzzahl mit 200 Binärstellen die Wurzel berechnet werden soll und man mit als erster Näherung beginnt, dann wird die Näherung mit jedem Schritt um etwa eine Binärstelle kürzer, d. h. erst nach etwa 100 Schritten hat die Näherung die richtige Länge von 100 Stellen. Danach reichen sechs bis sieben weitere Schritte (), um alle 100 Stellen vor dem Komma richtig zu berechnen.

Es empfiehlt sich somit, einen möglichst genauen Startwert zu bestimmen. Im Beispiel sollte man zuerst die Bitlänge von ermitteln und einen Startwert mit der halben Länge verwenden.

Fehlerabschätzung Bearbeiten

Für die Heron-Folge gilt:

und für den Fehler die folgende Abschätzung

Diese Fehlerabschätzung hat den Nachteil, dass nicht bekannt ist, sondern berechnet werden soll. Unter Verwendung der obigen Einschließung erhält man folgende praktikable Abschätzung:

Angewandt auf obiges Beispiel erhält man:

Für den relativen Fehler

gilt die Rekursion

Die Folge der ist also bei gegebenem relativen Fehler der Startnäherung unabhängig von .

Implementierung in Software Bearbeiten

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

Wenn dazu noch eine Gleitkommadarstellung mit einem Zweier-Exponenten benutzt wird, wird der Ansatz relativ einfach, als Beispiel wird die Wurzel aus 5 betrachtet und der relative Fehler zum Endwert verfolgt:

  • Zunächst wird von diesem Zweier-Exponenten eine gerade Anzahl abgespaltet, so dass als Exponent entweder eine 0 oder 1 übrig bleibt, die Zahl also auf das Intervall normalisiert wird. In diesem Intervall ist die Wurzelfunktion eine nur schwach gekrümmte Kurve, lässt sich also numerisch gut behandeln. Beispiel:, es wird also vorerst nur noch mit dem Ziel behandelt.
  • Als Startwert für die eigentliche Iteration approximiert man diese Kurve durch eine noch einfachere, die sich direkt ohne Iteration berechnen lässt. Mit dieser Anfangsberechnung wird der Startwert ermittelt, mit dem die folgende Iteration begonnen wird. Man kann diese Kurve mehr oder weniger aufwendig ansetzen, mit den steigend komplizierteren Ansätzen unten lässt sich gegebenenfalls ein Iterationsschritt einsparen:
    • eine einfache Konstante (beispielsweise 1),
      Beispiel: , relativer Fehler
    • eine Gerade mit Steigung und einer additiven Konstante von als Vereinfachung des nachfolgenden Falls
      Beispiel: , relativer Fehler
    • eine Gerade mit Steigung und einer additiven, optimierten Konstante von ,
      Beispiel: , relativer Fehler .
    • eine Gerade mit optimierter Steigung und einer additiven Konstante hier nicht näher betrachtet.
  • 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 beispielsweise 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.
    Beispiel mit drei Schritten nach Ansatz 1 (Konstante 1, mit den anderen Ansätzen konvergiert es noch einen Schritt schneller):
    , relativer Fehler , relativer Fehler
    , relativer Fehler kleiner als
    Man sieht die Wirkung der quadratischen Konvergenz, dass sich der relative Fehler von Schritt zu Schritt jeweils quadriert oder die Anzahl gültiger Stellen bzw. der negative Fehlerexponent etwa verdoppelt.
  • Zum Schluss wird der Exponent restauriert, indem man die Hälfte des im ersten Schritt abgespalteten Werts wieder hinzufügt.
    Beispiel: .

Verallgemeinerung des Verfahrens Bearbeiten

Dieses Verfahren lässt sich verallgemeinern, so dass für berechnet wird. Je größer ist, desto mehr Schritte werden benötigt, um die Wurzel genau zu berechnen.

Dabei wird das Newton-Verfahren zur Bestimmung der positiven Nullstelle der Funktion angewandt. Mit folgt aus der Rekursionsformel des Newton-Verfahrens die Iterationsvorschrift:

Beispielsweise lautet die rekursive Formel zur Berechnung der Kubikwurzel:

Hier muss die Folge mit einem geeigneten Startwert für den gesuchten Wert von gestartet werden.

Für ganzzahliges positives gelten die gleichen Konvergenzaussagen wie oben für

Bestimmung des Kehrwerts Bearbeiten

Für erhält man ein Verfahren, mit dem (ohne Verwendung der Division!) der Kehrwert näherungsweise errechnet werden kann:

Dieses Verfahren konvergiert für alle quadratisch gegen

Die Iteration ermöglichte für erste Computer ohne eingebaute Division die Zurückführung dieser Operation auf Multiplikation und Subtraktion. Die Division von zwei Zahlen wurde so ausgeführt, dass der Kehrwert des Nenners bestimmt wurde und mit dem Zähler multipliziert wurde.

Beispiel Bearbeiten

Es soll näherungsweise berechnet werden mit dem Startwert :

Für den Startwert erhält man

somit keine Konvergenz gegen den gesuchten Wert von

Historisches Bearbeiten

Das Verfahren war in Mesopotamien bereits zur Zeit von Hammurapi I. (ca. 1750 v. Chr.), eines Königs von Babylon, bekannt. Um 100 n. Chr. wurde es von Heron von Alexandria im ersten Buch seines Werkes Metrica beschrieben.

Literatur Bearbeiten

  • Bernd Ziegenbalg: Algorithmen: Von Hammurapi bis Gödel. Harri Deutsch Verlag 2007, ISBN 978-3-8171-1814-4, S. 54–59.
  • David Fowler, Eleanor Robson: Square Root Approximations in Old Babylonian Mathematics (PDF; 215 kB). Historica Mathematica 25, 1998, S. 366–378.
  • Hans R. Schwarz, Norbert Köckler: Numerische Mathematik. 6. Auflage. Teubner, Stuttgart 2006, ISBN 3-519-42960-8, S. 189–192.

Weblinks Bearbeiten

Commons: Heron-Verfahren – Sammlung von Bildern, Videos und Audiodateien

Anmerkungen Bearbeiten

  1. Startwert: Sofern der Ausgangswert bereits als Binärzahl (im Stellenwertsystem) vorliegt, kann einfach gezählt werden, an welcher Stelle seine höchstwertige '1' steht; Startwert wird dann . Sofern der Ausgangswert in (Binär-)Exponentialdarstellung vorliegt, kann als Startwert einfach der Exponent halbiert werden (um 1 Bit nach rechts schieben). Siehe auch Abschnitt Implementierung in Software

Einzelnachweise Bearbeiten

  1. (Nicht mehr online verfügbar.) In: Montanuniversität Leoben. 23. Februar 2005, archiviert vom Original am 22. August 2019; abgerufen am 27. August 2019.
  2. Bernd Ziegenbalg: Algorithmen: Von Hammurapi bis Gödel. Harri Deutsch Verlag 2007, ISBN 978-3-8171-1814-4, S. 54 (Auszug (Google))
  3. John J. O’Connor, Edmund F. Robertson: Heron-Verfahren. In: MacTutor History of Mathematics archive.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Heron Verfahren Heronsche Naherungsverfahren oder babylonische Wurzelziehen ist ein Rechenverfahren zur Berechnung einer Naherung der Quadratwurzel einer reellen Zahl a gt 0 displaystyle a gt 0 Hierbei wird die Zahl a displaystyle a als Flacheninhalt eines Rechtecks aufgefasst z B mit Seitenlangen a displaystyle a und 1 displaystyle 1 Dieses Rechteck wird dann schrittweise in ein flachengleiches Quadrat transformiert indem man in jedem Rechenschritt die langere Seite der vorherigen Rechtecks verkurzt und seine kurzere Seite so verlangert so dass der Flacheninhalt a displaystyle a erhalten bleibt Die verkurzte neue langere Seite berechnet sich dabei als Mittelwert der beiden Seiten des vorherigen Rechtecks siehe Grafik rechts Das Verfahren ist nach dem griechischen Mathematiker Heron von Alexandria benannt der es in seinem Werk Metrica beschrieb Allerdings wurde es schon uber 1000 Jahre fruher von den Babyloniern benutzt Berechnung von 5 displaystyle sqrt 5 mit dem Heronverfahren Inhaltsverzeichnis 1 Geometrische Veranschaulichung des Heron Verfahrens 2 Heron Verfahren als Spezialfall des Newton Verfahrens 2 1 Beispiel 2 2 Konvergenz 2 3 Fehlerabschatzung 3 Implementierung in Software 4 Verallgemeinerung des Verfahrens 4 1 Bestimmung des Kehrwerts 4 2 Beispiel 5 Historisches 6 Literatur 7 Weblinks 8 Anmerkungen 9 EinzelnachweiseGeometrische Veranschaulichung des Heron Verfahrens Bearbeiten nbsp Die ersten 4 Schritte zur Berechnung der Wurzel aus 9 mit dem Heron VerfahrenDem Heron Verfahren liegt die Idee zu Grunde dass ein Quadrat mit Flacheninhalt A displaystyle A nbsp eine Seitenlange von A displaystyle sqrt A nbsp hat Ausgangspunkt des Verfahrens ist ein beliebiges Rechteck mit Flacheninhalt A displaystyle A nbsp Schritt fur Schritt wird das Seitenverhaltnis des Rechtecks so geandert dass sich seine Form immer mehr der eines Quadrats annahert wahrend der Flacheninhalt gleich bleibt Die Seitenlangen des Rechtecks sind die Naherungswerte fur A displaystyle sqrt A nbsp Im ersten Schritt wird eine beliebige Seitenlange x 0 displaystyle x 0 nbsp fur das Rechteck gewahlt Damit dieses den gewunschten Flacheninhalt hat wird die zweite Seitenlange mit der Formel y 0 A x 0 displaystyle y 0 frac A x 0 nbsp berechnet Als Beispiel soll die Wurzel aus 9 berechnet werden Fur die eine Seitenlange wird der Wert 9 gewahlt sodass sich die andere Seitenlange zu 1 berechnet Das erste Rechteck hat deshalb die folgende Form nbsp Die Ahnlichkeit dieses Rechteckes mit einem Quadrat ist gering Das kommt auch dadurch zum Ausdruck dass die Seitenlangen 1 und 9 sehr schlechte Naherungen fur die Wurzel aus 9 sind Um eine bessere Annaherung an ein Quadrat zu erhalten muss die lange Seite gekurzt und die kurze Seite verlangert werden Als neue Lange der langen Seite wird der Mittelwert x 1 x 0 y 0 2 displaystyle x 1 frac x 0 y 0 2 nbsp der beiden bisherigen Seitenlangen genommen Die Lange der anderen Seite berechnet sich wie oben zu y 1 A x 1 displaystyle y 1 frac A x 1 nbsp Im Beispiel ergibt sich als Mittelwert die Seitenlange 5 Die dazugehorige kurze Seite hat eine Lange von 1 8 nbsp Auch hier ist die Ahnlichkeit zu einem Quadrat noch gering Allerdings ist das neue Rechteck im Vergleich zum vorhergehenden kompakter Der beschriebene Ablauf wird in jedem weiteren Schritt des Heron Verfahrens wiederholt Der Mittelwert der Seitenlangen eines Rechtecks entspricht der Lange der langen Seite des neuen Rechtecks und die Lange der kurzen Seite lasst sich daraus jeweils wie oben beschrieben berechnen Im Beispiel entstehen so in den nachsten zwei Schritten die folgenden beiden Rechtecke nbsp nbsp Das letzte Rechteck ist schon annahernd quadratisch Die Seitenlange 3 024 liegt entsprechend nah bei 3 dem exakten Wert von 9 displaystyle sqrt 9 nbsp Heron Verfahren als Spezialfall des Newton Verfahrens Bearbeiten nbsp Heron Verfahren zur Berechnung von 2 displaystyle sqrt 2 nbsp mit drei verschiedenen StartwertenDie Iterationsgleichung des Heron Verfahrens kann aus dem Newton Verfahren fur die Nullstelle der quadratischen Funktion f x x 2 a displaystyle f x x 2 a nbsp hergeleitet werden Mit f x 2 x displaystyle f x 2x nbsp folgt aus der Rekursionsformel des Newton Verfahrens x n 1 x n f x n f x n displaystyle x n 1 x n tfrac f x n f x n nbsp die Iterationsvorschrift x n 1 x n x n 2 a 2 x n x n 2 a 2 x n 1 2 x n a x n displaystyle x n 1 x n frac x n 2 a 2x n frac x n 2 a 2x n frac 1 2 cdot left x n frac a x n right nbsp Der Startwert x 0 displaystyle x 0 nbsp der Iteration kann solange er nicht gleich Null ist beliebig festgesetzt werden die Iteration konvergiert immer Zu beachten ist dass bei negativen Startwerten die Iteration gegen die negative Quadratwurzel konvergiert Eine qualifizierte Schatzung fur den Startwert erhalt man aus der Taylorreihen Entwicklung der binomischen Reihe um 1 deren zwei erste Glieder diese Gleichung liefern x 0 a 1 2 displaystyle x 0 tfrac a 1 2 nbsp Das Heron Verfahren gehort zu den Fixpunktverfahren 1 Setzt man f x 1 2 x a x textstyle varphi x frac 1 2 cdot left x frac a x right nbsp so gilt fur den Fixpunkt der die Bedingung f x x textstyle varphi x x nbsp erfullt x 2 a textstyle x 2 a nbsp mit der positiven Losung x a textstyle x sqrt a nbsp Beispiel Bearbeiten nbsp Die Folgenglieder der babylonischen Wurzelfolge mit dem Startwert a 0 1 4 displaystyle a 0 tfrac 1 4 nbsp Im folgenden einfachen Beispiel wird die Wurzel aus 9 als Annaherung mit drei Berechnungsschritten an den wahren Wert 9 3 displaystyle textstyle sqrt 9 3 nbsp gezeigt Mit a 9 displaystyle textstyle a 9 nbsp wird der Startwert x 0 9 1 2 5 displaystyle textstyle x 0 frac 9 1 2 5 nbsp fur die Iteration berechnet und in die Iterationsvorschrift eingesetzt x 1 1 2 5 9 5 1 2 34 5 34 10 3 4 displaystyle x 1 frac 1 2 cdot left 5 frac 9 5 right frac 1 2 cdot frac 34 5 frac 34 10 3 4 nbsp x 2 1 2 34 10 9 34 10 1 2 34 10 90 34 257 85 3 023 5294 displaystyle x 2 frac 1 2 cdot left frac 34 10 frac 9 frac 34 10 right frac 1 2 cdot left frac 34 10 frac 90 34 right frac 257 85 3 0235294 dots nbsp x 3 1 2 257 85 9 257 85 1 2 257 85 765 257 65537 21845 3 000 091554 displaystyle x 3 frac 1 2 cdot left frac 257 85 frac 9 frac 257 85 right frac 1 2 cdot left frac 257 85 frac 765 257 right frac 65537 21845 3 000091554 dots nbsp Konvergenz Bearbeiten Das Verfahren lasst sich folgendermassen als rekursiv definierte Folge ausdrucken x n 1 1 2 x n a x n displaystyle x n 1 frac 1 2 cdot left x n frac a x n right nbsp Es handelt sich dabei um eine rein positive Folge Man kann nun zeigen dass fur alle n 1 displaystyle n geq 1 nbsp das n displaystyle n nbsp te Folgenglied x n a displaystyle x n geq sqrt a nbsp ist Dazu zeigt man die aquivalente Ungleichung x n 2 a 0 displaystyle x n 2 a geq 0 nbsp x n 2 a 1 4 x n 1 a x n 1 2 a 1 4 x n 1 a x n 1 2 0 displaystyle x n 2 a frac 1 4 cdot left x n 1 frac a x n 1 right 2 a frac 1 4 cdot left x n 1 frac a x n 1 right 2 geq 0 nbsp Weiter zeigt man dass x n displaystyle left x n right nbsp eine monoton fallende Folge ist x n 1 x n 1 2 x n a x n x n a 2 x n x n 2 a x n 2 2 x n 0 displaystyle x n 1 x n frac 1 2 cdot left x n frac a x n right x n frac a 2x n frac x n 2 frac a x n 2 2x n leq 0 nbsp Durch die gezeigte Beschranktheit und Monotonie muss die Folge konvergieren und zwar von oben gegen die gesuchte Wurzel x 1 2 x a x x 2 a x a displaystyle x frac 1 2 cdot left x frac a x right Leftrightarrow x 2 a Leftrightarrow x sqrt a nbsp Da sich das Heron Verfahren aus dem Newtonschen Naherungsverfahren ableiten lasst und die zu berechnende Nullstelle einfach ist ist die Konvergenzordnung 2 Das Verfahren konvergiert sehr schnell wenn bereits eine gute Naherung vorliegt Die Zahl der richtigen Stellen wird mit jedem Schritt etwa verdoppelt Wenn die erste Naherung jedoch schlecht ist sind viele Schritte fur eine gute Naherung notig Wenn zum Beispiel aus einer Ganzzahl a displaystyle a nbsp mit 200 Binarstellen die Wurzel berechnet werden soll und man mit x 0 a displaystyle x 0 a nbsp als erster Naherung beginnt dann wird die Naherung mit jedem Schritt um etwa eine Binarstelle kurzer d h erst nach etwa 100 Schritten hat die Naherung die richtige Lange von 100 Stellen Danach reichen sechs bis sieben weitere Schritte log 2 100 displaystyle log 2 100 nbsp um alle 100 Stellen vor dem Komma richtig zu berechnen Es empfiehlt sich somit einen moglichst genauen Startwert x 0 displaystyle x 0 nbsp zu bestimmen Im Beispiel sollte man zuerst die Bitlange log 2 a 1 displaystyle lfloor log 2 a rfloor 1 nbsp von a displaystyle a nbsp ermitteln und einen Startwert mit der halben Lange verwenden Anmerkung 1 Fehlerabschatzung Bearbeiten Fur die Heron Folge x n n 1 displaystyle x n n geq 1 nbsp gilt a x n a x n displaystyle frac a x n leq sqrt a leq x n nbsp Einschliessung und fur den Fehler die folgende Abschatzung x n a 1 2 x n 1 x n 1 a 2 1 2 a x n 1 a 2 displaystyle x n sqrt a frac 1 2x n 1 left x n 1 sqrt a right 2 leq frac 1 2 sqrt a left x n 1 sqrt a right 2 nbsp quadratische Konvergenz Diese Fehlerabschatzung hat den Nachteil dass a displaystyle sqrt a nbsp nicht bekannt ist sondern berechnet werden soll Unter Verwendung der obigen Einschliessung erhalt man folgende praktikable Abschatzung x n a 1 2 x n 1 x n 1 a 2 1 2 x n 1 x n 1 a x n 2 1 2 x n 1 x n 2 x n 1 x n a 2 displaystyle x n sqrt a frac 1 2x n 1 left x n 1 sqrt a right 2 leq frac 1 2x n 1 left x n 1 frac a x n right 2 frac 1 2x n 1 cdot x n 2 left x n 1 cdot x n a right 2 nbsp Angewandt auf obiges Beispiel erhalt man x 3 3 1 2 x 2 x 2 3 2 0 000 091554 1 2 x 2 x 3 2 x 2 x 3 9 2 0 000 0922 displaystyle x 3 3 frac 1 2x 2 left x 2 3 right 2 0 000091554 dots leq frac 1 2x 2 cdot x 3 2 left x 2 cdot x 3 9 right 2 0 0000922 dots nbsp Fur den relativen Fehler e n x n a a displaystyle varepsilon n frac x n sqrt a sqrt a nbsp gilt die Rekursion e n 1 e n 2 2 1 e n displaystyle varepsilon n 1 frac varepsilon n 2 2 1 varepsilon n nbsp Die Folge der e n displaystyle varepsilon n nbsp ist also bei gegebenem relativen Fehler e 0 displaystyle varepsilon 0 nbsp der Startnaherung unabhangig von a displaystyle a nbsp Implementierung in Software BearbeitenDas Verfahren eignet sich besonders gut zur Implementierung in Software da nur Grundrechenarten benotigt werden s o Es wird heute angesichts der breiten Verfugbarkeit numerischer Prozessorhardware aber nur noch selten benotigt Wenn dazu noch eine Gleitkommadarstellung mit einem Zweier Exponenten benutzt wird wird der Ansatz relativ einfach als Beispiel wird die Wurzel aus 5 betrachtet und der relative Fehler zum Endwert x i x x displaystyle frac x i x x nbsp verfolgt Zunachst wird von diesem Zweier Exponenten eine gerade Anzahl abgespaltet so dass als Exponent entweder eine 0 oder 1 ubrig bleibt die Zahl also auf das Intervall 1 2 2 displaystyle tfrac 1 2 2 nbsp normalisiert wird In diesem Intervall ist die Wurzelfunktion eine nur schwach gekrummte Kurve lasst sich also numerisch gut behandeln Beispiel 5 4 1 25 2 1 25 2 1 118 034 2 236 068 displaystyle sqrt 5 sqrt 4 cdot 1 25 2 cdot sqrt 1 25 approx 2 cdot 1 118034 2 236068 nbsp es wird also vorerst nur noch a 1 25 displaystyle a 1 25 nbsp mit dem Ziel x 1 118 displaystyle x 1 118 nbsp behandelt Als Startwert fur die eigentliche Iteration approximiert man diese Kurve durch eine noch einfachere die sich direkt ohne Iteration berechnen lasst Mit dieser Anfangsberechnung wird der Startwert ermittelt mit dem die folgende Iteration begonnen wird Man kann diese Kurve mehr oder weniger aufwendig ansetzen mit den steigend komplizierteren Ansatzen unten lasst sich gegebenenfalls ein Iterationsschritt einsparen eine einfache Konstante beispielsweise 1 Beispiel x 0 1 displaystyle x 0 1 nbsp relativer Fehler 1 1 10 1 displaystyle 1 1 cdot 10 1 nbsp eine Gerade mit Steigung 1 2 displaystyle tfrac 1 2 nbsp und einer additiven Konstante von 1 2 displaystyle tfrac 1 2 nbsp als Vereinfachung des nachfolgenden FallsBeispiel x 0 1 2 1 25 2 1 125 displaystyle x 0 tfrac 1 2 tfrac 1 25 2 1 125 nbsp relativer Fehler 6 2 10 3 displaystyle 6 2 cdot 10 3 nbsp eine Gerade mit Steigung 1 2 displaystyle tfrac 1 2 nbsp und einer additiven optimierten Konstante von 2 2 4 2 2 2 0 464 8415 displaystyle left 2 cdot sqrt 4 2 sqrt 2 right 2 2 approx 0 4648415 nbsp Beispiel x 0 0 929 683 2 1 25 2 1 089 841 displaystyle x 0 tfrac 0 929683 2 tfrac 1 25 2 approx 1 089841 nbsp relativer Fehler 2 5 10 2 displaystyle 2 5 cdot 10 2 nbsp eine Gerade mit optimierter Steigung und einer additiven Konstante hier nicht naher betrachtet Ausgehend von dem so ermittelten Startwert x 0 displaystyle x 0 nbsp fuhrt man eine feste Anzahl von Iterationsschritten durch Die notige Anzahl um die gewunschte Genauigkeit zu erreichen lasst sich dank der obigen Fehlerabschatzung als Worst Case innerhalb des Startintervalls direkt ausrechnen Bei 32 Bits Mantisse und dem mittleren Startansatz braucht man beispielsweise nur drei Schritte Diese fest gewahlte Anzahl erspart wesentlich aufwendigere Abfragen auf Erreichung der Genauigkeit Der Ersatz der genannten Konstanten durch die Zahl 1 0 andert daran nichts Auch der noch kompliziertere Ansatz brachte zumindest bei dieser Genauigkeit keine Einsparung eines weiteren Iterationsschritts Bei hoheren Genauigkeitsanforderungen kann das anders aussehen Beispiel mit drei Schritten nach Ansatz 1 Konstante 1 mit den anderen Ansatzen konvergiert es noch einen Schritt schneller x 1 x 0 a x 0 2 x 1 x 0 1 25 x 0 2 1 1 25 1 2 1 125 displaystyle x 1 tfrac x 0 tfrac a x 0 2 x 1 tfrac x 0 tfrac 1 25 x 0 2 tfrac 1 tfrac 1 25 1 2 1 125 nbsp relativer Fehler 6 2 10 3 displaystyle 6 2 cdot 10 3 nbsp x 2 x 1 a x 1 2 1 125 1 25 1 125 2 1 118 056 displaystyle x 2 tfrac x 1 tfrac a x 1 2 tfrac 1 125 tfrac 1 25 1 125 2 approx 1 118056 nbsp relativer Fehler 2 0 10 5 displaystyle 2 0 cdot 10 5 nbsp x 3 x 2 a x 2 2 1 118 056 1 25 1 118 056 2 1 118 034 displaystyle x 3 tfrac x 2 tfrac a x 2 2 tfrac 1 118056 tfrac 1 25 1 118056 2 approx 1 118034 nbsp relativer Fehler kleiner als 10 6 displaystyle 10 6 nbsp Man sieht die Wirkung der quadratischen Konvergenz dass sich der relative Fehler von Schritt zu Schritt jeweils quadriert oder die Anzahl gultiger Stellen bzw der negative Fehlerexponent etwa verdoppelt Zum Schluss wird der Exponent restauriert indem man die Halfte des im ersten Schritt abgespalteten Werts wieder hinzufugt Beispiel 2 x 3 x 2 a x 2 1 118 056 1 25 1 118 056 2 236 068 displaystyle 2 cdot x 3 x 2 tfrac a x 2 1 118056 tfrac 1 25 1 118056 approx 2 236068 nbsp Verallgemeinerung des Verfahrens BearbeitenDieses Verfahren lasst sich verallgemeinern so dass a k displaystyle sqrt k a nbsp fur a gt 0 displaystyle a gt 0 nbsp berechnet wird Je grosser k displaystyle k nbsp ist desto mehr Schritte werden benotigt um die Wurzel genau zu berechnen Dabei wird das Newton Verfahren zur Bestimmung der positiven Nullstelle a k displaystyle sqrt k a nbsp der Funktion f x x k a displaystyle f x x k a nbsp angewandt Mit f x k x k 1 displaystyle f x kx k 1 nbsp folgt aus der Rekursionsformel des Newton Verfahrens x n 1 x n f x n f x n displaystyle x n 1 x n frac f x n f x n nbsp die Iterationsvorschrift x n 1 x n x n k a k x n k 1 k 1 x n k a k x n k 1 1 k k 1 x n a x n k 1 displaystyle x n 1 x n frac x n k a kx n k 1 frac k 1 x n k a kx n k 1 frac 1 k left k 1 x n frac a x n k 1 right nbsp Beispielsweise lautet die rekursive Formel zur Berechnung der Kubikwurzel x n 1 x n x n 3 a 3 x n 2 2 x n 3 a 3 x n 2 1 3 2 x n a x n 2 displaystyle x n 1 x n frac x n 3 a 3x n 2 frac 2x n 3 a 3x n 2 frac 1 3 left 2x n frac a x n 2 right nbsp Hier muss die Folge mit einem geeigneten Startwert x 0 displaystyle x 0 nbsp fur den gesuchten Wert von a k displaystyle sqrt k a nbsp gestartet werden Fur ganzzahliges positives k displaystyle k nbsp gelten die gleichen Konvergenzaussagen wie oben fur k 2 displaystyle k 2 nbsp Bestimmung des Kehrwerts Bearbeiten Fur k 1 displaystyle k 1 nbsp erhalt man ein Verfahren mit dem ohne Verwendung der Division der Kehrwert a 1 1 a displaystyle a 1 1 a nbsp naherungsweise errechnet werden kann x n 1 1 1 x n 1 a 1 x n 1 1 2 x n a x n 2 2 a x n x n displaystyle x n 1 frac 1 1 x n 1 a 1 x n 1 1 2x n ax n 2 2 ax n cdot x n nbsp Dieses Verfahren konvergiert fur alle x 0 0 2 a displaystyle x 0 in left 0 2 a right nbsp quadratisch gegen 1 a displaystyle 1 a nbsp Die Iteration ermoglichte fur erste Computer ohne eingebaute Division die Zuruckfuhrung dieser Operation auf Multiplikation und Subtraktion Die Division von zwei Zahlen wurde so ausgefuhrt dass der Kehrwert des Nenners bestimmt wurde und mit dem Zahler multipliziert wurde Beispiel Bearbeiten Es soll 1 3 displaystyle 1 3 nbsp naherungsweise berechnet werden mit dem Startwert x 0 1 2 lt 2 3 displaystyle x 0 tfrac 1 2 lt tfrac 2 3 nbsp x 1 2 3 1 2 1 2 1 4 0 25 displaystyle x 1 left 2 3 cdot frac 1 2 right cdot frac 1 2 frac 1 4 0 25 nbsp x 2 2 3 1 4 1 4 5 16 0 312 5 displaystyle x 2 left 2 3 cdot frac 1 4 right cdot frac 1 4 frac 5 16 0 3125 nbsp x 3 2 3 5 16 5 16 85 256 0 332 03125 displaystyle x 3 left 2 3 cdot frac 5 16 right cdot frac 5 16 frac 85 256 0 33203125 nbsp Fur den Startwert x 0 2 3 displaystyle x 0 frac 2 3 nbsp erhalt man x 1 2 3 2 3 2 3 0 displaystyle x 1 left 2 3 cdot frac 2 3 right cdot frac 2 3 0 nbsp x 2 2 3 0 0 0 displaystyle x 2 left 2 3 cdot 0 right cdot 0 0 nbsp somit keine Konvergenz gegen den gesuchten Wert von 1 3 displaystyle tfrac 1 3 nbsp Historisches BearbeitenDas Verfahren war in Mesopotamien bereits zur Zeit von Hammurapi I ca 1750 v Chr eines Konigs von Babylon bekannt 2 Um 100 n Chr wurde es von Heron von Alexandria im ersten Buch seines Werkes Metrica beschrieben 3 Literatur BearbeitenBernd Ziegenbalg Algorithmen Von Hammurapi bis Godel Harri Deutsch Verlag 2007 ISBN 978 3 8171 1814 4 S 54 59 David Fowler Eleanor Robson Square Root Approximations in Old Babylonian Mathematics PDF 215 kB Historica Mathematica 25 1998 S 366 378 Hans R Schwarz Norbert Kockler Numerische Mathematik 6 Auflage Teubner Stuttgart 2006 ISBN 3 519 42960 8 S 189 192 Weblinks Bearbeiten nbsp Commons Heron Verfahren Sammlung von Bildern Videos und Audiodateien Das Heron Verfahren zur Wurzelberechnung auf arndt bruenner de Erlauterung und Beispielrechner Interaktive Illustration in GeoGebra Papp Interaktive Illustration in GeoGebra Leo Anmerkungen Bearbeiten Startwert Sofern der Ausgangswert bereits als Binarzahl im Stellenwertsystem vorliegt kann einfach gezahlt werden an welcher Stelle i displaystyle i nbsp seine hochstwertige 1 steht Startwert wird dann 1 2 i 2 displaystyle 1 cdot 2 i 2 nbsp Sofern der Ausgangswert in Binar Exponentialdarstellung vorliegt kann als Startwert einfach der Exponent halbiert werden um 1 Bit nach rechts schieben Siehe auch Abschnitt Implementierung in SoftwareEinzelnachweise Bearbeiten Passende Umformungen Nullstellen und Fixpunkte Nicht mehr online verfugbar In Montanuniversitat Leoben 23 Februar 2005 archiviert vom Original am 22 August 2019 abgerufen am 27 August 2019 Bernd Ziegenbalg Algorithmen Von Hammurapi bis Godel Harri Deutsch Verlag 2007 ISBN 978 3 8171 1814 4 S 54 Auszug Google John J O Connor Edmund F Robertson Heron Verfahren In MacTutor History of Mathematics archive Abgerufen von https de wikipedia org w index php title Heron Verfahren amp oldid 238500551