1.1 Approximation des moindres carrés

Previous: 1 Programmation non linéaire Up: 1 Programmation non linéaire Next: 1.2 Optimisation sans contrainte

Subsections

1.1 Approximation des moindres carrés

On a réalisé $n$ expériences (indexées par $j\in \left[ 1..n\right]$ , consistant chacune en la mesure d'un résultat $y_{j}$ et de $p$ paramètres $x_{j,\, k}$ . On cherche, parmi toutes les descriptions linéaires $\displaystyle z_{j}=\sum _{k=1}^{p}c_{k}\, x_{j,\, k}$ , celle qui sera optimale au sens des moindres carrés, c'est à dire donnant la meilleure corrélation linéaire possible. On veut donc minimiser la quantité $\displaystyle \frac{1}{n}\sum _{j=1}^{n}\left( y_{j}-z_{j}\right) ^{2}$ . La valeur minimale obtenue s'appelle la variance réduite de $y$ .

1.1.1 Droite de régression linéaire

On se demande quelle est la droite qui "passe au mieux" parmi $n$ points $\left( x_{j},\, y_{j}\right)$ .

On pose $z=a\, x+b$ et l'on cherche à déterminer les constantes $a,\, b$ pour que l'écart quadratique $\Theta ^{2}=\frac{1}{n}\sum _{j=1}^{n}\left( y_{j}-a\, x_{j}-b\right) ^{2}$ entre $y$ et $z$ soit minimal.
On a $\frac{\mathrm{d}^{ }}{\mathrm{d}\, b ^{ }}\Theta ^{2}=\frac{-2}{n}\sum _{j=1}^{n}\left( y_{j}-a\, x_{j}-b\right)$ . Une première condition requise est donc $\frac{1}{n}\sum y-a\, \frac{1}{n}\sum x-b=0$ . Définissant $\mathrm{E}\left( x \right)$ par $\mathrm{E}\left( x \right) =\frac{1}{n}\sum x$ , il vient :

$\begin{displaymath} \mathrm{E}\left( y \right) =a\, \mathrm{E}\left( x \right) +b\end{displaymath}$

Autrement dit : la droite de meilleure approximation passe nécessairement par le point moyen de la distribution.
Introduisons maintenant les variables centrées : $\xi =x-\mathrm{E}\left( x \right)$ et $\eta =y-\mathrm{E}\left( y \right)$ et posons $\mathrm{var}\left( x \right) =\mathrm{E}\left( \xi ^{2} \right)$ , $\mathrm{var}\left( y \right) =\mathrm{E}\left( \eta ^{2} \right)$ et $\mathrm{cov}\left( x,\, y \right) =\mathrm{E}\left( xi\, \eta \right)$ . On a $\Theta ^{2}=\frac{1}{n}\sum _{j=1}^{n}\left( \eta _{j}-a\, \xi _{j}\right) ^{... ...j}^{2}-2\frac{a}{n}\sum \eta _{j}\, \xi _{j}+\frac{a^{2}}{n}\sum \xi _{j}^{2}$ et donc $\frac{\mathrm{d}^{ }}{\mathrm{d}\, a ^{ }}\Theta ^{2}=2a\, \mathrm{var}\left( x \right) -2\mathrm{cov}\left( x,\, y \right)$ . On en déduit :

$\begin{displaymath} a=\frac{\mathrm{cov}\left( x,\, y \right) }{\mathrm{var}\left( x \right) }\end{displaymath}$

1.1.2 Evaluation de la qualité de l'approximation

Il très important de quantifier la réduction de variance obtenue par ce procédé. En reportant, il vient $\mathrm{var}\_\mathrm{reduite}\, =\mathrm{var}\left( y \right) -\frac{\mathrm... ..., y \right) }{\mathrm{var}\left( x \right) }\mathrm{cov}\left( x,\, y \right)$ , soit :

$\begin{displaymath} \mathrm{var}\_\mathrm{reduite}\, =\mathrm{var}\left( y \righ... ...{var}\left( x \right) \, \mathrm{var}\left( y \right) }\right) \end{displaymath}$
L'écart-type réduit, qui est la racine carrée de la variance réduite, détermine l'épaisseur de la bande à placer de part et d'autre de la droite de régression pour obtenir une "probabilité raisonnable" de localisation des points mesurés.
Prenons pour exemple la suite de points $\left( 0,\, 0\right)$ , $\left( 1,\, 1\right)$ , $\left( 2,\, 4\right)$ , $\left( 3,\, 9\right)$ et $\left( 4,\, 16\right)$ : on a $0\leq x_{j}\leq 4$ et $y_{j}=x_{j}^{2}$ . Les calculs donnent $\mathrm{E}\left( x \right) =2$ , $\mathrm{E}\left( y \right) =\mathrm{E}\left( x^{2} \right) =6$ , $\mathrm{E}\left( xy \right) =\mathrm{E}\left( x^{3} \right) =20$ , $\mathrm{E}\left( y^{2} \right) =\mathrm{E}\left( x^{4} \right) =70.8$ . De là $\mathrm{var}\left( x \right) =6-4=2$ , $\mathrm{var}\left( y \right) =70.8-36=34.8$ et $\mathrm{cov}\left( x,\, y \right) =20-12=8$ . On trouve donc $a=4$ et le facteur de réduction de variance est $\left( 1-8^{2}\div 2\div 34.8\right) =0.081$ . La droite de régression linéaire "rend compte" de $92\%$ de la variance.
Prenons maintenant pour exemple la suite $-2\leq x_{j}\leq +2$ et $y_{j}=x_{j}^{2}$ , on trouve une covariance nulle et, pour ce nouvel exemple, "l'explication linéaire" n'explique plus rien et la droite "de régression" est horizontale.

