On pose \(J\) la fonctionnelle quadratique suivante pour \(A\) une matrice symétrique définie positive et \(b\) un vecteur de \(\R^{p}\) : \[J(v)=\frac{1}{2}\langle Av,v \rangle-\langle b,v \rangle.\] On cherche à minimiser la fonctionnelle \(J\) par une méthode de gradient par l’intermédiaire d’une suite récurrente \((u_k)_{k \in \N}\). On pose pour \(k\geq 0\) : \[w_k=Au_k-b,\quad \varrho_k=\frac{\|w_k\|_2^2}{\langle Aw_k,w_k \rangle},\quad u_{k+1}=u_k-\varrho_kw_k,\]
- \question{Montrer que la fonction $v\in \R^{p} \mapsto J(v)$ est de classe $\mathcal{C}^1$, et calculer $\nabla J(v)$ pour tout $v \in \R^{p}$.}
\indication{Utiliser la définition de la différentielle en calculant $J(v+h)$ et en isolant les termes linéaires en $h$. Noter que la symétrie de $A$ implique $\langle Ah,v \rangle = \langle h,Av \rangle = \langle Av,h \rangle$.}
\reponse{
La fonction $J$ est une combinaison linéaire de fonctions de classe $\mathcal{C}^{\infty}$ sur $\R^p$ :
- $v \mapsto \langle Av,v \rangle$ est une forme quadratique, donc polynomiale et ainsi $\mathcal{C}^{1}$
- $v \mapsto \langle b,v \rangle$ est une forme linéaire, donc $\mathcal{C}^{1}$
&= \frac{1}{2}\langle Av,h \rangle + \frac{1}{2}\langle Ah,v \rangle + \frac{1}{2}\langle Ah,h \rangle - \langle b,h \rangle
&= \langle Av,h \rangle + \frac{1}{2}\langle Ah,h \rangle - \langle b,h \rangle \quad \text{(car $A$ symétrique)}
&= \langle Av-b,h \rangle + o(\|h\|) \end{align*}$$ Par identification de la différentielle, on obtient : $$\boxed{\nabla J(v) = Av - b}$$ }
Montrer que la fonction \(v\in \R^{p} \mapsto J(v)\) est de classe \(\mathcal{C}^1\), et calculer \(\nabla J(v)\) pour tout \(v \in \R^{p}\).
Montrer que \(J\) est strictement convexe et coercive sur \(\R^{p}\). En déduire que \(J\) admet un unique minimum \(u\) vérifiant \(Au=b\).
Montrer les inégalités suivantes pour tout \(v,u \in \R^{p}\) : \[\langle \nabla J(v)-\nabla J(u),v-u \rangle \geq \lambda_1 \|v-u\|_2^2\] \[\|\nabla J(v)-\nabla J(u)\|_2\leq \lambda_p \|v-u\|_2,\] où \(\lambda_1\) et \(\lambda_p\) désignent respectivement la plus petite et la plus grande des valeurs propres de la matrice \(A\).
Montrer l’assertion suivante: s’il existe \(a\) et \(b\) tels que
\[0<a\leq \varrho_k\leq b<\frac{2\lambda_1}{\lambda_{p}^2},\,\forall k \in \N,\]
la méthode du gradient converge et la convergence est géométrique:
il existe \(\beta=\beta(\lambda_1,\lambda_p,a,b),\,\,\beta<1\) telle que:
\[\|u_k-u\|\leq \beta^k\|u_0-u\|.\]