Chercher minimum : Résoudre système linéaire (sous contraint & matrice réctangulaire) [Résolu]

[SKone]

Bonjour,

Il y a deux situation :
Pour la première, je pense que le titre résume assez bien la situation.
J'ai un système du genre :
Ax=b
A a aucune particularité intéressante, ni symétrique, ni creuse, ni carré, A est rectangulaire, dans le pire des cas 69x3000.
Je ne sais pas si le système est soluble, je dois donc trouver x pour minimiser la distance entre
Ax et b.
Comme vous pouvez le voir j'ai beaucoup moins d'équation que d'inconnu. Existe-t-il une méthode pour résoudre ce système numériquement.
Je dois trouver x pour faire faire converger Ax vers b.

La seconde situation est exactement la même a la différence près que A est carré. Donc même question comment trouver x pour faire converger, Ax vers b ou minimiser la distance entre Ax et b.

Merci

[davcha]

x=pinv(A)*b.

C'est la plus petite solution au problème des moindres carrés.

[SKone]

pinv == Pseudo Inverse ? => Moore-Penrose Pseudo Inverse ?

[davcha]

Oui.

Dans ton cas, si ta matrice 69x3000 est M, pinv(M) = M'(MM')^-1, où M' est la transposée de M et X^-1 l'inverse de X.

[SKone]

Mais comme le système est sous contraint (fortement 69 équations, 1500 inconnus), il me cela ne suffira pas...

Quel méthode utiliseriez-vous pour faire converger le système vers une solution ?

[galerien69]

qu'attendrais-du comme résolution pour le système
Ax=b
avec A=[1 1], et b=2
le système est sous contraint, il admet une infinité de solutions..
(x=[1,1], x=[2,0],[3,-1]...)

[SKone]

Je cherche la solution qui minimise la distance entre Ax et b.
Comme on ne peut pas être sur d'être dans le minimum globale je voudrais une distance inférieur à 10^-2 (distance euclidienne).

[galerien69]

davcha a déjà répondu à ton problème (je sais pas d'ailleurs pourquoi tu écartes sa solution, il te propose du pinv pour pallier le problème de la matrice rectangulaire. Je sais pas pourquoi ca minimise la distance des moindres carrés, mais ca serait plutot la question à poser plutot que d'écarter la solution!
)

C'est la plus petite solution au problème des moindres carrés.

si tu veux pas pinv, utilises levenberg marquardt par exemple
min ||Ax-b|| se réécrit
min somme_i=0^taille_de_x (f(x_i) - b_i)^2
avec f(x_i) = A(i,: )x

[souviron34]

Envoyé par SKone

Comme vous pouvez le voir j'ai beaucoup moins d'équation que d'inconnu. Existe-t-il une méthode pour résoudre ce système numériquement.

oui..

Algorithme du simplexe

[davcha]

Envoyé par SKone

Je cherche la solution qui minimise la distance entre Ax et b.
Comme on ne peut pas être sur d'être dans le minimum globale je voudrais une distance inférieur à 10^-2 (distance euclidienne).

Si tu as 1500 inconnues et 69 équations, alors seules 69 inconnues sont contraintes. Les 1431 autres sont libres. Au final, l'espace de tes solutions est un espace à 1431 dimensions. N'importe quel vecteur dans cet espace minimise ta distance à zéro.

C'est dans le cas inverse, où tu as plus d'équations linéairement indépendantes que d'inconnues que tu ne peux pas trouver une solution exacte qui satisfasse toutes tes contraintes.

Et dans les deux cas, la solution que je t'ai proposée est suffisante.

[souviron34]

Envoyé par davcha

C'est dans le cas inverse, où tu as plus d'équations linéairement indépendantes que d'inconnues que tu ne peux pas trouver une solution exacte qui satisfasse toutes tes contraintes.

tu as raison je me suis mélangé les pinceaux en lisant trop vite.. Bien entendu le simplex est pour ce cas...

[SKone]

En effet c'est très mal formuler je reformulé :
http://www.developpez.net/forums/d12...on-contrainte/

En tout cas ce problème là est [Résolu]

Merci