Figure: Régressions linéaires : efficace et inefficace.

$\resizebox*{0.45\columnwidth}{0.25\textheight}{\includegraphics{correl_sq_01.eps}}$

$\resizebox*{0.45\columnwidth}{0.25\textheight}{\includegraphics{correl_sq_02.eps}}$

1.1.3 Avec plusieurs variables explicatives

Prenons pour exemple $n=3$ , $p=2$ , $Y=\left[ \begin{array}{r} -59\\ 62\\ -55 \end{array}\right]$ et $X=\left[ \begin{array}{rr} 25 & 9\\ 40 & 61\\ 40 & -78 \end{array}\right]$ . L'objectif est de minimiser $n\, \Theta ^{2}=\left\langle X\, C-Y\, \vert\, X\, C-Y\right\rangle$ où l'on a posé $C=\left[ \begin{array}{c} c_{1}\\ c_{2} \end{array}\right]$ .
On a $X\, C-Y=\left[ \begin{array}{c} -59-25\, c_{1}-9\, c_{2}\\ 62-40\, c_{1}-61\, c_{2}\\ -55-40\, c_{1}+78\, c_{2} \end{array}\right]$ et donc $n\, \Theta ^{2}$ vaut $\left( -59-25\, c_{1}-9\, c_{2}\right) ^{2}+\left( 62-40\, c_{1}-61\, c_{2}\right) ^{2}+\left( -55-40\, c_{1}+78\, c_{2}\right) ^{2}$ .
Les dérivées partielles par rapport aux paramètres valent : $2390+7650\, c_{1}-910\, c_{2},\, -15082-910\, c_{1}+19772\, c_{2}$ . En les égalant à $0$ , on trouve $c_{1}=\frac{-23613}{105935},\, c_{2}=\frac{15944}{21187}$ , ce qui conduit à $\mathrm{var}\_\mathrm{reduite}\, =1469.584163$ , alors que l'on avait $\mathrm{var}\left( y \right) =3149.555556$ .
On explique donc environ $50\%$ de la variance, ce qui n'est pas si mal.

1.1.4 Méthode matricielle

On a $n\, \Theta ^{2}=\, ^{t}\! \left( X\, C-Y\right) .\left( X\, C-Y\right) =\, ^{t}C\, \, ^{t}\! X\, X\, C-2\, ^{t}C\, ^{t}\! X\, Y+\, ^{t}Y\, Y$ . En effet $\, ^{t}Y\, X\, C$ est un nombre et est donc égal à son transposé $\, ^{t}C\, \, ^{t}\! X\, Y$ .
Faisons varier $C$ pour le faire devenir $C+\mathrm{d}\hskip 0.05emC$ . Par linéarité, $n\, \Delta \, \Theta ^{2}$ vaut $\, ^{t}\mathrm{d}\hskip 0.05emC\, \, ^{t}\! X\, X\, C+\, ^{t}C\, \, ^{t}\! X\, X\, \mathrm{d}\hskip 0.05emC-2\, ^{t}\mathrm{d}\hskip 0.05emC\, ^{t}\! X\, Y$ $+\, ^{t}\mathrm{d}\hskip 0.05emC\, \, ^{t}\! X\, X\, \mathrm{d}\hskip 0.05emC$ . Comme les nombres $\, ^{t}\mathrm{d}\hskip 0.05emC\, \, ^{t}\! X\, X\, C$ et $\, ^{t}C\, \, ^{t}\! X\, X\, \mathrm{d}\hskip 0.05emC$ sont transposés l'un de l'autre, ils sont égaux, on a $n\, \mathrm{d}\hskip 0.05em\Theta ^{2}=2\, \mathrm{d}\hskip 0.05emC\left( \, ^{t}\! X\, X\, C-\, ^{t}Y\, X\right)$ , tandis que le terme de deuxième ordre n'est autre que $\left\vert X\, C\right\vert ^{2}$ qui est positif : les points critiques conduisent donc à un minimum.
La sémantique du problème conduit à $p<n$ : il n'y aurait pas grand sens à introduire beaucoup de "variables explicatives" pour expliquer un petit nombre de points. La taille des matrices $\, ^{t}Y\, X$ et $\, ^{t}\! X\, X$ est donc petite (respectivement $p$ et $p\times p$ ).
Dans le présent problème, le seul cas critique serait $\, ^{t}\! X\, X=0$ , c'est à dire la non-indépendance (sur-abondance) des paramètres ``explicatifs''.
Dans l'exemple choisi, on a $\, ^{t}Y\, X=\left[ \begin{array}{r} -1195\\ 7541 \end{array}\right]$ et $\, ^{t}\! X\, X=\left[ \begin{array}{rr} 3825 & -455\\ -455 & 9886 \end{array}\right]$ . D'où $C=\left( \, ^{t}\! X\, X\right) ^{-1}\, \left( \, ^{t}Y\, X\right) =\left[ \begin{array}{c} \frac{-23613}{105935}\\ \frac{15944}{21187} \end{array}\right]$ .

1.1.5 Un autre exemple

On cherche ``le'' point ``déterminé'' par les conditions $2x+y=1$ , $-x+y=3$ et $x+2y=-1$ . En fait, on veut minimiser la somme des carrés des distances.
Quelle est la signification ``géométrique'' de ce point ?
Que se passe-t-il lorsque l'on prend quatre droites ?

Previous: 1 Programmation non linéaire Up: 1 Programmation non linéaire Next: 1.2 Optimisation sans contrainte

douillet@ensait.fr
2001-11-21