Das Heron-Verfahren zur Wurzelberechnung
Zu den bestechendsten Anwendungen der Grenzwerttheorie für Folgen zählt ein effektives rekursives Verfahren zur Berechnung von Quadratwurzeln. Sei hierzu a eine positive reelle Zahl. Wir möchten eine Folge (xn)n ∈ ℕ konstruieren, die möglichst schnell gegen w = sqrt(a) konvergiert. Hierzu betrachten wir eine zunächst beliebige Approximation x > 0 an w. Überschätzt die Approximation x den Wert w (d. h. gilt w < x), so gilt
a = w2 = w w < w x,
sodass a/x < w. Damit unterschätzt a/x den Wert w. Analog folgt aus x < w, dass a/x > w. Für w ≠ x liegt also w zwischen a und x/a. Diese Überlegung motiviert, das arithmetische Mittel (x + a/x)/2 als nächste Approximation zu verwenden.
Definition (Heron-Verfahren)
Sei a > 0. Wir setzen x0 = a und definieren rekursiv
xn + 1 = xn + a/xn2 für alle n ∈ ℕ.
Die Folge (xn)n ∈ ℕ heißt die Heron-Folge für a (zum Startwert x0 = a).
Die wichtigsten Eigenschaften der Folge sind:
Satz (Eigenschaften der Heron-Folge)
Sei a > 0, und sei (xn)n ∈ ℕ die Heron-Folge für a. Dann gilt:
(a) | Ist a = 1, so ist xn = 1 für alle n ∈ ℕ. |
(b) | Ist a > 1, so ist (xn)n ∈ ℕ streng monoton fallend und es gilt xn2 > a für alle n ∈ ℕ. |
(c) | Ist a < 1, so ist x1 > x0, (xn)n ≥ 1 streng monoton fallend und es gilt xn2 > a für alle n ≥ 1. |
(d) | Sei x = infn ≥ 1 xn = limn xn. Dann gilt x = sqrt(a). |
Beweis
Der Nachweis von (a) − (c) kann dem Leser zur Übung überlassen bleiben. Nach diesen Eigenschaften existiert x = infn ≥ 1 xn = limn xn. Aus xn2 ≥ a folgt xn ≥ sqrt(a) für alle n ≥ 1, sodass x ≥ sqrt(a) > 0. Nach dem Limesregeln gilt
x = limn xn = limn xn + 1 = limnxn + a/xn2 = x + a/x2,
sodass 2x = x + a/x. Damit ist x = a/x und somit x2 = a. Wegen x > 0 ist also x = sqrt(a).
Dass wir die rekursive Definition der Folge zur Identifikation ihres Grenzwerts verwenden können gehört zu den schönsten Phänomenen der Analysis. Der Nachweise der Monotonie der Folge (ab dem Index 1) ist schwieriger als die Berechnung des Infimums. Durch den motivierten Ansatz der Verbesserung der Approximation bekommen wir den Limes geschenkt. Weitere Beispiele für diesen „rekursiven Trick“ liefern die Kettenbrüche im Ausblick.
Das Heron-Verfahren liefert einen weiteren Beweis der Existenz von Wurzeln: Die Heron-Folge für a können wir definieren, ohne zu wissen, dass sqrt(a) in ℝ existiert. Für den Beweis brauchen wir nur, dass xn2 ≥ a für alle n > 1 gilt. Hieraus folgt x2 = (limn xn)2 = limn xn2 ≥ a, sodass x > 0. Damit ergibt sich x2 = a wie im Beweis oben. Der Beweis ist nicht wirklich neu, da wir die Existenz von Wurzeln sehr leicht mit den Limesregeln beweisen konnten und diese Regeln beim Beweis von „limn xn = sqrt(a)“ für die Heron-Folge eine Schlüsselrolle spielen.
Die rekursive Konstruktion ist sehr einfach, sodass die Heron-Folge leicht berechnet werden kann. Zudem liefert sie sehr gute rationale Approximationen an die Quadratwurzel einer Zahl a. Genaue Ergebnisse über die Konvergenzgeschwindigkeit werden wir im vierten Abschnitt bei der Diskussion des Newton-Verfahrens und der Taylor-Entwicklung erhalten. Das folgende Beispiel illustriert an dieser Stelle die Approximationsgüte.
Beispiel: Rationale Approximation der Quadratwurzel aus 2
Für a = x0 = 2 erhalten wir
x1 = 32 = 1,5, x2 = 1712 = 1,416
x3 = 577408 = 1, 41421 56862…
x4 = 665857470832 = 1, 41421 35623 74689…
x5 = 886731088897627013566048 = 1, 41421 35623 73095 04880 16896
Auf 40 Nachkommastellen genau gilt
= 1, 41421 35623 73095 04880 16887 24209 69807 85696 …
Damit stimmen stimmen bereits die ersten 23 Nachkommastellen von x5 mit denen von sqrt(2) überein.
Unsere Approximation an sqrt(2) im Beweis der Existenz von Wurzeln in Kapitel 1.4 liefert für δ = 1023 den Bruch
q = n δ/(s + 1) = 22627416997969520780827/1621.
Zudem ist hier der Wert n nicht so einfach zu berechnen. Das Heron-Verfahren ist besser.