Calculer le determinant d'une matrice carrée

Version imprimable

24/08/2006, 12h14
NThierry

Calculer le determinant d'une matrice carrée

Salut
je voudrais ressortir le code recursif qui permettrait de calculer le determinant d'une matrice carrée. Par exple:
http://upload.wikimedia.org/math/9/6...d134092a09.png
24/08/2006, 12h18
Gamdwin

Moi, là, je mangerais plutôt une bonne entrecôte sauce roquefort.
24/08/2006, 13h57
fearyourself

Citation:

Envoyé par NThierry

Salut
je voudrais ressortir le code recursif qui permettrait de calculer le determinant d'une matrice carrée. Par exple:
http://upload.wikimedia.org/math/9/6...d134092a09.png

Nous ne sommes pas là pour écrire ton code. Si tu as un problème au niveau algorithmique, il y a un forum dédié. Par contre, si tu as déjà écris une partie du code, tu peux poser des questions spécifiques sur les zones qui posent problèmes...

Jc

Te mettre sur la voie

Je le dis tout de suite, je ne sais plus calculer le déterminant d'une matrice, mais, pour te mettre sur la voie, voici le principe de base d'une fonction récursive
Code:

1 2 3 4 5 6 7 8 9 Recursive(liste de parametres) si(CAS DE BASE ATTEINT) | renvoie valeur SINON | liste des actions à prendre dont | au moins une fois | Recursive(arguments pour l'élément suivant) | et renvoi au final

Citation:

je voudrais ressortir le code recursif qui permettrait de calculer le determinant d'une matrice carrée. Par exple:

Je suppose que i représente les lignes et j les colonnes d'une matrice carrée m. Voici une partie d'idée d'algo, je te promets rien:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 int parite; int detM; for (j = 1; j <= N; j++){ for(i = 1; i <= N; i++){ parite = (i+j) % 2; if (0 == parite) /*parité paire*/ detM += m(i,j) * detM(i,j); else detM += -m(i,j) * detM(i,j); } }
Ensuite, faudrait aussi que tu me dises à quoi correspond "detM(i,j)". que doit contenir ce tableau à deux dimensions? La valeur du déterminant ligne i, colonne j, ca me semble bizarre mais bon ne sais plus trop comment ca fonctionne exactement....

j ai resolu ton probleme
voila le main.c et main.h correspondants

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "main.h"   //contient les declarations des fonctions de ce fichier main.c
 
 
 
const long n=3,MAX=100,MIN=0;
 
int main(int argc, char *argv[])
{
 
    long c,i,j;
    double mat[n][n];
 
    srand(time(NULL));
 
	printf("calcul du determinant d'une matrice carree\n");
//  printf("calcul aleatoire de la matrice carree\n");
//  aleatmat(mat,n);    //permet de choisir une matrice aleatoire de nb entiers
    matdefinie(mat,n);  //definit la matrice
    affichemat(mat,n);  //affiche la matrice choisie
 
    printf("determinant de la matrice carree = %lf",determ(mat,n));
 
    scanf("%ld",&c);
    return 0;
}
 
double determ(double (*mat)[n], long n)     //fonction recursive qui calcule le determinant
{
        double M[n-1][n-1],det=0.0;
        long i,j;
 
        if(n>0)
        {
            j=n-1; //ici on a choisi de developper sur la derniere collone (colonne n-1)
            for(i=0;i<n;i++)
            {
                matricereduite(mat,M,n,i,j); //calcule la matrice mi,j de taille n-1 x n-1 dans M
                affichemat(M,n-1); //facultatif : affiche les matrices mi,j intermediaires
                printf("\n");
                det += mat[i][j]*pow(-1,i+j)*determ(M,n-1);
            }
            return det;
        }
        else
            return 1;
}
 
void matricereduite(double (*mat)[n], double (*M)[n], long n, long a,long b)
{
    //cette fonction cree la matrice M (mi,j) de taille n-1 x n-1
    //a partir de la matrice mat (mati,j) de taille nxn
    //elle enleve la ligne i et la collonne j de la matrice mat et met le
    //resultat dans la matrice M
    long k,kk=0,l,ll=0;
 
        if(n>0)
        {
        for(k=0;k<n;k++)
        {
            if(k>=a)
                kk=1;
            else //inutile ce else en fait
                kk=0;
 
            {
                for(l=0;l<n;l++)
                {
                    if(l>=b)
                        ll=1;
                    else
                        ll=0;
 
                    if(k!=a && l!=b)
                    {
                        M[k-kk][l-ll]=mat[k][l];
                    }
                }
            }
        }
        }
 
}
 
 
void aleatmat(double (*mat)[n],long n) // cree une matrice carree de nb entiers aleatoires
{
    long i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            mat[i][j]=rand()%(MAX-MIN+1)+MIN;
        }
    }
}
 
