Inversion de matrices : bug etrange

Marsh Posté le 06-03-2006 à 17:06:00

Bonjour,
j'ai ecrit le code suivant en C pour inverser de matrices de taille dim*dim. L'algo. (Gauss-Jordan) provient de ce que j'ai trouve sur le net.

Code :

int inverseMatrix(double ** matrix, double ** inversedMatrix, int dim){
int i, j, k;
double ** tempMatrix = malloc(sizeof(*double)*dim); /* Allocation of matrix memory */
for(i=0 ; i<dim ; i++){
tempMatrix = malloc(sizeof(double)*dim*2);
}
for(i=0 ; i<dim ; i++){ /* initialization of matrix values */
for(j=0 ; j<dim ; j++){
tempMatrix[i][j] = matrix[i][j];
if (i==j) {
tempMatrix[i][j+dim] = 1.0;
} else {
tempMatrix[i][j+dim] = 0.0;
}
}
}
printf("tempMatrix:\n" );
for(i=0 ; i<dim ; i++){
for(j=0 ; j<dim*2 ; j++){
printf("%f ", tempMatrix[i][j]);
}
printf("\n" );
}
for (i=0 ; i<dim ; i++){
if (tempMatrix[i][i]!=0){
for(j=0 ; j<2*dim ; j++){
tempMatrix[i][j] = tempMatrix[i][j]/tempMatrix[i][i];
}
for(k=0 ; k<dim ; k++){
if (k!=i){
for (j=0 ; j<2*dim ; j++){
printf("tempMatrix[%i][%i] : %f\n", k, j, tempMatrix[k][j]);
tempMatrix[k][j] = tempMatrix[k][j] - (tempMatrix[k][i]*tempMatrix[i][j]);
printf("puis tempMatrix[%i][%i]-tempMatrix[%i][%i](%f)*tempMatrix[%i][%i](%f) : %f\n", k, j, k, i, tempMatrix[k][i], i, j, tempMatrix[i][j], tempMatrix[k][j]);
}
}
}
} else {
for(i=0 ; i<dim ; i++){ /* free the allocated memory */
free(tempMatrix[i]);
}
free(tempMatrix);
return 0;
}
}
printf("tempMatrix:\n" );
for(i=0 ; i<dim ; i++){
for(j=0 ; j<dim*2 ; j++){
printf("%f ", tempMatrix[i][j]);
}
printf("\n" );
}
for (i=0 ; i<dim ; i++){ /* copy of the resulting matrix in the returned variable */
for(j=0 ; j<dim ; j++){
inversedMatrix[i][j] = tempMatrix[i][dim+j];
}
}
for(i=0 ; i<dim ; i++){ /* free the allocated memory */
free(tempMatrix[i]);
}
free(tempMatrix);
return 1;
}

Ce code me donne toujours en sortie une matrice diagonale avec toutes les valeurs diagonales a 1. J'ai donc ajoute les printf pour voir ce qui se passe et voila : quand je fais [i]"tempMatrix[k][j] = tempMatrix[k][j] - (tempMatrix[k][i]*tempMatrix[i][j]);", ca me sort toujours 0.00 ou 1.00 mais jamais les bonnes valeurs (genre il me fait 0.355235 - (0.0000 * 1.0000) = 0.0 :heink: ).
Si quelqu'un a une idee... :sweat:

Message édité par D_P_ le 06-03-2006 à 18:36:32

Reply

Marsh Posté le 06-03-2006 à 17:06:00

Reply

Marsh Posté le 06-03-2006 à 17:41:53

Code :

double ** tempMatrix = malloc(sizeof(double)*2*dim*dim); /* Allocation of matrix memory */
for(i=0 ; i<dim ; i++){
tempMatrix[i] = malloc(sizeof(double)*dim*2);
}

1) quel est l'interêt d'avoir un pointeur par ligne ?
2) ton premier malloc est faux tu n'as alloues pas un bloc de pointeurs, mais toute une matrice
=> double ** tempMatrix = malloc(sizeof(double*)*dim)
là tu as un bloc mémoire maintenant des pointeurs pour chaque ligne

3) pourquoi des dim*2 ?

4) de toutes manières, sapu ce genre de trucs utilise juste un "double *matrix" en temporaire/paramètre.

5) j'ai pas regardé l'algo, mais c'est vraiment nécessaire de faire une matrice temporaire ?

