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

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

    Informations forums :
    Inscription : mai 2004
    Messages : 323
    Points : 179
    Points
    179

    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 286
    Points
    1 286

    Par défaut

    x=pinv(A)*b.

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

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

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

    Informations forums :
    Inscription : mai 2004
    Messages : 323
    Points : 179
    Points
    179

    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 286
    Points
    1 286

    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 actif Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    323
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : Canada

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

    Informations forums :
    Inscription : mai 2004
    Messages : 323
    Points : 179
    Points
    179

    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
    474
    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 : 474
    Points : 652
    Points
    652

    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 actif Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    323
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : Canada

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

    Informations forums :
    Inscription : mai 2004
    Messages : 323
    Points : 179
    Points
    179

    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
    474
    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 : 474
    Points : 652
    Points
    652

    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 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 816
    Points
    12 816

    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 286
    Points
    1 286

    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 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 816
    Points
    12 816

    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 actif Avatar de SKone
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2004
    Messages
    323
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : Canada

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

    Informations forums :
    Inscription : mai 2004
    Messages : 323
    Points : 179
    Points
    179

    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
  •