void affichemat(double (*mat)[n], long n)  //affiche la matrice
{
    long i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("mat[%ld][%ld]=%lf\t",i,j,mat[i][j]);
        }
        printf("\n");
    }
}
 
void   matdefinie(double (*mat)[n],long n)
{
        mat[0][0]=1;    //ceci est une matrice 3x3 de determinant -33
        mat[0][1]=2;    //ça sert de test au programme
        mat[0][2]=2;
 
        mat[1][0]=4;
        mat[1][1]=3;
        mat[1][2]=1;
 
        mat[2][0]=5;
        mat[2][1]=1;
        mat[2][2]=4;
 
}

et main.h

Code:

1
2
3
4
5
6
7
 
# define N 3
void aleatmat(double (*mat)[N],long n);
void affichemat(double (*mat)[N], long n);
void   matdefinie(double (*mat)[N],long n);
void matricereduite(double (*mat)[N], double (*M)[N], long n, long a,long b);
double determ(double (*mat)[N], long n);

maintenant avec ces fonctions tu peux resoudre tout systeme de cramer d equations, si tu veux je peux te faire le code aussi pour ça

voici donc le code pour resoudre par la methode de cramer un systeme de n equations lineaire à n inconnues, autant vous dire qu il ne faut pas faire comme ça si n est trop grand sinon ça plante

main.c

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "main.h"   //contient les declarations des fonctions de ce fichier main.c
 
/* ce programme resoud un systeme de Cramer, a savoir un systeme de
n equations lineaires à n inconnues */
 
const long n=N,MAX=100,MIN=0;
 
int main(int argc, char *argv[])
{
 
    long c,i,j;
    double mat[n][n],x[n],b[n];
 
    srand(time(NULL));
 
	printf("calcul du determinant d'une matrice carree\n");
    switch(menu())
    {
        case 1 :
        matdefinie(mat,n); //matrice et vecteur b predefinis en fin de programme
        vectdefini(b,n);
        break;
 
        case 2 :
        aleatmat(mat,n);//permet de choisir une matrice aleatoire de nb entiers
        aleatvect(b,n); //vecteur de nb aleatoires
        break;
 
        default :
        return 0;
    }
 
    printf("la matrice M est \n");
    affichemat(mat,n);  //affiche la matrice choisie
    printf("le vecteur b vaut\n");
    affichevect(b,n);
 
    printf("determinant de la matrice carree = %lf\n",determ(mat,n));
 
    printf("resolution d'un systeme de %ld equations a %ld inconnues\n",n,n);
 
 
 
    cramer(mat,x,b,n);//resolution de mat*x=b
    printf("la solution x vaut\n");
    affichevect(x,n);
    printf("verification\n");
    MX(mat,x,b,n);
    printf("mat*x vaut \n");
    affichevect(b,n);
 
 
    scanf("%ld",&c);
    return 0;
}
 
double determ(double (*mat)[n], long n)     //fonction recursive qui calcule le determinant
{
        double M[n-1][n-1],det=0.0;
        long i,j;
 
        if(n>0)
        {
            j=n-1; //ici on a choisi de developper sur la derniere collone (colonne n-1)
            for(i=0;i<n;i++)
            {
                matricereduite(mat,M,n,i,j); //calcule la matrice mi,j de taille n-1 x n-1 dans M
                //affichemat(M,n-1); //facultatif : affiche les matrices mi,j intermediaires
                //printf("\n");
                det += mat[i][j]*pow(-1,i+j)*determ(M,n-1);
            }
            return det;
        }
        else
            return 1;
}
 
void matricereduite(double (*mat)[n], double (*M)[n], long n, long a,long b)
{
    //cette fonction cree la matrice M (mi,j) de taille n-1 x n-1
    //a partir de la matrice mat (mati,j) de taille nxn
    //elle enleve la ligne i et la collonne j de la matrice mat et met le
    //resultat dans la matrice M
    long k,kk=0,l,ll=0;
 
        if(n>0)
        {
        for(k=0;k<n;k++)
        {
            if(k>=a)
                kk=1;
            else //inutile ce else en fait
                kk=0;
 
            {
                for(l=0;l<n;l++)
                {
                    if(l>=b)
                        ll=1;
                    else
                        ll=0;
 
                    if(k!=a && l!=b)
                    {
                        M[k-kk][l-ll]=mat[k][l];
                    }
                }
            }
        }
        }
 
}
 
