13.2 Méthode générale

Considérons un système \(m\times n\), \[ (*):\quad A\boldsymbol{x}=\boldsymbol{b}\,, \] que l'on supposera incompatible, ce qui signifie \[ \min_{\boldsymbol{x}\in \mathbb{R}^n} \|A\boldsymbol{x}-\boldsymbol{b}\|\gt 0\,. \]

On dit que \(\boldsymbol{x}_*\in\mathbb{R}^n\) est une pseudo-solution de \((*)\), ou solution de \((*)\) au sens des moindres carrés si \[ \|A\boldsymbol{x}_*-\boldsymbol{b}\|= \min_{\boldsymbol{x}\in \mathbb{R}^n} \|A\boldsymbol{x}-\boldsymbol{b}\|\,. \]

Shématiquement:

Remarque: À propos de la terminologie ''moindres carrés'': Trouver le \(\boldsymbol{x}\) qui minimise une certaine norme revient au même que de trouver le \(\boldsymbol{x}\) qui minimise le carré de cette norme , donc la recherche d'une pseudo-solution revient à minimiser la fonction \[ \boldsymbol{x}\mapsto \|A\boldsymbol{x}-\boldsymbol{b}\|^2=\sum_{k=1}^m\bigl((A\boldsymbol{x})_k-b_k\bigr)^2\,, \] qui est une somme de carrés.

