Méthode de la Dichotomie

Nous allons présenter la méthode de Dichotomie pour minimiser une fonction unimodale.

function [intervalle,iter]=dicho(fonction,intervalle,epsilon,iter)
// Methode de dichotomie utilisant la dédivée
// En entree
// fonction   : fonction supposee unimodale de la forme 
//              y=fonction(x).
// intervalle : vecteur 1x2, intervalle de depart pour l'optimisation.
// epsilon    : reel positif, precision de l'optimisation.
// iter       : entier, nombre d'iteration pour l'algotithme.
// En sortie
// intervalle : vecteur 1x2, resultat de la dichotomie.
// iter       : nombre d'iterations restantes a effectuer.
//
// Test de  l'intervalle de départ 
//
init=iter;
binf=min(intervalle);
bsup=max(intervalle);
if norm(binf-bsup)==%inf then error('une des bornes de l''intervalle est infinie'), end;
  bdemi   = (binf+bsup)/2;
  f_binf  = fonction(binf);
  f_bsup  = fonction(bsup);
  f_bdemi = fonction(bdemi);
  u=file('open','results_dicho','unknown');
  
  // Methode de dichotomie
  while ((abs(bsup-binf)>= epsilon) & (iter >= 1))
    b1quart   = (bdemi+binf)/2;
    b3quart   = (bsup+bdemi)/2;
    f_b1quart = fonction(b1quart);
    f_b3quart = fonction(b3quart);
    
    tab=[f_binf,f_b1quart,f_bdemi,f_b3quart,f_bsup];
    [a,b]=gsort(tab,'c','i');
    
    if (b(1) == 1) | (b(1) == 2) then 
      bsup    = bdemi;
      bdemi   = b1quart;
      f_bsup  = f_bdemi;
      f_bdemi = f_b1quart;
    elseif b(1) == 3  then
      
      binf    = b1quart;
      bsup    = b3quart;
      f_binf  = f_b1quart;
      f_bsup  = f_b3quart;
    elseif (b(1) == 4) | (b(1) == 5) then
      binf     = bdemi;
      bdemi    = b3quart;
      f_binf   = f_bdemi;
      f_bdemi  = f_b3quart;
    end
    fprintf(u,'iter = %2.0f binf = %10.8f bsup = %10.8f precision %10.8f',...
	init-iter+1,binf,bsup,abs(bsup-binf));
    iter=iter-1;
  end
  intervalle=[binf,bsup];
  file('close',u)
endfunction