Rekursive Berechnung von Quadratwurzeln

Die Wurzel einer positiven reellen Zahl a, die > 1 ist, ist ebenfalls > 1. Ista < 1, ist die Wurzel auch < 1. Aus dieser Feststellung kann abgeleitet werden, dass

\(1 + r = \sqrt a \) Gl. 95

worin r ein noch nicht bekannter Rest ist. r ist positiv, wenn a > 1 sonst negativ.

Beidseitiges quadrieren von Gl. 95 führt auf

\( {\left( {1 + r} \right)^2} = a \) Gl. 96

Auflösen des Binoms

\( 1 + 2r + {r^2} = a \) Gl. 97

und Umstellen

\( r \cdot \left( {2 + r} \right) = a - 1 \) Gl. 98

Schließlich folgt die Rekursionsvorschrift für die Berechnung des Rests r:

\( r = \frac{ {a - 1} }{ {2 + r} } \) Gl. 99

Das r der linken Seite von Gl. 99 kann beliebig oft in das r der rechten Seite eingesetzt werden. Dies entspricht dem Selbstaufruf, der für Rekursionen typisch ist.

Für numerische Anwendungen wird Gl. 5-8 besser so geschrieben:

\( {r_{i + 1} } = \frac{ {a - 1} }{ {2 + {r_i} } } \) Gl. 100

Worin i den aktuellen Rekursionsschritt bezeichnet.

Beispiel

Gesucht ist die Quadratwurzel aus 2. Die Anwendung von Gl. 100 führt auf:

\( {r_{i + 1} } = \frac{ {2 - 1} }{ {2 + {r_i} } } = \frac{1}{ {2 + {r_i} } } \).

Mit der Startannahme, dass der Rest r0 gleich Null ist, führt der erste Schritt auf r1 = 0,5 und so weiter:

\( {r_{i + 1} } = \frac{1}{ {2 + \frac{1}{ {2 + \frac{1}{ {2 +..... + \frac{1}{ {2 + {r_0} } } } } } } } } \)

Dies ist ein Kettenbruch, der bereits nach vier Schritten eine Wert für den Rest von r4 = 0,41428... Der gesuchte Wurzelwert ergibt sich dann zu

1 + r = 1,41428...

Der korrekte Wert lautet 1,41421...