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.