CAMA : ma32 Méthode du gradiant pour système matriciel

Cours du 25/06

$Ax=b$ vu comme un probleme d'optimisation

Pour résoudre

$Ax=b$ on va chercher le minimum de la fonctionnelle

$$J(x)=\frac{1}{2}{x}^{T}Ax-b.x$$
La dérivée s'annule en ce point et est

$Ax-b$

Calcul de la dérivée

Les derivées de dimension supérieure a 1 peuvent être manipulées comme des derivées partielles ou une derivée totale. On s'intéresse à la derivée dans une direction, c.a.d la derivée partielle en

$y$ si on va dans la direction de l'axe

$y$.

Définition

$f:\mathrm{\Omega }\subset X\to Y$ (

$\mathrm{\Omega }$ ouvert) est dérivable en

$a\in \mathrm{\Omega }$ si

$$\begin{gathered} \mathrm{\exists }{f}^{\prime }(a)\in L(X,Y)telque \\ f(a+h)=f^{\prime }(a)+f(a)(h)+hϵ(h) \end{gathered}$$
avec:

• $\underset{h\to 0}{lim}ϵ(h)=0$
• $L(X,Y)$ applications linéaires continues de
  $X$ dans
  $Y$
• $f^{\prime }(a)\in L(X,Y)$ et non
  $f^{\prime }$

Si

$f$ est dérivable en

$a$ alors

$\mathrm{\forall }h\in X$

$$f^{\prime }(a)(h)=li{m}_{\theta \to 0}\frac{f(a+\theta h)-f(a)}{\theta }$$

Attention à vérifier le type de chaque terme.

$f$ est une fonction scalaire donc :

• $Y=\mathbb{R}$
• $X={\mathbb{R}}^{n}avecn>1$

Notation avec le gradient

$$f(a+h)=f(a)+(\mathrm{\nabla }f)(a{)}^{T}h+h^Tϵ(h)$$

• $f$ est scalaire
• $(\mathrm{\nabla }f)(a)$ est un vecteur dont le produit scalaire avec h donne un réel

Calculons la dérivée de J suivant une direction

On calcule la dérivée de

$J(x)$ au point

$a$ suivant la direction

$h$

$$\begin{gathered} J^{\prime }(a)(h)=\underset{\theta \to 0}{lim}\frac{J(a+\theta h)-J(a)}{\theta } \\ =\underset{\theta \to 0}{lim}\frac{1}{\theta }(\frac{1}{2}(a+\theta h{)}^{T}A(a+\theta h)-b^T(a+\theta h)-\frac{1}{2}{a}^{T}Aa+b^{T}a) \\ =\underset{\theta \to 0}{lim}\frac{1}{\theta }(\frac{1}{2}(\theta a^{T}Ah+\theta h^{T}Aa+{\theta }^2{h}^{T}Ah)-\theta b^{T}h) \\ =\frac{1}{2}(a^{T}Ah+h^{T}Aa)-b^{T}h \end{gathered}$$
donc

$$\begin{gathered} J^{\prime }:x\in \mathrm{\Omega }\subset {\mathbb{R}}^n\to L({\mathbb{R}}^n,\mathbb{R}) \\ x\mapsto \frac{1}{2}(x^{T}A+Ax)-b \end{gathered}$$

A symétrique

Dans le cas ou A est symétrique, on a:

$$J^{\prime }(x)=\mathrm{\nabla }J(x)=Ax-b$$

Si la dérivée s'annule, c.a.d qu'on trouve le minimum, on a résolu le système matriciel

Les conditions pour utiliser la méthode de gradient sont:

• A symétrique
• J a un minimum

Propriéte

Si A est symétrique et définie positive alors

$J$ est convexe strictement et coervice (

$\underset{\Vert a\Vert \to \mathrm{\infty }}{lim}J(a)=+\mathrm{\infty }$), alors elle a un minimum.