Eclats de vers : Matemat 10 : Optimisation - 1
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
\label{chap:optimisationlibre}
1.1. Minimum
- 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 $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\]