Trichotomie (algorithme de)

Imaginez une courbe qui descend jusqu’à un creux unique, puis remonte. Pour localiser ce creux, on marque deux points qui partagent l’intervalle en trois parts égales. La hauteur de la courbe à ces deux endroits indique de quel côté le minimum ne peut pas se trouver.

On écarte alors un tiers de la zone de recherche et on recommence sur la partie conservée. L’intervalle se resserre autour du minimum sans calculer de dérivée. Pour chercher un maximum, le même geste s’applique en inversant les comparaisons.

La trichotomie est une méthode de recherche d’un extremum d’une fonction réelle sur un intervalle fermé. Pour une minimisation, la fonction doit être unimodale sur cet intervalle : elle décroît strictement avant sa zone de minimum, qui peut se réduire à un point ou former un plateau, puis croît strictement après cette zone. Une fonction strictement convexe satisfait cette propriété, mais la convexité n’est pas nécessaire.

On note $[a,b][a,b]$ l’intervalle courant. Les deux points intérieurs, notés $m_{1}m\_1$ et $m_{2}m\_2$, sont définis par $m_1=a+\frac{b-a}{3}m\_1=a+\backslash frac\{b-a\}\{3\}$ et $m_2=b-\frac{b-a}{3}m\_2=b-\backslash frac\{b-a\}\{3\}$. Si la première valeur est plus petite, on conserve $[a,m_2][a,m\_2]$. Si elle est plus grande, on conserve $[m_1,b][m\_1,b]$. En cas d’égalité, $[m_1,m_2][m\_1,m\_2]$ contient au moins un minimum sous cette hypothèse d’unimodalité stricte hors de la zone minimale.

À chaque comparaison non égale, la longueur de l’intervalle est multipliée par 2/3. La méthode fournit donc un encadrement de plus en plus fin du minimum. Pour une maximisation, on applique les mêmes intervalles en renversant les signes de comparaison.

Pour minimiser une fonction unimodale sur l’intervalle $[a,b][a,b]$, strictement décroissante avant sa zone minimale puis strictement croissante après elle, cette zone pouvant être un point ou un plateau, on évalue la fonction aux deux tiers intérieurs $m_{1}m\_1$ et $m_{2}m\_2$. Si $f(m_1)<f(m_2)f(m\_1)\backslash lt\; f(m\_2)$, on remplace l’intervalle par $[a,m_2][a,m\_2]$. Si $f(m_1)>f(m_2)f(m\_1)\backslash gt\; f(m\_2)$, on garde $[m_1,b][m\_1,b]$. Si les valeurs sont égales, on garde $[m_1,m_2][m\_1,m\_2]$. On recommence jusqu’à ce que la longueur de l’intervalle respecte la précision choisie.

La méthode s’applique à une fonction réelle que l’on sait évaluer sur un intervalle initial contenant l’extremum recherché. Pour une minimisation, ses valeurs doivent d’abord décroître, éventuellement rester constantes sur une zone minimale, puis croître. Il faut aussi fixer un critère d’arrêt, par exemple une largeur d’intervalle inférieure à une tolérance positive.

Si la fonction possède deux creux séparés, la comparaison de deux valeurs ne permet plus d’exclure sûrement un tiers : l’algorithme peut converger vers un minimum local qui n’est pas le plus bas. Il faut alors découper le domaine en zones unimodales, employer une recherche globale ou disposer d’informations supplémentaires sur la fonction.

On cherche le minimum de la fonction $f(x)=(x-2{)}^{2}f(x)=(x-2)^2$ sur l’intervalle [0, 6]. Les données sont la borne gauche 0, la borne droite 6 et le critère d’arrêt choisi : une largeur inférieure à 1.

1. Les deux points sont 2 et 4. Leurs valeurs sont $f(2)=0f(2)=0$ et $f(4)=4f(4)=4$. La première est plus petite, donc le minimum reste dans [0, 4].

2. Dans [0, 4], les points sont 4/3 et 8/3. Les deux valeurs valent exactement 4/9. L’égalité autorise à conserver l’intervalle central [4/3, 8/3].