Message cité 1 fois

Reply

Marsh Posté le 06-03-2006 à 18:07:45

il y a des bibliotèques en C pour manipuler des matrices, comme gsl

Message cité 1 fois
Message édité par skelter le 06-03-2006 à 18:07:53

Reply

Marsh Posté le 06-03-2006 à 18:13:47

bjone a écrit :

Code :

double ** tempMatrix = malloc(sizeof(double)*2*dim*dim); /* Allocation of matrix memory */
for(i=0 ; i<dim ; i++){
tempMatrix[i] = malloc(sizeof(double)*dim*2);
}

1) quel est l'interêt d'avoir un pointeur par ligne ?
2) ton premier malloc est faux tu n'as alloues pas un bloc de pointeurs, mais toute une matrice
=> double ** tempMatrix = malloc(sizeof(double*)*dim)
là tu as un bloc mémoire maintenant des pointeurs pour chaque ligne

3) pourquoi des dim*2 ?

4) de toutes manières, sapu ce genre de trucs utilise juste un "double *matrix" en temporaire/paramètre.

5) j'ai pas regardé l'algo, mais c'est vraiment nécessaire de faire une matrice temporaire ?

1) si je fais uniquement un

Code :

double ** tableau = malloc(dim*dim*2*sizeof(double))

ca risque de me sortir une segmentation fault non ? En tout cas ca me le faisait sur une autre partie de prog ya pas longtemps, et la solution c'etait ca...

2) exact, j'ai corrige mais ca ne vient pas de la

3) ben pour inverser une matrice A de dimension n*n, je pose G=[A|I], puis j'applique Gauss pour obtenir G = [I|A^(-1)], et donc A^(-1)

4) bien mais moi, pas

5) ben je pense, cf. 3)
Cela dit, c'est pas le fait d'utiliser ou non une matrice temporaire qui devrait changer quoi que ce soit au resultat, non ? (hors performances)

Je pense pas que le probleme provienne d'une histoire d'allocation de tableau : le printf de la ligne 36 m'assure que je vais chercher les bonnes valeurs, mais le resultat de l'operation est faux ! Cela dit ca fait que 15 jours que je fais du C et je suis toujours sur le cul quand je vois d'ou proviennent mes erreurs :sweat:

Message cité 2 fois
Message édité par D_P_ le 06-03-2006 à 18:36:57

Reply

Marsh Posté le 06-03-2006 à 18:15:33

skelter a écrit :

il y a des bibliotèques en C pour manipuler des matrices, comme gsl

C'est ce que j'avais cherche en premier, mais j'avais rien trouve qui me convenait. Je vais tester gsl pour voir.

Neanmoins, je suis quand meme curieux de voir d'ou vient ce bug :heink: :whistle:

Message cité 2 fois
Message édité par D_P_ le 06-03-2006 à 18:16:33

Reply

Marsh Posté le 06-03-2006 à 18:20:56

D_P_ a écrit :

C'est ce que j'avais cherche en premier, mais j'avais rien trouve qui me convenait. Je vais tester gsl pour voir.

sur cette page il y a un code (get_inverse) qui tient en 10 lignes avec gsl, tu peux t'en inspirer

Reply

Marsh Posté le 06-03-2006 à 18:26:29

D_P_ a écrit :

Neanmoins, je suis quand meme curieux de voir d'ou vient ce bug :heink: :whistle:

rien que cette allocation

Code :

double ** tempMatrix = malloc(sizeof(double)*2*dim*dim); /* Allocation of matrix memory */
for(i=0 ; i<dim ; i++){
tempMatrix[i] = malloc(sizeof(double)*dim*2);
}

dans le premier malloc tu peux expliquer pourquoi 'sizeof(double)' au lieu de sizeof(double *) ? (ou mieux, 'sizeof *tempMatrix')
et pourquoi '*2' ?

aussi pourquoi tu parcours les colonnes jusqu'a dim*2 et des fois jusqu'a dim ?

Message cité 1 fois

Reply

Marsh Posté le 06-03-2006 à 18:35:15

skelter a écrit :

rien que cette allocation

Code :

double ** tempMatrix = malloc(sizeof(double)*2*dim*dim); /* Allocation of matrix memory */
for(i=0 ; i<dim ; i++){
tempMatrix[i] = malloc(sizeof(double)*dim*2);
}

