6.9 Méthode de Gradient

6.9.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)}}$$
  
  

6.9.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

6.9.2.1 Influence du conditionnement

La convergence de la méthode de gradient dépend du conditionnement de la matrice $A$. Plus le conditionnement augmente, et plus la vitesse de convergence diminue.

Pour améliorer la convergence, on préconditionne le système en multipliant par une matrice de préconditionnement $M^{-1}$:

$$A.X=B \leadsto M^{-1}A X=M^{-1}B$$

telle que $cond(M^{-1}A)\approx1$, i.e. que $M^{-1}$ est le même spectre de valeurs propres que $A^{-1}$ ( $M^{-1}\approx A^{-1}$).

remarque:

on ne calcule jamais explicitement $M^{-1}$, mais on résoud des systèmes linéaires $M.Y=V$

remarque:

le préconditionnement peut être fait à l'aide d'une méthode itérative (Jacobi, Gauss Seidel) ou par des factorisations incomplètes (ILU, Incomplet Cholesky).

6.9.3 Méthode de gradient conjugués

La direction de descente $P^{(k+1)}$ est telle qu'elle est orthogonale à la direction précédente $P^{(k)}$:

$$\left(P^{(k)}\right)^{t}.\left(AP^{(k+1)}\right)=0 \mbox{{ avec }} P^{(k+1)}=R^{(k)}+\beta_{k}P^{(k)}$$

d'où:

$$\beta_{k}=-\frac{\left(P^{(k)}\right)^{t}.\left(AR^{(k)}\right)}{\left(P^{(k)}\right)^{t}.\left(AP^{(k)}\right)}$$

L'itération de gradient conjugué s'écrit:

$$X^{(k+1)}=X^{(k)}+\lambda_{k}.P^{(k)}\mbox{ avec }\lambda_{k... ...^{(k)}\right)}{\left(P^{(k)}\right)^{t}.\left(A.P^{(k)}\right)}$$

La convergence de la méthode est quadratique, i.e. en $\theta(\sqrt{N})$

6.9.4 exemple

englishméthode de gradient sous Maple