Eclats de vers : Matemat 10 : Optimisation - 1

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\]

Auteur: chimay

Created: 2019-10-01 mar 12:33

Validate