Algorithme de trichotomie
L'algorithme de trichotomie est un algorithme permettant de trouver un encadrement du minimum d'une fonction convexe. Il est basé sur l'inégalité des pentes.
Soit $f:[a,b]\to\mathbb R$ une fonction convexe dont on cherche le minimum sur $[a,b]$. On va couper l'intervalle $[a,b]$ en $3$, en posant $a_0=a$, $a_3=b$, $a_1=(2a+b)/2$ et $a_2=(a+2b)/3$. On va noter également $\mu$ la pente de la corde entre les points $(a_{1},f(a_{1})$ et $(a_2,f(a_2))$, $$\mu=\frac{f(a_2)-f(a_1)}{a_2-a_1}.$$
Le but de l'algorithme de trichotomie est de déterminer, à partir de l'étude du signe de $\mu$, un intervalle $[a',b']$ avec $b'-a'=2(b-a)/3$ de sorte que $f$ atteigne son minimum sur $[a',b']$. Il suffit ensuite de réitérer pour trouver un encadrement de plus en plus précis du minimum.On distingue 2 cas :
- $\mu\leq 0$. Par l'inégalité des pentes, on sait que, pour tout $x\leq a_1$, on a
$$\frac{f(a_1)-f(x)}{a_1-x}\leq \frac{f(a_2)-f(a_1)}{a_2-a_1}=\mu\leq 0.$$
Ainsi, $f(a_1)\leq f(x)$, et la fonction atteint son minimum sur $[a_1,a_3]$. On pose
alors $a'=a_1$ et $b'=a_3$, de sorte que $b'-a'=2(b-a)/3$.
- $\mu>0$. Cette fois, l'inégalité des pentes nous dit que, pour tout $x\geq a_2$, on a
$$0<\mu=\frac{f(a_2)-f(a_1)}{a_2-a_1}\leq\frac{f(x)-f(a_2)}{x-a_2}.$$
Ainsi, $f(x)\geq f(a_2)$, et $f$ atteint son minimum sur $[a_0,a_2]$. On pose
alors $a'=a_0$ et $b'=a_2$, de sorte que $b'-a'=2(b-a)/3$.
Consulter aussi
Recherche alphabétique
Recherche thématique