La méthode de Fletcher-Reeves

La méthode s'inpspire du celle du gradient conjugué.

Algorithme :

1. choisir $z_0$.
   calculer $g_0=\nabla f(z^0)$, et poser $d_0=g_0;k=0$.
2. Etape k.
   $z^{k+1}=z^k+\lambda_k d_k$ où $\lambda_k$ minimise $g(\lambda)=f(z^k+\lambda d_k)$.
   $d_{k+1}=-g_{k+1}+\beta_k d_k$
   avec $\beta_k=\frac{\Vert g_{k+1}\Vert^2}{\Vert g_k\Vert^2}$ et $g_{k+1}=\nabla f(z^{k+1})$.
   

Une de nos difficultés a porté sur le calcul de $\nabla f$ :

$$\nabla f = \left ( \begin{array}{c} \frac{\partial f}{\part... ...\frac{\partial f}{\partial z_{(N-2)^2}}\\ \end{array}\right )$$

avec :

$$\frac{\partial f}{\partial z_i}=\frac{\partial \sum_{\tau\in\Delta} S(\tau)}{\partial z_i}$$

On examine les six triangles voisins du point $z_i$, la dérivée étant nulle ailleurs.

Figure: Triangles adjacents à $z_i$

donc on a :

$$\frac{\partial f}{\partial z_i}=\frac{\partial \sum_{\tau\in... ..._i} =\sum_{\tau\in V(i)} \frac{\partial S(\tau)}{\partial z_i}$$

où

$$S(\tau)=\frac{\left\Vert\overrightarrow{AB}\wedge\overrightarrow{AC}\right\Vert}{2} =\sqrt{u_1^2+u_2^2+u_3^2}$$

avec

$$u_1=(y_B-y_A)(z_C-z_A)-(z_B-z_A)(y_C-y_A)$$

$$u_2=(z_B-z_A)(x_C-x_A)-(x_B-x_A)(z_C-z_A)$$

$$u_3=(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)$$

d'où

$$\frac{\partial S(\tau)}{\partial z_i}=\frac{\partial \Vert u... ...l z_i}=\frac{\partial \sqrt{u_1^2+u_2^2+u_3^2}}{2\partial z_i}$$

$$\frac{\partial S(\tau)}{\partial z_i}(Z^k)=\frac{u_1(y_C-y_B)+u_2(x_B-x_C)}{2\sqrt{u_1^2+u_2^2+u_3^2}}$$

La formule est valable pour les six triangles voisins du point $z_i$.
Au total, on obtient $\frac{\partial f}{\partial z_i}(Z^k)$.