Discussion :

[Nemerle]

... régression et je trouve une valeur "moyenne" de x2.

après:
a13x3 = b1-valx1-valx2
...
am3x3 = b1-valx1-valx2

[sidahmed]

Re-bonjour,

merci pour ta réponse souviron. Je t'avoue que je ne vois pas trop comment m'en sortir avec de tels algorithmes... et surtout comment les mettre en oeuvre pour 300 000 équations...

Précision du problème:
les équations sont linéaires. On a tout bêtement un système matriciel de la forme:
Ax=b où je cherche x. si x=[x1 x2 x3 x4]
on a 300 000 fois (i désignant un numéro de ligne):
ai1*x1+ai2*x2+ai3*x3+ai4*x4 = bi

(Dans certains cas, je peux avoir jusqu'à 1 680 000 équations pour 4 inconnues)

est ce que d'un point de vue théorique on peut (étant donné que l'on se trouve dans le cas d'un système surdéterminé) utiliser la méthode de Gauss (substitution)? même question pour la factorisation LU (méthode de Crout), pour la méthode de Cholesky, pour la méthode de Householder?

Et si oui, connaissez vous l'algorithme de ces méthodes?
Merci beaucoup!

Bonjour steph42,

t'inquiète pas, surtout si tu n'es pas pressé !

je connais pas mal de méthodes de résolution des systèmes d'équations linéaires :

1. Méthodes directes :
   
   • Méthode d'élimination de Gauss (sans pivot et avec pivot)
   • Méthode de factorisation LU
   • Méthode de Cholerski
2. Méthodes itératives :
   
   • Méthode de JACOBI
   • Méthode de Gauss-Siedel
   • Méthode de relaxation

Je décris la toute première méthode via ce pseudo-code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
Algorithme sans pivotation c'est-à-dire a[l][l] différent de 0, quel que soit l :
 
1 - Triangularisation : [A, b] ---> [U, b'] (U matrice triangulaire supérieure)
  Pour l = 1 à n - 1 faire
    Pour i = l + 1 à n faire
      w = a[i][l] / a[l][l];
      Pour j := l à n + 1 faire
        a[i][j] := a[i][j] - w * a[l][j];
      FinPour
    FinPour
  FinPour
 
2 - Résolution du système UX = b' :
 
x[n] := u[n][n + 1] / u[n][n];
x[i] := (u[i][n + 1] - Sigma(j = i + 1, ..., n)(u[i][j] * x[j])) / u[i][i];    
pour i = n - 1, ..., 1.
Sigma : la somme

Bon courage ! N'hésite pas pour d'autres questions.

Cordialement,
Sidahmed.

[FR119492]

Salut !

En complément aux informations fournies par Sidahmed, j'ajouterais, parmi les méthodes directes, la méthode QR de Householder et surtout la méthode SVD (valeurs singulières)

D'autre part, je pense que MatLab est un excellent produit pour les problèmes de taille "moyenne"; en revanche, un tel outil à usage général ne peut pas être optimal pour des problèmes "monstrueux" comme le tien semble l'être. Dans un tel cas, tu devrais plutôt te tourner vers un langage de "bas" niveau et utiliser une des librairies écrites par les meilleurs spécialistes. Personnellement, j'écris mes monstres en Fortran (archaïque mais efficace) et j'utilise des librairies comme LinPack ou LAPack, qui sont disponibles gratuitement sur le site www.netlib.org et j'en suis très satisfait.

Bonne chance
Jean-Marc Blanc

[Matthieu Brucher]

Sachant que Matlab utilise justement ces bibliothèques...

[steph42]

Merci sidahmed.

Quelques questions tout de même... Toutes tes méthodes s'appliquent dans le cas de systèmes surdéterminés?? J'avais lu que la méthode LU, et pivot de Gauss ne fonctionnaient que pour des systèmes carrés (autant d'équations que d'inconnues, ce qui n'est pas mon cas).

Mon but étant de "tester" le maximum de méthodes possible, si vous en avez d'autres à me conseiller, je suis preneur!

Souviron, pourrais tu me donner des "références" sur l'algo du simplex tel que tu me l'as décrit? Car les seuls docs que je trouve (sur google et wikipedia) correspondent à un minimisation des fonctions de coût, et l'algo ne teste pas toutes les combinaisons d'équations possible comme tu me l'as dit...

Pour ce qui est de programmer l'algo du simplex tel que tu me l'as décrit, je vais le faire moi même, a priori ce n'est pas très compliqué.

La semaine prochaine, compte rendu des meilleures méthodes!

[steph42]

Merci FR119492.

Même remarque que pour La méthode LU et pivot de Gauss, la méthode QR ne me semble pas fonctionner dans le cas de systèmes surdéterminés...

Pour ce qui est de Matlab, il suffit de se "débrouiller" (Matlab peut lire une image... il la met sous forme matricielle... voilà l'initialisation d'une matrice, par exemple!) pour initialiser les variables (une grosse matrice pour moi) et il tourne. Au maximum le spm_svd (version de la svd adapté à un certain type d'image médicale) tourne en 15 minutes.

[Matthieu Brucher]

Au maximum le spm_svd (version de la svd adapté à un certain type d'image médicale) tourne en 15 minutes.

J'aime bien comment SPM s'approprie des choses qui ne viennent pas d'eux...
C'est simplement une réécriture de la SVD (voir le livre de Fukunaga).

[souviron34]

Merci sidahmed.

Quelques questions tout de même... Toutes tes méthodes s'appliquent dans le cas de systèmes surdéterminés?? J'avais lu que la méthode LU, et pivot de Gauss ne fonctionnaient que pour des systèmes carrés (autant d'équations que d'inconnues, ce qui n'est pas mon cas).

Mon but étant de "tester" le maximum de méthodes possible, si vous en avez d'autres à me conseiller, je suis preneur!

Souviron, pourrais tu me donner des "références" sur l'algo du simplex tel que tu me l'as décrit? Car les seuls docs que je trouve (sur google et wikipedia) correspondent à un minimisation des fonctions de coût, et l'algo ne teste pas toutes les combinaisons d'équations possible comme tu me l'as dit...

Pour ce qui est de programmer l'algo du simplex tel que tu me l'as décrit, je vais le faire moi même, a priori ce n'est pas très compliqué.

La semaine prochaine, compte rendu des meilleures méthodes!

je n'ai malheureusement pas mes sources dispo sous la main, et je ne les aurais pas avant au moins 6 mois...

Neanmoins voila quelques liens :

http://en.wikipedia.org/wiki/Simplex_algorithm

avec des liens et references a la fin.

Aussi :

http://www2.isye.gatech.edu/~spyros/LP/LP.html

http://www.cise.ufl.edu/~davis/Morgan/

http://www-fp.mcs.anl.gov/otc/GUIDE/...tion2_1_1.html avec plusieurs references de soft (ce qui m'a rafraichi la memoire concernant la biblio du CERN : IMSL...)

je n'ai pas le temps de remplir plus, mais avec cela, et en particulier la premiere et derniere reference, ca devrait aller...

[sidahmed]

Bonsoir,
hier j'avais un problème de connexion internet, c'est pour ça, je te réponds en retard !

Merci sidahmed.

Quelques questions tout de même... Toutes tes méthodes s'appliquent dans le cas de systèmes surdéterminés?? J'avais lu que la méthode LU, et pivot de Gauss ne fonctionnaient que pour des systèmes carrés (autant d'équations que d'inconnues, ce qui n'est pas mon cas).

Mon but étant de "tester" le maximum de méthodes possible, si vous en avez d'autres à me conseiller, je suis preneur!

Souviron, pourrais tu me donner des "références" sur l'algo du simplex tel que tu me l'as décrit? Car les seuls docs que je trouve (sur google et wikipedia) correspondent à un minimisation des fonctions de coût, et l'algo ne teste pas toutes les combinaisons d'équations possible comme tu me l'as dit...

Pour ce qui est de programmer l'algo du simplex tel que tu me l'as décrit, je vais le faire moi même, a priori ce n'est pas très compliqué.

La semaine prochaine, compte rendu des meilleures méthodes!

Je t'en prie ! Tu as tout à fait raison, toutes les méthodes que j'ai décris ci-dessus que ce soient directes ou itératives ne sont applicables que si et seulement si le nombre d'inconnus est égal au nombre d'équations, sans pour autant oublier que ces équations doivent être linéraires !

Dans le cas contraire, il faut faire recours à la méthode du Simplex dont le but est d'optimiser (minimaliser ou maximaliser) une fonction également linéaire appelée objectif ou fonction économique.

Si tu veux davantage d'informations, n'hésite pas ! Surtout à propos de la méthode du Simplex, je peux te la décrire pas à pas, et si vraiment tu te coïnces je te donnerai un programme Pascal de mes archives implémentant cette efficace méthode !

Bon courage !

Cordialement,
Sidahmed.

[sidahmed]

Salut !

En complément aux informations fournies par Sidahmed, j'ajouterais, parmi les méthodes directes, la méthode QR de Householder

Je ne suis pas d'accord, à ma connaissance les méthodes de Givens-Householder et QR interviennent dans le calcul des valeurs propres et vecteurs propres !

Cordialement,
Sidahmed.

[souviron34]

...Je t'en prie ! Tu as tout à fait raison, toutes les méthodes que j'ai décris ci-dessus que ce soient directes ou itératives ne sont applicables que si et seulement si le nombre d'inconnus est égal au nombre d'équations, sans pour autant oublier que ces équations doivent être linéraires !
....

C'était dans le titre du post !!!! et dans la première page... D'où ma suggestion du Simplex...

[FR119492]

Salut !

Je ne suis pas d'accord, à ma connaissance les méthodes de Givens-Householder et QR interviennent dans le calcul des valeurs propres et vecteurs propres !

Partiellement faux!

Effectivement, la méthode QR est souvent utilisée pour calculer pour les valeurs et vecteurs propres, mais elle convient aussi pour résoudre des systèmes linéaires.

Soit à résoudre le système A*x=b
On factorise A=Q*R où Q est orthogonale et R triangulaire droite, puis on résout successivement Q*y=b puis R*x=y
Pour plus de détail, voir la description de l'opérateur \ dans l'aide de MatLab,

Jean-Marc Blanc

[sidahmed]

Bonjour,

Salut !



Partiellement faux!

Effectivement, la méthode QR est souvent utilisée pour calculer pour les valeurs et vecteurs propres, mais elle convient aussi pour résoudre des systèmes linéaires.

Soit à résoudre le système A*x=b
On factorise A=Q*R où Q est orthogonale et R triangulaire droite, puis on résout successivement Q*y=b puis R*x=y

Merci pour tes explications, enfin j'ai dit ça d'après ce que j'ai étudié en calcul numérique !

Pour plus de détail, voir la description de l'opérateur \ dans l'aide de MatLab,

Malheureusement je n'ai jamais eu l'occasion de manipuler MatLab. En plus, je pense qu'il est cher !

Cordialement,
Sidahmed.

[Matthieu Brucher]

Il n'empêche que l'aide est en ligne et elle est gratuite.

[FR119492]

Malheureusement je n'ai jamais eu l'occasion de manipuler MatLab. En plus, je pense qu'il est cher !

C'est vrai, alors je résume. Dans MatLab, pour résoudre le système linéaire A*x=b , on tape x=A\b où l'opérateur \ représente une "division à gauche". MatLab procède comme suit:

1) Si A est triangulaire, il résout le système par substitution.

2) Si A est symétrique, il part de l'idée qu'elle est peut-être définie positive et essaie la méthode de Cholesky.

3) Si la méthode de Cholesky plante sur un pivot non positif, ou si A est carrée mais non symétrique, il applique la méthode de Crout (LU).

4) Si A est rectangulaire, il applique la méthode de Householder (QR).

Cette stratégie se justifie si l'on ne sait pas quelles propriétés particulières présente la matrice. En revanche, si le contexte nous dit, par exemple, que A est nécessairement définie positive, alors il est plus rapide d'utiliser une routine de LinPack ou LAPack. Imagine que ce ne soit qu'au dernier pivot que MatLab tombe sur une valeur négative!

Jean-Marc Blanc

[steph42]

Bonjour à tous.

Petit résumé des différentes techniques essayées.

Le mldivide de matlab: le \
réponse "instantanée". erreur moyenne en valeur absolue: 8*e7 (e7 signifie 10 puissance 7. c énorme je sais! mais ce qui compte pour moi, ce n'est pas de retrouver les valeurs, mais la démarcation des nuages de points. Et ça fonctionne visuellement plutôt pas mal).

La régression à bascule:
réponse en 0.174909s . erreur moyenne en valeur absolue: 4.2e8

Méthode des équations normales:
réponse en 0.088192 s. erreur moyenne en valeur absolue: 1.23e8

Méthode svd: en mode "economy size":
réponse en 0.69s. erreur moyenne en valeur absolue: 1.51e6

Méthode spm_svd avec mise à 0 de tous les éléments dont la valeur est >1 lors de la diagonalisation.
réponse en 621.20secondes soit 10min21s. erreur moyenne: 3.3e6

Ce qui ressort de la méthode svd, c'est que outre que ce soit elle qui donne les meilleurs résultats en terme d'erreur, c'est elle qui donne visuellement les meilleurs résultats. En effet, les nuages de points sont très séparés, surtout ceux qui m'intéressent!

Contrairement à ce qui été "prévu", le mldivide de Matlab n'est pas la méthode qui donne les meilleurs résultats. Prévu, car c'est sensé être la méthode qui minimise les moindres carrés d'après l'aide. D'ailleurs à ce propos, FR119492, j'ai une question. Si on cherche à résoudre par la méthode de la minimisation de l'erreur des moindres carrés, on se ramène à résoudre un système carré. Là, la méthode du pivot de Gauss fonctionne très bien. Je pensais donc que c'était ce que faisait Matlab (Gauss Substitution). Or, d'après toi, ce n'est pas le cas?

Pour ce qui est du simplex: j'ai laissé tomber! En effet, dans un nouveau cas pratique, j'ai au total 939 876 équations. Je supprime les lignes où il n'y a que des "0". Il me reste tout de même 429 940 équations. Si je veux "tester" toutes les combinaisons possibles de 4 combinaisons d'équations parmi ces 429940, il y a
1 423 685 644 715 248 338 165 résolutions de systèmes à effectuer (formule bête de proba de terminale)! Ce nombre me paraissant énorme, j'ai eu l'idée de le tester pour un système de 10 équations, parmi lesquelles on choisirait 4 équations. il y avait donc 15 possibilités. Matlab a mis 0.0112 secondes pour traiter le problème. Ce qui sous entend que pour mon cas, une règle de trois donne 1 063 018 614 720 718 759 secondes... c'est à dire environ... 33 708 099 147années... Or la vie est courte...

Je ne sais pas si ma méthode de calcul est "juste", aussi j'ai lancé tout de même Matlab pendant le week end. Le pc tournait à 100%, et je ne pouvais lancer aucun autre programme. Je l'ai bloqué ce matin (mardi à10h)... C'est beaucoup trop lent. Certes, mon implantation n'était peut être pas optimisée, mais tout de même..

Si tu as d'autres méthodes à me proposer Sidahmed, je suis preneur! Pour ce qui est des algo génétiques dont tu m'as parlé Nemerle, je ne connais pas du tout! Donc si tu pouvais m'éclairer un peu...

Merci à tous.

[Nemerle]

Comment as-tu défini ton erreur???

[steph42]

Très simple, je ne me suis pas foulé...
Pour chaque point:
(valeur du résultat mesuré-valeur prédite) au carré

Je fais la somme, et je divise par le nombre de points. Puis je prends la racine carré.

[briqueabrac]

Etant donné que tu as l'air d'avoir des erreurs de mesures, a ta place j'essaierais de la minimiser.
Est ce qu'on peut savoir ce que représentent les inconnues ? une transformation 2D ?

RANSAC peut être une solution

[steph42]

Bonjour.

En fait, j'ai 4 "mesures" d'une "image", selon des protocoles différents. Chaque "mesure" est prédicitive (d'après la littérature) de l'évolution finale de cette "image", donc de son allure finale, mais PAS de ses valeurs. J'ai donc eu l'idée de tester le modèle linéaire afin, non pas de prédire les valeurs finales, mais de prédire l'allure finale (et donc la segmentation visuelle des nuages de points). De ce fait, pour moi l'erreur moyenne importe moins que la qualité de l'allure prédite.
Les coefficients cherchés ne sont ni plus ni moins que des poids à donner à chaque mesure afin de trouver au mieux l'allure finale.
Je peux aussi assurer qu'il n'y a pas d'erreurs dans les mesures.

Pour ce qui est du RANSAC, il me semble que j'ai beaucoup trop de points pour l'appliquer... D'autre part, puisque d'après ce que j'ai compris (wikipedia), l'algo travaille de manière géométrique, avec des distances, c'est à peu près la même chose que l'isodata non? C'est une classification...