void cramer(double (*mat)[n],double *x, double *b, long n)
{ //resoud le systeme selon la formule de cramer
    long i;
    double matb[n][n],det;
    det=determ(mat,n);
    if(det==0)
        printf("desole mais il n'y a pas de solution !\n");
    else
    {
    for(i=0;i<n;i++)
    {
            echangecolone(mat,b,n,i,matb);
            x[i]=determ(matb,n)/det;
    }
    }
}
 
void echangecolone(double(*mat)[n], double *b,long n, long i, double(*matb)[n])
{ //met la colonne b dans la colonne n°i de mat
    long j;
    copiemat(mat,matb,n); //copie mat dans matb
    for(j=0;j<n;j++)
    {
        matb[j][i]=b[j];
    }
}
 
void copiemat(double(*mat)[n],double(*matb)[n],long n) //copie mat dans matb
{
    long i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            matb[i][j]=mat[i][j];
        }
    }
}
 
  void MX(double (*mat)[n], double *vect,double *b,long n)
  {//calcule mat*x et met le resultat dans b
    long i,k;
    double v;
    for(i=0;i<n;i++)
    {
        v=0.0;
        for(k=0;k<n;k++)
        {
            v +=mat[i][k]*vect[k];
        }
        b[i]=v;
    }
}
 
void aleatmat(double (*mat)[n],long n) // cree une matrice carree de nb entiers aleatoires
{
    long i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            mat[i][j]=rand()%(MAX-MIN+1)+MIN;
        }
    }
}
 
void aleatvect(double *x, long n) //cree un vecteur de nombres aleatoires
{
    long i;
    for(i=0;i<n;i++)
    {
            x[i]=rand()%(MAX-MIN+1)+MIN;
    }
}
 
void affichemat(double (*mat)[n], long n)  //affiche la matrice
{
    long i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("mat[%ld][%ld]=%lf\t",i,j,mat[i][j]);
        }
        printf("\n");
    }
}
 
void affichevect(double *x,long n) //affiche le vecteur
{
    long i;
    for(i=0;i<n;i++)
    {
        printf("vect[%ld]=%0.15lf\n",i,x[i]);
    }
}
 
void   matdefinie(double (*mat)[n],long n)
{
        mat[0][0]=3;    //ceci est une matrice 3x3 de determinant -22
        mat[0][1]=1;    //ça sert de test au programme
        mat[0][2]=3;
 
        mat[1][0]=-2;
        mat[1][1]=4;
        mat[1][2]=1;
 
        mat[2][0]=7;
        mat[2][1]=-3;
        mat[2][2]=2;
 
}
 
void vectdefini(double *b,long n)
{
    b[0]=8;     //la solution est (1,2,1)
    b[1]=7;
    b[2]=3;
}
 
void   matdefinieb(double (*mat)[n],long n)
{
        mat[0][0]=1;    //ceci est une matrice 3x3 de determinant -22
        mat[0][1]=3;    //ça sert de test au programme
        mat[0][2]=3;
 
        mat[1][0]=2;
        mat[1][1]=2;
        mat[1][2]=0;
 
        mat[2][0]=3;
        mat[2][1]=2;
        mat[2][2]=6;
 
}
 
void vectdefinib(double *b,long n)
{
    b[0]=0;     //la solution est (1,2,1)
    b[1]=2;
    b[2]=11;
}
 
long menu(void)
{
    long rep;
    do
    {
    printf("1- choix d'une matrice et d'un vecteur b predefinis\n");
    printf("2- choix d'une matrice et d'un vecteur b aleatoires\n");
    printf("\nvotre choix : ");
    scanf("%ld",&rep);
    } while (rep!=1 && rep!=2);
    return rep;
}

et le fichier header main.h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
# define N 3
void aleatmat(double (*mat)[N],long n);
void affichemat(double (*mat)[N], long n);
void   matdefinie(double (*mat)[N],long n);
void matricereduite(double (*mat)[N], double (*M)[N], long n, long a,long b);
double determ(double (*mat)[N], long n);
void affichevect(double *x,long n);
void aleatvect(double *x, long n);
void cramer(double (*mat)[N],double *x, double *b, long n);
void echangecolone(double(*mat)[N], double *b,long n, long i, double(*matb)[N]);
void copiemat(double(*mat)[N],double(*matb)[N],long n);
void MX(double (*mat)[N], double *vect,double *b,long n);
void vectdefini(double *b,long n);
long menu(void);
void   matdefinieb(double (*mat)[N],long n);
void vectdefinib(double *b,long n);

