Méthode de bisection avec moyenne géométrique
La méthode de bissection est une méthode bien connue de recherche de racines. Étant donné une fonction continue$f$ et un intervalle $[a,b]$ où $f(a)$ et $f(b)$ ont des signes opposés, une racine peut être garantie $(a,b)$. La méthode de bissection calcule$f(\frac{a+b}2)$et affine de manière itérative l'intervalle en fonction de son signe. Le principal avantage de ceci est la simplicité et la convergence linéaire garantie car à chaque itération on peut dire que l'erreur divise par deux.
En arithmétique à virgule flottante, cependant, le flottant qui est directement entre $a$ et $b$ n'est pas donné par $\frac{a+b}2$ mais plutôt $\sqrt{ab}$, en supposant $a$ et $b$sont tous les deux positifs. Pour cette raison, je me demande s'il est réellement avantageux d'utiliser la moyenne géométrique au lieu de la moyenne arithmétique. Similaire à la méthode de bissection arithmétique, la méthode de bissection géométrique réduit de moitié l'erreur de la$\log(a)$ et $\log(b)$ à chaque pas, la convergence linéaire est donc garantie de la même manière.
Fait intéressant, la moyenne arithmétique divise par deux l' erreur absolue , tandis que la moyenne géométrique divise par deux l' erreur relative .
Q: Devrions-nous utiliser la moyenne arithmétique ou géométrique (ou peut-être autre) lorsque nous utilisons une bissection avec des flottants? Quels sont les avantages et les inconvénients de chacun?
Réponses
Il semblerait être le cas, du moins pour autant que je l'ai testé, que la moyenne géométrique soit assez utile lorsque $a$ et $b$ diffèrent considérablement en ampleur.
Avantages des moyens géométriques:
En double précision, les cas extrêmes sont à peu près $10^{\pm308}$. Supposons que nous essayions d'atteindre$x=2$ pour usiner la précision en utilisant ces deux points initiaux:
- les moyennes arithmétiques nécessiteraient environ 1000 itérations .
- les moyennes géométriques nécessiteraient environ 60 itérations .
Cela signifie que le pire des cas pour les moyennes géométriques est bien meilleur.
Le scénario le moins extrême (comme avec un support comme $[1,6]$ pour $x=2$) a des moyennes arithmétiques nécessitant environ 50 itérations pour atteindre, mais il en va de même pour les moyennes géométriques. Cela peut être justifié en notant que la différence des moyennes arithmétiques et géométriques
$$\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}$$
décroît rapidement à mesure que l'intervalle se réduit.
Inconvénients des moyennes géométriques:
- Une certaine manipulation des cartons devient nécessaire (différents signes ou $0$ est l'un des points), ce qui signifie un code plus compliqué.
- Peut converger plus lentement que prévu si un point est très proche de $0$ et l'autre ne l'est pas (par exemple $[a,b]=[10^{-308},2]$ avec une racine à $x=1.3$) afin que la moyenne géométrique ne semble pas se rapprocher initialement de la racine aussi rapidement que la moyenne arithmétique.
- Coût arithmétique plus élevé par itération car une racine carrée (ou deux pour éviter un sous / débordement en utilisant $\sqrt x\cdot\sqrt y$) doit être calculé.
Corrections possibles:
- La gestion des cas où les points ne sont pas du même signe peut être effectuée en utilisant le plus petit flottant positif multiplié par le signe du plus grand nombre.
- Un mélange de moyennes arithmétiques et géométriques devrait retrouver le comportement initialement attendu.
- La moyenne arithmétique-géométrique peut être intéressante à utiliser.
- Une solution plus simple serait d'alterner entre les moyennes arithmétiques et géométriques.
Mise à jour du 26/10:
Comme je l'ai expliqué ici , après avoir$x/y\in(0.5,2)$, un passage de la moyenne géométrique à la moyenne arithmétique doit être utilisé. Cette conclusion est tirée sur la structure du double.
Mise à jour du 11/03:
Il devrait en fait avoir plus de sens d'utiliser $(3x+y)/4$ lorsque la moyenne géométrique ne parvient pas à réduire significativement l'erreur absolue, où $|x|<|y|$. Intuitivement, cela équivaut à peu près à deux itérations de moyennes arithmétiques. Dans le pire des cas, cela peut provoquer une ou deux itérations supplémentaires de moyennes arithmétiques alors qu'une itération de bissection aurait suffi. Ceci est particulièrement important en ce qui concerne les méthodes hybrides de recherche de racines, où la réduction de l'erreur absolue améliore plus facilement l'interpolation.