Méthode du gradient à pas constant

(Exercice d’oral Centrale Mp)
Soit {A\in\mathcal{M}_N(\mathbb{R})} symétrique, avec {\text{Sp}(A)\subset\mathbb{R}^{+*}}.

On note {0 \lt \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_N} les valeurs propres de {A}.

Soit {b\in\mathbb{R}^N}. On recherche une approximation de {v\in\mathbb{R}^{N}} tel que {Av=b}.

On note {(x,y)\mapsto \left(x\mid y\right)} et {x\mapsto\left\|{x}\right\|} la norme sur {\mathbb{R}^N}.

On munit {\mathcal{M}_{n}(\mathbb{R})} de la norme définie par : {\left\|M\right\|=\sup\limits_{x\ne0}\dfrac{\left\|{Mx}\right\|}{\left\|{x}\right\|}}.

Soit {\rho\in\mathbb{R}^{+*}}. Soit {u_0 \in \mathbb{R}^N } et : {\forall\, n \in \mathbb{N}, \; u_{n+1}=u_n- \rho (A u_n- b) \quad (\star)}

  1. Si la suite {(u_n)} converge, que peut-on dire de sa limite ?
  2. Montrer : {\| u_{n+1}-v \| \leq K \| u_n-v \|}, où {K=\max (|1\!-\!\rho \lambda_1|, |\rho \lambda_N\!-\!1|).}

    Quelle est la valeur de {\rho} qui réalise le plus petit coefficient {K\lt 1}?

  3. On note, pour tout {x} de {\mathbb{R}^N}: {f(x)=\dfrac{1}{2}\left({Ax}\mid{x}\right)-\left({b}\mid{x}\right)}.

    Montrer que {f} a un minimum global sur {\mathbb{R}^N}, atteint en {v}.

    Interpréter la relation {(\star)} et le comportement de la suite {(u_n)}.

Cliquer ici pour voir (ou cacher) le corrigé
 Pour voir ce contenu, vous devez avoir souscrit au site