2024-X-Ens-Pc-corrigé

Polytechnique–ESPCI–ENS — PC — 2024

Durée : quatre heures. Calculatrices interdites.

Notations

Soit {d\geq1}. Pour {A,B\in\mathcal M_d(\mathbb R)}, on pose {\langle A,B\rangle=\operatorname{tr}(A^TB)}. Le coefficient de ligne {i} et colonne {j} de {M} est noté {M_{ij}}.
Les vecteurs de {\mathbb R^d} sont considérés comme des colonnes. Leur produit scalaire et leur norme euclidiens sont notés {\langle u,v\rangle_{\mathbb R^d}=u^Tv} et {|u|}.
On note {\begin{array}{rcl}O_d(\mathbb R)&=&\{R\in\mathcal M_d(\mathbb R):R^TR=I_d\},\\[8pt]SO_d(\mathbb R)&=&\{R\in O_d(\mathbb R):\det R=1\},\\[8pt]\operatorname{Dep}(\mathbb R^d)&=&\mathbb R^d\times SO_d(\mathbb R).\end{array}}La notation {(a_1|\cdots|a_d)} désigne la matrice de colonnes {a_i}, et {\operatorname{Diag}(\alpha_1,\ldots,\alpha_d)} la matrice diagonale correspondante.

1. Préliminaires

(4) Soient {D=\operatorname{Diag}(\alpha_1,\ldots,\alpha_d)} avec {\alpha_i\geq0}, et {R\in O_d(\mathbb R)}.

2. Ensemble des déplacements de ℝᵈ

Pour {g=(\tau,R)\in\operatorname{Dep}(\mathbb R^d)}, on pose {\phi_g(x)=Rx+\tau}. Si {\tau=0}, il s’agit d’une rotation vectorielle ; si {R=I_d}, d’une translation. Dans le cas général, {\phi_g} est un déplacement.

(7) Soit {g=(\tau,R)\in\operatorname{Dep}(\mathbb R^d)}.

3. Distance à déplacement près

Soit {n\geq1}. L’espace {\mathcal E_d^n(\mathbb R)=(\mathbb R^d)^n} des familles de {n} points est muni de la norme {\|z\|=(\sum\limits_{i=1}^n|z_i|^2)^{1/2}}.
On définit {g\cdot z=(\phi_g(z_i))_{1\leq i\leq n}}.

Pour {x,y\in\mathcal E_d^n(\mathbb R)}, on pose {\delta(x,y)=\inf_{g\in\operatorname{Dep}(\mathbb R^d)}\|y-g\cdot x\|.}Cet infimum existe, car l’ensemble considéré est non vide et minoré par {0}.

Pour {x\in\mathcal E_d^n(\mathbb R)}, on note {c(x)=\{g\cdot x:g\in\operatorname{Dep}(\mathbb R^d)\}}.

4. Un problème d’optimisation

On fixe {x,y\in\mathcal E_d^n(\mathbb R)} et l’on définit {J(\tau,R)=\sum_{i=1}^n|y_i-(Rx_i+\tau)|^2.}Pour {g=(\tau,R)}, cette quantité vaut {\|y-g\cdot x\|^2}. On note {\bar x=n^{-1}\sum\limits_{i=1}^n x_i} et {\bar y=n^{-1}\sum\limits_{i=1}^n y_i}.

On munit {\mathcal M_d(\mathbb R)} de la topologie de la norme définie en (2).

5. Calcul de δ lorsque det(Z) est strictement positif

Soit {Z\in\mathcal M_d(\mathbb R)} inversible et {S=Z^TZ}.

(17) Pour {1\leq i\leq d}, on pose {v_i=Zu_i/\sqrt{\lambda_i}}.

(19) On suppose {\det Z>0}.

6. Le cas où det(Z) est strictement négatif

On considère d’abord {R\in O_d(\mathbb R)}.

On suppose désormais {\det R=-1}.

On considère {D=\operatorname{Diag}(\alpha_1,\ldots,\alpha_d)} avec {\alpha_1\geq\cdots\geq\alpha_d\geq0}, et {U=(u_1|\cdots|u_d)}.

(24) On pose {S_0=(S_{ij})_{1\leq i,j\leq d-1}}.