Connectez-vous pour consulter le corrigé.
La méthode des moindres carrés
Durée : 4 heures. Calculatrice autorisée.
Sujet du concours Centrale-Supélec 2026.
Ce problème comporte 5 parties. Les parties A, B, C et D sont indépendantes entre elles.
L’objet de ce sujet est l’étude d’une méthode très utile en intelligence artificielle : la méthode des moindres carrés. Les parties A et C présentent des domaines des mathématiques que l’on peut reformuler en termes de problème des moindres carrés. La partie D amène à résoudre des systèmes d’équations linéaires au sens des moindres carrés à l’aide de la notion de décomposition en valeurs singulières. La partie B introduit la notion de limites de suites de matrices, que l’on utilise dans la partie E pour résoudre le problème étudié dans la partie D.
Si \(k\) et \(l\) sont deux entiers tels que \(k\leqslant l\), on note \(\left[\kern-0.15em\left[ {k,l} \right]\kern-0.15em\right]\) l’ensemble des entiers \(i\) tels que \(k\leqslant i\leqslant l\).
L’espace vectoriel des polynômes à coefficients dans \(\mathbb{R}\) est noté \(\mathbb{R}[X]\). Pour \(n\in\mathbb{N}\), on note \(\mathbb{R}_n[X]\) l’espace vectoriel des polynômes à coefficients dans \(\mathbb{R}\) de degré inférieur ou égal à \(n\).
Pour \(n\in\mathbb{N}^\ast\) et \(p\in\mathbb{N}^\ast\), on note \(M_{n,p}(\mathbb{R})\) l’espace vectoriel des matrices à n lignes et \(p\) colonnes.
On note aussi \(M_n(\mathbb{R})=M_{n,n}(\mathbb{R})\) l’espace vectoriel des matrices carrées de taille \(n\).
La transposée d’une matrice \(A=(a_{i,j})_{\substack{1\leqslant i\leqslant n\\ 1\leqslant j\leqslant p}}\in M_{n,p}(\mathbb{R})\) est notée \(A^T\).
Elle est définie par \(A^T=(a_{j,i})_{\substack{1\leqslant i\leqslant n\\ 1\leqslant j\leqslant p}}\in M_{p,n}(\mathbb{R})\).
La trace d’une matrice \(A=(a_{i,j})_{1\leqslant i,j\leqslant n}\in M_n(\mathbb{R})\) est notée \(\mathrm{Tr}(A)\). Elle est définie par \(\mathrm{Tr}(A)=\displaystyle\sum_{i=1}^na_{i,i}\).
Le produit scalaire canonique sur l’espace vectoriel \(M_{n,1}(\mathbb{R})\) des vecteurs colonnes à \(n\) lignes est noté \(\langle\cdot,\cdot\rangle\) et sa norme associée est notée \(\left\| \cdot \right\|_2\). Ce produit scalaire est défini par : \[\forall A=\begin{pmatrix}a_1\\ \vdots\\ a_n\end{pmatrix},\ \forall B=\begin{pmatrix}b_1\\ \vdots\\ b_n\end{pmatrix},\qquad \langle A,B\rangle=A^TB=\sum_{i=1}^na_ib_i\quad\text{et}\quad\left\| A \right\|_2=\sqrt{\sum_{i=1}^na_i^2}\]
Le produit scalaire canonique sur l’espace vectoriel \(M_n(\mathbb{R})\) des matrices carrées est aussi noté \(\langle\cdot,\cdot\rangle\) et sa norme associée est notée \(\left\| \cdot \right\|_2\). Ce produit scalaire est défini par : \[\forall A=(a_{i,j})_{1\leqslant i,j\leqslant n},\ \forall B=(b_{i,j})_{1\leqslant i,j\leqslant n},\qquad \langle A,B\rangle=\mathrm{Tr}\!\left(A^TB\right)=\sum_{i=1}^n\sum_{j=1}^na_{i,j}b_{i,j}\] et : \[\left\| A \right\|_2=\sqrt{\sum_{i=1}^n\sum_{j=1}^na_{i,j}^2}\]
L’ensemble des valeurs propres complexes d’une matrice \(A\in M_n(\mathbb{R})\) s’appelle le spectre de \(A\) et se note \(\mathrm{Sp}(A)\).
On munit \(M_{4,1}(\mathbb{R})\) de son produit scalaire canonique. Soit \(F=\mathrm{Vect}(e_1,e_2,e_3)\) avec : \[e_1=\begin{pmatrix}1\\ -2\\ 1\\ 0\end{pmatrix}\qquad e_2=\begin{pmatrix}1\\ 1\\ 1\\ 0\end{pmatrix}\qquad e_3=\begin{pmatrix}1\\ 0\\ -1\\ 0\end{pmatrix}\]
Justifier que \((e_1,e_2,e_3)\) est une base orthogonale de \(F\). Proposer une base orthonormée de \(F\).
Calculer le projeté orthogonal sur \(F\) d’un vecteur colonne \(\begin{pmatrix}x\\ y\\ z\\ t\end{pmatrix}\in M_{4,1}(\mathbb{R})\).
On note \(v=\begin{pmatrix}1\\ 1\\ 1\\ 1\end{pmatrix}\). Calculer \(\displaystyle\min_{u\in F}\left\| v-u \right\|_2\).
Soit \(E=\mathcal{C}^0_{2\pi}(\mathbb{R},\mathbb{R})\) l’espace vectoriel des fonctions continues \(2\pi\)-périodiques. On munit \(E\) du produit scalaire défini par : \[\forall(f,g)\in E^2,\qquad \varphi\left(f,g\right)=\frac{1}{2\pi}\int_0^{2\pi}f(t)g(t)\ \mathrm{d}t\]
On note \(\left\| \cdot \right\|\) la norme associée. Les coefficients de Fourier d’une fonction \(f\in\mathcal{C}^0_{2\pi}(\mathbb{R},\mathbb{C})\) sont définis (pour \(n\geqslant1\)) par : \[a_0(f)=\frac{1}{2\pi}\int_0^{2\pi}f(t)\ \mathrm{d}t\qquad a_n(f)=\frac{1}{\pi}\int_0^{2\pi}f(t)\cos(nt)\ \mathrm{d}t\qquad b_n(f)=\frac{1}{\pi}\int_0^{2\pi}f(t)\sin(nt)\ \mathrm{d}t\]
Pour tout \(n\in\mathbb{N}\), nous introduisons les fonctions \(e_n:x\longmapsto\cos(nx)\) et \(f_n:x\longmapsto\sin(nx)\).
Les sommes partielles de la série de Fourier d’une fonction \(f\in E\) sont les fonctions définies par : \[\forall N\in\mathbb{N}^\ast,\qquad S_N(f)=a_0(f)+\sum_{n=1}^N\left(a_n(f)e_n+b_n(f)f_n\right)\]
Soient \(\alpha\in\mathbb{R}\setminus\mathbb{Z}\) et \(f\) la fonction \(2\pi\)-périodique telle que \(f(x)=\cos(\alpha x)\) pour tout \(x\in\left]-\pi,\pi\right]\).
Montrer que pour tout \(n\geqslant1\), on a \(b_n(f)=0\) et \(a_0(f)=\frac{\sin(\alpha\pi)}{\alpha\pi}\) et \(a_n(f)=\frac{(-1)^n}{\pi}\,\frac{2\alpha\sin(\alpha\pi)}{\alpha^2-n^2}\).
Montrer que les séries \(\displaystyle\sum_{n\geqslant1}\frac{1}{n^2-\alpha^2}\) et \(\displaystyle\sum_{n\geqslant1}\frac{1}{(n^2-\alpha^2)^2}\) convergent, et calculer \(\displaystyle\sum_{n=1}^{+\infty}\frac{1}{n^2-\alpha^2}\) et \(\displaystyle\sum_{n=1}^{+\infty}\frac{1}{(n^2-\alpha^2)^2}\).
Montrer que pour tout \(t\in\mathbb{R}\setminus\pi\mathbb{Z}\), on a \(\frac{\cos(t)}{\sin(t)}=\frac{1}{t}+\displaystyle\sum_{n=1}^{+\infty}\frac{2t}{t^2-(n\pi)^2}\).
Soit \(f:\mathbb{R}\longrightarrow\mathbb{C}\) une fonction \(2\pi\)-périodique de classe \(\mathcal{C}^2\) qui est solution de l’équation différentielle : \[f''+\mathrm{e}^{ix}f=0 \tag{$\mathcal{E}$}\]
Pour tout \(n\in\mathbb{Z}\), on pose \(c_n(f)=\displaystyle\frac{1}{2\pi}\int_0^{2\pi}f(t)\mathrm{e}^{-int}\ \mathrm{d}t\) et \(c_n(f'')=\displaystyle\frac{1}{2\pi}\int_0^{2\pi}f''(t)\mathrm{e}^{-int}\ \mathrm{d}t\).
Montrer que pour tout \(n\in\mathbb{N}^\ast\) on a \(c_n(f)=\frac{a_n(f)-ib_n(f)}{2}\) et \(c_{-n}(f)=\frac{a_n(f)+ib_n(f)}{2}\).
Montrer que pour tout \(n\in\mathbb{N}^\ast\) on a \(a_n(f)=c_n(f)+c_{-n}(f)\) et \(b_n(f)=i(c_n(f)-c_{-n}(f))\).
Soit \(n\in\mathbb{Z}\).
Montrer que \(c_n(f'')=-n^2c_n(f)\), puis que \(c_{n-1}(f)=n^2c_n(f)\).
En déduire que : \[c_n(f)=\begin{cases}\dfrac{c_0(f)}{(n!)^2} & \text{si } n\geqslant0\\ 0 & \text{si } n<0\end{cases}\]
Montrer que pour tout \(x\in\mathbb{R}\), on a \(f(x)=c_0(f)+\displaystyle\sum_{n=1}^{+\infty}\left(c_n(f)\mathrm{e}^{inx}+c_{-n}(f)\mathrm{e}^{-inx}\right)=c_0(f)\sum_{n=0}^{+\infty}\frac{\mathrm{e}^{inx}}{(n!)^2}\).
On admet que la fonction définie par \(x\longmapsto\displaystyle\sum_{n=0}^{+\infty}\frac{\mathrm{e}^{inx}}{(n!)^2}\) est bien une solution de l’équation \((\mathcal{E})\).
On rappelle que l’ensemble des solutions de l’équation \((\mathcal{E})\) est un sous-espace vectoriel de \(\mathcal{C}^\infty(\mathbb{R},\mathbb{C})\).
Quelle est sa dimension ? Justifier. L’équation \((\mathcal{E})\) admet-elle une solution qui n’est pas \(2\pi\)-périodique ?
Montrer que, pour tout \(N\in\mathbb{N}^\ast\), la famille \((e_0,\dots e_N,f_1,\dots,f_N)\) est orthogonale pour \(\varphi\). Est-elle orthonormale ?
Soient \(g\in E\) et \(N\in\mathbb{N}^\ast\). On note \(V_N=\mathrm{Vect}(e_0,\dots,e_N,f_1,\dots,f_N)\).
Quelle est la projection orthogonale de \(g\) sur \(V_N\) ? En déduire une fonction \(h\in E\) telle que \(\left\| g-h \right\|=\displaystyle\min_{v\in V_N}\left\| g-v \right\|\).
Soit \((M_k)_{k\in\mathbb{N}}\) une suite de matrices de \(M_{n,p}(\mathbb{R})\), avec \(M_k=\begin{pmatrix}m_{k,1,1} & \dots & m_{k,1,p}\\ \vdots & & \vdots\\ m_{k,n,1} & \dots & m_{k,n,p}\end{pmatrix}\) (pour tout \(k\in\mathbb{N}\)).
On dit que la suite \((M_k)_{k\in\mathbb{N}}\) converge si pour tout \((i,j)\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\times\left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right]\) la suite \((m_{k,i,j})_{k\in\mathbb{N}}\) converge. On note alors : \[\lim_{k\to+\infty}M_k=\begin{pmatrix}\displaystyle\lim_{k\to+\infty}(m_{k,1,1}) & \dots & \displaystyle\lim_{k\to+\infty}(m_{k,1,p})\\ \vdots & & \vdots\\ \displaystyle\lim_{k\to+\infty}(m_{k,n,1}) & \dots & \displaystyle\lim_{k\to+\infty}(m_{k,n,p})\end{pmatrix}\]
Lorsque la suite \((M_k)_{k\in\mathbb{N}}\) ne converge pas, on dit que la suite \((M_k)_{k\in\mathbb{N}}\) diverge.
On admettra sans preuve que, si \((M_k)_{k\in\mathbb{N}}\) converge, alors, pour tout \((q,r)\in\mathbb{N}^\ast\times\mathbb{N}^\ast\), toute matrice \(P\in M_{q,n}(\mathbb{R})\) et toute matrice \(Q\in M_{p,r}(\mathbb{R})\) la suite \((PM_kQ)_{k\in\mathbb{N}}\) converge et \(\displaystyle\lim_{k\to+\infty}(PM_kQ)=P\left(\lim_{k\to+\infty}M_k\right)Q\).
Soient \(A=\begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}\) et \(B=\begin{pmatrix}-1/2 & -\sqrt{3}/2\\ \sqrt{3}/2 & -1/2\end{pmatrix}\). Montrer que les suites \(\left(A^k\right)_{k\in\mathbb{N}}\) et \(\left(B^k\right)_{k\in\mathbb{N}}\) divergent.
Soit \(A\) une matrice diagonalisable sur \(\mathbb{R}\). Montrer que la suite \(\left(A^k\right)_{k\in\mathbb{N}}\) converge si et seulement si \(\mathrm{Sp}(A)\subset\left]-1,1\right]\).
Soit \(A=\frac{1}{2}\begin{pmatrix}0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0\end{pmatrix}\). Montrer que \(A\) est diagonalisable sur \(\mathbb{R}\), et que la suite de matrices \(\left(A^k\right)_{k\in\mathbb{N}}\) converge.
Montrer que les matrices \(A=\begin{pmatrix}0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 1 & -1\end{pmatrix}\) et \(T=\begin{pmatrix}1 & 0 & 0\\ 0 & -1 & 1\\ 0 & 0 & -1\end{pmatrix}\) sont semblables.
La suite de matrices \(\left(A^k\right)_{k\in\mathbb{N}}\) converge-t-elle ?
Dans la suite de l’énoncé, on pourra utiliser sans preuve le résultat suivant :
si \(M\in M_{n,p}(\mathbb{R})\) est une matrice et si \((M_k)_{k\in\mathbb{N}}\) est une suite de matrices de \(M_{n,p}(\mathbb{R})\), alors : \[\lim_{k\to+\infty}M_k=M\qquad\text{si et seulement si}\qquad\lim_{k\to+\infty}\left\| M_k-M \right\|_2=0\]
Soient \(n\in\mathbb{N}^\ast\) et \((x_0,\dots,x_n)\in\mathbb{R}^{n+1}\) une famille de nombres réels deux à deux distincts. Pour chaque \(i\in\left[\kern-0.15em\left[ {0,n} \right]\kern-0.15em\right]\), on note : \[L_i(X)=\prod_{\substack{0\leqslant j\leqslant n,\ j\neq i}}\frac{X-x_j}{x_i-x_j}\]
Montrer que pour tout \((i,k)\in\left[\kern-0.15em\left[ {0,n} \right]\kern-0.15em\right]^2\), on a \(L_i(x_k)=\begin{cases}1 & \text{si } k=i\\ 0 & \text{sinon}\end{cases}\)
Montrer que l’on peut munir \(\mathbb{R}_n[X]\) d’un produit scalaire \(\langle\cdot,\cdot\rangle\) en posant \(\langle P,Q\rangle=\displaystyle\sum_{k=0}^nP(x_k)Q(x_k)\).
Montrer que \((L_0,\dots,L_n)\) est une base orthonormée de \(\mathbb{R}_n[X]\) muni du produit scalaire \(\langle\cdot,\cdot\rangle\).
Montrer que pour tout \(P\in\mathbb{R}_n[X]\) et tout \(i\in\left[\kern-0.15em\left[ {0,n} \right]\kern-0.15em\right]\), on a \(\langle L_i,P\rangle=P(x_i)\), puis que \(P=\displaystyle\sum_{i=0}^nP(x_i)L_i\).
Soit \((a,b)\in\mathbb{R}^2\) tel que pour tout \(i\in\left[\kern-0.15em\left[ {0,n} \right]\kern-0.15em\right]\) on ait \(a<x_i<b\). Soit \(f\in\mathcal{C}^{n+1}([a,b],\mathbb{R})\). On note \(P_f=\displaystyle\sum_{i=0}^nf(x_i)L_i\).
Soient \(m\leqslant n\). En calculant \(\langle P_f-Q,P_f-Q\rangle\), montrer l’existence et l’unicité d’un polynôme \(R\in\mathbb{R}_m[X]\) tel que : \[\sum_{i=0}^n\left(f(x_i)-R(x_i)\right)^2=\min_{Q\in\mathbb{R}_m[X]}\left(\sum_{i=0}^n\left(f(x_i)-Q(x_i)\right)^2\right)\]
Soit \(g\in\mathcal{C}^{n+1}([a,b],\mathbb{R})\). On suppose que \(g\) possède au moins \(n+2\) zéros deux à deux distincts dans \([a,b]\). Montrer par récurrence sur \(n\) que \(g^{(n+1)}\) a au moins un zéro dans \([a,b]\). On pourra utiliser le théorème de Rolle.
Soit \(x\in[a,b]\) avec \(x\neq x_i\) pour tout \(i\in\left[\kern-0.15em\left[ {0,n} \right]\kern-0.15em\right]\). Soit \(K=\frac{f(x)-P_f(x)}{\prod_{i=0}^n(x-x_i)}\).
Montrer que \(W:t\longmapsto f(t)-P_f(t)-K\displaystyle\prod_{i=0}^n(t-x_i)\) s’annule en \(n+2\) points distincts de \([a,b]\).
En déduire l’existence de \(\xi_x\in[a,b]\) tel que \(f(x)-P_f(x)=\frac{\prod_{i=0}^n(x-x_i)}{(n+1)!}\,f^{(n+1)}(\xi_x)\).
Soit \(n\geqslant2\) un entier. Considérons \(n\) points du plan réel \((x_1,y_1),\dots,(x_n,y_n)\) avec \(x_1,\dots,x_n\) deux à deux distincts tels que \((x_1,\dots,x_n)\) ne soit pas colinéaire au vecteur \((1,\dots,1)\).
En dimension \(2\), la régression linéaire consiste à trouver une relation affine entre deux grandeurs physiques, c’est-à-dire à chercher une droite affine s’approchant le plus possible des points \((x_1,y_1),\dots,(x_n,y_n)\) (au sens des moindres carrés).
Pour formuler ce problème de manière précise et rigoureuse, nous notons : \[E(a,b)=\sum_{i=1}^n(y_i-a-bx_i)^2\qquad\text{et}\qquad A=\begin{pmatrix}1 & x_1\\ 1 & x_2\\ \vdots & \vdots\\ 1 & x_n\end{pmatrix}\qquad\text{et}\qquad Y=\begin{pmatrix}y_1\\ y_2\\ \vdots\\ y_n\end{pmatrix}\]
Le problème est alors de trouver les valeurs de \(a\) et \(b\) qui minimisent la fonction \(E\).
Montrer que \(E\) admet un minimum \(m\) sur \(\mathbb{R}^2\) (qu’on ne demande pas de calculer) et que \(m=\displaystyle\min_{(a,b)\in\mathbb{R}^2}\left\| A\begin{pmatrix}a\\ b\end{pmatrix}-Y \right\|_2^2\).
Montrer que \(\det\!\left(A^TA\right)=n\left(\displaystyle\sum_{k=1}^nx_k^2\right)-\left(\sum_{k=1}^nx_k\right)^2\), puis justifier l’affirmation \(\det\!\left(A^TA\right)>0\).
Indication : On pourra utiliser l’inégalité de Cauchy-Schwarz
Calculer le gradient de \(E:(a,b)\longmapsto E(a,b)\).
Soit \((a_0,b_0)\) un point critique de \(E\). Montrer que l’on a \(A^TA\begin{pmatrix}a_0\\ b_0\end{pmatrix}=A^TY\).
En déduire qu’il existe un unique couple \((c,d)\in\mathbb{R}^2\) tel que \(E(c,d)=\displaystyle\min_{(a,b)\in\mathbb{R}^2}E(a,b)\).
Nous allons maintenant généraliser les idées de la sous-section précédente au cas de la dimension quelconque.
Soit \(A\in M_{n,p}(\mathbb{R})\). Notons \(\mathrm{Col}(A)=\mathrm{Vect}(C_1,\dots,C_p)\) avec \(C_1,\dots C_p\) les colonnes de \(A\). Soit \(y\in M_{n,1}(\mathbb{R})\).
Soit \(x\in M_{p,1}(\mathbb{R})\) tel que \(A^TAx=0\). Montrer que \(\left\| Ax \right\|_2=0\).
Montrer que \(\mathrm{Ker}\!\left(A^TA\right)=\mathrm{Ker}\left(A\right)\), puis que \(\mathrm{rg}(A^TA)=\mathrm{rg}(A)\).
Montrer l’existence d’un unique couple \((u,d)\in M_{p,1}(\mathbb{R})\times(\mathrm{Col}(A))^\perp\) tel que \(y=Au+d\).
Montrer que pour tout \(x\in M_{p,1}(\mathbb{R})\), on a \(\left\| Ax-y \right\|_2\geqslant\left\| d \right\|_2\) avec égalité si et seulement si \(x-u\in\mathrm{Ker}(A)\).
Montrer que \(A^Ty=A^TAu\).
Soit \(x_0\in M_{p,1}(\mathbb{R})\). Montrer que : \[\left\| Ax_0-y \right\|_2=\min_{x\in M_{p,1}(\mathbb{R})}\left\| Ax-y \right\|_2\qquad\Longleftrightarrow\qquad A^TAx_0=A^Ty\]
Supposons \(n>p\) et que la matrice \(A\) est de rang maximal, c’est-à-dire que le rang de \(A\) est égal à \(p\).
Montrer que \(A^TA\) est inversible.
En déduire que l’équation \(\left\| Ab-y \right\|_2=\displaystyle\min_{x\in M_{p,1}(\mathbb{R})}\left\| Ax-y \right\|_2\) a une unique solution donnée par \(b=(A^TA)^{-1}A^Ty\).
Soient \(A\in M_{n,p}(\mathbb{R})\) non nulle et \(y\in M_{n,1}(\mathbb{R})\). Nous allons généraliser le résultat de la question Q33.
Dans la suite, nous notons \(\mathrm{Diag}_{k,l}(\alpha_1,\dots,\alpha_{\min(k,l)})\) la matrice de taille \(k\times l\) dont le coefficient en ligne \(i\) et colonne \(i\) est \(\alpha_i\) (pour tout indice \(i\leqslant\min(k,l)\)), et dont tous les autres coefficients sont nuls.
Montrer que pour tout vecteur colonne \(X\in M_{p,1}(\mathbb{R})\), les nombres \(X^TA^TAX\) et \(X^TX\) sont positifs ou nuls.
Montrer que les valeurs propres de la matrice \(A^TA\) sont toutes positives ou nulles.
Notons \(r=\mathrm{rg}\!\left(A^TA\right)=\mathrm{rg}\left(A\right)\) (égalité prouvée à la question Q28).
Montrer qu’il existe des nombres réels \(\lambda_1\geqslant\dots\geqslant\lambda_r>0\) et une matrice orthogonale \(V\in O_p(\mathbb{R})\) tels que \(A^TA=V\mathrm{Diag}_{p,p}(\lambda_1,\dots,\lambda_r,0,\dots0)V^T\).
Notons \(v_i\) la \(i\)-ème colonne de \(V\).
Montrer que la famille \((Av_1,\dots,Av_p)\) est orthogonale pour le produit scalaire canonique de \(M_{n,1}(\mathbb{R})\), et que, pour tout \(i\in\left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right]\), on a \(\left\| Av_i \right\|_2=\begin{cases}\sqrt{\lambda_i} & \text{si } i\leqslant r\\ 0 & \text{si } i\geqslant r+1\end{cases}\)
Montrer l’existence d’une base orthonormée \((u_1,\dots,u_n)\) de \(M_{n,1}(\mathbb{R})\) telle que \(u_i=\frac{1}{\sqrt{\lambda_i}}\,Av_i\) pour tout \(i\leqslant r\).
Notons \(U\) la matrice dont la \(i\)-ème colonne est \(u_i\) et \(D=\mathrm{Diag}_{n,p}\!\left(\sqrt{\lambda_1},\dots,\sqrt{\lambda_r},0:\dots,0\right)\in M_{n,p}(\mathbb{R})\).
Vérifier que \(U\in O_n(\mathbb{R})\) et que \(AV=UD\).
En particulier, on a \(A=UDV^T\). Cette écriture s’appelle une décomposition en valeur singulière de \(A\). Posons : \[\Delta=\mathrm{Diag}_{p,n}\!\left(\frac{1}{\sqrt{\lambda_1}},\dots,\frac{1}{\sqrt{\lambda_r}},0,\dots,0\right)\in M_{p,n}(\mathbb{R})\qquad\text{et}\qquad\widetilde{A}=V\Delta U^T\in M_{p,n}(\mathbb{R})\]
Montrer que \(A\widetilde{A}\) est la matrice de la projection orthogonale sur \(\mathrm{Im}(A)\).
Soit \(y\in M_{n,1}(\mathbb{R})\). Soit \(b=\widetilde{A}y\in M_{p,1}(\mathbb{R})\). Vérifier que \(\left\| Ab-y \right\|_2=\displaystyle\min_{x\in M_{p,1}(\mathbb{R})}\left\| Ax-y \right\|_2\).
Soit \(x_0\in M_{p,1}(\mathbb{R})\) un autre vecteur qui vérifie \(\left\| Ax_0-y \right\|_2=\displaystyle\min_{x\in M_{p,1}(\mathbb{R})}\left\| Ax-y \right\|_2\). Nous allons montrer que \(\left\| x_0 \right\|_2\geqslant\left\| b \right\|_2\).
Montrer que \(Ab-y\in\mathrm{Im}(A)^\perp\). En déduire que \(x_0-b\in\mathrm{Ker}(A)\)
Montrer que \(b\in\mathrm{Ker}(A)^\perp\).
Indication : on pourra exprimer \(\mathrm{Im}\!\left(\widetilde{A}\right)\) et \(\mathrm{Ker}(A)\) en fonction des vecteurs colonnes \(v_i\).
Montrer que \(\left\| x_0 \right\|_2\geqslant\left\| b \right\|_2\) avec égalité si et seulement si \(x_0=b\).
Soit \(A\in M_{n,p}(\mathbb{R})\) et \(y\in M_{n,1}(\mathbb{R})\). Nous avons vu à la question Q35 que les valeurs propres \(\lambda_1\leqslant\dots\leqslant\lambda_p\) de \(A^TA\) sont des nombres réels positifs ou nuls. Dans cette partie, nous supposons en plus que pour tout \(i\), on a \(\lambda_i>0\).
Nous reformulons notre problème des moindres carrés en remarquant (par le calcul) que : \[\forall x\in M_{p,1}(\mathbb{R}),\qquad \left\| Ax-y \right\|_2^2=\langle A^TAx,x\rangle-2\langle x,A^Ty\rangle+\langle y,y\rangle\]
Nous allons étudier une suite de matrices convergente dont la limite sera un minimum de la fonction : \[f:\begin{cases}M_{p,1}(\mathbb{R}) & \longrightarrow\quad\mathbb{R}\\ x & \longmapsto\quad\langle A^TAx,x\rangle-2\langle x,A^Ty\rangle\end{cases}\]
Soit \((e_1,\dots,e_p)\) une base orthonormale de \(M_{p,1}(\mathbb{R})\) telle que pour tout \(i\in\left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right]\) on ait \(A^TAe_i=\lambda_ie_i\).
Montrer que la matrice \(A^TA\) est inversible, et justifier que \(\mathrm{Ker}(A)=\{\,0\,\}\).
Montrer que l’application \(\begin{cases}M_{p,1}(\mathbb{R})\times M_{p,1}(\mathbb{R}) & \longrightarrow\quad\mathbb{R}\\ (x,y) & \longmapsto\quad\left\langle A^TAx,y\right\rangle\end{cases}\) est un produit scalaire.
Soient \((v_1,\dots,v_p)\in\mathbb{R}^p\) et \(v=\displaystyle\sum_{i=1}^pv_ie_i\).
Montrer que pour tout \((\alpha,\beta)\in\mathbb{R}^2\) on a : \(\alpha\beta\leqslant\frac{1}{4}(\alpha+\beta)^2\).
Montrer que : \[\left\langle A^TAv,v\right\rangle\left\langle(A^TA)^{-1}v,v\right\rangle\leqslant\frac{1}{4}\,\frac{\lambda_1}{\lambda_p}\left(\sum_{i=1}^p\left(\frac{\lambda_i}{\lambda_1}+\frac{\lambda_p}{\lambda_i}\right)v_i^2\right)^2\]
Soit \(\psi:t\longmapsto\frac{t}{\lambda_1}+\frac{\lambda_p}{t}\). Calculer le maximum de \(\psi\) sur \([\lambda_1,\lambda_p]\).
On note \(c(A)=\frac{\lambda_p}{\lambda_1}\). Montrer l’inégalité de Kantorovich : \[\left\langle A^TAv,v\right\rangle\left\langle(A^TA)^{-1}v,v\right\rangle\leqslant\frac{(c(A)+1)^2}{4c(A)}\left\| v \right\|_2^4\]
Nous souhaitons maintenant déterminer une approximation de l’unique solution \(\ell\) à l’équation \(A^TA\ell=A^Ty\).
Nous définissons une suite par récurrence en choisissant un vecteur \(x_0\in M_{p,1}(\mathbb{R})\) et en posant pour \(k\in\mathbb{N}\) : \[d_k=A^TAx_k-A^Ty\qquad\qquad t_k=\frac{\left\| d_k \right\|_2^2}{\langle A^TAd_k,d_k\rangle}\qquad\qquad x_{k+1}=x_k-t_kd_k\]
Pour que cette définition ait un sens, nous supposons que le vecteur \(d_k\) est non nul pour tout \(k\in\mathbb{N}\). Cette hypothèse n’est pas restrictive : s’il existe \(k\) tel que \(d_k=0\) alors \(x_k=\ell\) et nous avons ainsi la valeur exacte de \(\ell\).
Soit \(\ell=(A^TA)^{-1}A^Ty\in M_{p,1}(\mathbb{R})\).
Vérifier que pour tout \(x\in M_{p,1}(\mathbb{R})\), on a \(f(x)-f(\ell)=\langle A^TA(x-\ell),x-\ell\rangle\).
Montrer que pour tout \(k\in\mathbb{N}\), on a : \[f(x_{k+1})-f(\ell)=(f(x_k)-f(\ell))\left(1-\frac{\left\| d_k \right\|_2^4}{\langle A^TAd_k,d_k\rangle\langle(A^TA)^{-1}d_k,d_k\rangle}\right)\]
Montrer que pour tout \(k\in\mathbb{N}\), on a : \[\lambda_1\left\| x_k-\ell \right\|_2^2\leqslant f(x_k)-f(\ell)\leqslant(f(x_0)-f(\ell))\left(\frac{c(A)-1}{c(A)+1}\right)^{2k}\]
Montrer que la suite \((x_k)_{k\in\mathbb{N}}\) converge vers \(\ell\), et que \(\left\| A\ell-y \right\|_2=\displaystyle\min_{x\in M_{p,1}(\mathbb{R})}\left\| Ax-y \right\|_2\).
\(\diamond\)Fin\(\diamond\)
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
Un long sujet autour des moindres carrés : distance à un sous-espace et séries de Fourier, limites de puissances de matrices, interpolation de Lagrange, régression linéaire, équations normales et décomposition en valeurs singulières, puis convergence de la méthode du gradient avec l'inégalité de Kantorovich.
Les parties sont indépendantes et bien guidées, mais nombreuses.