Recherche d’une racine simple par la méthode de bissection ou dichotomie

1 Présentation

La méthode de la bissection exposée ici, est adaptée de celle de R.DONY qu’il développe dans son livre Graphisme scientifique sur micro-ordinateur publié chez Masson 1984/1985, aux pages 112,113,114,115,116 et 117. C’est un livre remarquable que je conseille à tous ceux qui souhaitent justement, s’initier aux graphismes 2D et 3D.

Nous nous limitons à la recherche d’une racine simple. La première démarche consiste à déterminer l’intervalle [x₁,x₂] où se trouve la racine. Une méthode rudimentaire consiste à tracer la fonction étudiée. L’exemple choisi sera très simple et les racines évidentes, ceci pour permettre une vérification aisée.

J’ai donc écrit trois commandes, qui vont être détaillées par la suite :

• l’une \pNodeRacine permet d’afficher graphiquement la racine dans l’intervalle proposé ;
• la deuxième \pNodeValeurRacine calcule et affiche la valeur approchée de la racine ;
• la troisième \pNodeIteration permet de suivre pas à pas comment l’encadrement autour de la racine se resserre : c’est une méthode qui converge très rapidement, nous en reparlerons ; la précision souhaitée peut être modifiée dans la commande.

2 La méthode de la bissection

Les explications ci-dessous sont extraites du livre de R.DONY.

Le choix de l’équation : elle sera définie dans une variable \Function par :

L’intervalle choisi est volontairement large [x₁ = 0.8,x₂ = 3].

«À chaque étape, l’intervalle étant divisé par deux, au bout de 10 itérations, l’intervalle initial sera réduit dans un facteur de 2¹⁰ !

ligne 2 :

On calcule l’abscisse x_M et l’ordonnée du milieu de [x₁ = 0.8,x₂ = 3].

ligne 7 :

Si y_M = 0 alors y_M est la racine.

lignes 8, 9, 10 :

Si y₁ × y_M > 0 alors la racine appartient à l’intervalle [x_M,x₂] et on pose x₁ = x_M, sinon elle appartient à l’intervalle [x₁,x_M] et on pose x₂ = x_M.

ligne 11 :

Si la condition d’arrêt n’est pas satisfaite, on recommence le processus avec un nouvel intervalle réduit de moitié. »

1 {  
2    /XM X1 X2 add 2 div def % abscisse du milieu  
3    /x X1 def  
4    /Y1 Function def % valeur de la fonction Y1=y(x) pour x=X1  
5    /x XM def  
6    /YM Function def % valeur de la fonction YM=y(XM) pour x=XM  
7     YM 0 eq {exit} if % si y(XM)=0 la racine est XM  
8     Y1 YM mul 0 ge {/X1 XM def}  
9                      {/X2 XM def}  
10     ifelse  
11  X1 X2 sub abs 1e-6 le {exit} if  
12 } loop

3 Les commandes PSTricks permettant d’expérimenter

3.1 La recherche graphique d’une racine simple : \pNodeRacine

Cette commande s’écrit \pNodeRacine(x1,x2){I}{\Function}.

• Le couple (x1,x2) correspond aux deux bornes de l’intervalle initial encadrant la racine.
• {I} est le nom du point dont l’abscisse correspond à la racine cherchée.
• {\Function} contient la définition de la fonction étudiée. {\Function} aura été définie ou redéfinie au préalable. Si elle a déjà été définie, comme dans la première partie, on utilisera la commande suivante, pour en définir une nouvelle : y = x⁴ - 9x³ - 2x² + 120x - 130.

  \renewcommand\Function{x 4 exp 9 x 3 exp mul sub 2 x 2 exp mul sub 120 x mul add 130 sub}

  Exemple que j’emprunte au livre de R.DONY, page 112.

Le cadre du dessin \begin{pspicture}(-4,-4)(10,2) doit être déterminé auparavant, on jouera aussi sur les échelles \psset{xunit=1,yunit=0.01}.

3.2 La recherche de la valeur approchée d’une racine simple : \pNodeValeurRacine

Elle s’utilise comme précédemment.

La racine comprise dans l’intervalle [-5,-2] vaut x =-3.60014
La racine comprise dans l’intervalle [0,2] vaut x =1.22859
La racine comprise dans l’intervalle [3,5] vaut x =3.97207
La racine comprise dans l’intervalle [6,8] vaut x =7.39948
Si l’on souhaite afficher la valeur de la racine au-dessus du point d’intersection, il suffit d’opérer ainsi :

4 Expérimenter pas à pas la méthode de la bissection

Il existe une commande dédiée à cela : \pNodeIteration. Elle s’utilise de la manière suivante :

[NbreIterations=0] permet de fixer le nombre d’itérations. L’intervalle s’affiche en rouge. L’intervalle initial est en bleu.

Une animation utilisant cette commande est visible sur la page Dichotomie_animation_png correspondante. On s’apercevra de la convergence très rapide de la méthode. L'ensemble des sources est disponible ici :