Munterbunt

Berechnung von Quadratwurzeln unter Vermeidung von Divisionen

Übersicht > Gleichungen > Numerische Verfahren > Berechnung von Quadratwurzeln unter Vermeidung von Divisionen

Aufgabe

Die Quadratwurzel $V~ a$ aus einer positiven reellen Zahl $a$ lässt sich mittels der elementaren Grundoperationen Addition / Subtraktion und Multiplikation ohne Verwendung von Divisionen berechnen. Das Verfahren beruht auf der Bestimmung der Nullstelle $1/ V~ a-$ der Funktion

f (x) = 1- -a x2

mittels Newtoniteration. Anschliessende Multiplikation von $1/ V~ a-$ mit $a$ liefert den gesuchten Wert $V~ a-$ .

Wie lautet die Iterationsvorschrift $N (x)$ der Newtoniteration für die Funktion $f$ ? Gesucht ist ein Ausdruck für $N(x)$ , der keine Divisionen enthält.
(Hinweis: Multiplikation mit 0.5 bzw. Division durch 2 ist nicht als eigentliche Division zu betrachten. Im Binärsystem entspricht dieser Operation nur eine Stellenverschiebung.)
Wie sieht ein auf obigem Verfahren beruhendes Computerprogramm aus, das $V~ -- a$ mit Genauigkeit $-6 10$ berechnet. Verlangt ist der Programmcode und ein Test für $V~ - 9$ .
Welche Werte $x 0$ liefern als Startwerte $x 0$ bei der Newtoniteration die gewünschte Nullstelle?

Lösung

$( ) xn+1 = 0.5xn 3 - ax2n$
-
$V~ 3 0 < x0 < a$