3. Dans ce nouvel intervalle, les points sont 16/9 et 20/9. Les deux valeurs valent exactement 4/81. On conserve [16/9, 20/9], dont la largeur est 4/9, donc inférieure à 1.

Le milieu de l’encadrement final est 2 : c’est ici le minimum exact, avec une valeur égale à 0. Le contrôle consiste à vérifier que 2 appartient à chaque intervalle conservé et que les largeurs successives sont 6, 4, 4/3 puis 4/9.

Pour régler un seul paramètre dont la qualité baisse puis remonte, la trichotomie resserre une plage d’essai à partir de simples évaluations. Elle est utile lorsque la dérivée est indisponible ou coûteuse. Si une dérivée fiable s’annule facilement, une méthode qui l’exploite peut demander moins d’évaluations.

Dans un calcul numérique, on arrête les itérations lorsque l’intervalle est assez court pour la précision recherchée. On renvoie souvent son milieu comme approximation et sa demi-largeur comme borne d’erreur sur la position, à condition qu’un minimum se trouve bien dans l’intervalle conservé.

Si chaque évaluation est coûteuse, la section dorée réutilise une valeur déjà calculée à l’itération suivante, contrairement à la trichotomie naïve. Ce critère observable peut la rendre préférable quand le nombre d’appels à la fonction domine le coût total.

Dichotomie. La dichotomie coupe un intervalle en deux et s’appuie souvent sur un changement de signe pour chercher une racine. La trichotomie compare les valeurs en deux points pour chercher un extremum. Pour résoudre $g(x)=0g(x)=0$ avec des signes opposés aux bornes, la dichotomie est le choix adapté.

Section dorée. Les deux méthodes réduisent un intervalle contenant un extremum unimodal. La section dorée place ses points selon le nombre d’or afin de réutiliser une évaluation ; la trichotomie les place aux tiers. Si un ancien point intérieur doit devenir l’un des points de l’itération suivante, il s’agit de la section dorée.

Recherche ternaire dans un tableau. Celle-ci partage en trois une suite triée pour retrouver une valeur selon l’ordre des éléments. La trichotomie d’optimisation compare des valeurs d’une fonction unimodale. La présence d’une valeur cible à localiser dans une liste triée signale le premier problème, pas le second.

Fonction non unimodale. Plusieurs creux séparés rendent l’élimination d’un tiers injustifiée. Le symptôme est qu’un balayage préalable révèle plusieurs descentes suivies de remontées. Il faut subdiviser le domaine ou utiliser une méthode d’optimisation globale.

Égalités numériques trompeuses. Avec des valeurs arrondies ou bruitées, deux évaluations peuvent paraître égales sans l’être. Au lieu de réduire automatiquement à l’intervalle central, il faut tenir compte de l’incertitude, répéter les mesures ou conserver un intervalle plus large.

Arrêt mal interprété. Si l’intervalle final a une largeur $\epsilon \backslash varepsilon$, son milieu est à une distance d’au plus $\epsilon \mathrm{/}2\backslash varepsilon/2$ d’un minimiseur contenu dans cet intervalle. Cette garantie concerne la position, pas l’écart entre les valeurs de la fonction. Il faut un contrôle distinct pour garantir une erreur sur la valeur minimale.

Minimum non unique. Une fonction unimodale peut avoir un fond plat. L’algorithme encadre alors un minimiseur, sans sélectionner un point intrinsèquement meilleur que les autres. Si l’application exige une solution unique, il faut ajouter un critère de départage explicite.

La fiche Dichotomie montre comment une autre réduction d’intervalle localise une racine grâce à un changement de signe.

La fiche Minimum précise l’objet que la trichotomie cherche à encadrer et la différence entre valeur minimale et point minimiseur.

La fiche nombre d’or éclaire la proportion qui permet à la méthode de la section dorée de réutiliser une évaluation.

La fiche concept de convexité approfondit une propriété suffisante, mais non nécessaire, pour obtenir le comportement unimodal recherché.