Exemple: (Généralisation du problème de l'exemple de motivation.) Supposons que l'on ait un nuage de points dans le plan, obtenu en prenant des mesures \[\mathcal{P}=\{(x_1,y_1),\dots,(x_N,y_N)\}\,,\] sensées obéir à une relation affine théorique de la forme \[y=\alpha x+\beta\,.\] Dans ce cas, le système \(N\times 2\) \[ \left\{ \begin{array}{ccccc} \alpha x_1 &+& \beta &=&y_1 \\ \alpha x_2 &+& \beta &=&y_2 \\ && &\vdots& \\ \alpha x_N &+& \beta &=&y_N \end{array} \right. \] est en général incompatible, et la solution au sens des moindres carrés correspond à minimiser \[ \boldsymbol{x}= \begin{pmatrix} \alpha\\ \beta \end{pmatrix} \mapsto \sum_{k=1}^N\bigl((\alpha x_k+\beta)-y_k\bigr)^2. \] La paire \((\alpha_*,\beta_*)\) qui minimise cette fonction fournit donc une droite qui approxime le nuage \(\mathcal{P}\), au sens des moindres carrés:

Par exemple, avec seulement \(N=3\) (comme dans l'exemple de motivation):
Pour une animation semblable, mais fonctionnant avec un nombre arbitraire de points, cliquer ici (Stats applets).

L'équation normale

Considérons une pseudo-solution \(\boldsymbol{x}_*\): \[ \|A\boldsymbol{x}_*-\boldsymbol{b}\|= \min_{\boldsymbol{x}\in \mathbb{R}^n} \|A\boldsymbol{x}-\boldsymbol{b}\|\,. \] Comme on sait, considérer tous les produits \(\boldsymbol{q}:= A\boldsymbol{x}\) possibles, lorsque \(\boldsymbol{x}\) varie, revient à considérer toutes les combinaisons linéaires possibles des colonnes de \(A\), et donc à parcourir tout le sous-espace \(\mathrm{Col}(A)\). Donc on peut tout aussi bien écrire \[ \min_{\boldsymbol{x}\in \mathbb{R}^n} \|A\boldsymbol{x}-\boldsymbol{b}\|= \min_{\boldsymbol{q}\in \mathrm{Col}(A)} \|\boldsymbol{q}-\boldsymbol{b}\|\,. \] Or on a vu que le minimum de cette distance est réalisé lorsque \(\boldsymbol{q}\) est la projection de \(\boldsymbol{b}\) sur \(\mathrm{Col}(A)\): \[ \boldsymbol{q}_* =\mathrm{proj}_{\mathrm{Col}(A)}(\boldsymbol{b}) \] On peut toujours calculer cette projection, typiquement en extrayant une base de \(\mathrm{Col}(A)\), et en l'orthogonalisant avec le procédé de Gram-Schmidt. (C'est ce que nous avons fait dans l'exemple de l'introduction.)

Mais nous allons voir qu'il est possible de passer outre le calcul explicite de cette projection.

En effet, commençons par rappeler que \(\boldsymbol{b}_\parallel=\mathrm{proj}_{\mathrm{Col}(A)}(\boldsymbol{b})\) est caractérisé par le fait que \(\boldsymbol{b}_\perp:= \boldsymbol{b}-\boldsymbol{b}_\parallel\) est orthogonal à \(\mathrm{Col}(A)\), i.e. \(\boldsymbol{b}^\perp\in \mathrm{Col}(A)^\perp\):

Or on a montré précédemment que \[ \mathrm{Col}(A)^\perp=\mathrm{Ker}(A^T)\,. \] Ainsi, \(\boldsymbol{b}^\perp\) doit satisfaire \(A^T\boldsymbol{b}^\perp=\boldsymbol{0}\), qui donne \[ A^T(\boldsymbol{b}-\boldsymbol{b}_\parallel)=\boldsymbol{0}\,, \] c'est-à-dire \[ A^T\boldsymbol{b}_\parallel= A^T\boldsymbol{b}\,. \] Comme \(\boldsymbol{b}_\parallel=A\boldsymbol{x}_*\), on a démontré:

Théorème: Un vecteur \(\boldsymbol{x}\in\mathbb{R}^n\) est solution de \(A\boldsymbol{x}=\boldsymbol{b}\) au sens des moindres carrés si et seulement si \(\boldsymbol{x}\) est solution de l'équation normale, donnée par \[ A^TA\boldsymbol{x}=A^T\boldsymbol{b}\,. \]

Exemple: Considérons l'exemple de l'introduction, où le système incompatible \(A\boldsymbol{x}=\boldsymbol{b}\) de départ était \[ \begin{pmatrix} 2&1\\ 12&1\\ 65&1 \end{pmatrix} \begin{pmatrix} \alpha\\ \beta \end{pmatrix} = \begin{pmatrix} 30\\52 \\147 \end{pmatrix}\,. \] Donnons la solution de cette équation sans passer par la projection, en utilisant le théorème ci-dessus. On obtient l'équation normale en multipliant des deux côtés par \(A^T\), qui donne \[ \begin{pmatrix} 2&12&65\\ 1&1&1 \end{pmatrix} \begin{pmatrix} 2&1\\ 12&1\\ 65&1 \end{pmatrix} \begin{pmatrix} \alpha\\ \beta \end{pmatrix} = \begin{pmatrix} 2&12&65\\ 1&1&1 \end{pmatrix} \begin{pmatrix} 30\\52 \\147 \end{pmatrix}\,, \] c'est-à-dire \[ \begin{pmatrix} 4373&79\\ 79&3 \end{pmatrix} \begin{pmatrix} \alpha\\ \beta \end{pmatrix} = \begin{pmatrix} 10239\\229 \end{pmatrix} \] La solution de ce dernier est donnée par \[\begin{aligned} \alpha&=\frac{12626}{6878}=1.8357\dots\\ \beta&=\frac{192536}{6878}=27.9930\dots\,, \end{aligned}\] comme nous avions trouvé en utilisant la projection.

Si \(A\) est \(m\times n\), \(A^TA\) est \(n\times n\), et donc l'équation normale représente un système carré \(n\times n\) qui possède toujours une solution.

Dans l'exemple précédent, la solution de l'équation normale était unique. Mais il peut arriver que l'équation normale possède plus d'une solution, ce que l'on aimerait éviter dans les problèmes pratiques. Voyons comment garantir l'unicité de la pseudo-solution:

Théorème: Soit \(A\) une matrice \(m\times n\). Sont équivalents:

  1. Pour tout \(\boldsymbol{b}\in \mathbb{R}^m\), la pseudo-solution de \(A\boldsymbol{x}=\boldsymbol{b}\) est unique.
  2. Pour tout \(\boldsymbol{b}\in \mathbb{R}^m\), la solution de l'équation normale \(A^TA\boldsymbol{x}=A^T\boldsymbol{b}\) est unique.
  3. \(A^TA\) (qui est \(n\times n\)) est inversible.
  4. Les colonnes de \(A\) sont linéairement indépendantes.

Ainsi, lorsque la pseudo-solution \(\boldsymbol{x}_*\) du système \(A\boldsymbol{x}=\boldsymbol{b}\) est unique, elle s'exprime explicitement par \[ \boldsymbol{x}_*=(A^TA)^{-1}A^T\boldsymbol{b}\,. \] Pour la preuve des équivalences énoncées dans le théorème, nous aurons besoin du résultat préliminaire suivant:

Lemme: Pour toute matrice \(A\) (\(m\times n\)), \(A\boldsymbol{x}=\boldsymbol{0}\) si et seulement si \(A^TA\boldsymbol{x}=\boldsymbol{0}\).

Il est évident que si \(A\boldsymbol{x}=\boldsymbol{0}\), alors \(A^TA\boldsymbol{x}=\boldsymbol{0}\).

Inversément, si \(A^TA\boldsymbol{x}=\boldsymbol{0}\), alors \[ \|A\boldsymbol{x}\|^2 =(A\boldsymbol{x})^T(A\boldsymbol{x}) =\boldsymbol{x}^T(A^TA\boldsymbol{x}) =\boldsymbol{0}\,, \] ce qui implique \(\|A\boldsymbol{x}\|=0\), c'est-à-dire \(A\boldsymbol{x}=\boldsymbol{0}\).

Passons maintenant à la preuve du théorème:

\(1.\Leftrightarrow 2.\): clair par ce que nous avons montré ci-dessus (un \(\boldsymbol{x}\) est pseudo-solution si et seulement si c'est une solution de l'équation normale).

\(2.\Leftrightarrow 3.\): On sait qu'un système carré \(M\boldsymbol{x}=\boldsymbol{y}\) possède une unique solution pour tout \(\boldsymbol{y}\) si et seulement si \(M\) est inversible.

\(3.\Leftrightarrow 4.\): En effet, les colonnes de \(A\) sont indépendantes si et seulement si l'équation \(A\boldsymbol{x}=\boldsymbol{0}\) ne possède que la solution triviale, et par le lemme ci-dessus, ceci est équivalent à dire que \(A^TA\boldsymbol{x}=\boldsymbol{0}\) ne possède que la solution triviale, qui encore une fois est équivalent à dire que \(A^TA\) est inversible, qui est \(2.\)

Exemple: Le système incompatible \[ \begin{pmatrix} 1&2&3\\ 1&-3&-2\\ 0&5&5\\ -1&1&0 \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} = \begin{pmatrix} 1\\ 2\\ 3\\ 4 \end{pmatrix} \] possède une infinité de pseudo-solutions. En effet, la troisième colonne de \(A\) est égale à la somme des deux premières; par le théorème, ceci implique que la solution n'est pas unique. On conclut que le nombre de solutions est infini, par le Théorème ''\(0,1,\infty\)'' appliqué à \(A^TA\boldsymbol{x}=A^T\boldsymbol{b}\).

Plus tard, nous appliquerons la méthode des moindres carrés pour résoudre d'autres problèmes d'optimisation, inspirés de l'analyse.