Oettinger-physics.de
URI QR-encoded:http://vorlesung.oettinger-physics.de/script/NewtonWurzel.html

Wurzeln approximieren

Näherung der Quadratwurzel

Die Quadratwurzel einer Zahl $a$ lässt sich zunächst nicht allgemein über ein einfaches Verfahren berechnen. Obwohl es kein besonderes Problem ist, eine Zahl mit sich selbst zu multiplizieren, gelingt die Umkehrung - die echte Berechnung von Wurzeln - nur in einigen speziellen Fällen, beispielsweise über eine Zerlegung in Primfaktoren (Anhang A).

Man behilft sich zunächst damit, dass man sich mit den Zahlen, die man quadriert stets auch die quadrierte Zahl selbst merkt - damit kann man mit der Zeit einige einfache Quadratwurzeln als bekannt annehmen. Bei größeren oder komplizierteren Zahlen hilft die Idee aber meist nicht weiter (nur wenn man 327 einmal quadriert hat, kennt man die Wurzel aus 106929!1). Zum Glück lassen sich Quadratwurzeln (und natürlich auch andere Wurzeln) aber ganz einfach näherungsweise bestimmen. Wendet man die Differentialrechnung geschickt an, geht das in wenigen Rechenschritten mit beinahe beliebiger Genauigkeit.

Näherung über das Newton-Verfahren

Das iterative Newton-Verfahren nähert Nullstellen einer differenzierbaren Funktion $f(x)$ mithilfe der ersten Ableitung der Funktion durch die Nullstellen von Tangenten an die Kurve der Funktion an. Im ersten Schritt wird dazu ein Startwert $x_0$ vorgegeben und im Punkt $(x_0 / f(x_0)) $  eine Tangente mit der Steigung $f'(x_0)$ (Ableitung der Funktion $f$ an der Stelle $x_0$) an die Kurve der Funktion gelegt. Die Nullstelle der Tangente $$ t(x) = f(x_0) + f'(x_0) (x - x_0) $$ an $f(x)$ ist einfach berechenbar, wir bezeichnen sie als $x_1$ und verstehen sie als eine Näherung für die Nullstelle der Funktion: $$ t(x_1) = f(x_0) + f'(x_0) (x_1 - x_0) = 0 \;\;\; \Rightarrow \;\;\; x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} $$ Nun folgt die Iteration: der gefundene Wert der Nullstelle von $t(x)$ kann als neuer Startwert benutzt werden, mit dem das Verfahren wiederholt wird. Im nächsten Schritt wird eine Tangente an den im vorherigen Schritt bestimmten Punkt $(x_1 / f(x_1)) $  an die Kurve gelegt, die eine neue Nullstelle $x_2$ liefert. Durch weitere Wiederholung des Verfahrens nach dem Schema $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$ nähert sich der gefundene Wert oft sehr schnell an die tatsächliche Nullstelle der Funktion $f(x)$ an.

Das Newton-Verfahren dient also der näherungsweisen Bestimmung von Nullstellen einer Funktion. Wie nähert man aber damit den Wert einer Wurzel? Man schreibt das Problem einfach in die Suche nach einer Nullstelle um. Die Funktion $$ f(x) = x^2 - a$$ mit der ersten Ableitung $$ f'(x) = 2 x $$ besitzt genau eine positive Nullstelle bei $x = +\sqrt{a}$ , was sich einfach nachrechnen lässt: $ f(\sqrt{a}) = (\sqrt{a})^2 - a = a -a = 0$    . Wenn es also gelingt, die Nullstelle der Funktion $f$ näherungsweise zu berechnen, hat man damit auch eine Näherung für die Wurzel der Zahl $a$ gefunden. Für unsere Funktion kann die Iteration des Newton-Verfahrens als $$ x_{n+1} = x_n - \frac{x_n^2 - a}{2x_n} $$ geschrieben werden, die jeweiligen Schritte sind relativ einfach berechenbar. Dieses Verfahren zur näherungsweisen Bestimmung von Wurzeln wurde bereits 1750 v. Chr. in Mesopotamien benutzt, es wird auch als Heron-Verfahren bezeichnet.

