Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 12 sur 12
  1. #1
    Membre confirmé Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2004
    Messages : 330
    Points : 209
    Points
    209

    Par défaut Chercher minimum : Résoudre système linéaire (sous contraint & matrice réctangulaire)

    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

  2. #2
    Membre Expert Avatar de davcha
    Profil pro
    Inscrit en
    avril 2004
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : avril 2004
    Messages : 1 257
    Points : 1 399
    Points
    1 399

    Par défaut

    x=pinv(A)*b.

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

  3. #3
    Membre confirmé Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2004
    Messages : 330
    Points : 209
    Points
    209

    Par défaut

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

  4. #4
    Membre Expert Avatar de davcha
    Profil pro
    Inscrit en
    avril 2004
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : avril 2004
    Messages : 1 257
    Points : 1 399
    Points
    1 399

    Par défaut

    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.

  5. #5
    Membre confirmé Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2004
    Messages : 330
    Points : 209
    Points
    209

    Par défaut

    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 ?

  6. #6
    Membre chevronné
    Homme Profil pro
    F5(){F5}
    Inscrit en
    avril 2008
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : F5(){F5}
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : avril 2008
    Messages : 477
    Points : 723
    Points
    723

    Par défaut

    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]...)

  7. #7
    Membre confirmé Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2004
    Messages : 330
    Points : 209
    Points
    209

    Par défaut

    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).

  8. #8
    Membre chevronné
    Homme Profil pro
    F5(){F5}
    Inscrit en
    avril 2008
    Messages
    477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : F5(){F5}
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : avril 2008
    Messages : 477
    Points : 723
    Points
    723

    Par défaut

    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

  9. #9
    Expert Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 183
    Détails du profil
    Informations personnelles :
    Âge : 57

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 183
    Points : 14 353
    Points
    14 353

    Par défaut

    Citation Envoyé par SKone Voir le message
    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
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  10. #10
    Membre Expert Avatar de davcha
    Profil pro
    Inscrit en
    avril 2004
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : avril 2004
    Messages : 1 257
    Points : 1 399
    Points
    1 399

    Par défaut

    Citation Envoyé par SKone Voir le message
    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.

  11. #11
    Expert Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 183
    Détails du profil
    Informations personnelles :
    Âge : 57

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 183
    Points : 14 353
    Points
    14 353

    Par défaut

    Citation Envoyé par davcha Voir le message
    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...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  12. #12
    Membre confirmé Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2004
    Messages : 330
    Points : 209
    Points
    209

    Par défaut

    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

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •