Eclats de vers : Matemat 10 : Optimisation

Index des Grimoires

Retour à l’accueil

Table des matières

\( \newcommand{\parentheses}[1]{\left(#1\right)} \newcommand{\crochets}[1]{\left[#1\right]} \newcommand{\accolades}[1]{\left\{#1\right\}} \newcommand{\ensemble}[1]{\left\{#1\right\}} \newcommand{\identite}{\mathrm{Id}} \newcommand{\indicatrice}{\boldsymbol{\delta}} \newcommand{\dirac}{\delta} \newcommand{\moinsun}{{-1}} \newcommand{\inverse}{\ddagger} \newcommand{\pinverse}{\dagger} \newcommand{\topologie}{\mathfrak{T}} \newcommand{\ferme}{\mathfrak{F}} \newcommand{\img}{\mathbf{i}} \newcommand{\binome}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\canonique}{\mathfrak{c}} \newcommand{\tenseuridentite}{\boldsymbol{\mathcal{I}}} \newcommand{\permutation}{\boldsymbol{\epsilon}} \newcommand{\matriceZero}{\mathfrak{0}} \newcommand{\matriceUn}{\mathfrak{1}} \newcommand{\christoffel}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\lagrangien}{\mathfrak{L}} \newcommand{\sousens}{\mathfrak{P}} \newcommand{\partition}{\mathrm{Partition}} \newcommand{\tribu}{\mathrm{Tribu}} \newcommand{\topologies}{\mathrm{Topo}} \newcommand{\setB}{\mathbb{B}} \newcommand{\setN}{\mathbb{N}} \newcommand{\setZ}{\mathbb{Z}} \newcommand{\setQ}{\mathbb{Q}} \newcommand{\setR}{\mathbb{R}} \newcommand{\setC}{\mathbb{C}} \newcommand{\corps}{\mathbb{K}} \newcommand{\boule}{\mathfrak{B}} \newcommand{\intervalleouvert}[2]{\relax \ ] #1 , #2 [ \ \relax} \newcommand{\intervallesemiouvertgauche}[2]{\relax \ ] #1 , #2 ]} \newcommand{\intervallesemiouvertdroite}[2]{[ #1 , #2 [ \ \relax} \newcommand{\fonction}{\mathbb{F}} \newcommand{\bijection}{\mathrm{Bij}} \newcommand{\polynome}{\mathrm{Poly}} \newcommand{\lineaire}{\mathrm{Lin}} \newcommand{\continue}{\mathrm{Cont}} \newcommand{\homeomorphisme}{\mathrm{Hom}} \newcommand{\etagee}{\mathrm{Etagee}} \newcommand{\lebesgue}{\mathrm{Leb}} \newcommand{\lipschitz}{\mathrm{Lip}} \newcommand{\suitek}{\mathrm{Suite}} \newcommand{\matrice}{\mathbb{M}} \newcommand{\krylov}{\mathrm{Krylov}} \newcommand{\tenseur}{\mathbb{T}} \newcommand{\essentiel}{\mathfrak{E}} \newcommand{\relation}{\mathrm{Rel}} \newcommand{\strictinferieur}{\ < \ } \newcommand{\strictsuperieur}{\ > \ } \newcommand{\ensinferieur}{\eqslantless} \newcommand{\enssuperieur}{\eqslantgtr} \newcommand{\esssuperieur}{\gtrsim} \newcommand{\essinferieur}{\lesssim} \newcommand{\essegal}{\eqsim} \newcommand{\union}{\ \cup \ } \newcommand{\intersection}{\ \cap \ } \newcommand{\opera}{\divideontimes} \newcommand{\autreaddition}{\boxplus} \newcommand{\autremultiplication}{\circledast} \newcommand{\commutateur}[2]{\left[ #1 , #2 \right]} \newcommand{\convolution}{\circledcirc} \newcommand{\correlation}{\ \natural \ } \newcommand{\diventiere}{\div} \newcommand{\modulo}{\bmod} \newcommand{\pgcd}{pgcd} \newcommand{\ppcm}{ppcm} \newcommand{\produitscalaire}[2]{\left\langle #1 \left|\right\relax #2 \right\rangle} \newcommand{\scalaire}[2]{\left\langle #1 \| #2 \right\rangle} \newcommand{\braket}[3]{\left\langle #1 \right| #2 \left| #3 \right\rangle} \newcommand{\orthogonal}{\bot} \newcommand{\forme}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\biforme}[3]{\left\langle #1 , #2 , #3 \right\rangle} \newcommand{\contraction}[3]{\left\langle #1 \odot #3 \right\rangle_{#2}} \newcommand{\dblecont}[5]{\left\langle #1 \right| #3 \left| #5 \right\rangle_{#2,#4}} \newcommand{\major}{major} \newcommand{\minor}{minor} \newcommand{\maxim}{maxim} \newcommand{\minim}{minim} \newcommand{\argument}{arg} \newcommand{\argmin}{arg\ min} \newcommand{\argmax}{arg\ max} \newcommand{\supessentiel}{ess\ sup} \newcommand{\infessentiel}{ess\ inf} \newcommand{\dual}{\star} \newcommand{\distance}{\mathfrak{dist}} \newcommand{\norme}[1]{\left\| #1 \right\|} \newcommand{\normetrois}[1]{\left|\left\| #1 \right\|\right|} \newcommand{\adh}{adh} \newcommand{\interieur}{int} \newcommand{\frontiere}{\partial} \newcommand{\image}{im} \newcommand{\domaine}{dom} \newcommand{\noyau}{ker} \newcommand{\support}{supp} \newcommand{\signe}{sign} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\unsur}[1]{\frac{1}{#1}} \newcommand{\arrondisup}[1]{\lceil #1 \rceil} \newcommand{\arrondiinf}[1]{\lfloor #1 \rfloor} \newcommand{\conjugue}{conj} \newcommand{\conjaccent}[1]{\overline{#1}} \newcommand{\division}{division} \newcommand{\difference}{\boldsymbol{\Delta}} \newcommand{\differentielle}[2]{\mathfrak{D}^{#1}_{#2}} \newcommand{\OD}[2]{\frac{d #1}{d #2}} \newcommand{\OOD}[2]{\frac{d^2 #1}{d #2^2}} \newcommand{\NOD}[3]{\frac{d^{#3} #1}{d #2^{#3}}} \newcommand{\deriveepartielle}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dblederiveepartielle}[2]{\frac{\partial^2 #1}{\partial #2 \partial #2}} \newcommand{\dfdxdy}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}} \newcommand{\dfdxdx}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\gradient}{\mathbf{\nabla}} \newcommand{\combilin}[1]{\mathrm{span}\{ #1 \}} \newcommand{\trace}{tr} \newcommand{\proba}{\mathbb{P}} \newcommand{\probaof}[1]{\mathbb{P}\left[#1\right]} \newcommand{\esperof}[1]{\mathbb{E}\left[#1\right]} \newcommand{\cov}[2]{\mathrm{cov} \left( #1 , #2 \right) } \newcommand{\var}[1]{\mathrm{var} \left( #1 \right) } \newcommand{\rand}{\mathrm{rand}} \newcommand{\variation}[1]{\left\langle #1 \right\rangle} \newcommand{\composante}{comp} \newcommand{\bloc}{bloc} \newcommand{\ligne}{ligne} \newcommand{\colonne}{colonne} \newcommand{\diagonale}{diag} \newcommand{\matelementaire}{\mathrm{Elem}} \newcommand{\matpermutation}{permut} \newcommand{\matunitaire}{\mathrm{Unitaire}} \newcommand{\gaussjordan}{\mathrm{GaussJordan}} \newcommand{\householder}{\mathrm{Householder}} \newcommand{\rang}{rang} \newcommand{\schur}{\mathrm{Schur}} \newcommand{\singuliere}{\mathrm{DVS}} \newcommand{\convexe}{\mathrm{Convexe}} \newcommand{\petito}[1]{o\left(#1\right)} \newcommand{\grando}[1]{O\left(#1\right)} \)

1 Optimisation libre

1.1 Minimum

\begin{theoreme} Soit $\varphi \in \continue^2(\setR^n,\setR)$. Supposons que que $a \in \setR^n$ annule la Jacobienne (on parlera ici plutôt de gradient) : $$\partial \varphi(a) = 0$$ Supposons également que la Hessienne en $a$ soit définie positive, c'est-à-dire que : $$\Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta \ge 0$$ pour tout $\Delta \in \setR^n$ qui vérifie $\Delta \ne 0$. Si ces conditions sont remplies, nous nous proposons de montrer que $\varphi$ atteint un minimum local en $a$. On peut donc trouver $\delta \strictsuperieur 0$ tel que : $$\varphi(a) \le \varphi(a + \Delta)$$ pour tout $\Delta \in \setR^n$ vérifiant $\norme{\Delta} \le \delta$. A l'inverse, si $\varphi$ atteint un minimum local en $a$, les conditions sur le gradient et la Hessienne seront remplies. \end{theoreme}
  • Supposons que les conditions sur le gradient et la hessienne soit remplies. Le développement d'ordre deux :

\[\varphi(a + \Delta) = \varphi(a) + \partial \varphi(a) \cdot \Delta + \unsur{2} \Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta + E(\Delta)\]

où \(E \sim \petito{\Delta^2}\) devient alors simplement :

\[\varphi(a + \Delta) = \varphi(a) + \unsur{2} \Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta + E(\Delta)\]

Choisissons \(h \in \setR^n\). Pour un \(\lambda \in \setR\) quelconque, posons \(\Delta = \lambda \cdot h\). On a alors :

\[\varphi(a + \Delta) = \varphi(a) + \frac{\lambda^2}{2} \cdot h^\dual \cdot \partial^2 \varphi(a) \cdot h + E(\lambda \cdot h)\]

Mais comme la Hessienne est définie positive et que \(E\) converge plus vite que \(\norme{\Delta}^2 = \lambda^2 \cdot \norme{h}^2\) vers \(0\), il suffit de choisir \(\lambda \strictsuperieur 0\) assez petit pour avoir :

\[\abs{E(\lambda \cdot h)} \le \frac{\lambda^2}{2} \cdot h^\dual \cdot \partial^2 \varphi(a) \cdot h\]

on a alors :

\[\unsur{2} \Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta + E(\Delta) \ge \unsur{2} \Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta - \abs{E(\Delta)} \ge 0\]

et :

\[\varphi(a + \Delta) = \varphi(a) + \unsur{2} \cdot \Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta + E(\Delta) \ge \varphi(a)\]

Nous avons donc bien un minimum local de \(\varphi\) en \(a\).

  • Inversément, si \(\varphi\) atteint un minimum local en \(a\), nous avons vu que la différentielle s'annulait. La jacobienne s'annule donc aussi et le développement d'ordre deux devient :

\[\varphi(a + \Delta) = \varphi(a) + \unsur{2} \Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta + E(\Delta) \ge \varphi(a)\]

La condition de minimum local nous dit donc que :

\[\Delta^\dual \cdot \partial^2 f(a) \cdot \Delta + E(\Delta) \ge 0\]

Choisissons à nouveau \(h \in \setR^n\) et posons \(\Delta = \lambda \cdot h\) pour un \(\lambda \in \setR\) quelconque. On a alors :

\[\frac{\lambda^2}{2} \cdot h^\dual \cdot \partial^2 f(a) \cdot h + E(\lambda \cdot h) \ge 0\]

Divisant par \(\lambda^2\), on obtient :

\[\unsur{2} \cdot h^\dual \cdot \partial^2 f(a) \cdot h + \frac{E(\lambda \cdot h)}{\lambda^2 \cdot \norme{h}^2} \cdot \norme{h}^2 \ge 0\]

Si on fait tendre \(\lambda \strictsuperieur 0\) vers \(0\), on arrive à la relation :

\[\unsur{2} \cdot h^\dual \cdot \partial^2 f(a) \cdot h \ge 0\]

Comme ce résultat est valable quel que soit \(h \in \setR^n\), on en conclut que la Hessienne est définie positive.

1.2 Maximum

Un raisonnement analogue nous montre que :

\begin{theoreme} Soit $\varphi \in \continue^2(\setR^n,\setR)$. Supposons que que $a \in \setR^n$ annule la Jacobienne (on parlera ici plutôt de gradient) : $$\partial \varphi(a) = 0$$ Supposons également que la Hessienne en $a$ soit définie négative, c'est-à-dire que : $$\Delta^\dual \cdot \partial^2 \varphi(a) \cdot \Delta \le 0$$ pour tout $\Delta \in \setR^n$ qui vérifie $\Delta \ne 0$. Si ces conditions sont remplies, $\varphi$ atteint un maximum local en $a$. On peut donc trouver $\delta \strictsuperieur 0$ tel que : $$\varphi(a) \ge \varphi(a + \Delta)$$ pour tout $\Delta \in \setR^n$ vérifiant $\norme{\Delta} \le \delta$. A l'inverse, si $\varphi$ atteint un maximum local en $a$, les conditions sur le gradient et la Hessienne seront remplies. \end{theoreme}

1.3 Equivalence

En pratique, on peut toujours se ramener à un problème de minimisation. En effet, maximiser une fonction revient à minimiser son opposé :

\[\arg\max_{x \in A} \varphi(x) = \arg\min_{x \in A} (-\varphi(x))\]

Nous nous restreindrons donc dans la suite aux problèmes de minimisation.

1.4 Dérivées ordinaires

Pour des fonctions \(f: \setR \mapsto \setR\), les conditions se simplifient en :

\( \OD{f}{t}(a) = 0 \\ \OOD{f}{t}(a) \ge 0 \)

pour un minimum et en :

\( \OD{f}{t}(a) = 0 \\ \OOD{f}{t}(a) \le 0 \)

pour un maximum.

1.5 Point de selle

Soit une fonction \(\lagrangien : \setR^n \times \setR^m \mapsto \setR\). Un point de selle \((\gamma,\lambda) \in \setR^n \times \setR^m\) est un couple d'élément qui minimise \(\lagrangien(x,y)\) par rapport à \(x\) et qui la maximise par rapport à \(y\). On aura alors :

\[\lagrangien(\gamma,y) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

1.6 Convexité

Soit l'ensemble :

\[L = \{ (s,t) \in \setR^2 : (s,t) \ge 0 \text{ et } s + t = 1 \}\]

Une fonction \(\varphi : \setR^n \mapsto \setR)\) est dite convexe si pour tout \(u, v \in \setR^n\) et \((s,t) \in L\), on a :

\[\varphi(s \cdot u + t \cdot v) \le s \cdot \varphi(u) + t \cdot \varphi(v)\]

1.6.1 Formulation équivalente

En substituant \(s = 1 - t\), on obtient :

\[\varphi(u + t \cdot (v - u)) \le \varphi(u) + t \cdot (\varphi(v) - \varphi(u))\]

ou :

\[\varphi(u + t \cdot (v - u)) - \varphi(u) \le t \cdot (\varphi(v) - \varphi(u))\]

1.6.2 Différentielle

Si \(\varphi\) est différentiable, on peut écrire par définition :

\[\differentielle{\varphi}{u}(t \cdot (v - u)) + \petito{t \cdot (v - u)} \le t \cdot (\varphi(v) - \varphi(u))\]

On peut bien entendu faire sortir le \(t\) par linéarité :

\[t \cdot \differentielle{\varphi}{u}(v - u) + \petito{t \cdot (v - u)} \le t \cdot (\varphi(v) - \varphi(u))\]

Il ne nous reste plus qu'à diviser par \(t\) et à faire tendre \(t \to 0\) pour annuler le terme d'erreur. On a alors la borne supérieure :

\[\differentielle{\varphi}{u}(v - u) \le \varphi(v) - \varphi(u)\]

En termes matriciels, cela se réécrit :

\[\partial \varphi(u) \cdot (v - u) \le \varphi(v) - \varphi(u)\]

1.6.3 Hessienne

Supposons à présent que la fonction convexe \(\varphi : \setR^n \mapsto \setR\) soit deux fois continûment différentiable. Soit \(u,v \in \setR^n\). Posons \(\Delta = v - u\). On considère le développement d'ordre deux :

\[\varphi(v) = \varphi(u) + \partial \varphi(u) \cdot \Delta + \unsur{2} \cdot \Delta^\dual \cdot \partial^2 \varphi(u) \cdot \Delta + \petito{\Delta^2}\]

La borne supérieure de la différentielle nous dit que :

\[\partial \varphi(u) \cdot \Delta \le \varphi(v) - \varphi(u)\]

On a donc :

\[\unsur{2} \cdot \Delta^\dual \cdot \partial^2 \varphi(u) \cdot \Delta + \petito{\Delta^2} = \varphi(v) - \varphi(u) - \partial \varphi(u) \cdot \Delta \ge 0\]

c'est-à-dire :

\[\Delta^\dual \cdot \partial^2 \varphi(u) \cdot \Delta + \petito{\Delta^2} \ge 0\]

Choisissons \(\delta \in \setR^n\) et \(t \in \setR\). Considérons le cas où \(v = u + t \cdot \delta\). On a alors \(\Delta = t \cdot \delta\) et :

\[t^2 \cdot \delta^\dual \cdot \partial^2 \varphi(u) \cdot \delta + \petito{t^2 \cdot \delta^2} \ge 0\]

Il suffit alors de diviser par \(t^2\) et de faire tendre \(t \to 0\) pour obtenir :

\[\delta^\dual \cdot \partial^2 \varphi(u) \cdot \delta \ge 0\]

Comme ce doit être valable pour tout \(\delta \in \setR^n\), la Hessienne est définie positive en tout \(u \in \setR^n\).

1.6.4 Globalité

Considérons le minimum global :

\[\lambda \in \arg\min_{x \in \setR^n} \varphi(x)\]

Supposons à présent que \(\varphi\) atteigne un minimum local en \(\gamma\). On sait que \(\varphi(\lambda) \le \varphi(\gamma)\) par définition de \(\lambda\). Mais comme \(\partial \varphi(\gamma) = 0\), on a aussi :

\[0 = \partial \varphi(\gamma) \cdot (\lambda - \gamma) \le \varphi(\lambda) - \varphi(\gamma)\]

On en déduit que :

\[\varphi(\gamma) \le \varphi(\lambda)\]

donc \(\varphi(\gamma) = \varphi(\lambda)\) est également un minimum global.

Attention toutefois, cela ne prouve aucunement que le point minimisant \(\varphi\) est unique.

1.6.5 Corollaire

Un corollaire important de ces résultats est que si \(\varphi\) est convexe et deux fois différentiable et que l'on trouve un point \(x\) tel que \(\partial \varphi(x) = 0\), ce point minimise localement \(\varphi\) car la Hessienne est définie positive. Le réel \(\varphi(x)\) est donc également le minimum global de \(\varphi\).

1.7 Convexité stricte

Une fonction \(\varphi : \setR^n \mapsto \setR)\) est dite strictement convexe si pour tout \(u, v \in \setR^n\) tels que \(u \ne v\) et tout \((s,t) \in L \setminus \{ (1,0),(0,1) \}\), on a :

\[\varphi(s \cdot u + t \cdot v) \strictinferieur s \cdot \varphi(u) + t \cdot \varphi(v)\]

1.7.1 Minima

Supposons qu'il existe deux \(u,v \in \setR^n\) distincts (\(u \ne v\)) tels que \(\varphi(u) = \varphi(v)\) soit le minimum global de \(\varphi\). On a alors :

\begin{align} \varphi(s \cdot u + t \cdot v) &\strictinferieur& s \cdot \varphi(u) + t \cdot \varphi(v) \\ &\strictinferieur& (s + t) \cdot \varphi(u) = \varphi(u) \end{align}

ce qui n'est pas possible puisque \(\varphi(u)\) est minimum global. Il existe donc au plus un seul \(u \in \setR^n\) minimisant globalement \(\varphi\) :

\[u = \arg\min_{x \in \setR^n} \varphi(x)\]

1.8 Concavité

Une fonction \(\psi : \setR^n \mapsto \setR\) est dite concave si pour tout \(u, v \in \setR^n\) et \((s,t) \in L\), on a :

\[\psi(s \cdot u + t \cdot v) \ge s \cdot \psi(u) + t \cdot \psi(v)\]

On voit que si \(\psi\) est concave, \(\varphi = -\psi\) est convexe. L'équivalence max-min nous montre alors que tout maximum local de \(\psi\) est également un maximum global.

1.9 Concavité stricte

Une fonction \(\psi : \setR^n \mapsto \setR\) est dite strictement concave si pour tout \(u, v \in \setR^n\) tels que \(u \ne v\) et tout \((s,t) \in L \setminus \{ (1,0),(0,1) \}\), on a :

\[\psi(s \cdot u + t \cdot v) \strictsuperieur s \cdot \psi(u) + t \cdot \psi(v)\]

On voit que si \(\psi\) est strictement concave, \(\varphi = -\psi\) est strictement convexe. L'équivalence max-min nous montre alors qu'il existe au plus un seul élément de \(\setR^n\) maximisant globalement \(\psi\).

1.10 Equation du second degré

Soit \(a,b,c \in \setR\) avec \(a \ne 0\). Soit le polynôme du second degré, ou polynôme de degré \(2\) défini par :

\[p(x) = a \cdot x^2 + b \cdot x + c\]

pour tout \(x \in \setR\). Nous allons chercher un éventuel extrema \(\gamma\) de ce polynôme. La dérivée première s'écrit :

\[\OD{p}{x}(x) = 2 \cdot a \cdot x + b\]

La condition :

\[\OD{p}{x}(\gamma) = 2 \cdot a \cdot \gamma + b = 0\]

nous donne :

\[\gamma = -\frac{b}{2a}\]

La dérivée seconde est donnée par :

\[\OOD{p}{x}(x) = 2 \cdot a\]

Si \(a \strictsuperieur 0\), la dérivée seconde est toujours positive et \(\gamma\) minimise localement \(p\). On vérifie que \(p\) est strictement convexe, et on en déduit que \(\gamma\) est l'unique réel qui minimise globalement \(p\).

Par contre, si \(a \strictinferieur 0\), la dérivée seconde est toujours négative et \(\gamma\) maximise localement \(p\). On vérifie que \(p\) est strictement concave, et on en déduit que \(\gamma\) est l'unique réel qui maximise globalement \(p\).

1.10.1 Racines

Intéressons-nous à présent à l'écart par rapport à \(\gamma\) :

\[\delta = x - \gamma = x + \frac{b}{2 a}\]

On a donc :

\[x = \gamma + \delta = - \frac{b}{2a} + \delta\]

et :

\[x^2 = (\gamma + \delta)^2 = \delta^2 - \frac{\delta \cdot b}{a} + \frac{b^2}{4 \cdot a^2}\]

En injectant ces relations dans la définition du polynôme, on obtient :

\begin{align} p(\gamma + \delta) &= a \cdot \delta^2 - b \cdot \delta + \frac{b^2}{4 \cdot a} + b \cdot \delta - \frac{b^2}{2 \cdot a} + c \\ &= a \cdot \delta^2 - \frac{b^2}{4 \cdot a} + c \end{align}

Cette expression nous permet d'obtenir les racines d'un polynôme du second degré. La condition :

\[p(\delta + \gamma) = 0\]

nous donne :

\[\delta^2 = \frac{b^2 - 4 \cdot a \cdot c}{4 \cdot a^2}\]

équation qui admet deux solution \(\delta_+, \delta_-\) :

\( \delta_+ = \frac{\sqrt{ b^2 - 4 \cdot a \cdot c }}{2 \cdot a} \\ \delta_- = - \frac{\sqrt{ b^2 - 4 \cdot a \cdot c }}{2 \cdot a} \)

Nous avons donc deux racines \(x_+,x_-\) :

\( x_+ = \frac{-b + \sqrt{b^2 - 4 \cdot a \cdot c}}{2 \cdot a} \\ \\ x_- = \frac{-b - \sqrt{b^2 - 4 \cdot a \cdot c}}{2 \cdot a} \)

telles que \(p(x_+) = p(x_-) = 0\).

1.11 Moindres-carrés

Soit la matrice \(A \in \matrice(\setR,m,n)\) et le vecteur matriciel \(b \in \matrice(\setR,m,1)\). On aimerait trouver le \(\xi \in \matrice(\setR^n,n,1)\) qui minimise la norme de l'erreur \(e\) définie par :

\[e(x) = A \cdot x - b\]

pour tout \(x \in \matrice(\setR^n,n,1)\). Comme la fonction \(\norme{x} \mapsto \norme{x}^2\) est strictement croissante sur \(\norme{x} \in \setR^+\), cela revient à minimiser :

\[\mathcal{E}(x) = \norme{x}^2 = e(x)^\dual \cdot e(x) = (A \cdot x - b)^\dual \cdot (A \cdot x - b)\]

En développant, on obtient :

\[\mathcal{E}(x) = x^\dual \cdot A^\dual \cdot A \cdot x - x^\dual \cdot A^\dual \cdot b - b^\dual \cdot A \cdot x + b^\dual \cdot b\]

Comme \((A^\dual \cdot A)^\dual = A^\dual \cdot A\) et \(x^\dual \cdot A^\dual \cdot b = b^\dual \cdot A^\dual \cdot x\), l'annulation de la dérivée nous donne :

\[\partial \mathcal{E}(\xi) = 2 A^\dual \cdot A \cdot \xi - 2 A^\dual \cdot b = 0\]

d'où l'on tire directement :

\[A^\dual \cdot A \cdot \xi = A^\dual \cdot b\]

Si \(A^\dual \cdot A\) est inversible, on en déduit que :

\[\xi = \left(A^\dual \cdot A\right)^{-1} \cdot A^\dual \cdot b\]

1.11.1 Orthogonalité

Considérons la partition en colonne \(A = [c_1 \ ... \ c_n]\). On a alors :

\( A^\dual =

\begin{Matrix}{c} c_1^\dual \\ \vdots \\ c_n^\dual \end{Matrix}

\)

La propriété :

\[A^\dual \cdot (A \cdot \xi - b) = A^\dual \cdot A \cdot \xi - A^\dual \cdot b = 0\]

nous dit donc que les colonnes de \(A\) sont orthogonales au vecteur \(r = A \cdot \xi - b\) :

\[\scalaire{c_i}{r} = c_i^\dual \cdot r = \ligne_i [ A^\dual \cdot (A \cdot \xi - b) ] = 0\]

1.11.2 Approximation de fonctions

On désire obtenir une approximation \(w\) d'une fonction \(u\) dont on connaît les valeurs aux points \(x_1,...,x_m\) en minimisant l'erreur :

\[\sum_{i=1}^{m} ( u(x_i) - w(x_i) )^2\]

On choisit alors les fonctions \(\varphi_1(x),...,\varphi_n(x)\), où \(n \le m\) et on pose :

\[w(x) = \sum_{i=1}^m a_i \cdot \varphi_i(x)\]

En utilisant les matrices :

\begin{align} A &= [\varphi_j(x_i)]_{i,j} \\ a &= [a_1 \ a_2 \ ... \ a_m]^T \\ b &= [u(x_1) \ u(x_2) \ ... \ u(x_n)]^T \end{align}

on peut réécrire le problème de minimisation comme suit :

\[a = \arg\min_z (A \cdot z - b)^\dual \cdot (A \cdot z - b)\]

La solution est donc :

\[a = (A^\dual \cdot A)^{-1} \cdot A^\dual \cdot b\]

2 Projections

2.1 Minimisation de l'écart

Soit un espace vectoriel \(E\) sur \(\setR\) et des vecteurs \(x,y \in E\), où \(x \ne 0\). La projection de \(y\) sur \(x\) est le vecteur :

\[p \in \combilin{x} = \{ \gamma \cdot x : \gamma \in \setR \}\]

qui minimise sur \(\combilin{x}\) la norme usuelle \(\norme{e} = \sqrt{ \scalaire{e}{e} }\) de l'écart \(e\) séparant \(y\) de \(p\). Afin de trouver le \(\lambda \in \setR\) minimisant cet écart, on utilise la fonction \(\mathcal{E} : \setR \mapsto \setR\) définie par :

\[\mathcal{E}(\gamma) = \scalaire{y - \gamma \cdot x}{y - \gamma \cdot x} = \scalaire{y}{y} - 2 \cdot \gamma \cdot \scalaire{x}{y} + \gamma^2 \cdot \scalaire{x}{x}\]

pour tout \(\gamma \in \setR\). Nous imposons l'annulation de la dérivée en un certain \(\gamma = \lambda\) qui minimise potentiellement l'écart :

\[\partial \mathcal{E}(\lambda) = - 2 \cdot \scalaire{x}{y} + 2 \cdot \lambda \cdot \scalaire{x}{x} = 0\]

ce qui nous donne :

\[\lambda = \frac{\scalaire{x}{y}}{\scalaire{x}{x}}\]

2.1.1 Produit scalaire complexe

Nous nous plaçons à présent dans le cas plus général où \(E\) est un espace vectoriel sur \(\setC\). Le \(\lambda\) défini plus haut devient donc un complexe. Nous allons déterminer s'il minimise la fonction \(\mathcal{E} : \setC \mapsto \setR\) définie par :

\[\mathcal{E}(\gamma) = \norme{y - \gamma \cdot x}^2\]

pour tout \(\gamma \in \setC\). Considérons le vecteur d'écart :

\[e = y - \lambda \cdot x\]

On voit qu'il vérifie la propriété :

\[\scalaire{x}{e} = \scalaire{x}{y} - \lambda \cdot \scalaire{x}{x} = 0\]

On a donc aussi :

\[\scalaire{e}{x} = \conjugue \scalaire{x}{e} = 0\]

On dit que le vecteur d'écart est orthogonal à \(x\). Soit l'écart \(\delta = \gamma - \lambda\). On a alors \(\gamma = \lambda + \delta\) et :

\[y - \gamma \cdot x = y - \lambda \cdot x - \delta \cdot x = e - \delta \cdot x\]

En utilisant les propriétés du produit scalaire, on en déduit :

\begin{align} \mathcal{E}(\gamma) &= \scalaire{e - \delta \cdot x}{e - \delta \cdot x} \\ &= \scalaire{e}{e} - \delta \cdot \scalaire{e}{x} - \conjaccent{\delta} \cdot \scalaire{x}{e} + \abs{\delta}^2 \cdot \scalaire{x}{x} \\ &= \scalaire{e}{e} + \abs{\delta}^2 \cdot \scalaire{x}{x} \end{align}

Comme \(\abs{\delta}^2 \cdot \scalaire{x}{x}\) est un réel \(\ge 0\), on a finalement :

\[\mathcal{E}(\gamma) \ge \scalaire{e}{e} = \mathcal{E}(\lambda)\]

Notre paramètre \(\lambda\) ainsi défini minimise donc bien \(\mathcal{E}\) sur \(\setC\). De plus, si \(\delta \ne 0\) on a \(\abs{\delta}^2 \strictsuperieur 0\) et \(\mathcal{E}(\gamma) \strictsuperieur \scalaire{e}{e}\), ce qui prouve que :

\[\lambda = \arg\min_{\gamma \in \setC} \mathcal{E}(\gamma)\]

est l'unique complexe à minimiser \(\mathcal{E}\). La racine carrée étant une fonction monotone strictement croissante sur \(\setR\), la norme \(\norme{e} = \sqrt{\mathcal{E}(\lambda)}\) est donc également minimisée et la projection s'écrit :

\[p = \lambda \cdot x = \frac{ \scalaire{x}{y} }{ \scalaire{x}{x} } \cdot x\]

2.2 Théorème de Pythagore

Calculons à présent la norme de \(y\) en partant de la relation :

\[y = p + e\]

On déduit de la propriété d'orthogonalité que :

\[\scalaire{p}{e} = \lambda \cdot \scalaire{x}{e} = 0\]

On peut donc appliquer le théorème de pythagore, qui nous dit que :

\[\norme{y}^2 = \norme{p + e}^2 = \norme{p}^2 + \norme{e}^2\]

2.3 Carré de la distance

Si :

\[D = \min_{\gamma \in \setC} \norme{y - \gamma \cdot x}\]

on a donc :

\[D^2 = \norme{y - \lambda \cdot x}^2 = \norme{e}^2 = \norme{y}^2 - \norme{p}^2\]

et finalement :

\[D^2 = \norme{y}^2 - \abs{\lambda}^2 \cdot \norme{x}^2\]

2.4 Cauchy-Schwartz

Par positivité du produit scalaire, on a bien évidemment :

\[\norme{e}^2 = \scalaire{e}{e} \ge 0\]

Le théorème de Pythagore implique donc que :

\[\scalaire{p}{p} = \norme{p}^2 \le \norme{y}^2 = \scalaire{y}{y}\]

En substituant \(p = \lambda \cdot x\), on obtient :

\[\conjaccent \lambda \cdot \lambda \cdot \scalaire{x}{x} \le \scalaire{y}{y}\]

Mais comme :

\[\conjaccent{\lambda} = \conjugue \frac{ \scalaire{x}{y} }{ \scalaire{x}{x} } = \frac{ \scalaire{y}{x} }{ \scalaire{x}{x} }\]

on a :

\[\frac{ \scalaire{y}{x} }{ \scalaire{x}{x} } \cdot \frac{ \scalaire{x}{y} }{ \scalaire{x}{x} } \cdot \scalaire{x}{x} \le \scalaire{y}{y}\]

En simplifiant et en multipliant par la norme carrée de \(x\), on a finalement :

\[\scalaire{y}{x} \cdot \scalaire{x}{y} \le \scalaire{x}{x} \cdot \scalaire{y}{y}\]

relation dont la racine nous donne l'inégalité de Cauchy-Schwartz :

\[\abs{ \scalaire{x}{y} } \le \norme{x} \cdot \norme{y}\]

2.5 Propriétés extrémales

L'égalité :

\[\norme{p}^2 = \norme{y}^2\]

n'est atteinte que lorsque \(\norme{e}^2 = 0\), c'est-à-dire \(e = 0\) et \(y = \lambda \cdot x\) pour un certain \(\lambda \in \setC\). Ce constat nous amène aux problèmes d'optimisations suivants. Soit un vecteur \(c \ne 0\) fixé et :

\[d = \norme{c} = \sqrt{ \scalaire{c}{c} }\]

On cherche à maximiser ou à minimiser :

\[\varphi(x) = \scalaire{c}{x}\]

sur l'ensemble \(B = \boule(0,r) = \{ x : \norme{x} \le r \}\). L'inégalité de Cauchy-Schwartz nous dit que :

\[- d \cdot r \le - \norme{c} \cdot \norme{x} \le \scalaire{c}{x} \le \norme{c} \cdot \norme{x} \le d \cdot r\]

Nous allons chercher nos solutions sous la forme \(x = \alpha \cdot c\), pour un certain \(\alpha \in \setC\). On a alors :

\[\norme{\alpha \cdot c} = \abs{\alpha} \cdot \norme{c} = \abs{\alpha} \cdot d \le r\]

et donc \(\abs{\alpha} \le r / d\). Si on choisit \(\alpha = r / d\), on a :

\[\scalaire{c}{x} = \frac{r}{d} \cdot \scalaire{c}{c} = \frac{r}{d} \cdot d^2 = d \cdot r\]

La borne supérieure est atteinte. La fonction \(\varphi\) est donc maximisée :

\[\eta = \frac{r}{d} \cdot c \in \arg\max_{x \in B} \scalaire{c}{x}\]

Si on choisit \(\alpha = - r / d\), on a :

\[\scalaire{c}{x} = - \frac{r}{d} \cdot \scalaire{c}{c} = - d \cdot r\]

La borne inférieure est atteinte. La fonction \(\varphi\) est donc minimisée :

\[\theta = - \frac{r}{d} \cdot c \in \arg\min_{x \in B} \scalaire{c}{x}\]

2.6 Sous-espace vectoriel

Soit l'espace vectoriel \(E\) sur \(\setR\) et un sous-espace vectoriel \(U \subseteq E\) possédant une base orthonormée \((u_1,...,u_n)\). La projection d'un vecteur quelconque \(z \in E\) sur \(U\) est le vecteur \(p \in U\) qui minimise la norme de l'écart entre \(z\) et \(p\). On cherche donc le \(\lambda = (\lambda_1,...,\lambda_n) \in \setR^n\) qui minimise la fonction \(\mathcal{E} : \setR^n \mapsto \setR\) définie par :

\[\mathcal{E}(\gamma) = \norme{z - \sum_{i = 1}^n \gamma_i \cdot u_i}^2\]

pour tout \(\gamma = (\gamma_1,...,\gamma_n) \in \setR^n\). En utilisant \(\scalaire{u_i}{u_j} = \indicatrice_{ij}\), on obtient :

\begin{align} \mathcal{E}(\gamma) &= \scalaire{z}{z} - 2 \sum_i \gamma_i \cdot \scalaire{u_i}{z} + \sum_{i,j} \gamma_i \cdot \gamma_j \cdot \scalaire{u_i}{u_j} \\ &= \scalaire{z}{z} - 2 \sum_i \gamma_i \cdot \scalaire{u_i}{z} + \sum_i \gamma_i^2 \end{align}

Imposant \(\partial_k \mathcal{E}(\lambda_1,...,\lambda_n) = 0\), on obtient les \(n\) équations :

\[-2 \lambda_k \cdot \scalaire{u_k}{z} + 2 \lambda_k = 0\]

On en déduit que le choix :

\[\lambda = (\lambda_1,...,\lambda_n) = (\scalaire{u_1}{z},...,\scalaire{u_n}{z})\]

minimise potentiellement \(\mathcal{E}\). Notre projection potentielle de \(z\) sur \(U\) est donc donnée par :

\[p = \sum_i \scalaire{u_i}{z} \cdot u_i\]

2.6.1 Produit scalaire complexe

Nous nous plaçons à présent dans le cas plus général où \(E\) est un espace vectoriel sur \(\setC\). Le \(\lambda\) défini plus haut devient donc un élément de \(\setC^n\). Nous allons déterminer s'il minimise la fonction \(\mathcal{E} : \setC^n \mapsto \setR\) définie par :

\[\mathcal{E}(\gamma) = \norme{z - \sum_{i = 1}^n \gamma_i \cdot u_i}^2\]

pour tout \(\gamma = (\gamma_1,...,\gamma_n) \in \setC^n\). Choisissons \(x \in U\). On a alors :

\[x = \sum_i x_i \cdot u_i\]

où \(x_i = \scalaire{u_i}{z}\). Considérons le vecteur d'écart :

\[e = z - p\]

On a alors :

\begin{align} \scalaire{x}{e} &= \sum_i \conjaccent{x_i} \cdot \scalaire{u_i}{z - p} \\ &= \sum_i \conjaccent{x_i} \cdot \scalaire{u_i}{z} - \sum_{i,j} \conjaccent{x_i} \cdot \scalaire{u_i}{u_j} \cdot \lambda_j \\ &= \sum_i \scalaire{x}{u_i} \cdot \scalaire{u_i}{z} - \sum_i \scalaire{x}{u_i} \cdot \scalaire{u_i}{z} = 0 \end{align}

Le vecteur d'écart est donc orthogonal à tous les \(x \in U\). On a également :

\[\scalaire{e}{x} = \conjugue \scalaire{x}{e} = 0\]

Soit l'écart \(\delta = \gamma - \lambda\). On a alors \(\gamma = \lambda + \delta\). Posons :

\( g = \sum_i \gamma_i \cdot u_i \\ p = \sum_i \lambda_i \cdot u_i \\ \Delta = \sum_i \delta_i \cdot u_i \)

On a alors \(z - g = z - p - \Delta = e - \Delta\) et :

\begin{align} \mathcal{E}(\gamma) &= \scalaire{e - \Delta}{e - \Delta} \\ &= \scalaire{e}{e} - \scalaire{e}{\Delta} - \scalaire{\Delta}{e} + \scalaire{\Delta}{\Delta} \end{align}

Comme \(\Delta \in U\), ses produits scalaires avec \(e\) s'annulent par orthogonalité et on a finalement :

\[\mathcal{E}(\gamma) = \scalaire{e}{e} + \scalaire{\Delta}{\Delta} \ge \scalaire{e}{e} = \mathcal{E}(\lambda)\]

Les scalaires \(\lambda_k\) minimisent donc bien la norme de l'écart sur \(U\).

2.6.2 Théorème de Pythagore

On a \(z = p + e\). Comme \(p\) est un vecteur de \(U\), on a \(\scalaire{p}{e} = \scalaire{e}{p} = 0\). Le théorème de Pythagore est donc applicable :

\[\norme{z}^2 = \norme{p}^2 + \norme{e}^2\]

2.6.3 Carré de la distance

Soit :

\[D = \min \{ \norme{z - v} : v \in U \}\]

Par orthonormalité, on a :

\[\norme{p}^2 = \sum_{i,j} \conjugue(\scalaire{u_i}{z}) \cdot \scalaire{u_j}{z} \cdot \scalaire{u_i}{u_j} = \sum_i \abs{\scalaire{u_i}{z}}^2\]

et donc :

\[D^2 = \norme{z}^2 - \norme{p}^2 = \norme{z}^2 - \sum_i \abs{\scalaire{u_i}{z}}^2\]

2.7 Tenseur de projection

On peut réécrire la projection de \(z\) sur \(U\) sous la forme :

\[p = \sum_i u_i \cdot \scalaire{u_i}{z}\]

Cette expression ressemble à la contraction d'ordre \(1\) d'un tenseur d'ordre \(2\). Effectivement, si on pose :

\[\mathcal{P} = \sum_i u_i \otimes u_i\]

on a alors :

\[p = \mathcal{P} \cdot z = \contraction{\mathcal{P} }{1}{z}\]

2.7.1 Identité locale

Pour tout \(y \in U\), on a :

\[y = \sum_i \scalaire{u_i}{y} \cdot u_i\]

et :

\[\mathcal{P} \cdot y = \sum_i u_i \cdot \scalaire{u_i}{y}\]

Ces deux expressions étant identiques, on a \(\mathcal{P} \cdot y = y\). Le tenseur de projection correspond donc localement (sur \(U\)) au tenseur identité.

2.7.2 Invariance

Pour tout \(z \in E\), on a \(y = \mathcal{P} \cdot z \in U\). On en conclut que :

\[\mathcal{P} \cdot z = y = \mathcal{P} \cdot y = \mathcal{P} \cdot (\mathcal{P} \cdot z)\]

Donc \(\mathcal{P} = \mathcal{P} \cdot \mathcal{P}\).

2.7.3 Complémentaire

Soit \((u_1,...,u_n)\) une base orthonormée de \(E\). On voit que le tenseur identité :

\[\tenseuridentite = \sum_{i = 1}^n u_i \otimes u_i\]

est le tenseur de projection de \(E\) dans lui-même. On considère le tenseur de projection sur \(\combilin{u_1,...,u_m}\), où \(m \le n\) :

\[\mathcal{P} = \sum_{i = 1}^m u_i \otimes u_i\]

Le tenseur complémentaire est défini par :

\[\mathcal{Q} = \tenseuridentite - \mathcal{P} = \sum_{i = 1}^n u_i \otimes u_i - \sum_{i = 1}^m u_i \otimes u_i = \sum_{i = m + 1}^n u_i \otimes u_i\]

Il s'agit donc d'un tenseur de projection sur l'espace complémentaire \(\combilin{u_{m + 1},...,u_n}\). Il est lié à l'écart de projection car \(e = z - p = \mathcal{Q} \cdot z\). On remarque l'orthogonalité :

\[\mathcal{Q} \cdot \mathcal{P} = (\tenseuridentite - \mathcal{P}) \cdot \mathcal{P} = \mathcal{P} - \mathcal{P} \cdot \mathcal{P} = 0\]

De même :

\[\mathcal{P} \cdot \mathcal{Q} = \mathcal{P} \cdot \mathcal{P} - \mathcal{P} = 0\]

On a aussi sans surprise :

\[\mathcal{Q} \cdot \mathcal{Q} = \mathcal{Q} - \mathcal{Q} \cdot \mathcal{P} = \mathcal{Q}\]

2.8 Gram-Schmidt

Nous allons construire une suite de vecteurs orthonormaux \((u_1,u_2,...u_n)\) à partir d'une suite \((a_1,a_2,...,a_n)\) de vecteurs linéairement indépendants de \(E\). L'indépendance linéaire nous garantit que \(a_1 \ne 0\). On peut donc normaliser pour obtenir le premier vecteur de la série :

\[u_1 = \frac{a_1}{ \norme{a_1} }\]

On a alors :

\[\scalaire{u_1}{u_1} = \frac{ \scalaire{a_1}{a_1} }{ \norme{a_1}^2 } = \frac{ \scalaire{a_1}{a_1} }{ \scalaire{a_1}{a_1} } = 1\]

Nous projetons \(a_2\) sur \(u_1\) en utilisant le tenseur \(\mathcal{P}_1 = u_1 \otimes u_1\) et nous évaluons l'écart :

\[e_2 = (\tenseuridentite - \mathcal{P}_1) \cdot a_2 = a_2 - u_1 \cdot \scalaire{u_1}{a_2}\]

Les propriétés d'orthogonalité de l'écart nous assurent alors que \(\scalaire{u_1}{e_2} = 0\). L'indépendance linéaire nous garantit que \(e_2 \ne 0\). On peut donc normaliser en utilisant \(u_2 = e_2 / \norme{e_2}\). On a alors clairement \(\scalaire{u_2}{u_2} = 1\) et \(\scalaire{u_1}{u_2} = 0\).

Supposons à présent avoir trouvé la suite orthonormée \((u_1,u_2,...,u_k)\), où \(k \le n - 1\). Nous projetons \(a_{k + 1}\) sur l'espace vectoriel \(U_k = \combilin{u_1,u_2,...,u_k}\) en utilisant le tenseur :

\[\mathcal{P}_k = \sum_{i = 1}^k u_i \otimes u_i\]

et nous évaluons l'écart :

\[e_{k + 1} = (\tenseuridentite - \mathcal{P}_k) \cdot a_{k + 1} = a_{k + 1} - \sum_{i = 1}^k u_i \cdot \scalaire{u_i}{a_{k + 1} }\]

Les propriétés d'orthogonalité de l'écart nous assurent alors que \(\scalaire{u_j}{e_{k + 1} } = 0\) pour tout \(j \in \{1,2,...,k\}\). L'indépendance linéaire nous garantit que \(e_{k + 1} \ne 0\). On peut donc normaliser en utilisant :

\[u_{k + 1} = \frac{e_{k + 1} }{ \norme{ e_{k + 1} } }\]

On a alors clairement \(\scalaire{u_j }{u_{k + 1} } = \indicatrice_{j, k + 1}\).

Nous disposons donc à la fin du processus d'une suite de vecteurs \((u_1,u_2,...,u_n)\) orthonormée :

\[\scalaire{u_i}{u_j} = \indicatrice_{ij}\]

Ce procédé est appelé processus d'orthogonalisation de Gram-Schmidt.

2.8.1 Remarque

Dans le cas où l'indépendance linéaire n'est pas garantie, il est toujours possible d'adapter l'algorithme en enlevant dynamiquement de la liste des \(a_k\) les vecteurs donnant un écart de projection nul. On se retrouve alors à la fin du processus avec une suite orthonormée \((u_1,...,u_m)\), où \(m \le n\).

2.9 Représentation matricielle

Soient \(u_1,u_2,...,u_m \in \matrice(\corps,n,1)\) des vecteurs matriciels orthonormés pour le produit scalaire usuel :

\[u_i^\dual \cdot u_j = \indicatrice_{ij}\]

La matrice de projection associée au tenseur de projection sur \(U = \combilin{u_1,...,u_m}\) s'écrit :

\[P = \sum_{k = 1}^m u_k \otimes u_k = \sum_{k = 1}^m u_k \cdot u_k^\dual\]

Il s'agit donc d'une matrice de taille \((n,n)\). Elle permet de projeter tout vecteur matriciel \(z \in \matrice(\corps,n,1)\) sur \(U\) :

\[P \cdot z = \sum_{k = 1}^m u_k \cdot u_k^\dual \cdot z = \sum_{k = 1}^m u_k \cdot \scalaire{u_k}{z}\]

2.10 Factorisation

En terme de composantes, si \(u_k = ( u_{kj} )_j\) et si \(P = ( p_{ij} )_{i,j}\), on a :

\[p_{ij} = \sum_{k = 1}^m u_{ki} \cdot \conjaccent{u}_{kj}\]

expression qui ressemble furieusement à un produit matriciel. Soit la matrice \(U\) de taille \((n,m)\) rassemblant les \(m\) vecteurs \(u_k\) :

\[U = [u_1 \ u_2 \ \hdots \ u_m]\]

On a alors :

\begin{align} \composante_{ik} U &= u_{ki} \\ \composante_{kj} U^\dual &= \conjugue \composante_{jk} U = \conjaccent{u}_{kj} \end{align}

Le produit ci-dessus peut donc s'écrire :

\[p_{ij} = \sum_{k = 1}^m b_{ik} \cdot c_{kj}\]

où \(b_{ik} = \composante_{ik} U\) et \(c_{kj} = \composante_{kj} U^\dual\). On a donc finalement :

\[P = U \cdot U^\dual\]

2.10.1 Propriétés

Comme les \(u_k\) sont orthonormaux, on a :

\[\composante_{ij} (U^\dual \cdot U) = u_i^\dual \cdot u_j = \scalaire{u_i}{u_j} = \indicatrice_{ij}\]

On a donc \(U^\dual \cdot U = I\), la matrice identité de taille \((m,m)\). On a également, comme attendu :

\[P^2 = U \cdot U^\dual \cdot U \cdot U^\dual = U \cdot I \cdot U^\dual = U \cdot U^\dual = P\]

Si on pose \(Q = I - P\), on a aussi :

\[P \cdot Q = Q \cdot P = P - P^2 = 0\]

2.10.2 Cas particulier

Les \(m\) vecteurs \(u_i\) étant linéairement indépendants dans \(\corps^n\) qui est de dimension \(n\), on doit forcément avoir \(m \le n\). Dans le cas où \(m = n\), on a de plus \(U^\dual = U^{-1}\) et :

\[\sum_{i = 1}^n u_i \otimes u_i = P = U \cdot U^{-1} = I\]

2.11 Vecteurs $A$-orthogonaux

Soit une matrice de produit scalaire \(A \in \matrice(\corps,n,n)\). On peut utiliser le procédé de Gram-Schmidt pour construire une base de vecteurs orthogonaux pour le produit scalaire :

\[\scalaire{x}{y} = x^\dual \cdot A \cdot y\]

On part d'une suite \((a_1,a_2,...,a_n)\) de vecteurs matriciels linéairement indépendants de \(\corps^n\) (typiquement la base canonique). On commence par normaliser \(a_1\) :

\[u_1 = \frac{a_1}{ \sqrt{a_1^\dual \cdot A \cdot a_1} }\]

et on construit étape après étape la suite des \(u_i\). Supposons être arrivé à la suite \((u_1,u_2,...,u_k)\) vérifiant \(\scalaire{u_i}{u_j} = u_i^\dual \cdot A \cdot u_j = \indicatrice_{ij}\), où \(k \le n - 1\). Nous projetons \(a_{k + 1}\) sur l'espace vectoriel \(\combilin{u_1,u_2,...,u_k}\) et nous évaluons l'écart :

\begin{align} e_{k + 1} &= a_{k + 1} - \sum_{i = 1}^k u_i \cdot \scalaire{u_i}{ a_{k + 1} } \\ &= a_{k + 1} - \sum_{i = 1}^k u_i \cdot u_i^\dual \cdot A \cdot a_{k + 1} \end{align}

Ensuite, nous normalisons le résultat :

\[u_{k + 1} = \frac{e_{k + 1} }{ \sqrt{e_{k + 1}^\dual \cdot A \cdot e_{k + 1} } }\]

Nous disposons donc à la fin du processus d'une suite de vecteurs \((u_1,u_2,...,u_n)\) orthonormée :

\[\scalaire{u_i}{u_j} = u_i^\dual \cdot A \cdot u_j = \indicatrice_{ij}\]

On dit que la suite des \(u_i\) est $A$-orthonormée. Si on définit la famille de matrices :

\[U_m = [u_1 \ u_2 \ ... \ u_m]\]

pour tout \(m \le n\), on peut réecrire l'orthogonalité comme suit :

\[U_m^\dual \cdot A \cdot U_m = I_m\]

On note aussi \(U = U_n\).

2.11.1 Complément orthogonal

Si les vecteurs orthonormaux \((u_1,...,u_p)\), où \(p \le n\), sont donnés, on peut simplement commencer le processus à \(k = p\) pour complèter la suite de vecteurs jusqu'à \(k = n\). On obtient alors la suite orthonormée \((u_1,...,u_p,u_{p + 1},...,u_n)\). On dit que \((u_{p + 1},...,u_n)\) est le complément orthogonal de \((u_1,...,u_p)\).

2.11.2 Orthogonalité usuelle

Dans le cas où l'on choisit \(A = I\), cette méthode offre un moyen d'obtenir (ou de compléter) une suite de vecteurs \(u_i\) tels que \(u_i^\dual \cdot u_j = \indicatrice_{ij}\) et des matrices \(U_m\) correspondantes telles que \(U_m^\dual \cdot U_m = I_m\). Comme \(U = U_n\) est carrée, on a de plus :

\[U^{-1} = U^\dual\]

2.11.3 Systèmes linéaires

Lorsqu'on dispose de \(n\) vecteurs $A$-orthonormés, il est facile de résoudre le système linéaire \(A \cdot x = y\). Les \(u_i\) forment alors une base de \(\corps^n\) et on peut trouver des scalaires \(x_i \in \corps\) tels que :

\[x = \sum_{i = 1}^n x_i \cdot u_i\]

En prenant le produit scalaire de \(x\) avec \(u_k\), on obtient :

\[u_k^\dual \cdot A \cdot x = \sum_{i = 1}^n (u_k^\dual \cdot A \cdot u_i) \cdot x_i = x_k\]

On voit donc apparaître une expression analogue à celle d'une projection usuelle :

\[x = \sum_{i = 1}^n u_i \cdot (u_i^\dual \cdot A \cdot x) = \sum_{i = 1}^n u_i \cdot u_i^\dual \cdot y\]

Attention, analogue n'est pas identique, les \(u_i\) ne sont en général pas orthonormés pour le produit scalaire usuel.

3 Algorithmes d'optimisation libre

3.1 Introduction

Nous allons présenter des algorithmes permettant de résoudre approximativement des problèmes de minimisation d'une fonction \(\varphi\) sur \(\setR^n\). Ces algorithmes partent d'un point initial \(x_0 \in \Omega\) et itèrent schématiquement comme suit :

\[x_{k + 1} = I(x_k) = x_k + p_k\]

pour un certain \(p_k \in \setR^n\). On espère bien entendu que la suite converge et que :

\[x_N \approx \lim_{k \to \infty} x_k = \arg\min_{x \in \Omega} \varphi(x)\]

pour \(N\) assez grand. Nous adoptons les notations :

\[J = (\partial \varphi)^\dual\]

pour le gradient, de taille \((n,1)\), et :

\[H = \partial^2 \varphi\]

pour la hessienne, de taille \((n,n)\). On note également :

\[\Phi_k = \Phi(x_k)\]

pour toute fonction \(\Phi\) (par exemple, \(\Phi \in \{\varphi,J,H\}\)).

3.2 Minimum dans une direction

Soit l'itération :

\[x_{k+1} = x_k - \alpha_k \cdot p_k\]

où \(\alpha_k \in \setR\) et \(p_k \in \setR^n\). On choisit généralement le paramètre \(\alpha_k\) de façon à minimiser le développement d'ordre deux :

\[\varphi_{k + 1} \approx \varphi_k - \alpha_k \cdot J_k^\dual \cdot p_k + \frac{\alpha_k^2}{2} \cdot p_k^\dual \cdot H_k \cdot p_k\]

En imposant l'annulation de la dérivée de ce développement par rapport à \(\alpha_k\), on en déduit que :

\[- J_k^\dual \cdot p_k + \alpha_k \cdot p_k^\dual \cdot H_k \cdot p_k = 0\]

La valeur optimale de \(\alpha_k\) s'écrit :

\[\alpha_k = \frac{J_k^\dual \cdot p_k}{p_k^\dual \cdot H_k \cdot p_k}\]

3.3 Méthode de la plus grande descente

La méthode de la plus grande pente consiste à partir à chaque itération du point \(x^{(k)}\) et à suivre la direction \(\delta_k\) où \(\varphi\) descend le plus rapidement dans le voisinage immédiat. En première approximation, si :

\[x_{k + 1} = x_k + \alpha_k \cdot \delta_k\]

pour un certain \(\alpha_k \in \setR\), on a :

\[\varphi_{k+1} \approx \varphi_k + \alpha_k \cdot J_k^\dual \cdot \delta_k\]

Nous choisissons le vecteur \(\delta_k\) qui minimise \(J_k^\dual \cdot \delta_k = \scalaire{J_k}{\delta_k}\) sur \(\boule(0,\norme{J_k})\), c'est-à-dire :

\[\delta_k = - J_k\]

On a alors :

\[x_{k + 1} = x_k - \alpha_k \cdot J_k\]

La valeur optimale de \(\alpha_k\) s'écrit donc :

\[\alpha_k = \frac{J_k^\dual \cdot J_k}{J_k^\dual \cdot H_k \cdot J_k}\]

3.4 Newton

Il s'agit ici d'optimiser le pas \(s_k\) :

\[x_{k + 1} = x_k + s_k\]

pour minimiser le développement :

\[\varphi_{k+1} \approx \varphi_k + J_k^\dual \cdot s_k + \unsur{2} \cdot s_k^\dual \cdot H_k \cdot s_k\]

Mais comme \(H = H^\dual\), l'annulation du gradient par rappord à \(s_k\) nous donne :

\[J_k + H_k \cdot s_k \approx 0\]

On en déduit la valeur optimale :

\[s_k = - H_k^{-1} \cdot J_k\]

3.5 Gradients conjugués

Soit l'itération :

\[x_{k + 1} = x_k - \alpha_k \cdot p_k\]

où \(\alpha_k \in \setR\) et \(p_k \in \setR^n\). On a comme d'habitude :

\[\alpha_k = \frac{J_k^\dual \cdot p_k}{p_k^\dual \cdot H_k \cdot p_k}\]

Lorsque \(k = 0\), on prend le gradient comme direction :

\[p_0 = J_0\]

Pour \(k \ge 1\), on choisit \(p_k\) comme combinaison linéaire du gradient \(J_k\) et du pas précédent \(p_{k - 1}\) :

\[p_k = J_k - \beta_k \cdot p_{k-1}\]

où \(\beta_k \in \setR\). L'idée des gradients conjugué est de construire une suite de \(p_k\) orthogonaux entre-eux afin de minimiser la fonction dans toutes les directions. Au bout de \(n\) itérations, on espère avoir construit une base de \(\setR^n\) et être très proche du minimum global. En fait, nous n'allons pas vérifier que toutes les directions sont orthogonales, mais seulement que deux directions successives le sont. On demande donc l'orthogonalité au sens du produit scalaire défini par \(H\) :

\[p_k^\dual \cdot H_k \cdot p_{k - 1} = J_k^\dual \cdot H_k \cdot p_{k - 1} - \beta_k \cdot p_{k - 1}^\dual \cdot H_k \cdot p_{k - 1} = 0\]

On en déduit la valeur de \(\beta_k\) :

\[\beta_k = \frac{J_k^\dual \cdot H_k \cdot p_{k - 1}}{p_{k - 1}^\dual \cdot H_k \cdot p_{k - 1}}\]

Nous allons à présent obtenir une valeur approximative de \(\beta_k\) en fonction des variations du gradient. Le développement d'ordre un de \(J\) s'écrit :

\[J_k - J_{k - 1} \approx H_k \cdot (x_k - x_{k - 1}) = - \alpha_k \cdot H_k \cdot p_{k - 1}\]

On en déduit que :

\[\beta_k \approx \frac{J_k^\dual \cdot (J_k - J_{k - 1})}{p_{k - 1}^\dual \cdot (J_k - J_{k - 1})}\]

3.6 Moindres carrés

Soit la fonction \(f : \setR^n \mapsto \setR^m\). On cherce à minimiser la fonction \(\varphi = f^\dual \cdot f / 2\). Le problème de minimisation s'écrit alors :

\[\arg\min_x \unsur{2} f(x)^\dual \cdot f(x)\]

Dans ce cas, si on définit :

\[D = \partial f\]

le gradient s'écrit :

\[J = D^\dual \cdot f\]

Si on suppose que les dérivées secondes de \(f\) sont négligeables par rapport aux dérivées premières, on a :

\[H \approx D^\dual \cdot D\]

La méthode de Newton devient dans ce cas :

\[x_{k+1} = x_k + s_k\]

avec :

\[s_k = -[D_k^\dual \cdot D_k]^{-1} \cdot D_k^\dual \cdot f_k\]

3.6.1 Zéros

Si \(S = \noyau f \ne \emptyset\), soit \(\gamma \in S\). On a alors :

\[0 \le \min \unsur{2} f(x)^\dual \cdot f(x) \le \unsur{2} f(\gamma)^\dual \cdot f(\gamma) = 0\]

On en déduit que tout \(x \in \setR^n\) minimisant \(\varphi\) vérifiera \(f(x) = 0\). La méthode de minimisation nous fournit donc une approximation d'un tel \(x\).

3.7 Levenberg-Marquardt

C'est une variante de la méthode des moindres carrés, utile dans les cas où \(D_k^\dual \cdot D_k\) est numériquement proche d'une matrice non inversible. On ajoute alors la matrice identité multipliée par un scalaire \(\lambda\) sur la diagonale :

\[s_k = -[D_k^\dual \cdot D_k+ \lambda_k \cdot I]^{-1} \cdot D_k^\dual \cdot f_k\]

4 Solveurs itératifs

4.1 Dépendances

  • Chapitre \ref{chap:matrice} : Les matrices

4.2 Méthodes itératives

Il s'agit de résoudre itérativement (et approximativement) en \(x\) un système linéaire \(A \cdot x = b\), où \(A\) est une matrice et \(b\) un vecteur. L'itération générique s'écrit :

\[x_{k + 1} = I(x_k)\]

et on espère que la suite des \(x_k \in \setR^n\) converge vers la solution. On initialise en général les algorithmes avec \(x_0 = 0\).

4.3 Résolution par minimisation

Soit une matrice \(H\) de taille \((n,n)\) hermitienne (\(H = H^\dual\)) et définie positive :

\[x^\dual \cdot H \cdot x \ge 0\]

pour tout \(x \in \setR^n\). Considérons la fonction définie par :

\[\varphi(x) = \unsur{2} x^\dual \cdot H \cdot x - x^\dual \cdot b\]

Si un certain \(x\) minimise \(\varphi\) sur \(\setR^n\), on doit avoir :

\[\partial \varphi(x) = H \cdot x - b = 0\]

ce qui revient à résoudre le système linéaire :

\[H \cdot x = b\]

Comme \(\partial^2 \varphi = H\) est définie positive, résoudre le système \(H \cdot x = b\) en \(x\) revient donc à minimiser \(\varphi\) sur \(\setR^n\). On peut obtenir une approximation de la solution en utilisant la méthode de la plus grande descente, le gradient étant donné par :

\[J = (\partial \varphi)^\dual = H \cdot x - b\]

On a donc des itérations \(k\) de la forme :

\[x_{k + 1} = x_k + \alpha_k \cdot (b - H \cdot x)\]

pour un \(\alpha_k \in \setR\) bien choisi. On peut aussi utiliser un autre algorithme, comme les gradients conjugués par exemple.

4.3.1 Résidu

On remarque que la direction de la descente est donné par le résidu :

\[-J = b - H \cdot x\]

4.3.2 Newton

On pourrait bien entendu résoudre par la méthode de Newton, mais cela reviendrait alors à inverser la matrice \(H\) directement, ce que l'on cherche précisément à éviter ici.

4.3.3 Généralisation

Soit la matrice \(A\) de taille \((N,n)\), où \(N \ge n\), et \(y \in \setR^N\). Considérons le système général :

\[A \cdot x = y\]

à résoudre en \(x \in \setR^n\). Si on multiplie à gauche par \(A^\dual\), on obtient :

\[A^\dual \cdot A \cdot x = A^\dual \cdot y\]

Posons :

\( H = A^\dual \cdot A \\ b = A^\dual \cdot y \)

On est donc amenés à résoudre le système :

\[H \cdot x = b\]

où \(H\) est clairement hermitienne et définie positive puisque :

\[x^\dual \cdot (A^\dual \cdot A) \cdot x = (A \cdot x)^\dual \cdot (A \cdot x) \ge 0\]

Cette technique présente deux avantages. Premièrement, si \(H\) est inversible, la solution :

\[x = H^{-1} \cdot b = (A^\dual \cdot A)^{-1} \cdot A^\dual \cdot y\]

minimise la norme \(\norme{A \cdot x - y}\) même si la solution de \(A \cdot x = y\) n'existe pas. Il est même possible d'utiliser cette méthode avec des matrices \(A\) strictement hautes. Ensuite, les propriétés de \(H\) nous disent qu'une solution du système minimise la fonction \(\varphi\) associée. Il est donc possible de se ramener au problème de minimisation :

\[x \in \arg\min_{z \in \setR^n} \left[ \unsur{2} z^\dual \cdot A^\dual \cdot A \cdot z - z^\dual \cdot A^\dual \cdot y \right]\]

que l'on peut de nouveau résoudre itérativement en utilisant par exemple la méthode de la plus grande descente ou les gradients conjugués.

4.4 Espaces de Krylov

Les espaces de Krylov sont des espaces de vecteurs engendrés par les puissances de la matrice \(A\) appliquées à un vecteur initial \(u\) :

\[\krylov_m(A,u) = \combilin{ u, A \cdot u, A^2 \cdot u, ..., A^{m - 1} \cdot u }\]

On a donc des éléments \(x \in \krylov_m(A,u)\) de la forme :

\[x = \left[ \sum_{i = 0}^{m - 1} \alpha_i \cdot A^i \right] \cdot u\]

pour certains \(\alpha_i \in \corps\). Il s'agit donc de polynômes matriciels appliquées à \(u\).

4.5 Méthode de projection

Soit la matrice \(A\) de taille \((n,n)\), le vecteur \(b \in \setR^n\) et le système \(A \cdot x = b\) à résoudre en \(x \in \setR^n\). On choisit \(m \le n\) beaucoup plus petit que \(n\) et les vecteurs \((v_1,...,v_m)\) de \(\setR^n\). Nous allons tenter de minimiser l'erreur en \(x_{k + 1}\) produite par l'itération générique suivante :

\[x_{k + 1} = x_k + \sum_{i = 1}^m v_i \cdot y_i\]

où les \(y_i \in \setR\). Posons :

\begin{align} V &= [v_1 \ ... \ v_m] \\ y &= [y_1 \ ... \ y_m]^\dual \end{align}

On peut réécrire l'itération sous la forme :

\[x_{k + 1} = x_k + V \cdot y\]

Nous avons vu en résolvant les moindres carrés qu'une condition nécessaire de minimisation était d'imposer l'orthogonalité entre \((A \cdot x - b)\) et les colonnes de \(A\). Nous imposant ici une variante :

\[w_i^\dual \cdot (b - A \cdot x_{k + 1}) = 0\]

pour certains \(w_1,...,w_m \in \setR^n\). En posant :

\[W = [w_1 \ ... \ w_m]\]

cette condition peut s'écrire :

\[W^\dual \cdot (b - A \cdot x_{k + 1}) = 0\]

Posons :

\[r_k = b - A \cdot x_k\]

On a alors :

\[b - A \cdot x_{k + 1} = b - A \cdot x_k - A \cdot V \cdot y = r_k - A \cdot V \cdot y\]

La condition d'orthogonalité devient :

\[W^\dual \cdot (r_k - A \cdot V \cdot y) = W^\dual \cdot r_k - W^\dual \cdot A \cdot V \cdot y = 0\]

Si la matrice \(W^\dual \cdot A \cdot V\) est inversible, on a :

\[y = (W^\dual \cdot A \cdot V)^{-1} \cdot W^\dual \cdot r_k\]

Comme \(V\) et \(W\) sont de taille \((n,m)\), la matrice \(W^\dual \cdot A \cdot V\) est de taille \((m,m)\), donc beaucoup plus petite que \(A\). Le système correspondant est donc beaucoup plus facile à résoudre.

4.5.1 Orthonormés

Si On choisit \(V = W\) et si les vecteurs \(v_i = w_i\) sont $A$-orthonormés, on a simplement :

\[\composante_{ij} W^\dual \cdot A \cdot V = w_i^\dual \cdot A \cdot v_j = v_i^\dual \cdot A \cdot v_j = \indicatrice_{ij}\]

et :

\[(W^\dual \cdot A \cdot V)^{-1} = W^\dual \cdot A \cdot V = I\]

4.5.2 Krylov

On peut par exemple choisir des vecteurs de base de \(\krylov_m(A,r_k)\) pour former les colonnes des matrices \(V\) et \(W\). On peut aussi utiliser aussi des vecteurs de base de \(\krylov_m(A^\dual,r_k)\).

4.6 Minimisation du résidu

On tente de minimiser la norme quadratique du résidu :

\[\mathcal{E}(y) = (r_k - A \cdot V \cdot y)^\dual \cdot (r_k - A \cdot V \cdot y)\]

La condition d'annulation de la dérivée par rapport à \(y\) nous donne la valeur optimale :

\[y = (V^\dual \cdot A^\dual \cdot A \cdot V)^{-1} \cdot (V^\dual \cdot A^\dual \cdot r_k)\]

4.7 Gradients biconjugués

Soit la matrice \(A\) de taille \((n,n)\) et les vecteurs \(b,c \in \corps^n\). Les gradients biconjugués permettent d'obtenir simultanément les deux solutions \(x,y \in \corps^n\) telles que :

\( A \cdot x = b \quad \text{ (système primal)} \\ A^\dual \cdot y = c \quad \text{ (système dual)} \)

Soit \((x_k,y_k)\) l'estimation de \((x,y)\) obtenues à l'itération \(k\) et les résidus :

\( r_k = b - A \cdot x_k \\ s_k = c - A^\dual \cdot y_k \)

L'algorithme est initialisé par \(x_0 = y_0 = 0\). On a alors \(r_0 = b\) et \(s_0 = c\). L'itération est donnée par :

\( x_{k + 1} = x_k + \alpha_k \cdot p_k \\ y_{k + 1} = y_k + \gamma_k \cdot q_k \)

où \(p_k,q_k \in \corps^n\) et \(\alpha_k,\gamma_k \in \corps\). Par analogie avec la plus grande descente, les premiers pas s'écrivent \(p_0 = r_0\) et \(q_0 = s_0\). On adapte ensuite à chaque itération les \(p_k, q_k\) par :

\( p_{k + 1} = r_{k + 1} + \beta_k \cdot p_k \\ q_{k + 1} = s_{k + 1} + \delta_k \cdot q_k \)

où \(\beta_k,\delta_k \in \corps\). On impose l'orthogonalité des résidus ainsi que l'$A$-orthogonalité des pas successifs :

\[s_k^\dual \cdot r_{k + 1} = r_k^\dual \cdot s_{k + 1} = q_k^\dual \cdot A \cdot p_{k + 1} = p_k^\dual \cdot A^\dual \cdot q_{k + 1} = 0\]

On voit que :

\begin{align} r_{k + 1} &= b - A \cdot x_{k + 1} \\ &= b - A \cdot x_k - \alpha_k\cdot A\cdot p_k \\ &= r_k - \alpha_k \cdot A \cdot p_k \\ s_{k + 1} &= c - A^\dual \cdot y_{k + 1} \\ &= c - A^\dual \cdot y_k - \gamma_k \cdot A^\dual \cdot q_k \\ &= s_k - \gamma_k \cdot A^\dual \cdot q_k \end{align}

Les conditions d'orthogonalité nous donnent donc les valeurs des coefficients

\begin{align} \alpha_k = \frac{s_k^\dual \cdot r_k}{s_k^\dual \cdot A \cdot p_k} \ \ && \ \ \gamma_k = \frac{r_k^\dual \cdot s_k}{r_k^\dual \cdot A^\dual \cdot q_k} \\ \\ \beta_k = - \frac{ q_k^\dual \cdot A \cdot r_{k + 1} }{q_k^\dual \cdot A \cdot p_k} \ \ && \ \ \delta_k = - \frac{ p_k^\dual \cdot A^\dual \cdot s_{k + 1} }{p_k^\dual \cdot A^\dual \cdot q_k} \end{align}

4.7.1 Simplification des coefficients

Il existe un procédé plus rapide pour évaluer les coefficients. En prenant le dual des relations entre les résidus successifs, on obtient \((s_k - s_{k + 1})^\dual = \conjaccent{\gamma_k} \cdot q_k^\dual \cdot A\). Donc :

\[q_k^\dual \cdot A \cdot r_{k + 1} = \unsur{\conjaccent{\gamma_k}} \cdot (s_k - s_{k + 1})^\dual \cdot r_{k + 1} = - \unsur{\conjaccent{\gamma_k}} \cdot s_{k + 1}^\dual \cdot r_{k + 1}\]

et :

\begin{align} q_k^\dual \cdot A \cdot p_k &= q_k^\dual \cdot A \cdot r_k - \beta_k \cdot q_k^\dual \cdot A \cdot p_{k - 1} = q_k^\dual \cdot A \cdot r_k \\ &= \unsur{\conjaccent{\gamma_k}} \cdot (s_k - s_{k + 1})^\dual \cdot r_k = \unsur{\conjaccent{\gamma_k}} \cdot s_k^\dual \cdot r_k \end{align}

On en conclut que :

\[\beta_k = \frac{ s_{k + 1}^\dual \cdot r_{k + 1} }{ s_k^\dual \cdot r_k }\]

D'un autre coté, \((r_k - r_{k + 1})^\dual = \conjaccent{\alpha_k} \cdot p_k^\dual \cdot A^\dual\). On obtient en suivant un raisonnement analogue :

\[\delta_k = \frac{ r_{k + 1}^\dual \cdot s_{k + 1} }{ r_k^\dual \cdot s_k }\]

5 Optimisation sous contrainte

5.1 Introduction

Ce chapitre traite de la résolution numérique de problèmes d'optimisation sous contraintes, ainsi que de leurs fondements théoriques. Les applications de ces méthodes sont nombreuses : maximisation du profit sous contrainte de ne pas dépasser un certain budget, maximiser la solidité d'une structure sans dépasser un certain poids, …

5.2 Problème de minimisation sous contrainte

Soit les fonctions convexes et et deux fois continument différentiables \(\omega_1,\omega_2,...,\omega_m : \setR^n \mapsto \setR\) et la fonction \(\omega : \setR^n \mapsto \setR^m\) définie par :

\[\omega(x) = (\omega_1(x), \omega_2(x), ..., \omega_m(x))\]

pour tout \(x \in \setR^n\). On considère l'ensemble associé :

\[\Omega = \{ x \in \setR^n : \omega(x) \le 0 \}\]

Par définition de l'ordre partiel sur \(\setR^m\), tout \(x \in \Omega\) doit donc vérifier les \(m\) contraintes :

\begin{align} \omega_1(x) &\le 0 \\ \omega_2(x) &\le 0 \\ \dots & & \\ \omega_m(x) &\le 0 \end{align}

Nous considérons le problème général suivant : trouver un \(\gamma \in \Omega\) qui minimise la fonction convexe et et deux fois continument différentiable \(\varphi : \setR^n \mapsto \setR\) sur \(\Omega\) :

\[\gamma \in \arg\min_{x \in \Omega} \varphi(x)\]

Nous avons donc un problème de minimisation à \(n\) paramètres :

\[x = (x_1,...,x_n)\]

et \(m\) contraintes correspondant aux \(\omega_i\). On dit que \(\varphi\) est la fonction objectif et \(\omega\) la fonction contraignante.

5.2.1 Lien avec la minimisation libre

Il est important de se rendre compte que si \(\xi\) est la solution de :

\[\partial \varphi(\xi) = 0\]

on sait que :

\[\xi \in \arg\min_{x \in \setR^n} \varphi(x)\]

mais rien ne nous dit que \(\xi\) respecte les contraintes exigées ! On ne peut donc pas dans le cas général appliquer la technique classique de la minimisation libre pour résoudre des problèmes de minimisation contraints.

5.3 Convexité

Soit \(u,v \in \Omega\) et \(s,t \in \setR\) tels que \(s,t \ge 0\) et \(s + t = 1\). On a alors par convexité des \(\omega_i\) :

\[\omega(s \cdot u + t \cdot v) \le s \cdot \omega(u) + t \cdot \omega(v) \le 0\]

On en conclut que \(w = s \cdot u + t \cdot v \in \Omega\). On a donc \(\convexe(\Omega) = \Omega\). L'ensemble \(\Omega\) est convexe.

5.4 Frontière

Soit \(x \in \frontiere \Omega\). Comme \(x \in \adh \Omega\), on a \(\distance(x,\Omega) = 0\). On peut donc construire une suite \(u_n \in \Omega\) convergeant vers \(x\). La continuité des \(\omega_i\) et la définition de \(\Omega\) nous disent que :

\[\omega_i(x) = \lim_{n \to \infty} \omega_i(u_n) \le \limsup_{n \to \infty} \omega_i(u_n) \le 0\]

pour tout \(i \in \{1,...,m\}\). Comme \(x \notin \interieur \Omega\), on a aussi \(\distance(x,\setR^n \setminus \Omega) = 0\) et on peut construire une suite \(v_n \in \setR^n \setminus \Omega\) convergeant vers \(x\). On peut alors trouver un \(i \in \{1,...,m\}\) tel que :

\[\omega_i(x) = \lim_{n \to \infty} \omega_i(v_n) \ge \liminf_{n \to \infty} \omega_i(v_n) \ge 0\]

Ces deux inégalités nous disent que, pour tout \(x \in \frontiere \Omega\), il existe un \(i\) tel que \(\omega_i(x) = 0\).

5.5 Pénalité

L'idée est de laisser l'objectif inchangé sur \(\Omega\) mais de l'augmenter suffisamment en dehors pour que le minimum sur \(\Omega\) soit également le minimum global. On utilise une fonction \(p\) convexe et différentiable vérifiant :

\begin{align} p(x) &= 0 \text{ pour tout } x \in \Omega \\ p(x) &\strictsuperieur& 0 \text{ pour tout } x \in \setR^n \setminus \Omega \end{align}

et on construit donc un nouvel objectif \(\psi\) par :

\[\psi(x) = \varphi(x) + p(x)\]

On dit alors que \(p(x)\) est un terme de pénalité. On a :

\[\min_{x \in \Omega} \psi(x) = \min_{x \in \Omega} \varphi(x) = \varphi(\gamma)\]

Choisissons :

\[\chi \in \arg\min_{x \in \setR^n \setminus \Omega} \psi(x)\]

Si \(p\) est assez élevée en dehors de \(\Omega\) pour avoir \(\psi(\chi) \ge \varphi(\gamma)\), on a :

\[\min_{x \in \setR^n} \psi(x) = \min \{ \psi(\chi) , \varphi(\gamma) \} = \varphi(\gamma)\]

Si de plus \(\psi(\chi) \strictsuperieur \varphi(\gamma)\), aucun minimum global ne pourra être en dehors de \(\Omega\) (sinon il serait minimisé par \(\varphi(\gamma)\)). On aura donc :

\[\arg\min_{x \in \setR^n} \psi(x) \subseteq \Omega\]

et il suffit de choisir :

\[\gamma \in \arg\min_{x \in \setR^n} \psi(x)\]

pour obtenir une solution à notre problème. De par les propriétés des fonctions convexes, \(\gamma\) sera une solution de \(\partial \psi(\gamma) = 0\).

5.6 Lagrangien

Par définition de \(\Omega\), on peut trouver au moins un \(\omega_i(x) \strictsuperieur 0\) pour tout \(x \notin \Omega\). Il est donc possible de s'en servir pour former un terme de pénalité. Comme chaque \(\omega_i\) est convexe, \(y_i \cdot \omega_i\) le sera aussi pour tout \(y_i \in \setR\) tel que \(y_i \ge 0\) (si \(y_i\) était strictement négatif, on aurait \(y_i \cdot \omega_i\) concave). Posons :

\[\mathcal{P} = \{ y \in \setR^m : y \ge 0 \}\]

L'objectif modifié s'écrit alors :

\[\lagrangien(x,y) = \varphi(x) + \sum_{i = 1}^m y_i \cdot \omega_i(x)\]

pour tout \(x \in \setR^n\) et tout \(y = (y_1,...,y_m) \in \mathcal{P}\). On dit que les \(y_i\) sont les multiplicateurs de Lagrange et que \(\lagrangien\) est le lagrangien associé au problème de minimisation. Utilisant la notation du produit scalaire entre vecteurs matriciels, on le note sous la forme schématique :

\[\lagrangien(x,y) = \varphi(x) + y^\dual \cdot \omega(x)\]

5.7 Conditions de Kuhn-Tucker

Nous allons à présent essayer de caractériser un choix \(y = \lambda\) tel que \(\gamma\) minimise globalement \(\lagrangien(x,\lambda)\) :

\[\lagrangien(\gamma,\lambda) = \min_{x \in \setR^n} \lagrangien(x,\lambda)\]

Puisqu'il s'agit d'un problème de minimisation libre, on sait que la dérivée doit s'annuler en \(\gamma\) :

\[\deriveepartielle{\lagrangien}{x}(\gamma,\lambda) = \partial \varphi(\gamma) + \lambda^\dual \cdot \partial \omega(\gamma) = 0\]

En terme de composantes, on a donc :

\[\partial \varphi(\gamma) + \sum_{i = 1}^m \lambda_i \cdot \partial \omega_i(\gamma) = 0\]

D'un autre coté, \(\gamma\) doit appartenir à \(\Omega\), où le terme de pénalité doit également s'annuler :

\[\lambda^\dual \cdot \omega(\gamma) = 0\]

On a donc :

\[\lagrangien(\gamma,\lambda) = \varphi(\gamma) + \lambda^\dual \cdot \omega(\gamma) = \varphi(\gamma) + 0 = \varphi(\gamma)\]

En terme de composantes, la condition d'annulation du terme de pénalité s'écrit :

\[\sum_i \lambda_i \cdot \omega_i(\gamma) = 0\]

Mais comme \(\lambda_i \ge 0\) et \(\omega_i(\gamma) \le 0\), on en déduit que \(\lambda_i \cdot \omega_i(\gamma) \le 0\). Que se passerait-il si on pouvait trouver un \(k\) tel que \(\lambda_k \cdot \omega_k(\gamma) \strictinferieur 0\) ? On aurait :

\[\sum_i \lambda_i \cdot \omega_i(\gamma) \le \lambda_k \cdot \omega_k(\gamma) \strictinferieur 0\]

ce qui est incompatible avec la condition d'annulation du terme de pénalité. On a donc :

\[\lambda_i^\dual \cdot \omega_i(\gamma) = 0\]

pour tout \(i \in \{1,2,...,m\}\). Les conditions :

\( \partial \varphi(\gamma) + \sum_{i = 1}^m \lambda_i \cdot \partial \omega_i(\gamma) = 0 \\ \\ \lambda_i^\dual \cdot \omega_i(\gamma) = 0 \\ \\ \omega(\gamma) \le 0 \)

sont appellées conditions de Kuhn-Tucker.

5.8 Point de selle

Supposons que \((\gamma,\lambda) \in \Omega \times \mathcal{P}\) vérifie les conditions de Kuhn-Tucker. Choisissons \(x \in \setR^n\) et \(y \in \mathcal{P}\). L'annulation du gradient (\(\partial_x \lagrangien(\gamma,\lambda) = 0\)) et la convexité du lagrangien par rapport à la variable \(x\) nous assurent que :

\[\lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

D'un autre coté, on a \(\lambda^\dual \cdot \omega(\gamma) = 0\) et \(\lagrangien(\gamma,\lambda) = \varphi(\gamma)\). On sait aussi que \(y \ge 0\) et que \(\omega(\gamma) \le 0\). Donc \(y^\dual \cdot \omega(\gamma) \le 0\) et :

\[\lagrangien(\gamma,y) = \varphi(\gamma) + y^\dual \cdot \omega(\gamma) \le \varphi(\gamma) = \lagrangien(\gamma,\lambda)\]

On voit que \(\lambda\) maximise le lagrangien par rapport à la variable \(y\). Ces deux propriétés extrémales nous montrent que \((\gamma,\lambda)\) est un point de selle :

\[\lagrangien(\gamma,y) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

5.8.1 Réciproque

Nous venons de voir que les conditions de Kuhn-Tucker remplies sur \(\Omega \times \mathcal{P}\) nous offraient un point de selle sur \(\setR^n \times \mathcal{P}\). Nous allons voir que la réciproque est également vraie. Supposons que \((\gamma,\lambda) \in \setR^n \times \mathcal{P}\) soit un point de selle du lagrangien :

\[\lagrangien(\gamma,y) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

pour tout \((x,y) \in \setR^n \times \mathcal{P}\). On a :

\[\lagrangien(\gamma,y) - \lagrangien(\gamma,\lambda) = (y - \lambda)^\dual \cdot \omega(\gamma) \le 0\]

relation qui doit être valable pour tout \(y \ge 0\). Fixons \(i \in \{1,2,...,m\}\) et choisissons :

\( yk =

\begin{cases} \lambda_k & \text{ si } k \ne i \\ 0 & \text{ si } k = i \end{cases}

\)

on en déduit que \((y - \lambda)^\dual \cdot \omega(\gamma) = -\lambda_i \cdot \omega_i(\gamma) \le 0\), c'est-à-dire :

\[\lambda_i \cdot \omega_i(\gamma) \ge 0\]

Considérons à présent le choix :

\( yk =

\begin{cases} \lambda_k & \text{ si } k \ne i \\ 2 \lambda_i & \text{ si } k = i \end{cases}

\)

On en déduit alors que :

\[(y - \lambda)^\dual \cdot \omega(\gamma) = \lambda_i \cdot \omega_i(\gamma) \le 0\]

On conclut de ces deux inégalités que :

\[\lambda_i \cdot \omega_i(\gamma) = 0\]

Enfin, si nous prenons :

\( yk =

\begin{cases} \lambda_k & \text{ si } k \ne i \\ \lambda_i + 1 & \text{ si } k = i \end{cases}

\)

on voit que :

\[(y - \lambda)^\dual \cdot \omega(\gamma) = 1 \cdot \omega_i(\gamma) = \omega_i(\gamma) \le 0\]

ce qui nous montre que \(\gamma \in \Omega\).

De plus, comme :

\[\gamma \in \arg\min_{x \in \setR^n} \lagrangien(x,\lambda)\]

les propriétés des fonctions dérivables nous imposent que \(\partial_x \lagrangien(\gamma,\lambda) = 0\).

5.9 Solution

Supposons que \((\gamma,\lambda)\) soit un point de selle du lagrangien. Choisissons \(x \in \Omega\). On a \(\omega(x) \le 0\) et \(\lambda^\dual \cdot \omega(x) \le 0\). On en déduit que :

\[\lagrangien(x,\lambda) = \varphi(x) + \lambda^\dual \cdot \omega(x) \le \varphi(x)\]

On a donc bien :

\[\varphi(\gamma) = \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda) \le \varphi(x)\]

ce qui prouve que \(\gamma\) minimise \(\varphi\) sur \(\Omega\). La solution du problème de point de selle du lagrangien contient donc la solution de notre problème de minimisation sous contrainte.

5.9.1 Généralisation

Remarquons que nous n'avons pas utilisé la convexité de \(\varphi\) ou de \(\omega\) pour démontrer que \(\gamma\) est bien la solution de notre problème. On peut donc appliquer la technique du point de selle du lagrangien à une classe de fonctions beaucoup plus générale.

Attention, si \(\varphi\) et/ou \(\omega\) ne sont plus supposées convexes, le point de selle impliquera toujours les conditions de Kuhn-Tucker mais l'inverse ne sera plus vrai. En pratique, on essaiera malgré tout de trouver une solution aux conditions de Kuhn-Tucker, et on déterminera a posteriori :

  • si le minimum trouvé est bien un minimum local (test de la Hessienne définie positive au \(\gamma\) obtenu)
  • si ce minimum local est aussi un minimum sur \(\Omega\)

5.10 Problème de maximisation sous contrainte

Soit les fonctions {\em concaves} et deux fois continument différentiables \(\vartheta_1,\vartheta_2,...,\vartheta_m : \setR^n \mapsto \setR\) et la fonction \(\vartheta : \setR^n \mapsto \setR^m\) définie par :

\[\vartheta(x) = (\vartheta_1(x), \vartheta_2(x), ..., \vartheta_m(x))\]

pour tout \(x \in \setR^n\). On considère l'ensemble associé :

\[\Theta = \{ x \in \setR^n : \vartheta(x) \ge 0 \}\]

Nous considérons le problème général suivant : trouver un \(\gamma \in \Theta\) qui maximise la fonction concave et et deux fois continument différentiable \(\psi : \setR^n \mapsto \setR\) sur \(\Theta\) :

\[\gamma \in \arg\max_{x \in \Theta} \psi(x)\]

On note que ce problème est équivalent au suivant :

\[\gamma \in \arg\min_{x \in \Omega} (-\psi(x))\]

où :

\[\Omega = \{ x \in \setR^n : -\vartheta(x) \le 0 \}\]

5.10.1 Lagrangien

On sait que maximiser \(\psi\) revient à minimiser \(-\psi\). Comme \(-\psi\) et \(-\vartheta\) sont convexes, on peut utiliser le lagrangien défini par :

\[\lagrangien_{\min}(x,y) = \Big[-\psi(x)\Big] + y^\dual \cdot \Big[-\vartheta(x)\Big] = -\psi(x) - y^\dual \cdot \vartheta(x)\]

pour tout \((x,y) \in \setR^n \times \mathcal{P}\). La solution \((\gamma,\lambda)\) vérifie alors :

\[\lagrangien_{\min}(\gamma,y) \le \lagrangien_{\min}(\gamma,\lambda) \le \lagrangien_{\min}(x,\lambda)\]

On voit que la fonction opposée :

\[\lagrangien_{\max}(x,y) = - \lagrangien_{\min}(x,y) = \psi(x) + y^\dual \cdot \vartheta(x)\]

vérifie les conditions du point de selle inversées :

\[\lagrangien_{\max}(x,\lambda) \le \lagrangien_{\max}(\gamma,\lambda) \le \lagrangien_{\max}(\gamma,y)\]

Il s'agit du lagrangien natif du problème de maximisation. Il est maximisé par rapport à \(x\) et minimisé par rapport aux multiplicateurs de Lagrange.

5.10.2 Kuhn-Tucker

Les conditions de Kuhn-Tucker associées à \(\lagrangien_{\min}\) s'écrivent :

\(

  • ∂ ψ(γ) - ∑i = 1m λi ⋅ ∂ ϑi(γ) = 0 \\
  • λi^\dual ⋅ ϑi(γ) = 0 \\
  • ϑ(γ) ≤ 0

\)

Elles sont équivalentes aux conditions analogues associées à \(\lagrangien_{\max}\) :

\( \partial \psi(\gamma) + \sum_{i = 1}^m \lambda_i \cdot \partial \vartheta_i(\gamma) = 0 \\ \\ \lambda_i^\dual \cdot \vartheta_i(\gamma) = 0 \\ \\ \vartheta(\gamma) \ge 0 \)

5.11 Contraintes d'égalité

Soit les fonctions deux fois continument différentiables \(\varrho_1,\varrho_2,...,\varrho_m : \setR^n \mapsto \setR\) et la fonction \(\varrho : \setR^n \mapsto \setR^m\) définie par :

\[\varrho(x) = (\varrho_1(x), \varrho_2(x), ..., \varrho_m(x))\]

pour tout \(x \in \setR^n\). On considère l'ensemble associé :

\[\Phi = \{ x \in \setR^n : \varrho(x) = 0 \}\]

Nous considérons le problème général suivant : trouver un \(\gamma \in \Phi\) qui minimise la fonction deux fois continument différentiable \(\varphi : \setR^n \mapsto \setR\) sur \(\Phi\) :

\[\gamma \in \arg\min_{x \in \Phi} \varphi(x)\]

5.11.1 Lagrangien

On peut réécrire l'ensemble \(\Phi\) sous la forme :

\[\Phi = \{ x \in \setR^n : \varrho(x) \le 0, \ \varrho(x) \ge 0 \}\]

On introduit donc deux séries de multiplicateurs et le lagrangien défini par :

\[L(x,y,z) = \varphi(x) + y^\dual \cdot \varrho(x) + z^\dual \cdot (-\varrho(x))\]

pour tout \((x,y,z) \in \setR^n \times \mathcal{P} \times \mathcal{P}\). On constate qu'il ne dépend que de \(x\) et de \(y - z\) :

\[L(x,y,z) = \varphi(x) + (y - z)^\dual \cdot \varrho(x)\]

On voit que \(u = y - z\) est libre d'aller où il veut dans \(\setR^m\). On pose :

\[\lagrangien(x,u) = \varphi(x) + u^\dual \cdot \varrho(x)\]

pour tout \((x,u) \in \setR^n \times \setR^m\).

5.11.2 Kuhn-Tucker

Comme on veut que \(\gamma\) minimise \(\lagrangien\) par rapport à la variable \(x\) sur \(\setR^n\), on impose \(\partial_x \lagrangien(\gamma,\lambda) = 0\). On doit avoir aussi \(\varrho(x) = 0\). Mais comme \(\partial_u \lagrangien(x,u) = \varrho(x)\), on se retrouve finalement avec les conditions nécessaires de Kuhn-Tucker :

\( \partial_x \lagrangien(\gamma,\lambda) = 0 \\ \\ \partial_u \lagrangien(\gamma,\lambda) = 0 \)

5.11.3 Point de selle

Nous allons montrer que tout point de selle est solution du problème de minimisation. Soit \((\gamma,\lambda)\) tel que :

\[\lagrangien(\gamma,u) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

pour tout \((x,u) \in \setR^n \times \setR^m\). On en déduit que :

\[\lagrangien(\gamma,u) - \lagrangien(\gamma,\lambda) \le 0\]

pour tout \(u \in \setR^m\), c'est-à-dire :

\[(u - \lambda)^\dual \cdot \varrho(\gamma) \le 0\]

Considérons la base canonique \((\canonique_1,...,\canonique_m)\) de \(\setR^m\). Si on prend \(u = \lambda + \canonique_i\), on obtient la condition

\[(u - \lambda)^\dual \cdot \varrho(\gamma) = \varrho_i(\gamma) \le 0\]

Mais comme \(u\) n'est pas forcément positif, on peut aussi prendre \(u = \lambda - \canonique_i\). On obtient alors la condition :

\[(u - \lambda)^\dual \cdot \varrho(\gamma) = -\varrho_i(\gamma) \le 0\]

On déduit de ces deux inégalités que \(\varrho(\gamma) = 0\), c'est à dire \(\gamma \in \Phi\).

A présent, soit \(x \in \Phi\). Comme \(\varrho(\gamma) = \varrho(x) = 0\), on a :

\[\varphi(\gamma) = \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda) = \varphi(x)\]

Le \(\gamma\) issu du point de selle est donc bien la solution de notre problème de minimisation contraint.

5.12 Récapitulation

Considérons l'ensemble :

\[\Omega = \{ x \in \setR^n : \omega(x) \le 0, \ \vartheta(x) \ge 0, \ \varrho(x) = 0 \}\]

5.12.1 Minimisation

Si on veut minimiser \(\varphi\) sur \(\Omega\), on utilisera le lagrangien défini par :

\[\lagrangien(x,y,z,u) = \varphi(x) + y^\dual \cdot \omega(x) - z^\dual \cdot \vartheta(x) + u^\dual \cdot \varrho(x)\]

pour tout \((x,y,z,u)\) tels que \(y,z \ge 0\). Le point de selle \((\gamma,\lambda,\mu,\nu)\) vérifiera :

\[\lagrangien(\gamma,y,z,u) \le \lagrangien(\gamma,\lambda,\mu,\nu) \le \lagrangien(x,\lambda,\mu,\nu)\]

Les conditions de Kuhn-Tucker s'écriront :

\( \partial \varphi(\gamma) + \sum_i \left[ \lambda_i \cdot \partial \omega_i(x) - \mu_i \cdot \partial \vartheta_i(x) + \nu_i \cdot \partial \varrho_i(x) \right] = 0 \\ \\ \lambda_i \cdot \omega_i(x) = 0 \\ \\ \mu_i \cdot \vartheta_i(x) = 0 \\ \\ \omega_i(x) \le 0 \\ \\ \vartheta_i(x) \ge 0 \\ \\ \varrho_i(x) = 0 \)

5.12.2 Maximisation

Si on veut maximiser \(\psi\) sur \(\Omega\), on utilisera le lagrangien défini par :

\[\lagrangien(x,y,z,u) = \psi(x) - y^\dual \cdot \omega(x) + z^\dual \cdot \vartheta(x) + u^\dual \cdot \varrho(x)\]

pour tout \((x,y,z,u)\) tels que \(y,z \ge 0\). Le point de selle \((\gamma,\lambda,\mu,\nu)\) vérifiera :

\[\lagrangien(x,\lambda,\mu,\nu) \le \lagrangien(\gamma,\lambda,\mu,\nu) \le \lagrangien(\gamma,y,z,u)\]

Les conditions de Kuhn-Tucker s'écriront :

\( \partial \psi(\gamma) + \sum_i \left[ -\lambda_i \cdot \partial \omega_i(x) + \mu_i \cdot \partial \vartheta_i(x) + \nu_i \cdot \partial \varrho_i(x) \right] = 0 \\ \\ \lambda_i \cdot \omega_i(x) = 0 \\ \\ \mu_i \cdot \vartheta_i(x) = 0 \\ \\ \omega_i(x) \le 0 \\ \\ \vartheta_i(x) \ge 0 \\ \\ \varrho_i(x) = 0 \)

5.12.3 Equivalence

On exprime parfois ces problèmes en utilisant des contraintes équivalentes. Si on pose \(s = - \omega(x)\), on a \(s \ge 0\). De même, on pose \(t = \vartheta(x) \ge 0\). On définit alors \(\Gamma\) comme l'ensemble des \((x,s,t)\) vérifiant les conditions :

\begin{align} s,t &\ge 0 \\ s + \omega(x) &= 0 \\ t - \vartheta(x) &= 0 \\ \varrho(x) &= 0 \end{align}

Et on minimise \(\varphi(x)\) (ou on maximise \(\psi(x)\)) sur les \((x,s,t) \in \Gamma\).

5.13 Découplage

5.13.1 Minimisation

Soit le problème de minimisation :

\[\gamma \in \arg\min_{x \in \Omega} \varphi(x)\]

où :

\[\Omega^+ = \{ x \in \corps^n : \omega(x) \le 0, \ x \ge 0 \}\]

La condition \(x \ge 0\) est équivalente à \(-x \le 0\). On définit le lagrangien :

\[L(x,y,z) = \varphi(x) + y^\dual \cdot \omega(x) - z^\dual \cdot x\]

La solution de notre problème vérifie les conditions du point de selle :

\[L(\gamma,y,z) \le L(\gamma,\lambda,\mu) \le L(x,\lambda,\mu)\]

pour tout \(x \in \setR^n\) et \(y,z \ge 0\). Si \(x \ge 0\), on a :

\[-z^\dual \cdot x \le 0\]

par positivité de \(z\). On a alors :

\[L(x,y,z) = \varphi(x) + y^\dual \cdot \omega(x) - z^\dual \cdot x \le \varphi(x) + y^\dual \cdot \omega(x) = L(x,y,0)\]

On en conclut qu'un choix permettant de maximiser \(L\) par rapport à son troisième argument est \(\mu = 0\). Introduisons le lagrangien modifié :

\[\lagrangien(x,y) = L(x,y,0) = \varphi(x) + y^\dual \cdot \omega(x)\]

Le problème du point de selle est équivalent à trouver \((\gamma,\lambda) \ge 0\) tel que :

\[\lagrangien(\gamma,y) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

pour tout \((x,y) \ge 0\). La différence est qu'on ne fait plus apparaître explicitement la contrainte de positivité de \(x\) dans le lagrangien.

5.13.2 Maximisation

Soit le problème de minimisation :

\[\gamma \in \arg\max_{x \in \Theta} \psi(x)\]

où :

\[\Theta = \{ x \in \corps^n : \vartheta(x) \ge 0, \ x \ge 0 \}\]

On pose le lagrangien :

\[L(x,y,z) = \psi(x) + y^\dual \cdot \omega(x) + z^\dual \cdot x\]

La solution de notre problème vérifie les conditions du point de selle inversé :

\[L(x,\lambda,\mu) \le L(\gamma,\lambda,\mu) \le L(\gamma,y,z)\]

pour tout \(x \in \setR^n\) et \(y,z \ge 0\). Si \(x \ge 0\), on a :

\[z^\dual \cdot x \ge 0\]

par positivité de \(z\). On a alors :

\[L(x,y,z) \ge L(x,y,0)\]

On en conclut qu'un choix permettant de minimiser \(L\) par rapport à son troisième argument est \(\mu = 0\). Introduisons le lagrangien modifié :

\[\lagrangien(x,y) = L(x,y,0) = \psi(x) + y^\dual \cdot \vartheta(x)\]

Le problème du point de selle est équivalent à trouver \((\gamma,\lambda) \ge 0\) tel que :

\[\lagrangien(x,\lambda) \le \lagrangien(\gamma,\lambda) \le \lagrangien(\gamma,y)\]

pour tout \((x,y) \ge 0\).

5.14 Dualité en optimisation linéaire

5.14.1 Problème primal

Soit une matrice réelle \(A\) de taille \((m,n)\), l'ensemble :

\[\Theta = \{ x \in \setR^n : A \cdot x \le b, \ x \ge 0 \}\]

et le vecteur \(c \in \setR^n\). Nous nous intéressons au problème de maximisation linéaire sous contrainte :

\[\gamma \in \arg\max_{x \in \Theta} \big[ c^\dual \cdot x \big]\]

5.14.2 Lagrangien

La contrainte \(A \cdot x \le b\) est équivalente à :

\[b - A \cdot x \ge 0\]

On introduit donc le lagrangien :

\begin{align} \lagrangien(x,y) &= c^\dual \cdot x + y^\dual \cdot (b - A \cdot x) \\ &= c^\dual \cdot x + y^\dual \cdot b - y^\dual \cdot A \cdot x \end{align}

défini pour tout \((x,y) \ge 0\).

5.14.3 Dualité

Comme on travaille dans les réels, on a par symétrie du produit scalaire :

\begin{align} c^\dual \cdot x &= x^\dual \cdot c \\ y^\dual \cdot b &= b^\dual \cdot y \\ y^\dual \cdot A \cdot x &= (A \cdot x)^\dual \cdot y = x^\dual \cdot A^\dual \cdot y \end{align}

Le lagrangien du problème primal peut donc se réécrire :

\begin{align} \lagrangien(x,y) &= x^\dual \cdot c + b^\dual \cdot y - x^\dual \cdot A^\dual \cdot y \\ &= b^\dual \cdot y + x^\dual \cdot (c - A^\dual \cdot y) \end{align}

On voit que la fonction duale définie par :

\[\lagrangien^\dual(y,x) = \lagrangien(x,y) = b^\dual \cdot y + x^\dual \cdot (c - A^\dual \cdot y)\]

pour tout \((y,x) \ge 0\) peut également être considérée comme un lagrangien formé à partir de l'objectif \(y \mapsto b^\dual \cdot y\) et d'une des deux contraintes suivantes :

\( ?

\begin{cases} c - A^\dual \cdot y \le 0 \\ c - A^\dual \cdot y \ge 0 \end{cases}

\)

Résoudre le problème primal revient à trouver un point \((\gamma,\lambda) \ge 0\) vérifiant :

\[\lagrangien(x,\lambda) \le \lagrangien(\gamma,\lambda) \le \lagrangien(\gamma,y)\]

pour tout \(x,y \ge 0\). En utilisant la définition de \(\lagrangien^\dual\), ces conditions se réécrivent :

\[\lagrangien^\dual(\lambda,x) \le \lagrangien^\dual(\lambda,\gamma) \le \lagrangien^\dual(y,\gamma)\]

Le couple \((\lambda,\gamma)\) est donc solution d'un problème de minimisation en \(y\). Dans un problème de minimisation, les contraintes associées aux multiplicateurs de lagrange doivent être négatives. On a donc \(c - A^\dual \cdot y \le 0\), autrement dit :

\[A^\dual \cdot y \ge c\]

Le problème primal est donc équivalent au problème dual suivant.

5.14.4 Problème dual

Trouver :

\[\lambda \in \arg\min_{y \in \Omega} (b^\dual \cdot y)\]

où :

\[\Omega = \{ y \in \setR^m : A^\dual \cdot y \ge c, \ y \ge 0 \}\]

5.14.5 Valeurs extrémales

Les conditions de Khun-Tucker des problèmes primal et dual impliquent :

\( \lambda^\dual \cdot (b - A \cdot \gamma) = 0 \\ \\ \gamma^\dual \cdot (c - A^\dual \cdot \lambda) = 0 \)

Les valeurs des lagrangiens aux points de selle s'écrivent donc :

\( \lagrangien(\gamma,\lambda) = c^\dual \cdot \gamma + \lambda^\dual \cdot (b - A \cdot \gamma) = c^\dual \cdot \gamma \\ \\ \lagrangien^\dual(\lambda,\gamma) = b^\dual \cdot \lambda + \gamma^\dual \cdot (c - A^\dual \cdot \lambda) = b^\dual \cdot \lambda \)

La définition du lagrangien dual implique que :

\[\lagrangien(\gamma,\lambda) = \lagrangien^\dual(\lambda,\gamma)\]

c'est-à-dire :

\[c^\dual \cdot \gamma = b^\dual \cdot \lambda\]

Le maximum de \(x \mapsto c^\dual \cdot x\) sur \(\Theta\) est donc égal au minimum de \(y \mapsto b^\dual \cdot y\) sur \(\Omega\). Dans la suite, on note :

\[V = \max_{x \in \Theta} (c^\dual \cdot x) = \min_{y \in \Omega} (b^\dual \cdot y)\]

5.14.6 Bornes

Par définition des maxima et minima, on a :

\[c^\dual \cdot x \le V \le b^\dual \cdot y\]

pour tout \(x \in \Theta\) et \(y \in \Omega\). Si les deux valeurs \(c^\dual \cdot x\) et \(b^\dual \cdot y\) sont proches, les éléments \(x\) et \(y\) sont presque optimaux.

5.14.7 Attention

Ne pas confondre la notion de dualité \(\max - \min\) avec la dualité au sens des applications linéaires.

5.15 Minimisation de la norme sous contraintes linéaires

Soit la matrice \(A \in \matrice(\setR,m,n)\), le vecteur colonne \(b \in \matrice(\setR,m,1)\) et l'ensemble :

\[\Phi = \{ x \in \matrice(\setR,n,1) : A \cdot x = b \}\]

On veut trouver le \(\gamma \in \Phi\) qui minimise la norme usuelle \(\norme{x} = \sqrt{x^\dual \cdot x}\) sur \(\Phi\). Comme la fonction $\norme{x} \mapsto \norme{x}2 /2 $ est une fonction monotone strictement croissante sur \(\norme{x} \in \setR^+\), cela revient à minimiser :

\[\gamma = \arg\min_{x \in \Phi} \left( \unsur{2} \cdot x^\dual \cdot x \right)\]

Afin de résoudre ce problème, on introduit le lagrangien :

\[\lagrangien(x,u) = \unsur{2} \cdot x^\dual \cdot x + u^\dual \cdot (b - A \cdot x)\]

On impose les conditions de Kuhn-Tucker :

\( \partial_x \lagrangien(\gamma,\lambda) = \gamma - A^\dual \cdot \lambda = 0 \\ \\ \partial_u \lagrangien(\gamma,\lambda) = b - A \cdot \gamma = 0 \)

On en déduit que \(\gamma = A^\dual \cdot \lambda\) et que :

\[A \cdot A^\dual \cdot \lambda = b\]

Si \(A \cdot A^\dual\) est inversible, on a donc :

\[\lambda = \left( A \cdot A^\dual \right)^{-1} \cdot b\]

et :

\[\gamma = A^\dual \cdot \left( A \cdot A^\dual \right)^{-1} \cdot b\]

6 Valeurs propres

6.1 Minimisation d'une forme quadratique avec norme contrainte

Soit un réel \(R \ne 0\), la matrice \(H \in \matrice(\setR,m,n)\) hermitienne et définie positive, et l'ensemble :

\[\Omega = \{ x \in \corps^n : \norme{x} = \sqrt{x^\dual \cdot x} = R \}\]

On peut reformuler \(\Omega\) de manière équivalente par :

\[\Omega = \{ x \in \corps^n : x^\dual \cdot x = R^2 \}\]

Soit l'objectif \(\varphi : \corps^n \mapsto \corps\) défini par :

\[\varphi(x) = x^\dual \cdot H \cdot x\]

pour tout \(x \in \corps^n\). On veut trouver le \(x \in \Omega\) qui minimise \(\varphi\) sur \(\Omega\). Définissons le lagrangien :

\[\lagrangien(x,\lambda) = x^\dual \cdot H \cdot x + \lambda \cdot (R^2 - x^\dual \cdot x)\]

où \(\lambda \in \setR\). On impose les conditions de Kuhn-Tucker :

\( \partial_x \lagrangien(x,\lambda) = 2 H \cdot x - 2 \lambda \cdot x = 0 \\ \partial_\lambda \lagrangien(x,\lambda) = R^2 - x^\dual \cdot x = 0 \)

Toute solution optimale \(x \in \Omega\) vérifie donc l'équation :

\[H \cdot x = \lambda \cdot x\]

pour un certain \(\lambda \in \setR\). Nous allons généraliser cette propriété aux applications linéaires.

6.1.1 Norme unité

Un cas particulier souvent utilisé est celui où \(R = 1\).

6.2 Application linéaire

Soit l'espace vectoriel \(E\) sur \(\corps\) et une application linéaire \(A : E \mapsto E\). Si le couple \((u,\lambda) \in (E \setminus \{0\}) \times \corps\) vérifie :

\[A(u) = \lambda \cdot u\]

On dit que \(u\) est vecteur propre de \(A\) correspondant à la valeur propre \(\lambda\).

6.2.1 Rapport de Rayleigh

En prenant le produit scalaire de \(u\) avec la relation \(A(u) = \lambda \cdot u\), on obtient :

\[\scalaire{u}{A(u)} = \lambda \cdot \scalaire{u}{u}\]

d'où l'on tire :

\[\lambda = \frac{ \scalaire{u}{A(u)} }{ \scalaire{u}{u} }\]

Une telle expression est appelée rapport de Rayleigh. Par extension, on définit :

\[R(v) = \frac{ \scalaire{v}{A(v)} }{ \scalaire{v}{v} }\]

pou tout vecteur non nul \(v \in E\).

6.2.2 Définie positive

Si \(A\) est définie positive, toute valeur propre \(\lambda = R(u) \ge 0\) est un réel positif.

6.2.3 Formulation équivalente

On voit qu'il est équivalent de chercher un scalaire \(\lambda\) et un vecteur \(u \ne 0\) tel que :

\[(A - \lambda \cdot \identite)(u) = A(u) - \lambda \cdot u = 0\]

6.3 Opérateurs auto-adjoints

Si l'application linéaire \(A\) est auto-adjointe (\(A^\dual = A\)), ses valeurs et vecteurs propres possèdent d'importantes propriétés. Soit \(u \in E\) et \(\lambda \in \setC\) tels que \(A(u) = \lambda \cdot u\) et \(\scalaire{u}{u} = 1\). On a alors :

\[\lambda = \scalaire{u}{A(u)} = \scalaire{A(u)}{u} = \conjugue \scalaire{u}{A(u)} = \bar{\lambda}\]

La valeur propre doit donc être réelle.

6.3.1 Orthonormalité

Soit la suite de vecteurs propres \(u_i \in \Omega\) et de valeurs propres \(\lambda_i \in \setR\). On a :

\[\scalaire{u_i}{A(u_j)} = \lambda_j \cdot \scalaire{u_i}{u_j}\]

ainsi que :

\[\scalaire{u_i}{A(u_j)} = \scalaire{A(u_i)}{u_j} = \lambda_i \cdot \scalaire{u_i}{u_j}\]

En soustrayant ces deux équations, on obtient :

\[(\lambda_j - \lambda_i) \cdot \scalaire{u_i}{u_j} = 0\]

Le produit scalaire doit s'annuler lorsque les valeurs propres diffèrent. Si toutes les valeurs propres sont distinctes, les vecteurs propres forment une suite orthonormée :

\[\scalaire{u_i}{u_j} = \indicatrice_{ij}\]

6.3.2 Orthogonalité par rapport à l'application linéaire

Si les vecteurs propres \(u_i \in \Omega\) sont orthonormés, on a :

\[\scalaire{u_i}{A(u_j)} = \lambda_j \cdot \scalaire{u_i}{u_j} = \lambda_j \cdot \indicatrice_{ij}\]

6.4 Représentation tensorielle

Supposons que la suite de vecteurs propres \((u_1,...,u_n)\) soit orthonormée. Pour tout \(x \in \combilin{u_1,...,u_n}\), on a alors :

\[x = \sum_i \scalaire{u_i}{x} \cdot u_i\]

et :

\begin{align} A(x) &= \sum_i \scalaire{u_i}{x} \cdot A(u_i) \\ &= \sum_i \lambda_i \cdot \scalaire{u_i}{x} \cdot u_i \end{align}

On peut donc représenter \(A\) sur \(\combilin{u_1,...,u_n}\) par le tenseur associé :

\[\mathcal{A} = \sum_i \lambda_i \cdot u_i \otimes u_i\]

de sorte que :

\[A(x) = \mathcal{A} \cdot x = \contraction{ \mathcal{A} }{1}{x}\]

6.5 Inverse

Supposons que les vecteurs propres \(u_i\) forment une base orthonormée de \(E\), et que les valeurs propres correspondantes \(\lambda_i\) soient non nulles. Si \(x,y \in E\) sont tels que \(A(x) = \mathcal{A} \cdot x = y\), on a :

\[y = \sum_i \scalaire{u_i}{y} \cdot u_i = \mathcal{A} \cdot x = \sum_i \lambda_i \cdot u_i \cdot \scalaire{u_i}{x}\]

On en déduit en comparant les coefficients de chaque vecteur \(u_i\) que \(\lambda_i \cdot \scalaire{u_i}{x} = \scalaire{u_i}{y}\), d'où :

\[\scalaire{u_i}{x} = \unsur{\lambda_i} \cdot \scalaire{u_i}{y}\]

Mais ces produits scalaires sont les coordonnées de \(x\) par rapport aux \(u_i\) :

\[x = \sum_i \scalaire{u_i}{x} \cdot u_i = \sum_i \unsur{\lambda_i} \cdot \scalaire{u_i}{y} \cdot u_i\]

Donc, si on pose :

\[\mathcal{A}^{-1} = \sum_i \unsur{\lambda_i} \cdot u_i \otimes u_i\]

on a :

\[x = \mathcal{A}^{-1} \cdot y\]

6.6 Représentation matricielle

On dit que \(\lambda \in \corps\) est la valeur propre de la matrice \(A \in \matrice(\corps,n,n)\) correspondant au vecteur propre non nul \(u \in \corps^n\) si ils sont valeurs et vecteurs propres de l'application linéaire sous-jacente :

\[A \cdot u = \lambda \cdot u\]

6.6.1 Formulation équivalente

On voit qu'il est équivalent de chercher un scalaire \(\lambda\) et un vecteur \(u \ne 0\) tel que :

\[(A - \lambda \cdot I) \cdot u = 0\]

6.6.2 Rapport de Rayleigh

On peut évaluer \(\lambda\) à partir de \(u\) en multipliant l'équation ci-dessus à gauche par \(u^\dual\). On obtient alors :

\[u^\dual \cdot A \cdot u = \lambda \cdot u^\dual \cdot u\]

et le rapport de Rayleigh en \(u\) s'en suit :

\[\lambda = \frac{u^\dual \cdot A \cdot u}{u^\dual \cdot u} = R(u)\]

6.7 Invariance

Soit la valeur propre \(\lambda\) de \(A\) et le vecteur propre correspondant \(u \ne 0\). On a :

\[A \cdot u = \lambda \cdot u\]

Multiplions cette équation à gauche par une matrice inversible \(Q\) :

\[Q \cdot A \cdot u = \lambda \cdot Q \cdot u\]

Posons à présent \(v = Q \cdot u\). On a alors \(u = Q^{-1} \cdot v\) et :

\[Q \cdot A \cdot Q^{-1} \cdot v = \lambda \cdot v\]

On constate aussi que \(v \ne 0\), car sinon :

\[0 \ne u = Q^{-1} \cdot v = Q^{-1} \cdot 0 = 0\]

ce qui est impossible. On en conclut que \(\lambda\) est aussi une valeur propre de la matrice :

\[B = Q \cdot A \cdot Q^{-1}\]

On dit que les valeurs propres sont des invariants sous transformation linéaire réversible.

6.8 Matrices triangulaires

Nous allons démontrer par récurrence sur la taille \(n\) d'une matrice triangulaire supérieure \(T\) que les composantes diagonales sont des valeurs propres de \(T\).

  • Si \(n = 1\), soit les uniques composantes \(\lambda = \composante_{11}(T)\) et \(\mu = \composante_1(u)\). On a :

\[T \cdot u = [\lambda] \cdot [\mu] = \lambda \cdot [1] \cdot [\mu] = \lambda \cdot u\]

ce qui montre que la composante diagonale \(\lambda\) est une valeur propre de \(T\).

  • Supposons que le résultat soit vrai pour \(n - 1\). Partitionnons à part la dernière ligne et la dernière colonne d'une matrice \(T \in \matrice(\corps,n,n)\) :

\( T =

\begin{Matrix}{cc} T^{(n-1)} & z \\ 0 & \lambda_n \end{Matrix}

\)

Donc, \(T^{(n-1)}\) est une matrice triangulaire de la forme :

\( T(n-1) =

\begin{Matrix}{ccc} \lambda_1 & \hdots & \hdots \\ 0 & \ddots & \hdots \\ 0 & 0 & \lambda_{n-1} \\ \end{Matrix}

\)

où les composantes diagonales \(\lambda_1,...,\lambda_{n-1}\) vérifient :

\[T^{(n-1)} \cdot u_i^{(n-1)} = \lambda_i \cdot u_i^{(n-1)}\]

pour certains vecteurs propres \(u_i^{(n-1)} \ne 0\). Nous allons chercher les vecteurs propres \(u \in \corps^n\) de \(T\) sous la forme :

\( u =

\begin{Matrix}{c} v \\ \mu \end{Matrix}

\)

où \(v \in \corps^{n - 1}\) et \(\mu \in \setC\). Si on choisit \(v = u_i^{(n-1)}\) pour \(i \in \{1,2,...,n-1\}\) et \(\mu = 0\), on a :

\begin{align} T \cdot u &= \begin{Matrix}{cc} T^{(n-1)} & z \\ 0 & \lambda_n \end{Matrix} \cdot \begin{Matrix}{c} u_i^{(n-1)} \\ 0 \end{Matrix} \\ &= \begin{Matrix}{c} T^{(n-1)} \cdot u_i^{(n-1)} \\ 0 \end{Matrix} = \begin{Matrix}{c} \lambda_i \cdot u_i^{(n-1)} \\ 0 \end{Matrix} \\ &= \lambda_i \cdot \begin{Matrix}{c} u_i \\ 0 \end{Matrix} = \lambda_i \cdot u \end{align}

Les valeurs propres de \(T^{(n-1)}\) sont donc également valeurs propres de \(T\). Il nous reste à examiner le cas de \(\lambda_n\). Posons :

\( A =

\begin{Matrix}{cccc} \lambda_1 - \lambda_n & \hdots & \hdots & \hdots \\ 0 & \ddots & \hdots & \hdots \\ 0 & 0 & \lambda_{n-1} - \lambda_n & \hdots \end{Matrix}

\)

On doit donc trouver un vecteur \(u \in \corps^n\) non nul tel que :

\( (T - λn ⋅ I) ⋅ u =

\begin{Matrix}{c} A \\ 0 \end{Matrix}

⋅ u =

\begin{Matrix}{c} A \cdot u \\ 0 \end{Matrix}

= 0 \)

Il suffit donc que \(u \ne 0\) vérifie \(A \cdot u = 0\). Mais comme \(A\) est de taille \((n - 1, n)\), le rang \(r\) vérifie \(r \le n - 1 \strictinferieur n\). Le système admet donc une infinité de solutions non nulles et \(\lambda_n\) est également une valeur propre de \(T\).

6.9 Forme de Schur

Soit une matrice carrée \(A\) de taille \((n,n)\). On choisit la valeur propre \(\lambda_1\) la plus grande de \(A\) et on évaluer un vecteur propre non nul correspondant \(u_1\) en résolvant le système :

\[(A - \lambda_1 \cdot I) \cdot u_1 = 0\]

On construit alors le complément orthogonal \((u_2, ..., u_n)\) tel que \((u_1,...,u_n)\) forme une suite orthonormée. On a donc \(u_j^\dual \cdot u_i = \indicatrice_{ij}\). Soit la matrice \(U\) de taille \((n,n)\) définie par :

\[U_1 = [u_1 \ u_2 \ ... \ u_n]\]

On a bien sur \(U_1^{-1} = U_1^\dual\) et :

\begin{align} A \cdot U_1 &= \begin{Matrix}{cccc} A \cdot u_1 & A \cdot u_2 & \hdots & A \cdot u_n \end{Matrix} \\ &= \begin{Matrix}{cccc} \lambda_1 \cdot u_1 & A \cdot u_2 & \hdots & A \cdot u_n \end{Matrix} \end{align}

En multipliant à gauche par la duale, on obtient :

\begin{align} U_1^\dual \cdot A \cdot U_1 &= \begin{Matrix}{cccc} (\lambda_1 \cdot u_1^\dual \cdot u_1) & (u_1^\dual \cdot A \cdot u_2) & \hdots & (u_1^\dual \cdot A \cdot u_n) \\ (\lambda_1 \cdot u_2^\dual \cdot u_1) & (u_2^\dual \cdot A \cdot u_2) & \hdots & (u_2^\dual \cdot A \cdot u_n) \\ \vdots & \vdots & \vdots & \vdots \\ (\lambda_1 \cdot u_n^\dual \cdot u_1) & (u_n^\dual \cdot A \cdot u_2) & \hdots & (u_n^\dual \cdot A \cdot u_n) \end{Matrix} \\ &= \begin{Matrix}{cccc} \lambda_1 & (u_1^\dual \cdot A \cdot u_2) & \hdots & (u_1^\dual \cdot A \cdot u_n) \\ 0 & (u_2^\dual \cdot A \cdot u_2) & \hdots & (u_2^\dual \cdot A \cdot u_n) \\ \vdots & \vdots & \vdots & \vdots \\ 0 & (u_n^\dual \cdot A \cdot u_2) & \hdots & (u_n^\dual \cdot A \cdot u_n) \end{Matrix} \\ \end{align}

ou, plus schématiquement :

\( U1^\dual ⋅ A ⋅ U1 =

\begin{Matrix}{cc} \lambda_1 & \hdots \\ 0 & A^{(n - 1)} \end{Matrix}

\)

On peut réitérer le même raisonnement en utilisant la plus grande valeur propre de \(A^{(n - 1)}\) et une matrice unitaire correspondante \(U^{(n - 1)}\). Posons :

\( U2 =

\begin{Matrix}{cc} 1 & 0 \\ 0 & U^{(n - 1)} \end{Matrix}

\)

On obtient :

\( U2^\dual ⋅ U1^\dual ⋅ A ⋅ U1 ⋅ U2 =

\begin{Matrix}{ccc} \lambda_1 & \hdots & \hdots \\ 0 & \lambda_2 & \hdots \\ 0 & 0 & A^{(n - 2)} \end{Matrix}

\)

On continue ainsi, en utilisant à l'étape \(k + 1\) la plus grande valeur propre de \(A^{(n - k)}\) et :

\( Uk + 1 =

\begin{Matrix}{cc} I_k & 0 \\ 0 & U^{(n-k)} \end{Matrix}

\)

On s'arrête évidemment lorsque \(k + 1 = n\). Posons :

\[U = U_1 \cdot ... \cdot U_n\]

On obtient à la fin du processus une matrice triangulaire :

\( U^\dual ⋅ A ⋅ U = T =

\begin{Matrix}{ccc} \lambda_1 & \hdots & \hdots \\ 0 & \ddots & \hdots \\ 0 & 0 & \lambda_n \end{Matrix}

\)

Comme :

\[U^{-1} = U_n^\dual \cdot ... \cdot U_1^\dual = U^\dual\]

on obtient, en multipliant la relation précédente à gauche par \(U\) et à droite par \(U^\dual\) la décomposition :

\[A = U \cdot T \cdot U^\dual\]

On appelle cette décomposition la forme de Schur et on la note :

\[(T,U) = \schur(A)\]

6.9.1 Valeurs propres

La matrice \(T\) étant triangulaire supérieure, ses éléments diagonaux sont des valeurs propres de \(T\). Par invariance sous transformation, on voit aussi que les valeurs propres de :

\[A = U \cdot T \cdot U^\dual = U \cdot T \cdot U^{-1}\]

sont égales aux valeurs propres de \(T\). La décomposition de Schur d'une matrice \(A\) nous permet donc de connaître les valeurs propres en examinant la matrice triangulaire obtenue.

6.9.2 Ordre

Nous allons montrer par récurrence sur la taille de \(A\) que les valeurs propres sont triées par ordre décroissant. Si \(n = 1\), il n'y a rien à montrer. Supposons à présent que le résultat soit vrai pour \(n - 1\). Soit :

\[(R,V) = \schur(A^{(n - 1)})\]

Par l'hypothèse de récurrence, \(R\) contient sur sa diagonale les valeurs propres de \(A^{(n - 1)}\) triées par ordre décroissant :

\[\lambda_2 \ge \lambda_3 \ge ...\]

Mais on a aussi :

\(

\begin{Matrix}{cc} 1 & 0 \\ 0 & V^\dual \end{Matrix}

⋅ U1^\dual ⋅ A ⋅ U1

\begin{Matrix}{cc} 1 & 0 \\ 0 & V \end{Matrix}

=

\begin{Matrix}{cc} \lambda_1 & \hdots \\ 0 & R \end{Matrix}

\)

Les valeurs propres de \(A^{(n - 1)}\) sont donc également les valeurs propres de \(A\). Par construction de l'algorithme, \(\lambda_1\) est la plus grande valeur propre et on a \(\lambda_1 \ge \max\{\lambda_2,...,\lambda_n\}\). On en conclut finalement que :

\[\lambda_1 \ge \lambda_2 \ge \lambda_3 \ge ...\]

6.10 Algorithme \(Q R\)

Le but est d'évaluer les valeurs propres d'une matrice \(A\). Pour cela, on tente d'obtenir une approximation de la forme de Schur. Il s'agit d'un algorithme itératif qui part de :

\[A_0 = A\]

A chaque itération \(k\), on décompose la matrice \(A_k\) obtenue à l'itération précédente en utilisant l'algorithme de Householder :

\[(Q_k, R_k) = \householder(A_k)\]

On a alors \(A_k = Q_k \cdot R_k\), avec \(Q_k^\dual = Q_k^{-1}\). On construit ensuite une nouvelle matrice \(A_{k+1}\) par :

\[A_{k + 1} = Q_k^\dual \cdot A_k \cdot Q_k = Q_k^\dual \cdot Q_k \cdot R_k \cdot Q_k = R_k \cdot Q_k\]

Au bout de \(p\) itérations, la matrice \(A_p\) produite par l'algorithme vérifie :

\[A_p = Q_p^\dual \cdot ... \cdot Q_0^\dual \cdot A \cdot Q_0 \cdot ... \cdot Q_p\]

En inversant cette relation, on obtient :

\[A = Q_0 \cdot ... \cdot Q_p \cdot A_p \cdot Q_p^\dual \cdot ... \cdot Q_0^\dual\]

En injectant l'identité \(A_p \cdot Q_p^\dual = R_p\), on arrive à :

\[A = Q_0 \cdot ... Q_p \cdot R_p \cdot Q_{p - 1}^\dual \cdot ... \cdot Q_0^\dual\]

Si les suites :

\[\mathcal{U}_p = Q_0 \cdot ... Q_p\]

et \(R_p\) convergent :

\( \lim_{p \to \infty} \mathcal{U}_p = U \\ \lim_{p \to \infty} R_p = R \)

on a bien évidemment :

\[\lim_{p \to \infty} \mathcal{U}_{p - 1}^\dual = U^\dual\]

On en déduit la forme approximative :

\[A = U \cdot R \cdot U^\dual \approx \mathcal{U}_N \cdot R_N \cdot \mathcal{U}_N^\dual\]

pour \(N\) suffisamment grand. Par invariance sous transformation réversible, les estimations des valeurs propres de \(A\) sont sur la diagonale de la matrice triangulaire supérieure \(R_N \approx R\). On peut se servir de ces estimations pour appliquer l'algorithme de Schur et construire une matrice triangulaire où les valeurs propres sont triées par ordre décroissant sur la diagonale.

6.11 Matrices hermitiennes

Si \(A\) est hermitienne (\(A = A^\dual)\), la forme de Schur \((T,U) = \schur(A)\) implique que :

\[A = U \cdot T \cdot U^\dual = A^\dual = U \cdot T^\dual \cdot U^\dual\]

On en déduit en multipliant à gauche par \(U^\dual\) et à droite par \(U\) que \(T = T^\dual\). Mais comme \(T\) est triangulaire supérieure, on a \(t_{ij} = \composante_{ij}(T) = 0\) si \(i \strictsuperieur j\). De l'autre coté de la diagonale, on a \(t_{ji} = \conjaccent{t}_{ij} = 0\). On en conclut que les seuls éléments potentiellement non nuls doivent se trouver sur la diagonale (\(i = j\)). La matrice \(T\) se réduit donc à une matrice diagonale formée à partir des valeurs propres \(\lambda_i\) (non nécessairement distinctes) de \(A\) :

\[T = \Lambda = \diagonale_n(\lambda_1,...,\lambda_n)\]

En multipliant \(A = U \cdot \Lambda \cdot U^\dual\) à droite par \(U\), on a :

\[A \cdot U = \Lambda \cdot U\]

Donc, si \(u_i = \colonne_i U\), on a :

\[A \cdot u_i = \lambda_i \cdot u_i\]

Les vecteurs propres sont donc donnés par les colonnes de \(U\). Comme \(U^\dual \cdot U = I\), on a la propriété d'orthonormalité :

\[u_i^\dual \cdot u_j = \indicatrice_{ij}\]

6.12 Théorème de Courant-Fisher

Soit une matrice hermitienne \(A\) et sa forme de Schur :

\[A = U \cdot \Lambda \cdot U^\dual\]

Nous posons :

\begin{align} \lambda_i &= \composante_{ii} \Lambda \\ u_i &= \colonne_i U \end{align}

pour les valeurs propres et vecteurs propres correspondants. Les valeurs propres étant triées par ordre décroissant, on a :

\[\lambda_1 \ge \lambda_2 \ge \lambda_3 \ge ...\]

On considère le rapport de Rayleigh défini par :

\[R(x) = \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

pour tout \(x \in \setC^n \setminus \{0\}\). Choisissons un tel \(x\). Comme les \(u_i\) forment une base orthonormée, on a :

\[x = \sum_{i = 1}^n a_i \cdot u_i\]

où \(a_i = \scalaire{u_i}{x}\) par orthonormalité. Le rapport s'écrit alors :

\begin{align} R(x) &= \frac{ \sum_{i,j = 1}^n \conjaccent{a}_i \cdot a_j \cdot u_i^\dual \cdot A \cdot u_j }{ \sum_{i,j = 1}^n \conjaccent{a}_i \cdot a_j \cdot u_i^\dual \cdot u_j} \\ \\ &= \frac{ \sum_{i = 1}^n \abs{a_i}^2 \cdot \lambda_i }{ \sum_{j = 1}^n \abs{a_j}^2 } \end{align}

Posons :

\[w_i = \frac{\abs{a_i}^2}{\sum_{j = 1}^n \abs{a_j}^2}\]

Il est clair que les \(w_i\) sont des réels positifs et que :

\[\sum_{i = 1}^n w_i = \frac{\sum_{i = 1}^n \abs{a_i}^2}{\sum_{j = 1}^n \abs{a_j}^2} = 1\]

On a alors :

\[R(x) = \sum_{i = 1}^n w_i \cdot \lambda_i\]

6.12.1 Propriétés extrémales

Nous allons analyser les extrema du rapport de Rayleigh sur les ensembles :

\begin{align} \mathcal{P}_m &= \combilin{u_1,u_2,...,u_m} \setminus \{0\} \\ \mathcal{Q}_m &= \mathcal{P}_{m - 1}^\orthogonal \setminus \{0\} \end{align}
  • Si \(x \in \mathcal{P}_m\), les seules coordonnées non nulles sont \(a_1,...,a_m\). Il en va donc de même des \(w_i\) et :

\[R(x) = \sum_{i = 1}^m w_i \cdot \lambda_i\]

On voit aussi que :

\begin{align} 1 = \sum_{i = 1}^n w_i &= \sum_{i = 1}^m w_i + \sum_{i = m + 1}^n w_i \\ &= \sum_{i = 1}^m w_i + 0 \\ &= \sum_{i = 1}^m w_i \end{align}

Les valeurs propres étant ordonnées par ordre décroissant, on a donc :

\[R(x) \ge \lambda_m \sum_{i = 1}^m w_i = \lambda_m\]

Cette borne inférieure est atteinte en \(u_m \in \mathcal{P}_m\) :

\[R(u_m) = \lambda_m\]

On en conclut que \(\lambda_m\) est le minimum de \(R\) sur l'espace \(\mathcal{P}_m\) :

\[\lambda_m = \min_{x \in \mathcal{P}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

et que \(u_m\) est solution du problème de minimisation :

\[u_m \in \arg\min_{x \in \mathcal{P}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

  • Si \(x \in \mathcal{Q}_m\), on doit avoir \(\scalaire{z}{x} = 0\) pour tout \(z \in \mathcal{P}_{m - 1}\), et en particulier :

\[a_k = \scalaire{u_k}{x} = 0\]

pour tout \(k \in \{1, ..., m - 1\}\). Les \(m - 1\) premières coordonnées sont nulles. Les \(m - 1\) premiers \(w_i\) le sont donc aussi et :

\[R(x) = \sum_{i = m}^n w_i \cdot \lambda_i\]

La somme des \(w_i\) se simplifie alors en :

\[\sum_{i = m}^n w_i = 1\]

Les valeurs propres étant ordonnées par ordre décroissant, on a donc :

\[R(x) \le \lambda_m \sum_{i = m}^n w_i = \lambda_m\]

Cette borne supérieure est atteinte en \(u_m \in \mathcal{Q}_m\) :

\[R(u_m) = \lambda_m\]

On en conclut que \(\lambda_m\) est le maximum de \(R\) sur l'espace \(\mathcal{Q}_m\) :

\[\lambda_m = \max_{x \in \mathcal{Q}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

et que \(u_m\) est solution du problème de maximisation :

\[u_m \in \arg\max_{x \in \mathcal{Q}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

6.12.2 Minimax

Soit \(m \in \setN\) et la collection d'espaces vectoriels de dimension \(m\) générés par des bases orthonormées :

\[\mathcal{D}_m = \{ \combilin{v_1,...,v_m} : v_i \in \setC^n, \ \scalaire{v_i}{v_j} = \delta_{ij} \text{ pour tout } i,j \in \{1,...,m\} \}\]

On définit des collections associées par :

\begin{align} \mathcal{V}_m &= \{ X \setminus \{0\} : X \in \mathcal{D}_m \} \\ \mathcal{W}_m &= \{ X^\orthogonal \setminus \{0\} : X \in \mathcal{D}_{m - 1} \} \end{align}
  • Soit \(X \in \mathcal{V}_m\) et la suite \((v_1,...,v_m)\) formant une base orthonormée de \(X\). Il est équivalent d'imposer la contrainte \(x \in X \cap \mathcal{Q}_m\), ou d'imposer simultanément que \(x \ne 0\) s'écrive :

\[x = \sum_{j = 1}^m a_j \cdot v_j\]

et que \(x\) soit orthogonal à \(u_1,...,u_{m - 1}\) :

\[\scalaire{u_i}{x} = \sum_{j = 1}^m \scalaire{u_i}{v_j} \cdot a_j = 0\]

pour tout \(i \in \{1,...,m - 1\}\). Soit la matrice \(C \in \matrice(\setC, m - 1, m)\) de composantes :

\[\composante_{ij} C = \scalaire{u_i}{v_j}\]

et le vecteur \(a = [a_1 \ ... \ a_m]^\dual\). On doit alors avoir \(C \cdot a = 0\). Cette matrice étant strictement longue, il existe une infinité de solution dans l'espace :

\[S = \{ a \in \setC^m : C \cdot a = 0 \}\]

On peut donc choisir \(a \ne 0\) dans \(S\) correspondant à un \(x \ne 0\) appartenant à \(X \cap \mathcal{Q}_m\). On a alors :

\[\min_{z \in X} R(z) \le R(x) \le \max_{z \in \mathcal{Q}_m} R(z) = \lambda_m\]

L'espace \(X\) produit donc un minimum inférieur ou égal à \(\lambda_m\). Le cas particulier \(X = \mathcal{P}_m \in \mathcal{V}_m\) atteignant la borne, on en déduit que :

\[\lambda_m = \max_{X \in \mathcal{V}_m} \min_{x \in X} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

  • Soit \(Y \in \mathcal{W}_m\). On peut alors trouver un \(X \in \mathcal{D}_{m - 1}\) tel que \(Y = X^\orthogonal \setminus \{0\}\). Soit la suite \((v_1,...,v_{m - 1})\) formant une base orthonormée de \(X\). Il est équivalent d'imposer la contrainte \(x \in Y \cap \mathcal{P}_m\), ou d'imposer simultanément que \(x \ne 0\) s'écrive :

\[x = \sum_{j = 1}^m a_j \cdot u_j\]

et que \(x\) soit orthogonal à \(v_1,...,v_{m - 1}\) :

\[\scalaire{v_i}{x} = \sum_{j = 1}^m \scalaire{v_i}{u_j} \cdot a_j = 0\]

pour tout \(i \in \{1,...,m - 1\}\). Soit la matrice \(C \in \matrice(\setC, m - 1, m)\) de composantes :

\[\composante_{ij} C = \scalaire{v_i}{u_j}\]

et le vecteur \(a = [a_1 \ ... \ a_m]^\dual\). On doit alors avoir \(C \cdot a = 0\). Cette matrice étant strictement longue, il existe une infinité de solution dans l'espace :

\[S = \{ a \in \setC^m : C \cdot a = 0 \}\]

On peut donc choisir \(a \ne 0\) dans \(S\) correspondant à un \(x \ne 0\) appartenant à \(Y \cap \mathcal{P}_m\). On a alors :

\[\lambda_m = \min_{z \in \mathcal{P}_m} R(z) \le R(x) \le \max_{z \in Y} R(z)\]

L'espace \(Y\) produit donc un maximum supérieur ou égal à \(\lambda_m\). Le cas particulier \(Y = \mathcal{Q}_m \in \mathcal{V}_m\) atteignant la borne, on en déduit que :

\[\lambda_m = \min_{Y \in \mathcal{W}_m} \max_{x \in Y} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

6.12.3 Remarque

Si les valeurs propres étaient ordonnées par ordre croissant :

\[\lambda_1 \le \lambda_2 \le \lambda_3 \le ...\]

on aurait bien entendu :

\[\lambda_m = \min_{X \in \mathcal{V}_m} \max_{x \in X} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x} = \max_{Y \in \mathcal{W}_m} \min_{x \in Y} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

6.12.4 Résolution numérique

Les propriétés extrémales nous offrent un moyen d'obtenir numériquement des approximations des valeurs et vecteurs propres d'une matrice hermitienne.

6.12.4.1 Valeur propre maximale

Nous allons nous servir d'un algorithme d'optimisation pour obtenir le maximum \(\lambda_1\) de \(R\) sur \(\mathcal{Q}_1 = \setR^n\). A titre d'exemple, nous choisissons « la plus grande montée », qui n'est rien d'autre que l'opposé de la plus grande descente. On part d'un vecteur \(x \ne 0\) et on considère l'itération \(k\) :

\[x_{k + 1} = x_k + \alpha_k \cdot \delta_k\]

où \(\alpha_k \in \setR\) et \(\delta_k \in \setR^n\). Soit \(J_k = (\partial R(x_k))^\dual\) et le développement :

\[R(x_{k + 1}) \approx R(x_k) + \alpha_k \cdot J_k^\dual \cdot \delta_k\]

On a vu que pour maximiser \(J_k^\dual \cdot \delta_k = \scalaire{J_k}{\delta_k}\) sur \(\boule(0,\norme{J_k})\), il suffit de choisir \(\delta_k = J_k\). On pose donc :

\[x_{k + 1} = x_k + \alpha_k \cdot J_k\]

Si \(H_k = \partial^2 R(x_k)\), la valeur optimale de \(\alpha_k\) s'écrit :

\[\alpha_k = \frac{J_k^\dual \cdot J_k}{J_k^\dual \cdot H_k \cdot J_k}\]

On peut aussi utiliser un autre algorithme de minimisation libre pour construire une suite \(x_k\) dont on espère que \(\lim_{k \to \infty} x_k = u_1\) et \(\lim_{k \to \infty} R(x_k) = \lambda_1\).

6.12.4.2 Autres valeurs propres

Supposons que l'on ait déjà obtenu une bonne approximation de \((\lambda_1,...,\lambda_{m - 1})\) et de \((u_1,...,u_{m - 1})\). Si on veut que \(x \in \mathcal{Q}_m\), il faut et il suffit d'imposer que :

\[\scalaire{u_1}{x} = ... = \scalaire{u_{m - 1}}{x} = 0\]

On est donc amenés à construire le complémentaire orthogonal \((v_m,...,v_n)\) de \((u_1,...,u_{m - 1})\) et à poser :

\[V = [v_m \ v_{m + 1} \ ... \ v_n]\]

On a alors \(\combilin{v_m,...,v_n} = \mathcal{Q}_m\). Pour tout \(x \in \mathcal{Q}_m\), on peut donc trouver \(z = [z_m \ ... \ z_n]^\dual \in \setR^{n - m + 1}\) tel que :

\[x = \sum_{i = m}^n z_i \cdot v_i = V \cdot z\]

On pose donc :

\[\varrho(z) = R(V \cdot z) = \frac{z^\dual \cdot V^\dual \cdot A \cdot V \cdot z}{z^\dual \cdot V^\dual \cdot V \cdot z}\]

Par orthonormalité, on a \(V^\dual \cdot V = I\). On est donc finalement amené à maximiser :

\[\varrho(z) = \frac{z^\dual \cdot V^\dual \cdot A \cdot V \cdot z}{z^\dual \cdot z}\]

sur \(\setR^{n - m + 1}\). Pour cela, on part de \(z_0 \ne 0\) et on itère :

\[z_{k + 1} = z_k + \alpha_k \cdot \partial \varrho(z_k)\]

où :

\[\alpha_k = \frac{\partial \varrho(z_k)^\dual \cdot \partial \varrho(z_k)}{\partial \varrho(z_k)^\dual \cdot \partial^2 \varrho(z_k) \cdot \partial \varrho(z_k)}\]

7 Valeurs singulières

7.1 Décomposition en valeurs singulières

Soit les espaces vectoriels \(E\) et \(F\) et une application linéaire \(A : E \mapsto F\) admettant un dual \(A^\dual : F \mapsto E\). Les applications \(A^\dual \circ A\) et \(A \circ A^\dual\) étant auto-adjointes, il y a fort à parier que leurs valeurs et vecteurs propres possèdent d'importantes propriétés.

Supposons que \(A^\dual \circ A\) admette les valeurs propres \(\lambda_i \in \corps\) triées par ordre décroissant ($λ1 ≥ λ2 ≥ λ3 ≥ …$) et correspondant aux vecteurs propres \(v_i \in E\) formant une suite orthonormée. On a donc :

\[A^\dual \circ A(v_i) = \lambda_i \cdot v_i\]

On voit que les vecteurs \(z_i = A(v_i) \in F\) possèdent la propriété :

\[A^\dual(z_i) = A^\dual \circ A(v_i) = \lambda_i \cdot v_i\]

et :

\[A \circ A^\dual(z_i) = A(\lambda_i \cdot v_i) = \lambda_i \cdot A(v_i) = \lambda_i \cdot z_i\]

Les \(z_i\) sont donc vecteurs propres de \(A \circ A^\dual\) de valeurs propres \(\lambda_i\) identiques à celles de \(A^\dual \circ A\). On a l'orthogonalité :

\( \scalaire{z_i}{z_j} = \scalaire{A(v_i)}{A(v_j)} = \scalaire{v_i}{A^\dual \circ A(v_j)} = \lambda_j \cdot \scalaire{v_i}{v_j} = \lambda_i \cdot \indicatrice_{ij} \)

On voit aussi que les valeurs propres sont positives :

\[\lambda_i = \scalaire{A(v_i)}{A(v_i)} \ge 0\]

Comme elles sont également triées par ordre décroissant, on a \(\lambda_1 \ge \lambda_2 \ge ... \ge \lambda_r \strictsuperieur 0\) pour un certain \(r \in \setN\), et \(\lambda_n = 0\) pour tout \(n \strictsuperieur r\). Dans la suite, nous nous restreignons aux valeurs propres non nulles. On peut alors poser :

\[\sigma_i = \sqrt{\lambda_i} \strictsuperieur 0\]

afin de normaliser les \(z_i\) :

\[u_i = \unsur{\sigma_i} \cdot z_i = \unsur{\sigma_i} \cdot A(v_i)\]

On a alors :

\[\scalaire{u_i}{u_j} = \scalaire{v_i}{v_j} = \indicatrice_{ij}\]

ainsi que :

\[A^\dual(u_i) = \frac{\lambda_i}{\sigma_i} \cdot v_i = \sigma_i \cdot v_i\]

Nous disposons donc des relations primales et duales :

\( A(v_i) = \sigma_i \cdot u_i \\ A^\dual(u_i) = \sigma_i \cdot v_i \)

Pour tout \(x \in \combilin{v_1,...,v_r}\), on a :

\[x = \sum_{i = 1}^r \scalaire{v_i}{x} \cdot v_i\]

et :

\begin{align} A(x) &= \sum_{i = 1}^r \scalaire{v_i}{x} \cdot A(v_i) \\ &= \sum_{i = 1}^r \scalaire{v_i}{x} \cdot \sigma_i \cdot u_i \end{align}

7.2 Représentation tensorielle

On conclut de ce qui précède que \(A\) peut être représentée sur \(\combilin{v_1,...,v_n}\) par le tenseur associé :

\[\mathcal{A} = \sum_{i = 1}^r \sigma_i \cdot u_i \otimes v_i\]

de sorte que :

\[A(x) = \mathcal{A} \cdot x = \contraction{ \mathcal{A} }{1}{x} = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot \scalaire{v_i}{x}\]

On appelle une telle représentation une décomposition en valeurs singulières.

7.3 Dualité

Le tenseur dual est donc :

\[\mathcal{A}^\dual = \sum_{i = 1}^r \sigma_i \cdot v_i \otimes u_i\]

7.3.1 Propriétés

On retrouve sans surprise les représentation de :

\begin{align} \mathcal{A}^\dual \cdot \mathcal{A} &= \sum_{i,j = 1}^r \sigma_i \cdot \sigma_j \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes v_j \\ &= \sum_{i = 1}^r \sigma_i^2 \cdot v_i \otimes v_i \end{align}

et de :

\begin{align} \mathcal{A} \cdot \mathcal{A}^\dual &= \sum_{i,j = 1}^r \sigma_i \cdot \sigma_j \cdot \scalaire{v_i}{v_j} \cdot u_i \otimes u_j \\ &= \sum_{i = 1}^r \sigma_i^2 \cdot u_i \otimes u_i \end{align}

en fonction de leurs valeurs et vecteurs propres.

7.4 Inverse

Supposons que \((v_1,...,v_r)\) forme une base de \(E\) et que \((u_1,...u_r)\) forme une base de \(F\). Soit \(x \in E\) et \(y \in F\) tels que \(y = A(x) = \mathcal{A} \cdot x\). On a :

\[y = \sum_{i = 1}^r \scalaire{u_i}{y} \cdot u_i = \mathcal{A} \cdot x = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot \scalaire{v_i}{x}\]

On en déduit en comparant que \(\sigma_i \cdot \scalaire{v_i}{x} = \scalaire{u_i}{y}\), ce qui nous donne les produits scalaires correspondant aux coordonnées de \(x\) par rapport aux \(v_i\) :

\[\scalaire{v_i}{x} = \unsur{\sigma_i} \cdot \scalaire{u_i}{y}\]

On a donc :

\[x = \sum_i \scalaire{v_i}{x} \cdot v_i = \sum_i \unsur{\sigma_i} \cdot \scalaire{u_i}{y} \cdot v_i\]

Donc, si on pose :

\[\mathcal{A}^{-1} = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i\]

on a :

\[x = \mathcal{A}^{-1} \cdot y\]

7.5 Pseudo-inverse

Nous ne supposons à présent plus que les suites de vecteurs \((u_1,...,u_r)\) et \((v_1,...,v_r)\) forment des bases de \(E\) et \(F\), mais nous définissons malgré tout par analogie le tenseur pseudo-inverse de \(A\) par :

\[\mathcal{A}^\pinverse = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i\]

Le pseudo-inverse \(A^\pinverse\) de l'application linéaire correspondante \(A\) est donc défini par :

\[A^\pinverse(y) = \mathcal{A}^\pinverse \cdot y = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot \scalaire{u_i}{y}\]

7.5.1 Tenseurs de projections

On voit que :

\begin{align} \mathcal{A}^\pinverse \cdot \mathcal{A} &= \sum_{i,j = 1}^r \unsur{\sigma_i} \cdot \sigma_j \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes v_j \\ &= \sum_{i = 1}^r v_i \otimes v_i \end{align}

correspond au tenseur de projection sur \(\combilin{v_1,...,v_r}\). De même :

\begin{align} \mathcal{A} \cdot \mathcal{A}^\pinverse &= \sum_{i,j = 1}^r \sigma_i \cdot \unsur{\sigma_j} \cdot \scalaire{v_i}{v_j} \cdot u_i \otimes u_j \\ &= \sum_{i = 1}^r u_i \otimes u_i \end{align}

correspond au tenseur de projection sur \(\combilin{u_1,...,u_r}\).

7.5.2 Dualité

On a clairement :

\( (\mathcal{A} \cdot \mathcal{A}^\pinverse)^\dual = \mathcal{A} \cdot \mathcal{A}^\pinverse \\ (\mathcal{A}^\pinverse \cdot \mathcal{A})^\dual = \mathcal{A}^\pinverse \cdot \mathcal{A} \)

7.5.3 Produits

On déduit des résultats ci-dessus que :

\begin{align} \mathcal{A} \cdot \mathcal{A}^\pinverse \cdot \mathcal{A} &= \sum_{i,j = 1}^r \sigma_i \cdot \scalaire{v_i}{v_j} \cdot u_i \otimes v_j \\ &= \sum_{i = 1}^r \sigma_i \cdot u_i \otimes v_i \\ &= \mathcal{A} \end{align}

et :

\begin{align} \mathcal{A}^\pinverse \cdot \mathcal{A} \cdot \mathcal{A}^\pinverse &= \sum_{i,j = 1}^r \unsur{\sigma_i} \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes u_j \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i \\ &= \mathcal{A}^\pinverse \end{align}

7.5.4 Orthogonalité

Soit le tenseur identité \(\tenseuridentite\). On déduit de ce qui précède les propriétés d'orthogonalité :

\( \mathcal{A} \cdot (\tenseuridentite - \mathcal{A}^\pinverse \cdot \mathcal{A}) = 0 \\ \mathcal{A}^\pinverse \cdot (\tenseuridentite - \mathcal{A} \cdot \mathcal{A}^\pinverse) = 0 \)

7.6 Représentation matricielle

Soit une matrice \(A \in \matrice(\corps,m,n)\) et \(p = \min \{ m , n \}\). L'algorithme de décomposition en valeurs singulières est très simple. On évalue :

\( (\Lambda_1, U) = \schur(A \cdot A^\dual) \\ (\Lambda_2, V) = \schur(A^\dual \cdot A) \)

On a alors \(U,\Lambda_1 \in \matrice(\corps,n,n)\) et \(V,\Lambda_2 \in \matrice(\corps,m,m)\). Comme les matrices \(A^\dual \cdot A\) et \(A \cdot A^\dual\) sont hermitiennes et que leurs valeurs propres sont identiques, les matrices « triangulaires » obtenues sont en fait diagonales et :

\( \Lambda_1 = \diagonale_n(\lambda_1,...\lambda_p) \\ \Lambda_2 = \diagonale_m(\lambda_1,...\lambda_p) \)

On pose alors \(\sigma_i = \sqrt{\lambda_i}\) pour \(i \in \{1,2,...,p\}\) et on a \(\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_r \strictsuperieur 0\) et \(\sigma_{r + 1} = ... = \sigma_p = 0\). Les colonnes de \(U\) et de \(V\) sont les vecteurs propres correspondant :

\( u_i = \colonne_i U \\ v_i = \colonne_i V \)

On a également \(U^{-1} = U^\dual\) et \(V^{-1} = V^\dual\). La décomposition en valeurs singulières de \(A\) s'écrit :

\[A = \sum_{i = 1}^r \sigma_i \cdot u_i \otimes v_i = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot v_i^\dual\]

Si nous posons :

\[S = \diagonale_{m,n}(\sigma_1,...,\sigma_r)\]

on peut réécrire la décomposition de \(A\) sous la forme :

\[A = U \cdot S \cdot V^\dual\]

On note alors :

\[(U,S,V) = \singuliere(A)\]

7.7 Pseudo-inverse

Le pseudo-inverse est donné par :

\[A^\pinverse = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot u_i^\dual\]

On a donc :

\[S^\pinverse = \diagonale_{n,m}\left(\unsur{\sigma_1},...,\unsur{\sigma_r}\right)\]

et :

\[A^\pinverse = V \cdot S^\pinverse \cdot U^\dual\]

7.8 Systèmes linéaires

7.8.1 Moindres carrés

Soit la matrice \(A \in \matrice(\corps,m,n)\), le vecteur matriciel \(b \in \corps^m\) et l'erreur produite par \(x \in \corps^n\) :

\[e(x) = b - A \cdot x\]

On dit aussi que \(e(x)\) est le résidu du système en \(x\). Nous allons tenter de minimiser :

\[\mathcal{E}(x) = e(x)^\dual \cdot e(x) = \norme{e(x)}^2\]

en utilisant la décomposition en valeurs singulières \(A = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot v_i^\dual\). Comme \((v_1,...,v_n)\), suite orthonormée et linéairement indépendante, forme une base de \(\corps^n\), on peut exprimer \(x\) en fonction de ses coordonnées dans cette base :

\[x = \sum_{i = 1}^n x_i \cdot v_i = \sum_{i = 1}^n \scalaire{v_i}{x} \cdot v_i\]

Comme \((u_1,...,u_m)\), suite orthonormée et linéairement indépendante, forme une base de \(\corps^m\), on peut exprimer \(b\) comme :

\[b = \sum_{i = 1}^m \scalaire{u_i}{b} \cdot u_i\]

On a également :

\[A \cdot x = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot \scalaire{v_i}{x} = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot x_i\]

On en conclut que l'erreur s'écrit :

\[e(x) = \sum_{i = 1}^r (\scalaire{u_i}{b} - \sigma_i \cdot x_i) \cdot u_i + \sum_{i = r + 1}^m \scalaire{u_i}{b} \cdot u_i\]

Posons :

\( ei(x) =

\begin{cases} \scalaire{u_i}{b} - \sigma_i \cdot x_i & \text{ si } i \in \{1,...,r\} \\ \scalaire{u_i}{b} & \text{ si } i \in \{r + 1, ...,m\} \\ \end{cases}

\)

On a alors \(e(x) = \sum_{i = 1}^m e_i(x) \cdot u_i\) et :

\[\mathcal{E}(x) = \norme{e(x)}^2 = \sum_{i,j = 1}^m \conjaccent{e}_i(x) \cdot e_j(x) \cdot u_i^\dual \cdot u_j = \sum_{i = 1}^m \abs{e_i(x)}^2\]

On a donc :

\[\mathcal{E}(x) = \sum_{i = 1}^r \abs{\scalaire{u_i}{b} - \sigma_i \cdot x_i}^2 + \sum_{i = r + 1}^m \abs{\scalaire{u_i}{b}}^2\]

Dans le cas où l'on travaille avec des réels, l'annulation de la dérivée par rapport aux \(x_i\) nous donne :

\[2 (\scalaire{u_i}{b} - \sigma_i \cdot x_i) = 0\]

lorsque \(i \in \{1,...,r\}\). Nous n'avons par contre aucune contrainte sur \(x_{r + 1},...,x_n\). Un choix satisfaisant les conditions ci-dessus est donc :

\( xi =

\begin{cases} \scalaire{u_i}{b} / \sigma_i & \text{ si } i \in \{1,...,r\} \\ 0 & \text{ si } i \in \{r + 1, ...,n\} \\ \end{cases}

\)

Notre \(x\) potentiellement optimal s'écrit donc :

\[x = \sum_{i = 1}^r \unsur{\sigma_i} \cdot \scalaire{u_i}{b} \cdot v_i\]

La somme ressemble à une expression faisant intervenir le pseudo-inverse. En effet, on a :

\[A^\pinverse \cdot b = \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot \scalaire{u_i}{b} = x\]

Considérons à présent le cas général complexe. On voit que pour le choix \(x = A^\pinverse \cdot b\) :

\[\mathcal{E}(x) = \sum_{i = r + 1}^m \abs{\scalaire{u_i}{b}}^2\]

On en déduit la borne inférieure de l'erreur :

\[\mathcal{E}(z) = \sum_{i = 1}^r \abs{\scalaire{u_i}{b} - \sigma_i \cdot \scalaire{v_i}{z}}^2 + \sum_{i = r + 1}^m \abs{\scalaire{u_i}{b}}^2 \ge \sum_{i = r + 1}^n \abs{\scalaire{u_i}{b}}^2 = \mathcal{E}(x)\]

pour tout \(z \in \setC^n\). Le choix \(x = A^\pinverse \cdot b\) minimise bien la norme de l'erreur sur \(\setC^n\) :

\[x = A^\pinverse \cdot b \in \arg\min_{z \in \setC^n} \mathcal{E}(z)\]

Les \(x_{r + 1},...,x_n\) étant des complexes arbitraires, nous allons montrer que l'ensemble optimal s'écrit :

\[\arg\min_{z \in \setC^n} \mathcal{E}(z) = \Gamma = \left\{ \left(A^\pinverse \cdot b + \sum_{i = r + 1}^n x_i \cdot v_i \right) : \ x_{r + 1},...,x_n \in \setC \right\}\]

En effet, on a \(\mathcal{E}(z) = \mathcal{E}(x)\) pour tout \(z \in \Gamma\). On voit aussi que tout choix de \(z \notin \Gamma\) provoque :

\[\sum_{i = 1}^r \abs{\scalaire{u_i}{b} - \sigma_i \cdot \scalaire{v_i}{z}}^2 \strictsuperieur 0\]

et donc \(\mathcal{E}(z) \strictsuperieur \mathcal{E}(x)\).

7.8.2 Projection

On peut réécrire \(\Gamma\) sous la forme :

\[\Gamma = \{ A^\pinverse \cdot b \} + \combilin{v_{r + 1},...,v_n}\]

Soit la matrice de projection :

\[P = \sum_{i = r + 1}^n v_i \otimes v_i\]

On sait que \(P \cdot z \in \combilin{v_{r + 1},...,v_n}\) pour tout \(z \in \setC^n\) et que \(P \cdot y = y\) pour tout \(y \in \combilin{v_{r + 1},...,v_n}\). On en conclut que tout \(x \in \Gamma\) peut s'écrire sous la forme :

\[x = A^\pinverse \cdot b + P \cdot z\]

pour un certain \(z \in \corps^n\). La matrice de projection \(P\) est également la complémentaire de la projection sur \(\combilin{v_1,...,v_r}\). Or, on a a vu que \(A^\pinverse \cdot A\) est précisément cette matrice de projection. On retrouve donc fort logiquement :

\[I - A^\pinverse \cdot A = \sum_{i = 1}^n v_i \otimes v_i - \sum_{i = 1}^r v_i \otimes v_i = \sum_{i = r + 1}^n v_i \otimes v_i = P\]

On a donc en définitive des vecteurs optimaux de la forme :

\[x = A^\pinverse \cdot b + (I - A^\pinverse \cdot A) \cdot z\]

7.8.3 Solutions

Soit l'espace des solutions :

\[S = \{ x \in \setC^n : A \cdot x = b \} = \{ x \in \setC^n : \mathcal{E}(x) = 0 \}\]

Si \(\scalaire{u_{r + 1}}{b} = ... = \scalaire{u_m}{b} = 0\), le minimum de l'erreur est nul et \(\mathcal{E}(x) = 0\) pour tout \(x \in \Gamma\). On en conclut que \(x \in S\), d'où \(\Gamma \subseteq S\). D'un autre coté, tout \(z \in S\) minimise \(\mathcal{E}(z) = 0\). On a donc également \(S \subseteq \Gamma\) et finalement \(\Gamma = S\).

Inversément, si \(S \ne \emptyset\), on conclut que \(\scalaire{u_{r + 1}}{b} = ... = \scalaire{u_m}{b} = 0\).

7.8.4 Norme contrainte

Supposons que \(S \ne \emptyset\). Soit \(x \in \Gamma = S\), que l'on écrit sous la forme :

\begin{align} x &= A^\pinverse \cdot b + \sum_{i = r + 1}^n x_i \cdot v_i \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \cdot \scalaire{u_i}{b} + \sum_{i = r + 1}^n x_i \cdot v_i \\ \end{align}

Par orthonormalité des \(v_i\), on a :

\[\norme{x}^2 = x^\dual \cdot x = \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot \abs{\scalaire{u_i}{b}}^2 + \sum_{i = r + 1}^n \abs{x_i}^2\]

On voit que :

\[\norme{x}^2 \ge \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot \abs{\scalaire{u_i}{b}}^2 = \norme{A^\pinverse \cdot b}^2\]

On en conclut que le choix \(x = A^\pinverse \cdot b\) minimise la norme de \(x\) sur \(S\) :

\[A^\pinverse \cdot b \in \arg\min_{z \in S} \norme{z}^2\]

7.8.5 Lien avec les résultats précédents

  • On a montré précédemment en dérivant les expressions matricielles que le choix :

\[x = (A^\dual \cdot A)^{-1} \cdot A^\dual \cdot b\]

minimise également l'erreur \(\mathcal{E}\) sur \(\setR^n\) lorsque l'inverse de \(A^\dual \cdot A\) existe. Si tel est le cas, on a :

\[(A^\dual \cdot A)^{-1} = \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot v_i \otimes v_i\]

et :

\begin{align} (A^\dual \cdot A)^{-1} \cdot A^\dual &= \sum_{i,j = 1}^r \frac{\sigma_j}{\sigma_i^2} \cdot \scalaire{v_i}{v_j} \cdot v_i \otimes u_j \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i = A^\pinverse \end{align}
  • On a vu aussi en utilisant les multiplicateurs de lagrange que le choix :

\[x = A^\dual \cdot (A \cdot A^\dual)^{-1} \cdot b\]

minimise également la norme de \(x\) sur \(S\) lorsque l'inverse de \(A \cdot A^\dual\) existe. Si tel est le cas, on a :

\[(A \cdot A^\dual)^{-1} = \sum_{i = 1}^r \unsur{\sigma_i^2} \cdot u_i \otimes u_i\]

et :

\begin{align} A^\dual \cdot (A \cdot A^\dual)^{-1} &= \sum_{i,j = 1}^r \frac{\sigma_i}{\sigma_j^2} \cdot \scalaire{u_i}{u_j} \cdot v_i \otimes u_j \\ &= \sum_{i = 1}^r \unsur{\sigma_i} \cdot v_i \otimes u_i = A^\pinverse \end{align}

7.9 Image et noyau

Tout vecteur \(b = A \cdot x = \sum_{i = 1}^r \sigma_i \cdot \scalaire{v_i}{x} \cdot u_i\) est exprimé comme une combinaison linéaire des \((u_1,...,u_r)\). On en conclut que \(\image A \subseteq \combilin{u_1,...,u_r}\). Réciproquement, si \(b \in \combilin{u_1,...,u_r}\), on a \(\scalaire{u_{r + 1}}{b} = \scalaire{u_m}{b} = 0\) et l'espace des solutions \(\{ x \in \setC^n : A \cdot x = b\}\) n'est pas vide. On en conclut que \(\combilin{u_1,...,u_r} \subseteq \image A\). D'où finalement :

\[\image A = \combilin{u_1,...,u_r}\]

Tout vecteur \(z \in \combilin{v_{r + 1},...,v_n}\) vérifie \(\scalaire{v_1}{z} = ... = \scalaire{v_r}{z} = 0\). On en déduit que \(A \cdot z = \sum_{i = 1}^r \sigma_i \cdot 0 \cdot u_i = 0\) et que \(\combilin{v_{r + 1},...,v_n} \subseteq \noyau A\). Réciproquement, si \(z \in \noyau A\), on a \(\sum_{i = 1}^r \sigma_i \cdot \scalaire{v_i}{z} \cdot u_i = 0\) ce qui implique \(\scalaire{v_1}{z} = ... = \scalaire{v_r}{z} = 0\). On en conclut que \(\noyau A \subseteq \combilin{v_{r + 1},...,v_n}\). D'où finalement :

\[\noyau A = \combilin{v_{r + 1},...,v_n}\]

7.10 Normes

La décomposition en valeurs singulières permet d'évaluer facilement la norme usuelle des applications linéaires :

\[\norme{A}_\lineaire = \sup_{x \ne 0} \frac{\norme{A \cdot x}}{\norme{x}} = \max \{\sigma_1,...,\sigma_r\}\]

ainsi que la norme de Frobénius :

\[\norme{A}_F = \sqrt{A^\dual : A} = \sqrt{\sum_{i = 1}^r \sigma_i^2}\]

7.11 Fonctions de matrices

La décomposition en valeurs singulières permet d'étendre la définition d'une fonction \(f : \setR \mapsto \setR\). Soit la décomposition de \(A\) :

\[A = \sum_{i = 1}^r \sigma_i \cdot u_i \cdot v_i^\dual\]

On définit alors :

\[f(A) = \sum_{i = 1}^r f(\sigma_i) \cdot u_i \cdot v_i^\dual\]

8 Espaces de Hilbert

8.1 Définition

Un espace de Hilbert \(H\) est un espace de Banach dont la distance découle d'un produit scalaire \(\scalaire{}{}\) défini sur \(H\) :

\[\distance(u,v) = \norme{u - v} = \sqrt{\scalaire{u - v}{u - v}}\]

Dans la suite, nous considérons un espace de Hilbert \(H\) sur \(\corps\).

8.2 Utilisation

Les espaces de Hilbert permettent de généraliser en dimension infinie nombre de résultats valables en dimension finie. Parmi eux, les espaces fonctionnels sont très utilisés. Ils permettent entre-autres de relier la solution de certaines équations différentielles à des problèmes de minimisation.

8.3 Complétude du noyau

Soit \(\varphi \in H^\dual\) et une suite de Cauchy \(\{x_1,x_2,...\} \subseteq \noyau \varphi \subseteq H\). L'espace \(H\) étant complet, cette suite converge vers \(x \in H\). Par continuité de \(\varphi\), on a :

\[\forme{\varphi}{x} = \lim_{n \to \infty} \forme{\varphi}{x_n} = 0\]

On en conclut que \(x \in \noyau \varphi\). L'espace vectoriel \(\noyau \varphi\) est donc complet.

8.4 Complétude de l'image

Soit l'application linéaire continue \(A : H \mapsto H\) et une suite de Cauchy \(\{y_1,y_2,...\} \subseteq \image A \subseteq H\). L'espace \(H\) étant complet, cette suite converge vers \(y \in H\). Comme les \(y_i \in \image A\), on peut trouver des \(x_i \in H\) tels que \(A(x_i) = y_i\). Par continuité de \(A\), on a :

\[y = \lim_{n \to \infty} y_n = \lim_{n \to \infty} A(x_n) = A(x) \in \image A\]

On en conclut que \(y \in \image A\). L'espace vectoriel \(\image A\) est donc complet.

8.5 Complétude de l'espace orthogonal

Soit \(V \subseteq H\). Considérons une suite de Cauchy \(\{x_1,x_2,...\} \subseteq V^\orthogonal \subseteq H\). Comme \(H\) est complet, cette suite est convergente vers \(x \in H\). Choisissons \(z \in V\). On a :

\[\scalaire{x - x_n}{z} = \scalaire{x}{z} - \scalaire{x_n}{z} = \scalaire{x}{z}\]

On en déduit que :

\[\abs{\scalaire{x}{z}} = \abs{\scalaire{x - x_n}{z}} \le \norme{x - x_n} \cdot \norme{z}\]

Comme cette relation doit être valable pour tout \(n\) et que \(\norme{x - x_n}\) converge vers \(0\), on en déduit que :

\[\scalaire{x}{z} = 0\]

c'est-à-dire \(x \in V^\orthogonal\). On en conclut que \(V^\orthogonal\) est un espace complet.

8.6 Théorème de projection

\begin{theoreme} Soit $V \subseteq H$ un sous-espace vectoriel complet. Pour tout $x \in H$, il existe un unique $u \in V$ vérifiant : \norme{$$x - u} = \inf_{z \in V} \norme{x - z} = \distance(x,V)$$ \end{theoreme} \begin{demonstration} Soit $x \in H$ et : $$D = \{ \norme{x - z} : z \in V \} \subseteq \setR$$ L'ensemble $D$ est inclu dans $\setR$ et minoré puisque $0 \le D$. On en conclut que l'infimum $\lambda = \inf D$ existe. On a par définition $\distance(x,V) = \lambda$. Comme $D \subseteq \setR$, on a $\lambda \in \adh D$ et la distance au sens des réels est nulle : $$\distance(\lambda,D) = \inf_{r \in D} \abs{\lambda - r} = 0$$ On peut donc contruire une suite de $z_n \in V$ tels que : $$\lim_{n \to \infty} \norme{x - z_n} = \lambda$$ Choisissons $\epsilon \strictsuperieur 0$ et $m,n \in \setN$ tels que : $$\max\{\norme{x - z_m} , \norme{x - z_n} \} \le \lambda + \epsilon$$ et appliquons l'égalité du parallèlogramme à : #+BEGIN_CENTER \( v = x - z_m \\ w = x - z_n \) #+END_CENTER On a alors : #+BEGIN_CENTER \( v + w = 2 x - (z_m + z_n) \\ v - w = z_n - z_m \) #+END_CENTER et donc : $$\norme{2 x - (z_m + z_n)}^2 + \norme{z_n - z_m}^2 = 2 \left( \norme{x - z_m}^2 + \norme{x - z_m}^2 \right)$$ Comme : $$\norme{2 x - (z_m + z_n)}^2 = \norme{2 \left(x - \frac{z_m + z_n}{2}\right)}^2 = 4 \norme{x - \frac{z_m + z_n}{2}}^2$$ on peut réécrire ce résultat sous la forme : $$\norme{z_n - z_m}^2 + 4 \norme{x - \frac{z_m + z_n}{2}}^2 = 2 \left( \norme{x - z_m}^2 + \norme{x - z_m}^2 \right)$$ et donc : $$\norme{z_n - z_m}^2 = 2 \left( \norme{x - z_m}^2 + \norme{x - z_m}^2 \right) - 4 \norme{x - \frac{z_m + z_n}{2}}^2$$ Comme $V$ est un espace vectoriel, on a $(z_m + z_n)/2 \in V$. Donc, par définition de l'infimum : $$\norme{x - \frac{z_m + z_n}{2}} \ge \lambda$$ On a aussi : $$\norme{x - z_m}^2 + \norme{x - z_m}^2 \le 2 (\lambda + \epsilon)^2$$ On en déduit que : $$\norme{z_n - z_m}^2 \le 4 (\lambda + \epsilon)^2 - 4 \lambda^2 = 8 \lambda \cdot \epsilon + 4 \epsilon^2$$ ce qui montre que les $z_n$ forment une suite de Cauchy. L'espace $V$ étant complet, cette suite converge vers un certain $u \in V$. On a alors : $$\norme{x - u} = \lim_{n \to \infty} \norme{x - z_n} = \lambda = \distance(x,V)$$ Nous avons donc prouvé l'existence d'un vecteur $u \in V$ minimisant la distance à $x$. Supposons à présent que $u,v \in V$ vérifient : $$\norme{x - u} = \norme{x - v} = \lambda$$ Appliquons le parallélogramme à $u - x$ et $x - v$. On a : #+BEGIN_CENTER \( (u - x) + (x - v) = u - v \\ (u - x) - (x - v) = u + v - 2 x \) #+END_CENTER et : \begin{align} \norme{u - v}^2 + \norme{u + v - 2 x}^2 &= 2 ( \norme{u - x}^2 + \norme{x - v}^2 ) \\ &= 2 (\lambda^2 + \lambda^2) = 4 \lambda^2 \end{align} On en conclut que : \begin{align} \norme{u - v}^2 &= 4 \lambda^2 - \norme{u + v - 2 x}^2 \\ &= 4 \lambda^2 - 4 \norme{\frac{u + v}{2} - x}^2 \end{align} Mais comme $(u + v)/2 \in V$, on a : $$\norme{\frac{u + v}{2} - x}^2 \ge \lambda^2$$ et : $$0 \le \norme{u - v}^2 \le 4 \lambda^2 - 4 \lambda^2 = 0$$ Donc, $\norme{u - v} = 0$ et $u = v$, ce qui prouve l'unicité de la solution optimale. \end{demonstration}

8.7 Application projective

On peut donc définir l'application de projection \(P : H \mapsto V\) par :

\[\norme{x - P(x)} = \inf_{z \in V} \norme{x - z}\]

ou :

\[P(x) = \argument_H\inf_{z \in V} \norme{x - z}\]

Comme \(P(x) \in V\), cela revient à :

\[P(x) = \arg\min_{z \in V} \norme{x - z}\]

8.8 Orthogonalité

Soit \(x \in H\) et \(u = P(x)\). L'écart \(e = x - u\) possède-t-il les mêmes propriétés d'orthogonalité qu'en dimension finie ? Soit \(\alpha \in \corps\) et \(v \in V\). On a \(u + \alpha \cdot v \in V\) et donc :

\[\norme{x - u}^2 = \norme{e}^2 \le \norme{x - u - \alpha \cdot v}^2 = \norme{e - \alpha \cdot v}^2\]

En développant ce dernier membre, on obtient :

\[\norme{e}^2 \le \norme{e}^2 - 2 \Re(\alpha \cdot \scalaire{e}{v}) + \abs{\alpha}^2 \cdot \norme{v}^2\]

On en déduit que :

\[\abs{\alpha}^2 \cdot \norme{v}^2 - 2 \Re(\alpha \cdot \scalaire{e}{v}) \ge 0\]

Utilisant la définition du produit complexe, il vient :

\[\abs{\alpha}^2 \cdot \norme{v}^2 - 2 \Re(\alpha) \cdot \Re(\scalaire{e}{v}) + 2 \Im(\alpha) \cdot \Im(\scalaire{e}{v}) \ge 0\]

Choisissons \(\alpha = \gamma \in \setR\), avec \(\gamma \strictsuperieur 0\). On a \(\Re(\alpha) = \gamma\), \(\Im(\alpha) = 0\) et \(\abs{\alpha}^2 = \gamma^2\). Donc :

\[\gamma^2 \cdot \norme{v}^2 - 2 \gamma \cdot \Re(\scalaire{e}{v}) \ge 0\]

Si nous divisons par \(\gamma\) et que nous faisons passer le second terme dans le second membre, il vient :

\[2 \Re(\scalaire{e}{v}) \le \gamma \cdot \norme{v}^2\]

Comme ce doit être valable pour tout \(\gamma\) strictement positif, on en conclut que \(\Re(\scalaire{e}{v}) \le 0\). Recommençons le même procédée avec \(\alpha = - \gamma \strictinferieur 0\). On a :

\[\gamma^2 \cdot \norme{v}^2 + 2 \gamma \cdot \Re(\scalaire{e}{v}) \ge 0\]

et :

\[2 \Re(\scalaire{e}{v}) \ge - \gamma \cdot \norme{v}^2\]

Comme ce doit être valable pour tout \(\delta = - \gamma\) strictement négatif, on en conclut que \(\Re(\scalaire{e}{v}) \ge 0\). D'où finalement \(\Re(\scalaire{e}{v}) = 0\).

Choisissons à présent \(\alpha = \img \gamma\), où le réel \(\gamma \strictsuperieur 0\) et où \(\img = \sqrt{-1}\). On a \(\Re(\alpha) = 0\), \(\Im(\alpha) = \gamma\) et \(\abs{\alpha}^2 = \gamma^2\). Donc :

\[\gamma^2 \cdot \norme{v}^2 + 2 \gamma \cdot \Im(\scalaire{e}{v}) \ge 0\]

On en déduit que :

\[2 \Im(\scalaire{e}{v}) \ge - \gamma \cdot \norme{v}^2\]

Comme ce doit être valable pour tout \(\delta = - \gamma\) strictement négatif, on en conclut que \(\Im(\scalaire{e}{v}) \ge 0\). Recommençons le même procédée avec \(\alpha = - \img \gamma\), avec \(\gamma \strictsuperieur 0\). On a :

\[\gamma^2 \cdot \norme{v}^2 - 2 \gamma \cdot \Im(\scalaire{e}{v}) \ge 0\]

et :

\[2 \Im(\scalaire{e}{v}) \le \gamma \cdot \norme{v}^2\]

Comme ce doit être valable pour tout \(\gamma\) strictement positif, on en conclut que \(\Im(\scalaire{e}{v}) \le 0\). D'où finalement \(\Im(\scalaire{e}{v}) = 0\). Ce produit scalaire ayant des parties réelles et imaginaires nulles, il est nul :

\[\scalaire{e}{v} = 0\]

Cette relation d'orthogonalité étant valable pour tout \(v \in V\), on en conclut que \(e \in V^\orthogonal\).

8.9 Identité locale

Soit \(v \in V\). Il est clair que le choix \(u = v\) minimise la distance \(\norme{v - u} \ge 0\) sur \(u \in V\) puisque \(\norme{v - v} = 0\). Par unicité de la solution optimale, on en déduit que \(P(v) = v\) pour tout \(v \in V\).

8.10 Invariance

Comme \(v = P(x) \in V\) pour tout \(x \in H\), on a :

\[P^2(x) = P \circ P(x) = P(v) = v = P(x)\]

d'où \(P^2 = P\).

8.11 Somme directe

On peut donc exprimer tout \(x \in H\) comme une somme :

\[x = u + e\]

où \(u = P(x) \in V\) et \(e = x - P(x) \in V^\orthogonal\). Nous allons voir que cette décomposition est unique. Soit \(x \in H\) et les vecteurs \(u,v \in V\) et \(y,z \in V^\orthogonal\) tels que :

\[x = u + y = v + z\]

On a :

\[0 = \norme{x - x}^2 = \norme{u + y - v - z}^2 = \norme{(u - v) + (y - z)}^2\]

Comme \(u - v \in V\) et \(y - z \in V^\orthogonal\), on a \(\scalaire{u - v}{y - z} = 0\). On peut donc appliquer le théorème de Pythagore. On obtient :

\[0 = \norme{(u - v) + (y - z)}^2 = \norme{u - v}^2 + \norme{y - z}^2\]

ce qui n'est possible que si \(\norme{u - v} = \norme{y - z} = 0\), c'est-à-dire \(u = v\) et \(y = z\), ce qui prouve l'unicité de la décomposition. L'espace \(H\) est donc la somme directe de \(V\) et de \(V^\orthogonal\) :

\[H = V \bigoplus V^\orthogonal\]

8.12 Biorthogonal

  • Soit \(x \in V\). Pour tout \(z \in V^\orthogonal\), on a :

\[\scalaire{x}{z} = 0\]

Donc \(x \in (V^\orthogonal)^\orthogonal\) et \(V \subseteq (V^\orthogonal)^\orthogonal\).

  • Soit \(x \in (V^\orthogonal)^\orthogonal \subseteq H\). On pose \(u = P(x) \in V\) et \(v = x - P(x) \in V^\orthogonal\). On a donc \(x = u + v\). Par définition de \((V^\orthogonal)^\orthogonal\), on a :

\[\scalaire{x}{z} = 0\]

pour tout \(z \in V^\orthogonal\). Comme \(u \in V\), on a aussi \(\scalaire{u}{z} = 0\) et finalement :

\[0 = \scalaire{x}{z} = \scalaire{u}{z} + \scalaire{v}{z} = \scalaire{v}{z}\]

Si on choisit \(z = v\), cela donne \(\scalaire{v}{v} = 0\), d'où \(v = 0\) et \(x = u \in V\). On en conclut que \((V^\orthogonal)^\orthogonal \subseteq V\).

On conclut de ces deux inclusions que :

\[(V^\orthogonal)^\orthogonal = V\]

8.13 Théorème de représentation de Riesz

Nous allons à présent établir une équivalence entre les formes linéaires de \(H^\dual\) et le produit scalaire sur \(H\).

\begin{theoreme} Pour toute forme linéaire $\varphi \in H^\dual$, il existe un et un seul $u \in H$ tel que : $$\forme{\varphi}{x} = \scalaire{u}{x}$$ pour tout $x \in H$. On dit que $u$ représente $\varphi$ sur $H$. \end{theoreme} \begin{demonstration} Soit le noyau : $$N = \noyau \varphi = \{ x \in H : \forme{\varphi}{x} = 0 \}$$ - Si $N = H$, il suffit de choisir $u = 0$. On a alors : $$\forme{\varphi}{x} = 0 = \scalaire{0}{x} = \scalaire{u}{x}$$ pour tout $x \in H$. Pour prouver l'unicité, si on a aussi $v \in H$ représente également $\varphi$, le choix $x = v$ nous donne : $$\forme{\varphi}{v} = 0 = \scalaire{v}{v}$$ ce qui implique que $v = 0$. - Dans le cas contraire, on a $H \setminus N \ne \emptyset$. Comme $N$ est complet, on peut lui appliquer les résultats relatifs aux projections, dont la somme directe $H = N \bigoplus N^\orthogonal$. Choisissons $a \in H \setminus N$. On a $\forme{\varphi}{a} \ne 0$ et une unique décomposition $a = b + c$, où $b \in N$ et $c \in N^\orthogonal$. On a donc par définition $\forme{\varphi}{b} = 0$ et : $$0 \ne \forme{\varphi}{a} = \forme{\varphi}{b} + \forme{\varphi}{c} = \forme{\varphi}{c}$$ En partant de vecteurs de la forme $\gamma \cdot c$, où $\gamma \in \corps$, on peut obtenir la valeur de $\varphi$ en n'importe quel $x \in H$ : $$\forme{\varphi}{\gamma \cdot c} = \gamma \cdot \forme{\varphi}{c} = \forme{\varphi}{x}$$ Il suffit donc de choisir : $$\gamma = \frac{ \forme{\varphi}{x} }{ \forme{\varphi}{c} }$$ Considérons un $x \in H$ quelconque et sa décomposition unique $x = y + z$, où $y \in N$ et $z \in N^\orthogonal$. Si : $$w = \frac{ \forme{\varphi}{x} }{ \forme{\varphi}{c} } \cdot c$$ on a $\forme{\varphi}{w} = \forme{\varphi}{x}$. Posons $v = x - w$. On a alors : $$\forme{\varphi}{v} = \forme{\varphi}{x} - \forme{\varphi}{w} = 0$$ On en déduit que $v \in N$. Comme on a aussi $w \in N^\orthogonal$ et $x = v + w$, on conclut par unicité de la décomposition que $v = y$ et $w = z$. Pour tout $u \in H$, on a : $$\scalaire{u}{x} = \scalaire{u}{v} + \scalaire{u}{w}$$ Par analogie avec $\forme{\varphi}{v} = 0$, on voudrait bien que $\scalaire{u}{v} = 0$. Pour cela, il suffit de choisir $u \in N^\orthogonal$, par exemple $u = \lambda \cdot c$ pour un certain $\lambda \in \corps$. Si on veut que $u$ représente $\varphi$, il faut en particulier que $\scalaire{u}{c} = \forme{\varphi}{c}$, c'est-à-dire : $$\scalaire{\lambda \cdot c}{c} = \conjaccent{\lambda} \cdot \scalaire{c}{c} = \forme{\varphi}{c}$$ d'où : $$\lambda = \frac{ \conjaccent{\forme{\varphi}{c}} }{ \scalaire{c}{c} }$$ et : $$u = \frac{ \conjaccent{\forme{\varphi}{c}} }{ \scalaire{c}{c} } \cdot c$$ Soit $x \in H$. On a la décomposition : $$x = \frac{ \forme{\varphi}{x} }{ \forme{\varphi}{c} } \cdot c + v$$ où $v \in N$. Donc : \begin{align} \scalaire{u}{x} &= \frac{ \forme{\varphi}{x} }{ \forme{\varphi}{c} } \cdot \frac{ \forme{\varphi}{c} }{ \scalaire{c}{c} } \cdot \scalaire{c}{c} + \scalaire{u}{v} \\ &= \forme{\varphi}{x} \end{align} Nous avons prouvé l'existence d'un $u \in H$ représentant $\varphi$. Pour l'unicité, si $u$ et $p$ représentent $\varphi$, on a : $$\scalaire{u - p}{x} = \scalaire{u}{x} - \scalaire{p}{x} = \forme{\varphi}{x} - \forme{\varphi}{x} = 0$$ pour tout $x \in H$, et en particulier pour $x = u - p$, d'où : $$\norme{u - p}^2 = \scalaire{u - p}{u - p} = 0$$ ce qui implique $u - p = 0$ et donc $u = p$. \end{demonstration}

8.14 Extension aux formes bilinéaires

\begin{theoreme} Si $\vartheta : H \times H \mapsto \corps$ est une forme bilinéaire de norme finie sur $H$, il existe une unique application linéaire et continue $A : H \mapsto H$ telle que : $$\biforme{u}{\vartheta}{v} = \scalaire{A(u)}{v}$$ pour tout $u,v \in H$. \end{theoreme} \begin{demonstration} Pour tout $u \in H$, on définit la forme linéaire $\varphi_u : H \mapsto \corps$ par : $$\forme{\varphi_u}{x} = \biforme{u}{\vartheta}{x}$$ pour tout $x \in H$. Pour $u \in H$ fixé, $\varphi_u$ est continue car : $$\norme{\forme{\varphi_u}{x}} = \norme{\biforme{u}{\vartheta}{x}} \le \norme{\vartheta}_\lineaire \cdot \norme{u} \cdot \norme{x}$$ d'où $\norme{\varphi_u} \le {\vartheta}_\lineaire \cdot \norme{u} \strictinferieur +\infty$. On peut donc trouver un unique représentant $A(u) \in H$ tel que : $$\scalaire{A(u)}{x} = \forme{\varphi_u}{x} = \biforme{u}{\vartheta}{x}$$ pour tout $x \in H$, ce qui définit l'application $A : u \in H \mapsto A(u) \in H$. Cette application est linéaire car : \begin{align} \scalaire{A(\alpha \cdot u + \beta \cdot v)}{x} &= \biforme{\alpha \cdot u + \beta \cdot v}{\vartheta}{x} \\ &= \alpha \cdot \biforme{u}{\vartheta}{x} + \beta \cdot \biforme{v}{\vartheta}{x} \\ &= \alpha \cdot \scalaire{A(u)}{x} + \beta \cdot \scalaire{A(v)}{x} \end{align} pour tout $u,v,x \in H$ et $\alpha,\beta \in \corps$. Elle est également continue car : $$\norme{A(u)}^2 = \scalaire{A(u)}{A(u)} = \biforme{u}{\vartheta}{A(u)} \le \norme{\vartheta}_\lineaire \cdot \norme{u} \cdot \norme{A(u)}$$ On a donc soit $A = 0$ et a fortiori $A$ continue, soit : \norme{$$A(u)} \le \norme{\vartheta}_\lineaire \cdot \norme{u} \strictinferieur +\infty$$ \end{demonstration}

8.15 Application adjointe

\begin{theoreme} Soit une application $A : H \mapsto H$ linéaire et continue. Il existe une unique application $A^\dual : H \mapsto H$ telle que : $$\scalaire{A^\dual(v)}{u} = \scalaire{v}{A(u)}$$ pour tout $(u,v) \in H^2$. \end{theoreme} \begin{demonstration} Choisissons $v \in H$. L'application $\varphi_v : u \mapsto \scalaire{v}{A(u)}$ est une forme linéaire. Elle est continue car : $$\abs{\forme{\varphi_v}{u}} = \abs{\scalaire{v}{A(u)}} \le \norme{v} \cdot \norme{A(u)} \le \norme{v} \cdot \norme{A} \cdot \norme{u}$$ On a donc : $$\abs{\varphi_v} \le \norme{A} \cdot \norme{v}$$ Le théorème de Riesz nous dit qu'il existe un unique $A^\dual(v) \in H$ tel que : $$\scalaire{A^\dual(v)}{u} = \forme{\varphi_v}{u} = \scalaire{v}{A(u)}$$ pour tout $u \in H$. Comme ce résultat est également valable quel que soit $v \in H$, nous avons défini l'application $A^\dual : H \mapsto H$ demandée. \end{demonstration}

8.16 Théorème de Lax-Milgram

\begin{theoreme} Soit une forme bilinéaire $\vartheta : H \times H \mapsto \corps$ de norme finie. Nous supposons qu'il existe un réel $\varrho \strictsuperieur 0$ tel que : $$\biforme{u}{\vartheta}{u} \ge \varrho \cdot \norme{u}^2$$ pour tout $u \in H$. On dit que $\vartheta$ est coercive. Soit une forme linéaire et continue $\varphi : H \mapsto \corps$. Nous allons montrer qu'il existe un unique $s \in H$ tel que : $$\biforme{s}{\vartheta}{v} = \forme{\varphi}{v}$$ pour tout $v \in H$. \end{theoreme} \begin{demonstration} En appliquant le théorème de Riesz, on peut trouver un unique $f \in H$ qui représente $\varphi$ sur $H$ : $$\forme{\varphi}{v} = \scalaire{f}{v}$$ pour tout $v \in H$. On dispose aussi d'une application linéaire continue $A$ telle que : $$\biforme{u}{\vartheta}{v} = \scalaire{A(u)}{v}$$ pour tout $u,v \in H$. Pour tout $s$ vérifiant la condition du théorème, on doit donc avoir : $$\scalaire{f}{v} = \forme{\varphi}{v} = \biforme{s}{\vartheta}{v} = \scalaire{A(s)}{v}$$ et donc $\scalaire{f}{v} = \scalaire{A(s)}{v}$ pour tout $v \in H$. Par linéarité, on en déduit que : $$\scalaire{f - A(s)}{v} = 0$$ Le cas particulier $v = f - A(s)$ nous donne : $$\scalaire{f - A(s)}{f - A(s)} = \norme{f - A(s)}^2 = 0$$ On en déduit que $f - A(s) = 0$, autrement dit $A(s) = f$. On sait que l'image $V = \image A \subseteq H$ est un espace complet. On a dès lors la somme directe $H = V \bigoplus V^\orthogonal$. Soit $u \in V^\orthogonal$. On a $\scalaire{A(x)}{u} = 0$ pour tout $x \in H$. Le choix $x = u$ combiné avec la coercivité de $\vartheta$ nous donne : $$0 \le \varrho \cdot \norme{u}^2 \le \biforme{u}{\vartheta}{u} = \scalaire{A(u)}{u} = 0$$ Divisant alors par $\varrho$ strictement positif, on obtient $\norme{u}^2 = 0$, ce qui n'est possible que si $u = 0$. On en déduit que $V^\orthogonal = \{0\}$. Pour tout $x \in H$, on a donc la décomposition $x = y + 0 = y$ avec $y \in V$. On en déduit que $H = V = \image A$. Donc $f \in \image A$, ce qui prouve l'existence d'au moins un $s \in H$ tel que $A(s) = f$. D'un autre coté, si $s,t \in H$ vérifient $A(s) = A(t) = f$, on a $A(s - t) = A(s) - A(t) = f - f = 0$. Donc : $$0 \le \varrho \cdot \norme{s - t}^2 \le \biforme{s - t}{\vartheta}{s - t} = \scalaire{A(s - t)}{s - t} = \scalaire{0}{s - t} = 0$$ ce qui implique que $\norme{s - t}^2 = 0$, d'où $s = t$. La solution $s$ est donc unique. \end{demonstration}

8.16.1 Inverse

Nous avons également prouvé que pour tout \(v \in H\), il existe un unique \(u \in H\) vérifiant \(A(u) = v\). L'application \(A\) est donc inversible et \(A^{-1}(v) = u\).

8.17 Suite orthonormée

Si une suite \(\{ u_i \in H : i \in \setN\}\) vérifie :

\[\scalaire{u_i}{u_j} = \delta_{ij}\]

pour tout \(i,j \in \setN\), on dit qu'elle est orthonormée. Dans la suite, nous considérons une suite \(\{ u_i \in H : i \in \setN\}\) orthonormée.

8.18 Inégalité de Bessel

Soit \(x \in H\) et une suite orthonormée \(\{ u_i \in H : i \in \setN\}\). Par analogie avec les projections sur des espaces de dimension finie, on pose (sous réserve de convergence) :

\[p = \sum_{i = 1}^{+\infty} \scalaire{u_i}{x} \cdot u_i\]

Soit \(e = x - p\). On a :

\begin{align} \scalaire{u_k}{e} &= \scalaire{u_k}{x} - \sum_i \scalaire{u_i}{x} \scalaire{u_k}{u_i} \\ &= \scalaire{u_k}{x} - \sum_i \scalaire{u_i}{x} \delta_{ik} \\ &= \scalaire{u_k}{x} - \scalaire{u_k}{x} \\ &= 0 \end{align}

On en conclut que :

\[\scalaire{p}{e} = \sum_i \scalaire{x}{u_i} \cdot \scalaire{u_i}{e} = 0\]

On a donc :

\[\norme{x}^2 = \norme{p + e}^2 = \norme{p}^2 + \norme{e}^2\]

d'où :

\[\norme{x}^2 - \norme{p}^2 = \norme{e}^2 \ge 0\]

Par orthonormalité, la norme de \(p\) vérifie :

\[\norme{p}^2 = \sum_i \abs{\scalaire{u_i}{x}}^2\]

d'où :

\[\norme{x}^2 - \sum_i \abs{\scalaire{u_i}{x}}^2 \ge 0\]

c'est-à-dire :

\[\sum_i \abs{\scalaire{u_i}{x}}^2 \le \norme{x}^2\]

8.19 Base hilbertienne

Si, pour tout \(x \in H\), la suite des projections finies :

\[p_n = \sum_{i = 1}^n \scalaire{u_i}{x} \cdot u_i\]

converge vers \(x\) :

\[x = \lim_{n \to \infty} \sum_{i = 1}^n \scalaire{u_i}{x} \cdot u_i\]

au sens de la distance dérivant du produit scalaire, on dit que les \(u_i\) forment une base de Hilbert (ou une base hilbertienne) de \(H\). On a alors :

\[x = \sum_{i = 1}^{+\infty} \scalaire{u_i}{x} \cdot u_i\]

Les scalaires :

\[x_i = \scalaire{u_i}{x}\]

sont appelés les coordonnées de \(x\) par rapport aux \(u_i\). Dans la suite, nous considérons une suite \(\{ u_i \in H : i \in \setN \}\) formant une base hilbertienne de \(H\).

8.20 Egalité de Parseval

Soit \(x \in H\) et \(\epsilon \strictsuperieur 0\). On peut trouver un \(n \in \setN\) tel que :

\[D = \norme{x - \sum_{i = 1}^n \scalaire{u_i}{x} \cdot u_i} \le \epsilon\]

Mais les propriétés des projections nous disent que :

\[0 \le D^2 = \norme{x}^2 - \sum_{i = 1}^n \abs{\scalaire{u_i}{x}}^2\]

et donc :

\[0 \le \norme{x}^2 - \sum_{i = 1}^n \abs{\scalaire{u_i}{x}}^2 \le \epsilon^2\]

En faisant tendre \(n \to \infty\), on a \(\epsilon \to 0\) et donc :

\[0 \le \norme{x}^2 - \sum_{i = 1}^{+\infty} \abs{\scalaire{u_i}{x}}^2 \le 0\]

c'est-à-dire :

\[\norme{x}^2 = \sum_{i = 1}^{+\infty} \abs{\scalaire{u_i}{x}}^2\]

8.21 Produit scalaire

Soit \(x,y \in E\). On a :

\( x = \sum_{i = 1}^{+\infty} x_i \cdot u_i \\ y = \sum_{i = 1}^{+\infty} y_i \cdot u_i \)

où \(x_i = \scalaire{u_i}{x}\) et \(y_i = \scalaire{u_i}{y}\). Par orthonormalité, leur produit scalaire s'écrit :

\[\scalaire{x}{y} = \lim_{n \to \infty} \sum_{i = 1}^n \conjaccent{x}_i \cdot y_i\]

On a donc :

\[\scalaire{x}{y} = \sum_{i = 1}^{+\infty} \conjaccent{x}_i \cdot y_i\]

9 Théorie spectrale

9.1 Progression géométrique

Soit un espace de Hilbert \(H\) et une application linéaire \(A : H \mapsto H\). On voit que :

\begin{align} \sum_{k = 0}^n A^k &= \identite + A + A^2 + ... + A^n \\ A \circ \sum_{k = 0}^n A^k &= A + A^2 + A^3 + ... + A^{n + 1} \end{align}

En soustrayant ces deux équations, on obtient :

\[(\identite - A) \circ \sum_{k = 0}^n A^k = \identite - A^{n + 1}\]

On montre de même que :

\[\left[ \sum_{k = 0}^n A^k \right] \circ (\identite - A) = \identite - A^{n + 1}\]

9.1.1 Infinie

Si \(\norme{A} \strictinferieur 1\), on a \(\norme{A^n} \le \norme{A}^n \to 0\) lorsque \(n \to \infty\) et donc \(A^n \to 0\). On en déduit que :

\[(\identite - A) \circ \sum_{k = 0}^{+\infty} A^k = \lim_{n \to \infty} (\identite - A^{n + 1}) = \identite\]

On a aussi :

\[\left[ \sum_{k = 0}^{+\infty} A^k \right] \circ (\identite - A) = \identite\]

On en déduit que :

\[(\identite - A)^{-1} = \sum_{k = 0}^{+\infty} A^k\]

9.2 Convergence

Soit une application linéaire continue \(A : H \mapsto H\). Choisissons \(\lambda \in \setC\) tel que \(\norme{A} \strictinferieur \abs{\lambda}\). On a :

\[\norme{A^k} \le \norme{A}^k \strictinferieur \abs{\lambda}^k\]

Posons \(r = \norme{A} / \abs{\lambda} \strictinferieur 1\) et divisons par le module de \(\lambda\) puissance \(k\) :

\[\frac{ \norme{A^k} }{ \abs{\lambda}^k } \le \frac{ \norme{A}^k }{ \abs{\lambda}^k } = r^k \strictinferieur 1\]

On en déduit que :

\[\sum_{k = 0}^n \frac{ \norme{A^k} }{ \abs{\lambda}^k } \le \sum_{k = 0}^n r^k = \frac{1 - r^k}{1 - r} \le \unsur{1 - r}\]

La suite des :

\[S_n = \sum_{k = 0}^n \frac{ \norme{A^k} }{ \abs{\lambda}^k }\]

étant croissante et bornée, elle converge vers son supremum :

\[S = \sum_{k = 0}^{+\infty} \frac{ \norme{A^k} }{ \abs{\lambda}^k } = \lim_{n \to \infty} S_n = \sup_{n \in \setN} S_n\]

Soit \(x \in H\) et la suite définie par \(u_0 = x\) et :

\[u_n = \sum_{k = 0}^n \unsur{\lambda^k} \cdot A^k(x)\]

Pour tout \(m,n \in \setN\) avec \(m \ge n\), on a :

\[\norme{u_m - u_n} = \norme{\sum_{k = n + 1}^m \unsur{\lambda^k} \cdot A^k(x)} \le \sum_{k = n + 1}^m \frac{ \norme{A^k(x)} }{ \abs{\lambda}^k }\]

Majorons par la norme de \(A^k\), puis la norme de \(A\) puissance \(k\) :

\[\norme{u_m - u_n} \le \left[ \sum_{k = n + 1}^m \frac{ \norme{A^k} }{ \abs{\lambda}^k } \right] \cdot \norme{x} \le \left[ \sum_{k = n + 1}^m \frac{ \norme{A}^k }{ \abs{\lambda}^k } \right] \cdot \norme{x}\]

et effectuons le changement de variable \(i = k - (n + 1)\). Il vient :

\[\norme{u_m - u_n} \le \frac{ \norme{A}^{n + 1} }{ \abs{\lambda}^{n + 1} } \left[ \sum_{i = 0}^{m - n - 1} \frac{ \norme{A}^i }{ \abs{\lambda}^i } \right] \cdot \norme{x} = r^{n + 1} \cdot S_{m - n - 1} \cdot \norme{x}\]

Mais comme \(S_{m - n - 1} \le S\), on a finalement :

\[\norme{u_m - u_n} \le r^{n + 1} \cdot S \cdot \norme{x}\]

qui converge vers \(0\) lorsque \(n \to \infty\). La suite des \(u_n\) est donc de Cauchy et converge vers un certain \(L(x) \in H\), ce qui définit l'application \(L : H \mapsto H\), que l'on note :

\[L = \sum_{k = 0}^{+\infty} \unsur{\lambda^k} \cdot A^k\]

9.2.1 Continuité

Cette application est de norme finie et donc continue car pour tout \(n \in \setN\) :

\[\norme{u_n} \le \left[ \sum_{k = 0}^n \frac{ \norme{A}^k }{ \abs{\lambda}^k } \right] \cdot \norme{x} = \frac{ 1 - r^{n + 1} }{1 - r} \cdot \norme{x} \le \frac{\norme{x}}{1 - r}\]

On a donc :

\[\norme{L(x)} = \lim_{n \to \infty} \norme{u_n} \le \frac{\norme{x}}{1 - r}\]

d'où :

\[\norme{L} \le \unsur{1 - r}\]

9.2.2 Inverse

Comme l'application \(B = A / \lambda\) vérifie \(\norme{B} \strictinferieur 1\), on a :

\( (\lambda \cdot \identite - A) \circ (\unsur{\lambda} \cdot L) = (\identite - \unsur{\lambda} \cdot A) \circ L = \identite \\ (\unsur{\lambda} \cdot L) \circ (\lambda \cdot \identite - A) = L \circ (\identite - \unsur{\lambda} \cdot A) = \identite \)

et donc :

\[(\lambda \cdot \identite - A)^{-1} = \unsur{\lambda} \cdot L\]

9.3 Exponentielle

Soit une application linéaire continue \(A : H \mapsto H\). Sous réserve de convergence, on définit l'opérateur \(\exp(A)\) associé par :

\[\exp(A) = \sum_{k = 0}^{+\infty} \unsur{k !} \cdot A^k\]

On a donc :

\[\exp(A)(u) = \sum_{k = 0}^{+\infty} \unsur{k !} \cdot A^k(u)\]

pour tout \(u \in H\).

10 Calcul variationnel

10.1 Méthode des variations

Soit l'espace fonctionnel \(\mathcal{F}\) et la forme \(I : \mathcal{F} \mapsto \setR\). Un problème variationnel consiste à chercher une fonction \(u\) qui minimise \(I\) sur \(\mathcal{F}\) :

\[I(u) \le I(v)\]

pour tout \(v\in\mathcal{F}\). L'astuce consiste à transformer ce problème en considérant la famille de fonctions \(\{ J_w : w \in \mathcal{F} \}\) définies par :

\[J_w(\epsilon) = I(u + \epsilon \cdot w)\]

pour tout \(\epsilon\in\setR\). Comme \(\mathcal{F}\) est un espace vectoriel, \(u + \epsilon \cdot w \in \mathcal{F}\). On en déduit que :

\[J_w(0) = I(u) \le J_w(\epsilon)\]

Si les fonctions \(J_w\) sont dérivables, les propriétés des extrema des fonctions \(\setR \mapsto \setR\) nous disent que :

\[\OD{J_w}{\epsilon}(0) = 0\]

pour toute variation \(w \in \mathcal{F}\). Si la dérivée seconde existe, on doit également avoir :

\[\OOD{J_w}{\epsilon}(0) \ge 0\]

Ces équations nous permettent de caractériser la solution \(u\) de notre problème variationnel.

10.2 Discrétisation

Une technique couramment employée pour résoudre les problèmes variationnels est de choisir une suite de fonctions \(\varphi_i \in \mathcal{F}\) linéairement indépendantes et de minimiser sur l'espace vectoriel \(\mathcal{F}_n = \combilin{\varphi_1,\varphi_2,...,\varphi_n} \subseteq \mathcal{F}\). On espère que la solution obtenue sera proche de la solution exacte. Ce sera par exemple le cas si on a schématiquement :

\[\lim_{n \to \infty} \adh \mathcal{F}_n = \mathcal{F}\]

au sens de la distance \(\distance\) définie sur \(\mathcal{F}\). Pour toute précision \(\epsilon > 0\), on pourra alors trouver un \(n \in \setN\) assez grand et un \(u_n\in \mathcal{F}_n\) tels que :

\[\distance(u_n,u) \le \epsilon\]

10.3 Moindres carrés

Soit \(f : A \mapsto \setR\) et le sous-ensemble \(\mathcal{F} \subseteq \fonction(A,\setR)\). On cherche la fonction \(u \in \mathcal{F}\) qui se rapproche le plus possible de \(f\) au sens intégral des moindres carrés. On cherche donc le \(u\) qui minimise la fonctionnelle :

\[I(u) = \int_A \Big[ u(x) - f(x) \Big]^2 dx\]

Afin de résoudre ce problème, on pose :

\[J_v(\epsilon) = I(u + \epsilon \cdot v) = \int_A \Big[ u(x) + \epsilon \cdot v(x) - f(x) \Big]^2 dx\]

pour tout \(\epsilon \in \setR\) et \(v \in \mathcal{F}\). La dérivée s'écrit :

\[\OD{J_v}{\epsilon}(\epsilon) = \int_A 2 \big[ u(x) + \epsilon \cdot v(x) - f(x) \big] \cdot v(x) \ dx\]

Comme elle doit s'annuler en \(\epsilon = 0\), on a :

\[\OD{J_v}{\epsilon}(0) = 2 \int_A \big[ u(x) - f(x) \big] \cdot v(x) \ dx = 0\]

donc :

\[\int_A \big[ u(x) - f(x) \big] \cdot v(x) \ dx = 0\]

pour tout \(v \in F\).

10.3.1 Discrétisation

On résout approximativement ce problème en posant :

\[u_n(x) = \sum_{i = 1}^n U_i \cdot \varphi_i(x)\]

où les \(\varphi_i \in \mathcal{F}\) sont des fonctions connues et où les \(U_i\) sont des réels à déterminer. Comme on désire que \(u_n \approx u\), on impose :

\[\int_A (u_n(x) - f(x)) \cdot \varphi_i(x) \ dx = 0\]

On a alors :

\[\int_A \varphi_i \sum_j U_j \cdot \varphi_j \ dx = \int_A \varphi_i \cdot f \ dx\]

ou :

\[\sum_j \left[ \int_A \varphi_i \cdot \varphi_j \ dx \right] \cdot U_j = \int_A \varphi_i \cdot f \ dx\]

Définissons les matrices \(A \in \matrice(\setR,n,n)\), \(B \in \matrice(\setR,n,1)\) et \(U \in \matrice(\setR,n,1)\) :

\begin{align} A &= \left[ \int_A \varphi_i \cdot \varphi_j \ dx \right]_{i,j} \\ B &= \left[ \int_A \varphi_i \cdot f \ dx \right]_i \\ U &= \left[ U_i \right]_i \end{align}

Le problème peut alors s'exprimer sous forme matricielle :

\[A \cdot U = B\]

Si la matrice \(A\) est inversible, la solution est donnée par :

\[U = A^{-1} \cdot B\]

et nous en déduisons notre approximation \(u_n = \sum_i U_i \cdot \varphi_i\).

10.4 Lax-Milgram

Soit un espace fonctionnel de Hilbert \(\mathcal{F}\). Nous considérons une forme bilinéaire \(a : \mathcal{F} \times \mathcal{F} \mapsto \setR\), de norme finie, coercive et symétrique :

\[\biforme{u}{a}{v} = \biforme{v}{a}{u}\]

pour tout \(u,v \in F\). Nous considérons également une forme linéaire continue \(b : \mathcal{F} \mapsto \setR\) et nous définissons la fonctionnelle \(I : \mathcal{F} \mapsto \setR\) par :

\[I(v) = \unsur{2} \biforme{v}{a}{v} - \forme{b}{v}\]

  • Supposons que \(I\) atteigne un minimum global en \(u\). On a alors :

\[I(u) \le I(v)\]

pour tout \(v \in F\). Choisissons un quelconque \(w \in \mathcal{F}\) et posons :

\[J_w(\epsilon) = I(u + \epsilon \cdot w)\]

pour tout \(\epsilon \in \setR\). Tenant compte des propriétés de \(a\) et \(b\), on obtient :

\[J_w(\epsilon) = \unsur{2} \biforme{u}{a}{u} + \epsilon \cdot \biforme{u}{a}{w} + \frac{\epsilon^2}{2} \cdot \biforme{w}{a}{w} - \forme{b}{u} - \epsilon \cdot \forme{b}{w}\]

La dérivée s'écrit :

\[\OD{J_v}{\epsilon}(\epsilon) = \biforme{u}{a}{w} + \epsilon \cdot \biforme{w}{a}{w} - \forme{b}{w}\]

La condition extrémale sur \(u\) nous dit que \(J_w(0) \le J_w(\epsilon)\) pour tout \(\epsilon \in \setR\). On doit donc avoir :

\[\OD{J_v}{\epsilon}(0) = \biforme{u}{a}{w} - \forme{b}{w} = 0\]

c'est-à-dire :

\[\biforme{u}{a}{w} = \forme{b}{w}\]

pour tout \(w \in \mathcal{F}\). Le théorème de Lax-Milgram nous dit qu'il existe un unique \(u \in \mathcal{F}\) vérifiant cette condition.

  • Supposons à présent que \(u \in \mathcal{F}\) soit l'unique élément de \(\mathcal{F}\) vérifiant :

\[\biforme{u}{a}{w} = \forme{b}{w}\]

pour tout \(w \in \mathcal{F}\). Choisissons \(v \in \mathcal{F}\) et posons \(w = v - u\). Comme \(\biforme{u}{a}{w} = \forme{b}{w}\), on a :

\begin{align} I(v) &= I(u + w) \\ &= \unsur{2} \biforme{u}{a}{u} + \biforme{u}{a}{w} + \unsur{2} \cdot \biforme{w}{a}{w} - \forme{b}{u} - \forme{b}{w} \\ &= \unsur{2} \biforme{u}{a}{u} + \unsur{2} \cdot \biforme{w}{a}{w} - \forme{b}{u} \\ &= I(u) + \unsur{2} \biforme{w}{a}{w} \ge I(u) \end{align}

On a donc :

\[u = \arg\min_{ v \in \mathcal{F} } I(v)\]

10.4.1 Orthogonalité

Soit le sous-espace vectoriel \(\mathcal{G} \subseteq \mathcal{F}\) et :

\[v \in \arg\min_{ z \in \mathcal{G} } I(z)\]

On a alors :

\[\biforme{v}{a}{w} = \forme{b}{w}\]

pour tout \(w \in \mathcal{G}\).

Supposons que \(u \in \mathcal{F}\) minimise \(I\) sur \(\mathcal{F}\) et posons \(e = v - u\). On a :

\[\biforme{e}{a}{w} = \biforme{v}{a}{w} - \biforme{u}{a}{w} = \forme{b}{w} - \forme{b}{w} = 0\]

Cette propriété est similaire aux propriétés d'orthogonalité vue dans les projections. On est tenté d'en déduire que le \(v\) en question minimise la « norme » de l'écart \(e\) au sens de \(a\). Soit \(z \in \mathcal{G}\) et \(\delta = z - v\). On a \(z - u = z - v + v - u = \delta + e\) et :

\[\biforme{z - u}{a}{z - u} = \biforme{\delta}{a}{\delta} + 2 \biforme{e}{a}{\delta} + \biforme{e}{a}{e}\]

Mais comme \(\delta \in \mathcal{G}\), on a \(\biforme{e}{a}{\delta} = 0\) et :

\[\biforme{z - u}{a}{z - u} = \biforme{\delta}{a}{\delta} + \biforme{e}{a}{e} \ge \biforme{e}{a}{e}\]

ce qui prouve que :

\[v \in \arg\min_{ z \in \mathcal{G} } \biforme{z - u}{a}{z - u}\]

10.4.2 Borne inférieure

Comme \(a\) est coercive, on peut trouver un réel \(\varrho \strictsuperieur 0\) tel que :

\[a(u,u) \ge \varrho \cdot \norme{u}^2\]

pour tout \(u \in \mathcal{F}\). On sait aussi que :

\[\norme{b} = \sup \{ \abs{b(u)} : u \in \mathcal{F}, \ \norme{u} = 1 \} \strictinferieur +\infty\]

Posons :

\[K(\epsilon) = I(\epsilon \cdot v) = \frac{\epsilon^2}{2} \cdot \biforme{v}{a}{v} - \epsilon \cdot \forme{b}{v}\]

et cherchons la valeur de \(\epsilon = \gamma\) qui minimise cette fonction. On trouve :

\[\OD{K}{\epsilon}(\gamma) = \gamma \cdot \biforme{v}{a}{v} - \forme{b}{v} = 0\]

Donc :

\[\gamma = \frac{ \forme{b}{v} }{ \biforme{v}{a}{v} }\]

et :

\[K(\gamma) = \frac{ \forme{b}{v}^2 }{ 2 \biforme{v}{a}{v} } - \frac{ \forme{b}{v}^2 }{ \biforme{v}{a}{v} } = - \frac{ \forme{b}{v}^2 }{ 2 \biforme{v}{a}{v} }\]

On en déduit que :

\[I(v) = K(1) \ge K(\gamma) = - \frac{ \forme{b}{v}^2 }{ 2 \biforme{v}{a}{v} }\]

Mais comme :

\( \forme{b}{v}^2 \le \norme{b}^2 \cdot \norme{v}^2 \\ \biforme{v}{a}{v} \ge \varrho \cdot \norme{v}^2 \)

on a :

\[\frac{ \forme{b}{v}^2 }{ 2 \biforme{v}{a}{v} } \le \frac{\norme{b}^2}{2 \varrho}\]

et :

\[I(v) \ge - \frac{\norme{b}^2}{2 \varrho}\]

Ce résultat étant valable pour tout \(v \in \mathcal{F}\), on a la borne inférieure :

\[\inf_{ v \in \mathcal{F} } I(v) \ge - \frac{\norme{b}^2}{2\varrho}\]

10.4.3 Discrétisation

Afin de trouver une approximation \(u_n \approx u\), on pose :

\[u_n = \sum_{i = 1}^n U_i \cdot \varphi_i\]

où les \(\varphi_i \in \mathcal{F}\) sont connues et où les \(U_i\) sont des réels à déterminer. La linéarité de \(a\) et \(b\) nous permet de développer :

\[I(u_n) = \unsur{2} \sum_{i,j = 1}^n U_i \cdot \biforme{\varphi_i}{a}{\varphi_j} \cdot U_j - \sum_{i=1}^n \forme{b}{\varphi_i} U_i\]

Si nous définissons les matrices :

\begin{align} A &= \left[ \biforme{\varphi_i}{a}{\varphi_j} \right]_{i,j} \\ B &= \left[ \forme{b}{\varphi_i} \right]_i \\ U &= \left[ U_i \right]_i \end{align}

on peut réécrire \(I(u_n)\) sous forme matricielle :

\[I(u_n) = J(U) = \unsur{2} U^\dual \cdot A \cdot U - U^\dual \cdot B\]

La condition \(\partial J(U) = 0\) nous amène à :

\[A \cdot U - B = 0\]

Si la matrice \(A\) est inversible, on en déduit :

\[U = A^{-1} \cdot B\]

ce qui nous donne \(U\) et donc \(u_n\).

10.5 Valeurs propres

Soit un espace vectoriel \(E\) et les formes bilinéaires \(a,b : E \times E \mapsto \setR\). Nous supposons que \(a,b\) sont symétriques et définies positives. Nous allons tenter de minimiser la fonctionnelle :

\[I(v) = \biforme{v}{a}{v}\]

sur l'ensemble :

\[\Omega = \{ v \in E : \biforme{v}{b}{v} = 1 \}\]

L'espace \(\Omega\) n'est malheureusement pas un sous-espace vectoriel. Par exemple, si \(u\) appartient à \(\Omega\), on a :

\[\biforme{2 u}{b}{2 u} = 4 \biforme{u}{b}{u} = 4 \ne 1\]

Donc \(2 u \notin \Omega\). Par conséquent, nous ne pouvons pas utiliser les techniques de projection sur un espace vectoriel pour résoudre ce problème. Nous allons donc employer les techniques de minimisation sous contraintes. Définissons le lagrangien :

\[\lagrangien(v,y) = \biforme{v}{a}{v} + y \cdot (1 - \biforme{v}{b}{v})\]

pour tout \((v,y) \in E \times \setR\). La fonction \(u\) minimisant \(I\) sur \(\Omega\) peut dès lors s'obtenir via le point de selle \((u,\lambda)\) :

\[\lagrangien(u,y) \le \lagrangien(u,\lambda) \le \lagrangien(v,\lambda)\]

pour tout \((v,y) \in E \times \setR\). Nous allons évaluer le minimum sur \(v\) en utilisant la méthode des variations. Soit \(w \in E\) et \(\epsilon \in \setR\). On pose :

\begin{align} J_v(\epsilon) &= \lagrangien(u + \epsilon \cdot w, \lambda) \\ &= \biforme{u + \epsilon \cdot w}{a}{u + \epsilon \cdot w} + \lambda \cdot [ 1 - \biforme{u + \epsilon \cdot w}{b}{u + \epsilon \cdot w} ] \end{align}

Utilisant les propriétés de \(a,b\) et la contrainte \(\biforme{u}{b}{u} = 1\), il vient :

\( J_v(\epsilon) = \biforme{u}{a}{u} + 2 \epsilon \cdot \biforme{w}{a}{u} + \epsilon^2 \cdot \biforme{w}{a}{w} \\ \qquad - \lambda \cdot [ 2 \epsilon \cdot \biforme{w}{b}{u} + \epsilon^2 \cdot \biforme{w}{b}{w} ] \)

Les propriétés du point de selle en \((u,\lambda)\) nous garantissent que :

\[J_v(0) \le J_v(\epsilon)\]

pour tout \(\epsilon\in\setR\). La dérivée :

\[\OD{J_v}{\epsilon}(\epsilon) = 2 \biforme{w}{a}{u} + 2 \epsilon \cdot \biforme{w}{a}{w} - 2 \lambda \cdot [ \biforme{w}{b}{u} + \epsilon \cdot \biforme{w}{b}{w} ]\]

doit donc s'annuler en \(\epsilon = 0\) :

\[\OD{J_v^\lambda}{\epsilon}(0) = 2 \biforme{w}{a}{u} - 2 \lambda \cdot \biforme{w}{b}{u} = 0\]

c'est-à-dire :

\[\biforme{w}{a}{u} = \lambda \cdot \biforme{w}{b}{u}\]

pour tout \(w \in E\). On dit alors que \(\lambda\) est valeur propre de \(a,b\) correspondant à la fonction propre \(u\).

10.5.1 Propriétés extrémales

Si nous choisissons \(w = u\), nous obtenons :

\[\biforme{u}{a}{u} = \lambda \cdot \biforme{u}{b}{u} = \lambda\]

La valeur propre est donc la valeur minimale de \(I\) sur \(\Omega\) :

\[\lambda = \biforme{u}{a}{u} = \min_{v \in \Omega} \biforme{v}{a}{v}\]

10.5.2 Rapport de Rayleigh

Supposons que \(b\) soit strictement définie positive. Posons \(x = \alpha \cdot u\), pour un certain \(\alpha \in \setR\) non nul. On a \(\biforme{x}{a}{x} = \alpha^2 \cdot \biforme{u}{a}{u}\) et \(\biforme{x}{b}{x} = \alpha^2 \cdot \biforme{u}{b}{u} = \alpha^2\). Donc :

\[\lambda = \biforme{u}{a}{u} = \frac{ \biforme{x}{a}{x} }{ \biforme{x}{b}{x} }\]

Considérons la même expression pour un quelconque \(z \in E\) non nul :

\[R(z) = \frac{ \biforme{z}{a}{z} }{ \biforme{z}{b}{z} }\]

On dit que \(R(z)\) est le rapport de Rayleigh de \(z\). Soit \(v = z / \sqrt{ \biforme{z}{b}{z} }\). On a :

\[\biforme{v}{a}{v} = \frac{ \biforme{z}{a}{z} }{ \biforme{z}{b}{z} } = R(z)\]

et :

\[\biforme{v}{b}{v} = \frac{ \biforme{z}{b}{z} }{ \biforme{z}{b}{z} } = 1\]

ce qui prouve que \(v \in \Omega\). On a donc :

\[\lambda = R(x) \le \biforme{v}{a}{v} = R(z)\]

On en conclut que \(x\) minimise le rapport de Rayleigh sur \(E_0 = E \setminus \{0\}\) :

\[\lambda = R(x) = \arg\min_{z \in E_0} R(z) = \arg\min_{z \ne 0} R(z)\]

Comme \(\Omega \subseteq F\), on en conclut que la réciproque est vraie : si \(x\) minimise \(R\) sur \(E_0\), le vecteur \(x/\sqrt{ \biforme{x}{b}{x} }\) minimise la fonctionnelle \(I\) sur \(\Omega\). Les deux problèmes de minimisation sont donc équivalents.

10.5.3 Suite de vecteurs propres

On peut en fait définir une suite de vecteurs et de valeurs propres. Soit \(\Omega_1 = \Omega\) et \(e_1 = u\). On pose récursivement :

\[\Omega_{n + 1} = \{ v \in \Omega : \biforme{v}{b}{e_1} = ... = \biforme{v}{b}{e_n} = 0 \}\]

et :

\[e_{n + 1} \in \arg\min_{ v \in \Omega_{n + 1} } \biforme{v}{a}{v}\]

On aura alors bien sûr \(\Omega_{n + 1} \subseteq \Omega_n \subseteq ... \Omega_1\). Les propriétés extrémales des valeurs propres nous montrent que \(\lambda_{n + 1} \ge \lambda_n \ge ... \ge \lambda_1\).

10.5.4 Discrétisation

On pose :

\[u_n = \sum_{i=1}^n U_i \cdot \varphi_i\]

On a alors :

\( \biforme{u_n}{a}{u_n} = \sum_{i,j = 1}^n U_i \cdot \biforme{\varphi_i}{a}{\varphi_j} \cdot U_j \\ \biforme{u_n}{b}{u_n} = \sum_{i,j = 1}^n U_i \cdot \biforme{\varphi_i}{b}{\varphi_j} \cdot U_j \)

Avec les matrices :

\( A = \left[ \biforme{\varphi_i}{a}{\varphi_j} \right]_{i,j} \\ B = \left[ \biforme{\varphi_i}{b}{\varphi_j} \right]_{i,j} \)

le lagrangien peut s'écrire :

\[\lagrangien(u_n,y) = U^\dual \cdot A \cdot U + y \cdot \left[ 1 - U^\dual \cdot B \cdot U \right]\]

Les conditions :

\( \partial_v \lagrangien(u_n,\lambda) = 2 A \cdot U - 2 \lambda \cdot B \cdot U = 0 \\ \partial_y \lagrangien(u_n,\lambda) = 1 - U^\dual \cdot B \cdot U = 0 \)

nous amènent au problème :

\( A \cdot U = \lambda \cdot B \cdot U \\ U^\dual \cdot B \cdot U = 1 \)

à résoudre en \(U\). Notons que si on choisit les \(\varphi_i\) « orthonormées » dans le sens du pseudo-produit scalaire introduit par \(b\), on a :

\[\biforme{\varphi_i}{b}{\varphi_j} = \delta_{ij}\]

et \(B = I\). On peut par exemple construire une telle suite de \(\varphi_i\) en utilisant la méthode de Gram-Schmidt. Le problème se simplifie alors en :

\( A \cdot U = \lambda \cdot U \\ U^\dual \cdot U = 1 \)

11 Algorithmes d'optimisation contrainte

11.1 Introduction

Nous allons présenter des algorithmes permettant de résoudre approximativement des problèmes de minimisation d'une fonction \(\varphi\) sur un ensemble \(\Omega \subseteq \setR^n\). Ces algorithmes partent d'un point initial \(x_0 \in \Omega\) et itèrent schématiquement comme suit :

\[x_{k + 1} = I(x_k) = x_k + p_k\]

pour un certain \(p_k \in \setR^n\). On espère bien entendu que la suite converge et que :

\[x_N \approx \lim_{k \to \infty} x_k = \arg\min_{x \in \Omega} \varphi(x)\]

pour \(N\) assez grand. Nous adoptons les notations :

\[J = \partial \varphi\]

pour le gradient, de taille \((n,1)\) et :

\[H = \partial^2 \varphi\]

pour la hessienne, de taille \((n,n)\). On note également :

\[\Phi_k = \Phi(x_k)\]

pour toute fonction \(\Phi\) (par exemple, \(\Phi \in \{\varphi,J,H\}\)).

11.2 Contraintes linéaires

Nous considérons le cas de contraintes linéaires :

\[\Omega = \{ x \in \setR^n : A \cdot x = b \}\]

où \(A\) est une matrice de taille \((m,n)\) et \(b\) un vecteur de taille \((m,1)\). On choisit généralement \(x_0 = 0\). L'itération \(k\) part d'un \(x_k\) satisfaisant les contraintes :

\[A \cdot x_k = b\]

Si on veut que \(x_{k + 1} = x_k + s_k \in \Omega\), il est nécessaire et suffisant que \(A \cdot (x_k + s_k) = b\), ou que :

\[A \cdot s_k = A \cdot (x_k + s_k) - A \cdot x_k = b - b = 0\]

On doit donc avoir \(s_k \in \noyau A\). Soit les \(u_i \in \setR^m\), \(v_i \in \setR^n\) et \(\sigma_i \in \setR\) constituant la décomposition en valeurs singulières de \(A\). On forme une matrice à partir des vecteurs de base de \(\noyau A\) :

\[V = [v_{r + 1} \ ... \ v_n]\]

On a alors :

\[s_k = \sum_{i = r + 1}^n p_{k,i} \cdot v_i = V \cdot p_k\]

où \(p_k = [p_{k, r + 1} ... p_{k,n}]^\dual\).

11.2.1 Newton projeté

Il s'agit de l'adaptation de la méthode de Newton :

\[x_{k + 1} = x_k + V \cdot p_k\]

On minimise le développement d'ordre deux :

\[\varphi_{k+1} \approx \varphi_k + J_k^\dual \cdot V \cdot p_k + \unsur{2} \cdot p_k^\dual \cdot V^\dual \cdot H_k \cdot V \cdot p_k\]

L'annulation du gradient par rapport à \(p_k\) nous donne :

\[V^\dual \cdot J_k + V^\dual \cdot H_k \cdot V \cdot p_k = 0\]

et donc :

\[p_k = - (V^\dual \cdot H_k \cdot V)^{-1} \cdot V^\dual \cdot J_k\]

11.3 Contraintes d'inégalité

Examinons à présent le cas où :

\[\Omega = \{ x \in \setR^n : \omega(x) \le 0 \}\]

Nous laissons à présent tomber le \(k\) des itérations, afin d'alléger les notations.

11.3.1 Méthodes de penalité

La méthode de pénalité consiste à ajouter une fonction positive à \(\varphi\) lorsque \(x\) sort de \(\Omega\). Si l'on augmente la valeur de la fonction pénalité, on rapproche alors le minimum global de \(\Omega\). La solution à notre problème contraint devrait donc être approchée en faisant tendre l'amplitude de la pénalité vers l'infini. Soit la fonction \(\varpi : \setR^n \mapsto \setR^m\) définie par :

\[\varpi_i(x) = \max\{\omega_i(x),0\}\]

On a par construction \(\varpi(x) = 0\) pour tout \(x \in \Omega\) et \(\varpi(x) \strictsuperieur 0\) pour tout \(x \notin \Omega\). On ajoute la somme des carrés \(\varpi(x)^\dual \cdot \varpi(x) = \sum_i \varpi_i(x)^2\) multipliée par un paramètre réel \(k \ge 0\) à la fonction objectif pour obtenir l'objectif modifié :

\[\psi_k(x) = \varphi(x) + k \cdot \varpi(x)^\dual \cdot \varpi(x)\]

On utilise ensuite un algorithme de minimisation libre pour évaluer le minimum global :

\[\mu(k) = \arg\min_{x \in \setR^n} \psi_k(x)\]

On espère que \(\mu\) converge à l'infini et que :

\[\lim_{k \to \infty} \mu(k) = \arg\min_{x \in \Omega} \varphi(x)\]

Il suffit dans ce cas de choisir \(k\) assez grand pour obtenir une estimation de la solution du problème contraint.

12 Réseaux de neurones

12.1 Définition

Commençons par la description d'un neurone \(i\) de fonction caractéristique \(\sigma\). La relation entre les entrées \(x_j\) et la sortie \(y_i\) s'écrit :

\[y_i = \sigma\left( \sum_j ( w_{ij} \ x_j ) + b_i \right)\]

Un réseau de neurones est composé de neurones reliés entres eux (la sortie d'un neurone peut servir d'entrée à un autre).

La fonction caractéristique est généralement l'une de celles décrites ci-dessous :

\( \sigma(x) = \mt{sign}(x) \\ \sigma(x) = \tanh(x) \\ \sigma(x) = \exp(-x^2) \\ \sigma(x) = x \exp(-x^2) \)

12.2 Perceptron à une couche

Le perceptron monocouche est composé d'une rangée de neurones reliant les entrées \(x_i\) aux sorties \(y_i\) (le perceptron multicouche est composé de monocouches assemblées l'une à la suite de l'autre). La relation entrées-sorties s'écrit :

\[y_i = P_{\theta}(x) = c + \sum_j v_j \ \sigma\left( \sum_k ( w_{jk} \ x_k ) + b_j \right)\]

On écrit \(y_i = P_{\theta}(x)\) pour mettre en évidence l'influence des paramètres du résau \(\theta = (v,w,b,c)\) sur la sortie \(y\).

12.3 Entrainement

Les réseaux de neurones sont principalement utilisés afin de calquer le comportement d'un système difficille à modéliser par d'autres méthodes. On dispose d'un certain nombre de vecteurs \(y^{(n)}\in\setR^M\), \(x^{(n)}\in\setR^{N}\), où \(n=1,...,K\). On aimerait bien trouver le vecteur des paramètres, \(\theta\), qui correspond le mieux à cette série d'entrées-sorties. On va alors entrainer le réseau de neurones défini par \(y=R_{\theta}(x)\) en utilisant une méthode d'optimisation non linéaire afin d'obtenir la solution de

\[\theta^* = \arg\min_{\theta} \sum_n \norme{ y^{(n)} - R_{\theta}\left( x^{(n)} \right) }^2\]

Auteur: chimay

Created: 2019-10-01 mar 12:34

Validate