Discussion :

[gautret]

Salut,

Voici un code que j'ai ecris pour calculer le determinant d'une matrice. Il fonctionne . Il est à améliorer, c'est sur, allocation dynamique entre autre.
Je voudrai avoir des avis sur son efficacité avec de grosse matrice et la précision? Ce qu'en pense les expert de la programmation et les mathématiciens .

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
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
 
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
 
 
 
void main()
{
	int i,j,l,n=4;
	double matrix[4][4],c,det=1;
 
 
	matrix[0][0]=1;matrix[0][1]=2;matrix[0][2]=3;matrix[0][3]=1;
	matrix[1][0]=3;matrix[1][1]=3;matrix[1][2]=1;matrix[1][3]=2;
	matrix[2][0]=2;matrix[2][1]=3;matrix[2][2]=2;matrix[2][3]=1;
	matrix[3][0]=2;matrix[3][1]=1;matrix[3][2]=2;matrix[3][3]=2;
 
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%f\t",matrix[i][j]);
		}
		printf("\n");
	}
	printf("\nmatrice triangulaire:\n");
 
	for(i=0;i<n-1;i++)
	{
		for(j=i+1;j<n;j++)
		{
			c=matrix[j][i];
			for(l=i;l<n;l++)
			{
				matrix[j][l]=matrix[j][l]-c*matrix[i][l]/matrix[i][i];
			}
		}
 
	}
 
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%f\t",matrix[i][j]);
		}
		printf("\n");
	}
 
	for(i=0;i<n;i++)
	{
		det=det*matrix[i][i];
	}
	printf("\ndeterminant = %f\n",det);
}

Thank a lot et bon week end

[plegat]

Salut,

Juste une petite remarque sur la partie triangularisation de la matrice.
Tu divises systématiquement par le pivot en [i][i] de ta matrice. La méthode utilisé pour la résolution de système par la méthode du pivot de Gauss préconise de rechercher quelle est la ligne possédant la plus grande valeur pour ce pivot, ceci afin de minimiser les erreurs numériques. Je ne sais pas si cela à une réelle importance pour la triangularisation par contre... je lance juste une "alerte intellectuelle"...

[gautret]

C'est parfaitement le genre de réponse que j'attend.
Merci et si il y en a d'autres, je prend.

[pcaboche]

