Die Wurzel ziehen nach Heron

Die Wurzel w einer reellen Zahl a=w^{2} soll ermittelt werden. Ist w_n eine Näherung der Wurzel, so gibt es einen kleinen Rest w= w_n+r und es würde genügen diesen Rest r zu ermitteln. Die Mutmaßung, dass bei kleinem r das Quadrat r^2 noch viel viel kleiner ist, liefert wegen

    \[a=(w_n+r)^2=w_n^2+2w_nr+r^2\approx w_n^2+2w_nr\]

eine Näherung für r\approx(a/w_n- w_n)/2 und damit eine hoffentlich bessere Näherung

    \[w_{n+1}=w_n + r = \dfrac{a/w_n + w_n}{2}\]

für die Wurzel. Man kann tatsächlich beweisen, dass

    \[\lim_{n\rightarrow \infty}w_n=w\]

Es sei angemerkt, dass dieses Verfahren viel schneller gegen die Wurzel w konvergiert als das Intervallhalbierungsverfahren.

Heroniteration vs. Intervallhalbierung

Die Heroniteration konvergiert viel(!) schneller gegen die Wurzel als das Intervallhalbierungsverfahren. Genauer gelten für eine positive Zahl

Satz (Heron)
Sei \left(w_{n}\right)_{n\in\mathbb{N}} die Folge aus der Heroniteration. Wenn für den Startwert w_{0} die Bedingung w_{0}^{2}\in\left[a,4a\right] erfüllt ist, so gilt auf jeden Fall

    \[ \left|w_{n}-w\right|\leq\dfrac{1}{2^{2^{n}-1}}\left|w_{0}-w\right| \]

Wer unbedingt einen Beweis sehen will, klicke hier.

Satz (Intervallhalbierung)
Sei \left[a_{n},b_{n}\right] das n-te Intervall beim Intervallhalbierungsverfahren. Als Näherung w_{n} nehmen wir immer die Mitte des Intervalls, also w_{n}=\left(a_{n}+b_{n}\right)/2. Es gilt auf jeden Fall

    \[ \left|w_{n}-w\right|\leq\frac{1}{2^{n+1}}\left|b_{0}-a_{0}\right| \]

Zum Vergleich: Nach n=10 Iterationen hat man für die Faktoren jeweils

    \[ \frac{1}{2^{2^{10}-1}}=\frac{1}{2^{1023}}\leq\frac{1}{10^{307}}\qquad\text{und}\qquad\frac{1}{2^{10+1}}=\frac{1}{2048}\leq\frac{1}{10^{3}} \]

Wärend man bei Heron also schon sicher sagen kann, dass \left|w_{10}-w\right|\leq0,0\ldots01\cdot\left|w_{0}-w\right| (306 Nullen nach dem Komma) ist, kann man beim Intervallhablierungsverfahren gerademal sicher sagen, dass \left|w_{10}-w\right|\leq0,001\cdot\left|b_{0}-a_{0}\right| gilt.

Implementiere Herons Algorithmus in JAVA

Schreibe dazu eine Methode sqrt, die einen double Wert a erhält und die Wurzel von a zurückgibt. Sicherlich musst du eine Schleife verwenden. Überlege dir selbst, was eine gute Abbruchbedingung für diese Schleife sein sollte.

Schreibe einen Kommentar