La méthode de dichotomie

A chaque itération k de l'algorithme de Fletcher-Reeves il est nécessaire de calculer le $\lambda_{k}$ optimal, c'est à dire celui qui minimise la surface dans la direction de descente $d_{k}$.
On cherche ainsi à minimiser la fonction g définie par:

$$g(\lambda)=f(Z_{k}+\lambda d_{k})$$

On a choisi la méthode de dichotomie sans dérivée en supposant que g est unimodale.
Principe de l'algorithme:

Figure 2.2: Exemple de fonction unimodale

On utilise la propriété d'unimodalité de g, pour tous $\lambda_{1}$, $\lambda_{2}\in$[A,B] tels que $\lambda_{1}<\lambda_{2}$ on a :

$$g(\lambda_{1}) < g(\lambda_{2}) \Rightarrow \lambda_{2} \geq \overline{\lambda}$$

$$g(\lambda_{2}) > g(\lambda_{1}) \Rightarrow \lambda_{1} \leq \overline{\lambda}$$

A chaque itération, on cherche à éliminer deux des quatres intervalles:

• $[a,d]$
• $[d,c]$
• $[c,e]$
• $[e,d]$

Seulement deux tests sont nécessaires :

• $\mbox{si } g(c)>g(e) \mbox{ alors on conserve } [c,b]$
• $\mbox{si } g(d)<g(c) \mbox{ alors on conserve } [a,c]$
• $\mbox{sinon on conserve } [d,e]$

On arrête dès que la longeur de est inferieure à un choisi.


Code du source :

float minimisation1D(maillage xk,float dk[N-2][N-2]) {
  float lk,A=0.,B=5.;
  float a,b,c,d,e;
  float fc,fd,fe;
  float epsilon=0.01;
  a=A;b=B;c=0.5*(a+b);
  fc=CalculSurface(xk,c,dk);
  while ((b-a)>epsilon){    
    d=0.5*(a+c); e=0.5*(c+b);
    fd=CalculSurface(xk,d,dk);
    fe=CalculSurface(xk,e,dk);
    if(fc>fe){
      a=c; c=e; fc=fe;
    } 
    else { 
      if(fd<fc){
	b=c;c=d;fc=fd;
      } 
      else {
	a=d;b=e;
      }
    }
  } 
  return(c);
}