Halbierungsmethode mit geometrischem Mittelwert
Die Halbierungsmethode ist eine bekannte Methode zur Wurzelfindung. Gegeben eine stetige Funktion$f$ und ein Intervall $[a,b]$ wo $f(a)$ und $f(b)$ Haben entgegengesetzte Vorzeichen, kann garantiert werden, dass eine Wurzel in ist $(a,b)$. Die Halbierungsmethode berechnet$f(\frac{a+b}2)$und verfeinert iterativ das Intervall basierend auf seinem Vorzeichen. Der Hauptvorteil dabei ist die Einfachheit und garantierte lineare Konvergenz, da bei jeder Iteration gesagt werden kann, dass sich der Fehler halbiert.
In der Gleitkomma-Arithmetik jedoch das Gleitkomma, das direkt dazwischen liegt $a$ und $b$ ist nicht gegeben durch $\frac{a+b}2$ sondern $\sqrt{ab}$unter der Annahme $a$ und $b$sind beide positiv. Aus diesem Grund frage ich mich, ob es tatsächlich vorteilhaft ist, das geometrische Mittel anstelle des arithmetischen Mittels zu verwenden. Ähnlich wie bei der arithmetischen Halbierungsmethode halbiert die geometrische Halbierungsmethode den Fehler der$\log(a)$ und $\log(b)$ Bei jedem Schritt wird auf ähnliche Weise eine lineare Konvergenz gewährleistet.
Interessanterweise halbiert das arithmetische Mittel den absoluten Fehler , während das geometrische Mittel den relativen Fehler halbiert .
F: Sollten wir das arithmetische oder geometrische (oder möglicherweise andere) Mittel verwenden, wenn wir die Halbierung mit Gleitkommazahlen verwenden? Was sind die Vor- und Nachteile von jedem?
Antworten
Zumindest soweit ich getestet habe, scheint es so zu sein, dass das geometrische Mittel sehr nützlich ist, wenn $a$ und $b$ unterscheiden sich stark in der Größe.
Vorteile geometrischer Mittel:
Bei doppelter Genauigkeit sind die Extremfälle ungefähr $10^{\pm308}$. Angenommen, wir versuchen zu erreichen$x=2$ zur Präzision der Maschine unter Verwendung dieser beiden Anfangspunkte:
- arithmetische Mittel würden ungefähr 1000 Iterationen erfordern .
- geometrische Mittel würden ungefähr 60 Iterationen erfordern .
Dies bedeutet, dass das Worst-Case-Szenario für geometrische Mittel weitaus besser ist.
Das weniger extreme Szenario (wie bei einer Klammer wie $[1,6]$ zum $x=2$) hat arithmetische Mittel, für deren Erreichen ungefähr 50 Iterationen erforderlich sind, aber das Gleiche gilt auch für geometrische Mittel. Dies kann gerechtfertigt werden, indem festgestellt wird, dass der Unterschied zwischen arithmetischem und geometrischem Mittel besteht
$$\frac{a+b}2-\sqrt{ab}=\frac{(\sqrt a-\sqrt b)^2}2=\frac{(a-b)^2}{2(\sqrt a+\sqrt b)^2}\sim\frac{(a-b)^2}{8x}$$
zerfällt schnell, wenn das Intervall kleiner wird.
Nachteile geometrischer Mittel:
- Es ist eine gewisse Handhabung der Kanten erforderlich (unterschiedliche Vorzeichen oder $0$ ist einer der Punkte), was komplizierteren Code bedeutet.
- Kann langsamer als erwartet konvergieren, wenn ein Punkt sehr nahe liegt $0$ und der andere ist nicht (z $[a,b]=[10^{-308},2]$ mit einer Wurzel bei $x=1.3$), so dass sich das geometrische Mittel anfangs nicht so schnell der Wurzel zu nähern scheint wie das arithmetische Mittel.
- Höhere Rechenkosten pro Iteration, da eine Quadratwurzel (oder zwei, um einen Unter- / Überlauf zu vermeiden) $\sqrt x\cdot\sqrt y$) muss berechnet werden.
Mögliche Korrekturen:
- Fälle, in denen Punkte nicht das gleiche Vorzeichen haben, können mit dem kleinsten positiven Float multipliziert mit dem Vorzeichen der größeren Zahl behandelt werden.
- Eine Mischung aus arithmetischen und geometrischen Mitteln sollte das ursprünglich erwartete Verhalten wiederherstellen.
- Das arithmetisch-geometrische Mittel kann interessant sein.
- Eine einfachere Lösung wäre, zwischen arithmetischen und geometrischen Mitteln zu wechseln.
Update 26.10.:
Wie ich hier erklärt habe , nachdem man hat$x/y\in(0.5,2)$sollte ein Wechsel vom geometrischen zum arithmetischen Mittelwert verwendet werden. Diese Schlussfolgerung basiert auf der Struktur des Doppelten.
Update 11/03:
Es sollte eigentlich sinnvoller sein, es zu verwenden $(3x+y)/4$ wenn das geometrische Mittel den absoluten Fehler nicht signifikant reduziert, wo $|x|<|y|$. Intuitiv entspricht dies ungefähr zwei Iterationen arithmetischer Mittelwerte. Im schlimmsten Fall kann dies zu einer oder zwei zusätzlichen Iterationen arithmetischer Mittel führen, wenn eine Iteration der Halbierung ausgereicht hätte. Dies ist besonders wichtig in Bezug auf hybride Wurzelfindungsmethoden, bei denen die Reduzierung des absoluten Fehlers die Interpolation leichter verbessert.