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é

  1. On a : {\forall n\in\mathbb{N},\;u_{n+1}=u_n- \rho (A u_n - b)}. Supposons {\displaystyle\lim_{n\to+\infty}u_n = x}.

    Par continuité, {x=x-\rho (Ax-b)} donc (sachant {\rho \neq 0}) {Ax=b} donc {x=v}.

    Ainsi, si la suite {(u_n)} converge, c’est vers le vecteur {v}.

  2. On a toujours {u_{n+1}=u_n- \rho (A u_n- b)}. On en déduit : {u_{n+1}-v=u_n-v- \rho (A u_n-Av)=(I_n- \rho A)( u_n-v)}Ainsi {\forall n\in\mathbb{N},\;\| u_{n+1}-v \| \leq \| I_n - \rho A \| \| u_n-v \|}.

    On diagonalise {I_n-\rho A} dans une base orthonormée.

    On trouve alors : {\| I_n - \rho A \| \leq \max\limits_{1\le i\le N} |1-\rho \lambda_i|=K}.

    Par hypothèse : { (1- \rho \lambda_n) \leq (1-\rho \lambda_{n-1}) \leq \cdots \leq (1- \rho\lambda_1)}.

    Ainsi {K=\max (|1- \rho \lambda_1|, |1- \rho \lambda_n|)}.

    Le {\rho} optimal minimise {K=\max (|1- \rho \lambda_1|, |\rho \lambda_N-1|)}.

    On rappelle que {0 \lt \lambda_1 \leq \lambda_N}.

    On voit ci-dessous les graphes de {x \mapsto |1-x \lambda_1|} et {x \mapsto |1-x \lambda_N|}.

    Le {\rho} qui minimise {K} vérifie {\rho \lambda_N-1=1- \rho \lambda_1}.

    On trouve {\rho=\dfrac{2}{\lambda_1+\lambda_N}} et on a alors {K=\dfrac{\lambda_N - \lambda_1}{\lambda_N+\lambda_1}\lt 1}.

    • La fonction {f} est {C^1} car polynomiale. Soient {x} et {h \in \mathbb{R}^N}. Alors : {\begin{array}{rl}f(x+h)&=\dfrac 12 \left({a(x+h)}\mid{x+h}\right) - \left({b}\mid{x+h}\right)\\\\&=\dfrac 12 \left({Ax}\mid{x}\right) - \left({b}\mid{x}\right) +\dfrac 12\left({Ax}\mid{h}\right) +\dfrac 12 \left({Ah}\mid{x}\right)\\\\&= - \left({b}\mid{h}\right) + \dfrac 12 \left({Ah}\mid{h}\right) =f(x) + \left({Ax-b}\mid{b}\right)+ o ( \| h \|)\end{array}}(on a utilisé la symétrie de {a} et le fait que {Ah=O(\|h\|)}).

      Ainsi, par identification : {\text{grad} f (x)=Ax-b}.

    • Le vecteur {v} est donc le seul point critique de {f}.

      Il suffit de montrer que {f} admet bien un minimum ce qui peut se faire avec un argument de continuité et le fait que {\| f(x) \| \to + \infty} lorsque {\|x \| \to + \infty} (facile en diagonalisant).

      Autre idée : dans une base orthonormée, on a {f(x)=\sum \lambda_i x_i^2 - \sum b_i x_i} et la mise sous forme canonique prouve qu’il y a un minimum global ({\lambda_i>0}).

    • D’après le calcul du gradient de {f}, {(\star)} s’écrit : {u_{n+1}=u_n- \rho \, \text{grad} f (u_n)}.

      Si {(u_n)} converge, c’est donc vers un point critique de {f} donc un éventuel extremum.

      Le gradient, normal aux lignes de niveaux, est dirigé suivant les “{f} croissants”.

      Ainsi, la relation {u_{n+1}=u_n- \rho\, \text{grad} f (u_n)} montre que pour construire {u_{n+1}} on part de {u_n}, qui est sur une ligne de niveau, et on ajoute {- \rho \, \text{grad} f (u_n)} qui est normal à cette ligne de niveau et part dans le sens “{f} décroissants”. Voilà pourquoi on peut espérer arriver à un minimum de {f}. Mais tout est dans le choix de {\rho} : bien sûr, il faut le prendre strictement positif et si {\rho} est trop grand, on risque de sauter d’un coup trop de lignes de niveaux…