5.2. Analyse numérique¶
5.2.1. Résolution d’équations par dichotomie¶
Il s’agit ici de calculer une valeur approchée d’une solution d’une équation du type \(f(x)=0\). On ne cherche pas à obtenir une expression exacte d’une telle solution, ce qui est de toute façon évidemment impossible de manière générale.
On suppose qu’on dispose d’une fonction \(f\) continue et strictement monotone sur un intervale \([a,b]\) vérifiant \(f(a)f(b)\leq0\). Le théorème des valeurs intermédiaires garantit l’existence d’une unique solution à l’équation \(f(x)=0\) sur l’intervalle \([a,b]\). Pour obtenir une valeur approchée de cette solution, on procède par dichotomie :
- On calcule \(c=(a+b)/2\) et \(f(c)\).
- Si \(f(a)f(c)\leq0\), la solution appartient à l’intervalle \([a,c]\). Sinon, elle appartient à l’intervalle \([c,b]\).
- Dans le premier cas, on remplace \(b\) par \(c\) tandis que dans le second cas, on remplace \(a\) par \(c\).
- On répète les étapes 1., 2. et 3. tant que la longeur de l’intervalle \([a,b]\) est supérieur à une précision \(\epsilon\) donnée.
- La valeur de \(c\) est alors une valeur appochée de la solution de \(f(x)=0\) à \(\epsilon/2\) près.
In [1]: def dicho(f, a, b, eps):
...: while abs(b-a) > eps:
...: c = (a + b) / 2
...: if f(a) * f(c) <= 0:
...: b = c
...: else:
...: a = c
...: return (a+b) / 2
...:
In [2]: from math import sin
In [3]: dicho(sin, 2, 4, .0001)
Out[3]: 3.141571044921875
Il est à remarquer que le module scipy
dispose déjà de fonctions pouvant résoudre de manière approchée des équations du type \(f(x)=0\).
In [4]: from scipy.optimize import fsolve
In [5]: from math import cos
In [6]: f = lambda x: cos(x**2)
In [7]: x0 = fsolve(f, 0)
In [8]: x0
Out[8]: array([-49.99136881])
In [9]: f(*x0)