Simulation: das Newton-Verfahren

Hier kann die Näherung einer Quadratwurzel über das Newton-Verfahren ausprobiert werden: gesucht ist die Wurzel aus . Der Startwert ist bei der verwendeten Funktion unkritisch, der Einfachheit halber benutzt die Funktion den Wert $a$ = . Die Näherung bewegt sich in wenigen Schritten auf die Nullstelle zu, dabei sind bei großen Werten mehr Schritte notwendig (der Startwert liegt ja weiter von der Nullstelle entfernt). In der Grafik sind die Tangenten der einzelnen Schritte in blau eingetragen.


Näherung über ein Taylorpolynom

Eine weitere Möglichkeit den Wert einer Quadratwurzel näherungsweise zu bestimmen führt über ein Taylor- oder MacLaurin-Polynom. Viele Funktionen lassen sich mit Hilfe der Taylor oder MacLaurin-Entwicklung in eine Reihe (eine unendliche Summe) entwickeln (hier ist die Erklärung dazu), für die etwas einfachere MacLaurin-Reihe hat sie die Form $$ f(x) = \sum_{n=0}^{\infty}a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots $$ mit den Entwicklungskoeffizienten $$ a_n = \frac{f^{(n)}(0)}{n!} \;\;\; \text{ mit } f^{(n)}(x) = \frac{d^n f(x)}{dx^n} \;\;\; \text{ und } n \in \mathbb{N} $$ Bricht man die Reihe nach einer bestimmten Zahl von Summanden ab, erhält man eine Näherung für die Funktion $f(x)\;\; $ - man spricht dann von einem MacLaurin-Polynom. Beim $n $-ten MacLaurin-Polynom läuft der Index $k $ von $0 $ bis $n $, es besteht also aus $n+1\;\;$ Summanden. Wir beschränken uns hier auf das zweite MacLaurin-Polynom mit $n = 2 \;$ als Näherung: $$ f(x) \approx T_2(x) = \sum_{k=0}^{n}a_k x^k = a_0 + a_1 x + a_2 x^2 $$ mit den Koeffizienten aus nullter, erster und zweiter Ableitung $$ a_0 = \frac{f(0)}{0!}, \;\;\; a_1 = \frac{f'(0)}{1!}, \;\;\; a_2 = \frac{f''(0)}{2!} $$ Versucht man, den positiven Ast einer Quadratwurzel in eine MacLaurin-Reihe zu entwickeln, stellt sich allerdings das Problem, dass die Ableitungen der Funktion $f(x) = \sqrt(x) \;\;\;$ an der Stelle $x_0 = 0\;\; $ verschwinden (alle, auch die Funktion selbst als nullte Ableitung) - damit lässt sich keine brauchbare Reihendarstellung erzeugen. Man kann sich aber durch eine einfache Tranformation behelfen: statt der einfachen Wurzelfunktion wird die Funktion $f(x) = \sqrt{a^2+x}\;\;\;$ entwickelt 3. Die Entwicklung entspricht einer Taylor-Entwicklung um die Stelle $x_0 = a^2\;\;\;$ und liefert nahe $a^2 $ eine gute Näherung für die Quadratwurzel.

Die Entwicklung besteht aus der Bestimmung der Koeffizienten, in unserem Fall ist das nicht kompliziert ($0!\; $ ist die Null-Fakultät, sie ist definiert als $1 $). $$ a_0 = \frac{f(0)}{0!} = \sqrt{a^2 + 0} = a $$ $$ a_1 = \frac{f'(0)}{1!} = \frac{1}{2} \frac{1}{\sqrt{a^2 + 0}} = \frac{1}{2a} $$ $$ a_2 = \frac{f''(0)}{2!} = - \frac{1}{2}\frac{1}{2} \frac{1}{\sqrt{a^2+0}^3} = - \frac{1}{4a^3} $$ Das Taylorpolynom lautet also $$ \begin{align} f(x) = \sqrt{a^2+x}\;\; \approx \;\; T_2(x) &= \sum_{k=0}^{n}a_k x^k = a_0 + a_1 x + a_2 x^2 \\ &= a + \frac{1}{2a}\cdot x - \frac{1}{4a^3}\cdot x^2 \end{align} $$ Um jetzt beispielsweise den Wert der Quadratwurzel $\sqrt{4,2}\;\; $ zu nähern, kann einfach ausgenutzt werden, dass das Quadrat $2^2 = 4 = a^2\;\;$ bekannt und die Zahl $4,2 $ als $4 + 0,2 = 2^2 + 0,2\;\;\;\; $ geschrieben werden kann. Damit ist natürlich auch $$ \sqrt{4,2} = f(0,2) \text{ mit } f(x) = \sqrt{2^2 + x} $$ Also muss fü die gesuchte Wurzel gelten, dass $$ \sqrt{4,2} = \sqrt{2^2 + 0,2} \; \approx \; T_2(0,2) = 2 + \frac{1}{2\cdot 2}\cdot 0,2 - \frac{1}{4\cdot 2^3}\cdot 0,2^2 = 2 + \frac{1}{20} - \frac{1}{800} = 2,04875 $$ Zum Vergleich das Ergebnis des Rechners: $ \sqrt{4,2} = 2,04939\;\;\;\; $ - nicht schlecht für diese einfache Näherung.

Um die Näherung zu verbessern, können mehr Summanden des Taylorpolynoms berücksichtigt werden. Mit der Zahl der Summanden verbessert sich die Näherung weiter, bis sie schließlich im Grenzübergang $n \to \infty\;\;\; $ in den exakten Ausdruck der Funktion übergeht. Damit ergibt sich die Möglichkeit, die Quadratwurzel einer Zahl eben doch exakt zu berechnen - weil sie aber allgemein nur als eine Summe mit einer unendlichen Anzahl von Summanden geschrieben werden kann, ist sie eher symbolisch.


Anhang A: Primzahlzerlegung

Jede ganze Zahl kann in ein Produkt von Primzahlen (die Primfaktoren der Zahl) zerlegt werden. In manchen Fällen kann dadurch die Quadratwurzel auch großer Zahlen recht einfach bestimmt werden. Hier ist ein Beispiel dazu:

Gesucht sei die Quadratwurzel der Zahl $44100$, sie kann zerlegt werden in das Produkt $$ 44100 = 2\cdot 22050 = 2\cdot 2\cdot 11025 $$ $$ = 2\cdot 2 \cdot 5 \cdot 2205 = 2\cdot 2 \cdot 5 \cdot 5 \cdot 441 $$ $$ = 2\cdot 2 \cdot 5 \cdot 5 \cdot 3\cdot 147 = 2\cdot 2 \cdot 5 \cdot 5 \cdot 3\cdot 3\cdot 49 $$ $$ = 2\cdot 2 \cdot 5 \cdot 5 \cdot 3\cdot 3\cdot 7\cdot 7 = 2^2 \cdot 5^2 \cdot 3^2 \cdot 7^2 $$ Weil die Primfaktoren in diesem speziellen Fall immer paarweise auftreten, ist das Ziehen der Wurzel hier einfach: $$ \sqrt{44100} = \sqrt{ 2^2 \cdot 5^2 \cdot 3^2 \cdot 7^2 } = 2\cdot 5\cdot 3 \cdot 7 = 30\cdot 7 = 210 $$


  • 1106929 kann in Primfaktoren zerlegt werden: es gilt 106929 = 3·3· 109· 109.
  • 2Genauer: dargestellt ist die Differenz zwischen der Näherung und der Standard-Javascript-Funktion Math.sqrt(), die mit 64-bit Gleitkommaoperationen etwa 16 Nachkommastellen Genauigkeit erreicht.
  • 3Die Quadratwurzel ist keine Funktion (sie liefert für jeden Variablenwert zwei Funktionswerte!), sie wird hier aber als Funktion behandelt - man betrachtet stets nur den positiven Ast. Die Rechnung liefert damit auch nur eine Lösung der Quadratwurzel, aus der man durch Vorzeichenumkehr sehr einfach die zweite gewinnt.