Systèmes sur-contraints

Soient A une matrice de taille nxp et b un vecteur de taille n. Le système Ax=b est sur-contraint si le nombre d'inconnues p est inférieur au nombre d'équations indépendantes.

Dans ce cas, le système n'a pas de solution exacte. Le problème consiste alors à trouver x qui réalise un minimum de la somme des écarts quadratiques (ou critère des moindres carrés ordinaires)

$$J(x)=\Vert Ax - b \Vert^2.$$

Cette fonction est convexe. Elle atteint un minimum global aux points critiques vérifiant l'équation d'Euler :

$$A^\ast A x = A^\ast b.$$

Si rg(A)=p, alors cette équation admet une unique solution donnée par

$$x = (A^\ast A)^{-1} A^\ast b,$$

qui correspond au produit de la pseudo-inverse de A et de b.

Cette solution peut s'obtenir en matlab ou octave de différentes façons :

• avec les fonctions \ ou mldivide,
• avec un calcul de pseudo-inverse par la fonction pinv,
• avec un calcul explicitant l'équation,
• ou encore avec la commande ols de résolution du problème des moindres carrés ordinaires.

x = A\b
x = mldivide(A,b)
x = pinv(A)*b
x = inv(A'*A)*A'*b
x = ols(b,A);

Si rg(A)<p, l'équation d'Euler admet une infinité de solutions. Il existe alors différentes manière de restreindre l'ensemble de solutions. Par exemple, on peut prendre pour solution celle qui est de norme minimale. Celle-ci est donnée par la pseudo inverse de A.

Lorsque r=rg(A)<p, les solutions apportées par les fonctions matlab vont être différentes.

• Les fonctions \ ou mldivide donneront une solution qui a au plus r composantes non nulles,
• La fonction pinv calculera la solution de norme minimale.

Voici un exemple en matlab qui illustre les différences entre ces fonctions :

 
A  = magic(8); A = A(:,1:6);  %matrice de rang 3  
b  = 260*ones(8,1);
x  = pinv(A)*b 
y  = A\b
norm(x)
norm(y)

renvoie

x =
    1.1538
    1.4615
    1.3846
    1.3846
    1.4615
    1.1538
y =
    4.0000
    5.0000
         0
         0
         0
   -1.0000
ans=
    3.2817  
ans=
    6.4807

A noter, en octave, les fonctions \ et pinv produisent toutes les deux le premier résultat.