2.1 Algorithme de bisection
L’algorithme de bisection est une méthode simple pour trouver les racines de fonctions unidimensionnelles. Le but est de trouver une racine \(x_0\in\) telle que \(f(x_0)=0\). L’algorithme commence par un grand intervalle, connu pour contenir \(x_0\), puis réduit successivement la taille de l’intervalle jusqu’à ce qu’il encadre la racine. La base théorique de l’algorithme est le théorème des valeurs intermédiaires, qui stipule que si une fonction continue \(f\) prend les valeurs \(f(a)\) et \(f(b)\) aux extrémités de l’intervalle \(\), alors \(f\) doit prendre toutes les valeurs entre \(f(a)\) et \(f(b)\) quelque part dans l’intervalle. Ainsi, si \(f(a) < \gamma < f(b)\), alors il existe un \(c\in\) tel que \(f(c)=\gamma\).
À partir de ces informations, nous pouvons présenter l’algorithme de bissection. Tout d’abord, nous devons vérifier que \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). Sinon, l’intervalle ne contient pas la racine et il faudra peut-être l’élargir. Nous pouvons alors procéder:
-
Let \(c = \frac{a + b}{2}\).
-
Si \(f(c) = 0\), on s’arrête et on retourne \(c\).
-
Si \(\text{sign}(f(a))\ne\text{sign}(f(c))\), alors mettez \(b\leftarrow c\). Sinon, si \(\text{sign}(f(b))\ne\text{sign}(f(c))\), alors mettez \(a\leftarrow c\).
-
Passez au début et répétez jusqu’à convergence (voir ci-dessous).
Après \(n\) itérations, la taille de l’intervalle encadrant la racine sera \(2^{-n}(b-a)\).
L’algorithme de bissection est utile, conceptuellement simple, et facile à mettre en œuvre. En particulier, vous n’avez pas besoin d’informations particulières sur la fonction \(f\), sauf la capacité de l’évaluer en divers points de l’intervalle. Les inconvénients sont qu’il n’est utile que dans une dimension et que sa convergence est linéaire, ce qui est le taux de convergence le plus lent pour les algorithmes dont nous parlerons (nous y reviendrons plus tard).
L’algorithme de bisection peut rencontrer des problèmes dans les situations où la fonction \(f\) ne se comporte pas bien. La situation idéale pour l’algorithme de bisection ressemble à quelque chose comme ceci.
Configuration idéale pour l’algorithme de bisection.
Ici, \(f(a)\) et \(f(b)\) sont de signes opposés et la racine est clairement entre \(a\) et \(b\).
Dans le scénario ci-dessous, l’algorithme ne démarrera pas car \(f(a)>0\) et \(f(b)>0\).
Dérivée de \(f\) à la racine est \(0\).
Dans ce scénario suivant, il y a deux racines entre \(a\) et \(b\), en plus d’avoir \(f(a)>0\) et \(f(b)>0\). Il faudrait réduire la longueur de l’intervalle de départ pour trouver l’une ou l’autre des racines.
Deux racines dans l’intervalle.
Dans le scénario ci-dessous, l’algorithme démarre parce que \(f(a)\) et \(f(b)\) sont de signe opposé, mais il n’y a pas de racine.
L’intervalle contient une asymptote mais pas de racine.
La convergence de l’algorithme de bissection peut être déterminée soit en ayant \(|b-a|<\varepsilon\) pour un certain petit \(\varepsilon\) soit en ayant \(|f(b)-f(a)|<\varepsilon\). Le critère que vous utiliserez dépendra de l’application spécifique et des types de tolérances requises.
2.1.1 Exemple : Quantiles
Donné une fonction de distribution cumulative \(F(x)\) et un nombre \(p\in (0, 1)\), un quantile de \(F\) est un nombre \(x\) tel que \(F(x) = p\). L’algorithme de bissection peut être utilisé pour trouver un quantile \(x\) pour un \(p\) donné en définissant la fonction \(g(x) = F(x) – p\) et en résolvant la valeur de \(x\) qui permet d’obtenir \(g(x) = 0\).
Une autre façon de présenter cela est que nous inversons la CDF pour calculer \(x = F^{-1}(p)\). Donc l’algorithme de bissection peut être utilisé pour inverser des fonctions dans ces situations.