Algorithmus um die Wurzel zu berechnen?
Wir haben kürzlich den folgenden simplen Algorithmus angeschaut, der dazu dient die Wurzel einer Zahl zu berechnen:
Dabei iteriert man immer wieder über r = 0.5 * (r + x / r), wobei r die gesuchte Wurzel ist von der Zahl x bis man sich mit einer bestimmten Toleranz sicher ist, die Wurzel gefunden zu haben. Um einen Startwert zu haben, setzt man anfangs r=x.
Ich konnte den Algorithmus zwar implementieren, nun frage ich mich aber, weshalb der Ausdruck r = 0.5 * (r + x / r) mit der Zeit gegen die Wurzel konvergiert? Kann man das formal herleiten?
Es scheint zumindest nicht ganz unintuitiv zu sein: Ich nehme r=x als Beginn und rechne dann die Hälfte davon (0.5 * r), addiere aber gleichzeitig wieder 1 * 0.5 (bei der ersten Iteration). Bei der zweiten habe ich dann ja nur noch etwa die Hälfte von der usprünglichen Zahl und halbiere sie wieder, rechne aber wieder 0.5 * (x/r) dazu, wobei dann ja sicherlich x/r > 1 ist. Und so weiter ....
Wäre froh, wenn mir da jemand auf die Sprünge helfen könnte.
1 Antwort
Haben zwei positive Zahlen a und b das Produkt a*b = p , so liegt der Wert der Quadratwurzel √(p) zwischen a und b .
Beispiel: √(40) = ? Wegen 40 = 5*8 muss der gesuchte Wurzelwert zwischen 5 und 8 liegen, denn offensichtlich ist 5*5 = 25 < 40 und 8*8 = 64 > 40.
Nehmen wir also als nächsten Probierwert eine Zahl zwischen 5 und 8, also vielleicht mal etwa den Mittelwert , also (5+8)/2 = 6.5 .
Bilden wir nun den Quotienten 40/6.5 = 6.1538... . Wegen 6.5^2=42.25>40 ist die 6.5 etwas zu groß für den gesuchten Wurzelwert und folglich 40/6.5 ≈ 6.1538... = etwas zu klein.
Die beiden neuen Probierwerte 6.5 und 6.1538... liegen deutlich näher beieinander als die ersten beiden (5 und 8). Nehmen wir also als nächsten Testwert das Mittel aus 6.5 und 6.1538... , also 6.3269... . Beim Fortfahren in derselben Weise kommen sich die beiden Probierwerte (also t und 80/t) immer näher. Es sieht also danach aus, dass die so berechneten Zahlenwerte gegen einen gewissen Grenzwert w streben. Unter dieser Annahme der Konvergenz ist es ganz leicht zu zeigen, dass folgendes gelten muss:
FALLS die so berechneten Zahlenwerte gegen einen (positiven) Grenzwert w streben, so muss dieser Grenzwert der gesuchte Quadratwurzelwert sein, also w^2 = 40 und damit w = √(40) .
(Die exakte Durchführung des Konvergenzbeweises, samt Angabe der Voraussetzungen, ist in der Regel Thema eines Analysiskurses an der Uni.)