dans le premier malloc tu peux expliquer pourquoi 'sizeof(double)' au lieu de sizeof(double *) ? (ou mieux, 'sizeof *tempMatrix')
et pourquoi '*2' ?

aussi pourquoi tu parcours les colonnes jusqu'a dim*2 et des fois jusqu'a dim ?

J'ai deja repondu a ces questions plus haut. Je vais editer le code pour virer les conneries.

Reply

Marsh Posté le 06-03-2006 à 18:41:37

D_P_ a écrit :

1) si je fais uniquement un

Code :

double ** tableau = malloc(dim*dim*2*sizeof(double))

ca risque de me sortir une segmentation fault non ? En tout cas ca me le faisait sur une autre partie de prog ya pas longtemps, et la solution c'etait ca...

2) exact, j'ai corrige mais ca ne vient pas de la

3) ben pour inverser une matrice A de dimension n*n, je pose G=[A|I], puis j'applique Gauss pour obtenir G = [I|A^(-1)], et donc A^(-1)

4) bien mais moi, pas

5) ben je pense, cf. 3)
Cela dit, c'est pas le fait d'utiliser ou non une matrice temporaire qui devrait changer quoi que ce soit au resultat, non ? (hors performances)

Je pense pas que le probleme provienne d'une histoire d'allocation de tableau : le printf de la ligne 41 m'assure que je vais chercher les bonnes valeurs, mais le resultat de l'operation est faux ! Cela dit ca fait que 15 jours que je fais du C et je suis toujours sur le cul quand je vois d'ou proviennent mes erreurs :sweat:

4) bien moi si, parceque justement ça évite tes bugs et c'est plus performant.

pour une matrice carré de dimension "dim" soit dim² éléments, soit tu fais:

type **LinePtrs=malloc( dim * sizeof( type * ) );
for( int i=0 ; i < dim ; ++i )
LinePtrs[i]=malloc( dim * sizeof(type) );

soit:

type *Elements=malloc( dim*dim *sizeof(type) );

Message cité 1 fois

Reply

Marsh Posté le 06-03-2006 à 18:45:47

oki pour le dim*2 vu que c'est le pivot de gauss.

Reply

Marsh Posté le 06-03-2006 à 18:45:47

Reply

Marsh Posté le 06-03-2006 à 18:49:07

bjone a écrit :

4) bien moi si, parceque justement ça évite tes bugs et c'est plus performant.

ok pour la performance, pas pour les bugs. Je trouve plus lisible et facile a manipuler d'avoir un tableau a 2 dimensions que de faire des tab[i*dim+j] a foison. En quoi l'utilisation d'un tableau a deux dimensions serait plus propice aux bugs ?

bjone a écrit :

pour une matrice carré de dimension "dim" soit dim² éléments, soit tu fais:

type **LinePtrs=malloc( dim * sizeof( type * ) );
for( int i=0 ; i < dim ; ++i )
LinePtrs[i]=malloc( dim * sizeof(type) );

soit:

type *Elements=malloc( dim*dim *sizeof(type) );

La-dessus on est d'accord.

Message cité 1 fois

Reply

Marsh Posté le 06-03-2006 à 19:02:21

D_P_ a écrit :

ok pour la performance, pas pour les bugs. Je trouve plus lisible et facile a manipuler d'avoir un tableau a 2 dimensions que de faire des tab[i*dim+j] a foison. En quoi l'utilisation d'un tableau a deux dimensions serait plus propice aux bugs ?

La-dessus on est d'accord.

je parlais de -tes- bugs: confusion entre un tableau à 2 dimensions et un tableau de pointeurs. (enfin tableau n'est pas le bon terme)

Message édité par bjone le 06-03-2006 à 19:02:36

Reply

Marsh Posté le 06-03-2006 à 19:51:19

D_P_ a écrit :

1) si je fais uniquement un

Code :

double ** tableau = malloc(dim*dim*2*sizeof(double))

ca risque de me sortir une segmentation fault non ?

Oui, bien sûr. Tu as choisi une implémentation par tableau dynamique de tableaux dynamique. Ton implémentation (corrigée) est correcte.

Message édité par Emmanuel Delahaye le 06-03-2006 à 19:52:37

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

Reply

Inversion de matrices : bug etrange

Sujets relatifs:

Leave a Replay