26/08/2006, 12h52
informatik

question

je suis debutant, qui peut m expliquer pourquoi le programme precedent fait exploser la memoire semble t il des que n=6 (le programme cree plein de matrices intermediaires il est vrai mais quand meme)

merci
26/08/2006, 13h19
pcaboche

Fait une recherche dans le forum "Algorithme".

On a eu le cas de quelqu'un qui cherchait à calculer le déterminant d'une matrice et il est apparu, après discussion avec des membres ayant vraisemblablement un bon niveau en math (en tous cas meilleur que le mien) que la formule que tu veux utiliser est très belle (compacte et récursive) mais que ce n'est pas la méthode la plus efficace niveau temps de calculs pour calculer le déterminant d'une matrice (il y en a une autre, avec des pivots façon Gauss).

Sinon, si tu cherches vraiment à implémenter cette fonction à partir de la formule du premier message (tirée de wikipedia), il est tout à fait possible d'économiser beaucoup de mémoire en utilisant toujours la même matrice (pas de recopie) mais en ne conservant dans les appels de fonction que les listes des lignes/colonnes que l'on souhait garder pour le calcul). Il n'empèche que l'autre méthode se révèle quand même beaucoup plus efficace.
26/08/2006, 15h07
koala01

Citation:

Envoyé par informatik

je suis debutant, qui peut m expliquer pourquoi le programme precedent fait exploser la memoire semble t il des que n=6 (le programme cree plein de matrices intermediaires il est vrai mais quand meme)

merci

Je n'ai pas compilé le code, mais les idées qui viennent tout de suite en tete sont du genre

-Une fonction récursive, si elle est appelée à de nombreuses occasion, va rapidement saturer le stack (la pile) du processeur, avec pour résultat le fameux "stack overflow"

Citation:

Envoyé par FIXME

Le contenu de la matrice en lui-meme sera-t-il mis en stack, ou sera-ce juste un pointeur vers celle-ci???

Si c'est toute la matrice qui est mise en stack, il sera d'autant plus vite saturé ;)

-Pour chaque matrice de N ligne et M colones (ici, N et M sont identiques, du fait qu'il s'agit d'une matrice carré) on doit réserver N*M éléments.

Comme la mémoire n'est pas infinie (et, qu'en plus, certains OS limitent la mémoire pour les applications), et que le type double est un type qui, de lui-même demande pas mal de place en mémoire, si chaque appel récursif de la fonction nécessite l'allocation de (N-1)*(M-1) éléments par rapport aux valeurs de la fonction "appelante", on peut effectivement se dire que la mémoire sera vite saturée...
26/08/2006, 15h10
Franck.H

Citation:

Envoyé par koala01

J
-Une fonction récursive, si elle est appelée à de nombreuses occasion, va rapidement saturer le stack (la pile) du processeur, avec pour résultat le fameux "stack overflow"

Bin dans ce cas faut voir pour transformer la fonction récursive en fonction récursive terminale, cela évite justement de staturer la pile !
26/08/2006, 15h55
informatik

l algorithme recursif de calcul de determinant par detM=Somme(m(i,j)*(-1)^(i+j)*detMi,j) consomme de façon exponentielle de la memoire avec la taille n et exp(6)=403 !

une bonne methode alternative est celle de la triangulation de la matrice par la methode de gauss par exemple
26/08/2006, 15h58
pcaboche

Citation:

Envoyé par informatik

une bonne methode alternative est celle de la triangulation de la matrice par la methode de gauss par exemple

Oui, c'est ce dont je parlais (faire une recherche dans le forum "Algo", le sujet y est peut-être encore...)
27/08/2006, 00h08
informatik

Citation:

Envoyé par Franck.H

Bin dans ce cas faut voir pour transformer la fonction récursive en fonction récursive terminale, cela évite justement de staturer la pile !

je suis vraiment debutant et j aimerais qu on m explique ce que c est une fonction recursive terminale et comment ça se programme ? merci
27/08/2006, 10h16
Emmanuel Delahaye

Citation:

Envoyé par informatik

je suis vraiment debutant et j aimerais qu on m explique ce que c est une fonction recursive terminale et comment ça se programme ?

C'est un problème d'algorithme, pas de langage. On t'a déjà indiqué le bon forum...
27/08/2006, 11h31
Franck.H

Citation:

Envoyé par informatik

je suis vraiment debutant et j aimerais qu on m explique ce que c est une fonction recursive terminale et comment ça se programme ? merci

Voici un tout petit cours et exemple: Récursivité terminale mais il est clair que c'est avant tout un problème algorithmique !