Petite question (ça remonte à loin la dernière fois que j'ai fait un calcul de déterminant), mais ça de se calcul pas par récursion?



Source: http://fr.wikipedia.org/wiki/D%C3%A9...C3%A9matiques)


Ici, je ne vois pas d'appel récursif à une fonction det.

***

J'avais programmé une fonction pour le calcul de déterminant une fois en suivant cette formule, seulement, pour le calcul de M(i;j) (la sous-matrice déduite de M en en ayant enlevé la ligne i et la colonne j), j'avais procédé ainsi:
- j'avais une liste des lignes et une liste des colonnes à conserver dans la matrice. Je n'examinais que les lignes et les colonnes contenues dans cette liste.
- la recursivité me permettait de supprimer de la liste une ligne et une colonne en début d'appel de la fonction et de les rajouter en fin d'appel de la fonction. De cette façon, je gardais les même listes tout au long du programme (pas d'allocation/recopie/désallocation)
- mes "listes" étaient en fait des tableaux de booléens pour savoir si on doit prendre en compte la ligne/colonne dans le calcul ou pas.

Cela m'évitait de devoir recopier la matrice entière, avec juste une ligne et une colonne en moins à chaque fois. Cela économise ENORMEMENT de mémoire et aussi pas mal de temps en recopie de matrices (puisque c'est un algo sur place: on utilise la même matrice du début à la fin)

A bon entendeur !

[Matthieu Brucher]

Calculer le déterminant par récursion, c'est fatal à n'importe qui. Le temps de calcul est alors exponentiel en la taille de la matrice.
La méthode ici est bonne, mais effectivement, on divise par le plus grand pivot possible. En revanche, si tu connait la taille exacte de tes matrices, ou si tu sais quelle sera la taille max et qu'elle n'est pas trop importante, tu peux plutôt mettre la formule explicite.

[j.p.mignot]

Le calcul récurcif est "très joli et concis du point de vue formulation" mais désatreux du point de vue numérique!
La triangularisation ou la décomposition LU est à conseiller.
Numériquement, la recherche du pivot de plus grande valeur absolue est à conseiller fortement.
par exemple
Voir les Numerical recipes

[progfou]

Je rejoinds j.p.mignot, cf :
http://library.lanl.gov/numerical/bookcpdf/c2-3.pdf

[plegat]

Je rejoinds j.p.mignot, cf :
http://library.lanl.gov/numerical/bookcpdf/c2-3.pdf

Roooh! Avec le copyright bien visible, c'est limite de mettre ça en lien!

Sinon, est-ce que vous pourriez quantifier le "désastreux du point de vue numérique", grosso modo, même à la louche, histoire d'avoir un ordre de grandeur? Je me suis implémenté un calcul de déterminant par la méthode récursive (sur des matrices 6x6 avec un peu plus de la moitié de termes nuls), j'aimerais savoir si ça vaut le coup que je reprogramme la méthode...

[j.p.mignot]

Le lien
http://library.lanl.gov/numerical/bookcpdf/c2-3.pdf
est tout à fait correct, on download légalement tout le livre depuis le site de l'éditeur.
J'en conseille tout de même l'achat !

pour en revenir à la question, un déterminant d'ordre n calculé par développement suivant une ligne et/ou une colonne implique le calcul de n déterminants d'ordre n-1. on arrive donc à environ n! adition de n multiplications. Une décomposition LU nécessite environ 0.5 * N^3 opérations .
La situation est " pire " que décrite par miles qui parlait de

le calcul est alors exponentiel

il est factoriel ce qui croît encore plus vite que l'exponentielle...

dans votre cas avec n=6 cela représente 240 additions de termes qui sont le résultats de 6 produits.
avec LU il y aurait de l'ordre de 100 opérations.
A ces chiffres déjà éloquents, il faut ajouter dans la cas récursif n! appels à la routine DET avec toutes les opérations "Background" de push pop que cela cache. Cela induit de plus des problèmes potentiels qui peuvent devenir sérieux sur la stack si n croît.

.....

[pcaboche]

Le calcul récurcif est "très joli et concis du point de vue formulation" mais désatreux du point de vue numérique!

dans votre cas avec n=6 cela représente 240 additions de termes qui sont le résultats de 6 produits.
avec LU il y aurait de l'ordre de 100 opérations.

.....

Ok ok! Je suis pas mathématicien et c'est pour ça que je demande parce qu'en vérité, je ne me souvenais que de la formule que j'ai citée (et pour laquelle j'ai proposé certaines "optimisations" (d'un point de vue purement informatique) pour éviter d'avoir à créer de nouvelles matrices à chaque fois).

Maintenant une question que je me pose: d'un point de vue mathématique la solution LU est géniale, elle permet de faire beaucoup moins de calculs, etc. etc. Cependant, une bonne partie de ces calculs fait intervenir des divisions et donc, d'un point de vue informatique, introduit des imprécisions liées à la représentation machine des flottants. Avec l'autre solution, on n'a pas ce problème vue que l'on n'a que des additions, soustractions et multiplications.

Ma question est donc simple: ne vaut-il pas mieux utiliser une méthode, certes plus lente, mais qui est sûre de nous retourner le bon résultat?

[j.p.mignot]

Est-ce plus sur ???
si il faut faite l'adition de n! multiplications de n éléments?
si on multiplie 100 X des chiffres "usuels" comme 100 on arrive à 10^200.
si il faut soustraire de tels chiffres pour revenir avec de la précision autour de 1 ou 10, good luck!
Je ne suis pas un spécialiste du calcul numérique et me fie aux conseils des livres / articles spécialisés mais tous rejettent une approche récursive du calcul du déterminant.

[pcaboche]

Ok, merci pour ces précisions? (comme je l'ai dit, ça remonte à loin la dernière fois que j'ai fait un calcul de déterminant).

[DrTopos]

Ce sujet a été déjà très largement discuté ici.