5.6 Méthode de Gradient

5.6.1 description de la méthode

• A est une matrice symétrique définie positive si
  $X^{t}.A.X>0$ si $X\neq0$ i.e. $\lambda_{i}>0$
• soit la forme quadratique définie positive
  
  $$\phi(X)=\frac{1}{2}X^{t}.A.X-X^{t}.B$$
  
  
  
  
  $$\phi(X)=\sum_{i=1}^{n}\sum_{j=1}^{n}X_{j}.A_{ij}.X_{i}-\sum_{i=1}^{n}X_{i}.B_{i}$$
  
  

• Le minimum de $\phi(X)$ est solution de $A.X=B$
  X = Arg Min($\phi(X)$) $\Leftrightarrow$ $A.X=B$
  
  $$\frac{\partial\phi(X)}{\partial X_{i}}=\sum_{j=1}^{n}A_{ij}.X_{j}-B_{i}$$
  
  

• itération de Gradient = minimisation de $\phi(X)$
  suite $X^{(k)}$ tq $\phi(X^{(k+1)})<\phi(X^{k})$
  
  $$R^{(k)}=B-A.X^{(k)}=-grad(\phi(X^{(k)}))$$
  
  
  
  
  $$X^{(k+1)}=X^{(k)}+\lambda_{k}.R^{(k)}\mbox{ avec }\lambda_{k}=\frac{R^{(k)}.R^{(k)}}{R^{(k)}.A.R^{(k)}}$$
  
  

5.6.2 convergence de la méthode

théorème:

Si A est une matrice à symétrique définie positive, alors la méthode de gradient converge

$$\phi(X^{(k+1)})=\min_{\lambda\in\mathbb{R}}\phi(X^{(k)}+\lambda.R^{(k)})$$

$$\mbox{car }\frac{\partial\phi(\lambda_{k})}{\partial\lambda}=0$$

$$\mbox{et }\phi(X^{(k+1)})<\phi(X^{(k)})$$

d'ou la convergence de l'algorithme de gradient

• variante de l'algorithme: algorithme de "gradients conjugués"