Discussion :

[Peltchag]

Retouche effectuee

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
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
    //----- parcours de la matrice pour verrifier que son determinant n'est pas nul ----- 
    Indice = 1 
     Répéter 
        //on cherche d'abord sur la ligne 
        LigneNulle = Vrai 
        //on se place sur la ligne voulu 
        Ligne = Indice 
        //et on parcourt chaque colonne 
        Colonne = 1 
         Répéter 
            //des qu'on tombe sur un coefficient different de zero 
            Si (TabCoeffs(Ligne, Colonne) <> 0) Alors 
                //on dit que la ligne n'est pas nulle 
                LigneNulle = Faux 
             FinSi 
            //on passe a la colonne suivante 
            Colonne = Colonne + 1 
        //on sort s'il n'y a plus de colonnes 
        //ou si on sait que la ligne n'est pas nulle 
         Jusqu 'à ((Colonne > Dimension) Ou (LigneNulle = Faux)) 
 
        //si la ligne est bonne, on regarde la colonne 
        //par le meme principe 
        Si (LigneNulle = Faux) Alors 
            ColonneNulle = Vrai 
            Colonne = Indice 
            Ligne = 1 
             Répéter 
                Si (TabCoeffs(Ligne, Colonne) <> 0) Alors 
                    ColonneNulle = Faux 
                 FinSi 
                Ligne = Ligne + 1 
             Jusqu 'à ((Ligne > Dimension) Ou (ColonneNulle = Faux)) 
         FinSi 
 
        //une fois qu'on a regarde ligne et colonne, 
        //on passe a l'indice suivant 
        Indice = Indice + 1 
    //on s'arrete si on a parcouru toute la matrice 
    //ou si on a trouve une ligne ou une colonne nulle 
     Jusqu 'à ((Indice > Dimension) Ou (LigneNulle = Vrai) Ou (ColonneNulle = Vrai)) 
 
    //si une ligne ou une colonne est nulle, le determinant est nul 
    Si (LigneNulle = Vrai) Ou (ColonneNulle = Vrai) Alors 
        DeterminantCalcule = 0 
    //sinon, on se lance dans le calcul 
    Else 
        //----- methode par la triangularisation (pivot de gauss) ----------------------------
        //----- le determinant d'une matrice triangulaire est le produit de sa diagonale -----
        //on parcourt la matrice ligne par ligne 
        LignePivot = 1
        Répéter
            //initialisation du booleen d'arret de la fonction
            ArretFonction = Faux
 
            //si le coefficient de la diagonale est nul
            Si (TabCoeffs(LignePivot, LignePivot) = 0) Alors 
                //on cherche a permutter la ligne avec une autre, dont le coeff n'est pas nul 
                LignePermutation = LignePivot + 1 
                //on parcourt les lignes en dessous de la ligne actuelle 
                Tant que ((LignePivot + 1 <= Dimension) et (PermutationEffectuee = Faux)) 
                    //des qu'un coeff n'est pas nul 
                    Si (TabCoeffs(LignePermutation, LignePivot) <> 0) Alors 
                        //on inverse les deux lignes 
                        PermutterLigne(LignePivot, LignePermutation) 
                        PermutationEffectuee = Vrai 
                    FinSi 
                //on s'arrete si on a parcouru toutes les lignes 
                //ou si on a effectue une permutation 
                FinTq
 
                //si pas de permutation effectuee, on s'arrete car un coefficient de la diagonale est nul
                Si (PermutationEffectuee = Faux) Alors
                    ArretFonction = Vrai
                FinSi
             FinSi
 
             Si (ArretFonction = Faux) Alors            
                 //on met les coefficients dans la colonne du pivot a zero 
                 Pour Ligne <- LignePivot + 1 à Dimension - 1 
                     //calcul du coefficient pour l'opération
                     CoefficientMultiplication = -TabCoeffs(Ligne, Ligne) / TabCoeffs(LignePivot, Ligne)
                     //Ly <- Ly - u Lx 
                     OperationSurLigne(Ligne, LignePivot, CoefficientMultiplication) 
                 FinPour 
            FinSi 
        Jusqu'à ((LignePivot > Dimension) Ou (ArretFonction = Vrai))
 
        //----- Calcul du determinant -----
        //Si on est sorti a cause d'un coeff sur la diagonale nul, le determinant est nul
        Si (ArretFonction = Vrai) Alors
            DeterminantCalcule = Faux
        Sinon 
            //on calcule le determinant en faisant le produit de la diagonale 
            DeterminantCalcule = 1 
            Pour Ligne <- 1 à Dimension 
                DeterminantCalcule = DeterminantCalcule * TabCoeffs(Ligne, Ligne) 
            FinPour 
        FinSi
    FinSi 
 
    Retourner(DeterminantCalcule)

[alveric]

mais je ne vais pas travailler avec des flottants moi, juste des decimaux (2 ou 5 chiffres apres la virgule, jamais plus).

En machine, ca s'appelle des flottants; et les flottants sont rarement representables exactement sur un ordinateur...
Quand tu calcules les nouveaux coefficients, par exemple

Code :

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

a'21 = a21 - (a21/a11)*a11

, les arrondis materiels feront que tu ne retomberas pas exactement sur zero, mais sur 10^-5, 10^-15... et le test (a'21 == 0) echouera. Tu me diras que pour a'21, ce n'est pas grave... Mais si, par exemple, a11 = a12 et a21 = a22, alors a'22 aura la meme valeur "presque nulle". Et la deuxieme iteration du pivot fera des trucs bizarres... Tu peux essayer, pour voir les resultats numeriques qui sortent, ca pourra montrer des ordres de grandeur des erreurs commises (ce qui est toujours interessant a connaitre).

Code :

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

1
2
3
4
5
6
7
             Si (ArretFonction = Faux) Alors           
                 Pour Ligne <- LignePivot + 1 à Dimension - 1
                     CoefficientMultiplication = -TabCoeffs(Ligne, Ligne) / TabCoeffs(LignePivot, Ligne)
                     //Ly <- Ly - u Lx
                     OperationSurLigne(Ligne, LignePivot, CoefficientMultiplication)
                 FinPour
            FinSi

1) pourquoi jusqu'a (Dimension -1) ?
2) Si tu mets la formule en commentaire, mais que tu utilises d'autres notations, c'est moins comprehensible... Ly, c'est Ligne ou LignePivot ? Si on connait l'algo, on comprend, mais quelqu'un relit apres... il aura un peu de mal a suivre (de oute facon, ca doit etre precise dans la doc de la fonction que tu appelles).
3) L'operation, c'est une combinaison lineaire... (enfin, une combinaison particuliere).

[alveric]

mais je ne vais pas travailler avec des flottants moi, juste des decimaux (2 ou 5 chiffres apres la virgule, jamais plus).

En machine, ca s'appelle des flottants; et les flottants sont rarement representables exactement sur un ordinateur...
Quand tu calcules les nouveaux coefficients, par exemple

Code :

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

a'21 = a21 - (a21/a11)*a11

, les arrondis materiels feront que tu ne retomberas pas exactement sur zero, mais sur 10^-5, 10^-15... et le test (a'21 == 0) echouera. Tu me diras que pour a'21, ce n'est pas grave... Mais si, par exemple, a11 = a12 et a21 = a22, alors a'22 aura la meme valeur "presque nulle". Et la deuxieme iteration du pivot fera des trucs bizarres... Tu peux essayer, pour voir les resultats numeriques qui sortent, ca pourra montrer des ordres de grandeur des erreurs commises (ce qui est toujours interessant a connaitre).

Code :

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

1
2
3
4
5
6
7
             Si (ArretFonction = Faux) Alors           
                 Pour Ligne <- LignePivot + 1 à Dimension - 1
                     CoefficientMultiplication = -TabCoeffs(Ligne, Ligne) / TabCoeffs(LignePivot, Ligne)
                     //Ly <- Ly - u Lx
                     OperationSurLigne(Ligne, LignePivot, CoefficientMultiplication)
                 FinPour
            FinSi

1) pourquoi jusqu'a (Dimension -1) ?
2) Si tu mets la formule en commentaire, mais que tu utilises d'autres notations, c'est moins comprehensible... Ly, c'est Ligne ou LignePivot ? Si on connait l'algo, on comprend, mais si quelqu'un relit apres... il aura un peu de mal a suivre (de toute facon, ca doit etre precise dans la doc de la fonction que tu appelles).
3) L'operation, c'est une combinaison lineaire... (enfin, une combinaison particuliere).

[Peltchag]

je ne savais pas pour les flottants, j'apprends quelque chose ! donc il faut que je remplace le test par un test :

Code :

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

Si (abs(coeff) < 10^-x) Alors

mais quelle valeur doit avoir x, si je travaille avec des decimaux qui ont 5 chiffres apres la virgule ?

pour repondre aux remarques :
1. euh... parce que j'ai pas tres bien dormi
2. c'est vrai, mais bon, celui qui lit ce code, il a interet a connaitre le pivot de gauss de toute facon !!!
3. merci, j'avais oublie! c'est loin tout ca

[alveric]

Ce n'es pas forcement un nombre de la forme 10^(-x). Suivant le langage et le systeme, tu peux avoir des constantes predefinies, qui donnent par exemple la valeur strictement positive la plus petite representable sur le systeme (avec un nom comme EPSILON), et qui permet de dire "A = B" quand tu as en fait abs(A-B) < EPSILON. Ada permet meme de la configurer, il me semble.
Pour ce qui est de te donner une valeur acceptable, bah surement quelques ordres de grandeur inferieur a 10^(-5). Apres, une valeur precise...

[Matthieu Brucher]

Heureusement que j'ai dit que la manière la plus simple était par les matrices de Houseolder... Une SVD complète est inutile, il faut juste la partie capable de bidiagonaliser une matrice.
Si ton code a une complexité supérieure à O(n^3), prends cette solution. En plus la GSL propose ça "facilement".
Il y a pleins de librairies OS de calcul matriciel, si vous pouvez les utiliser, utilisez-les ! - je n'ai pas pu le faire dans mon cas et ma librairie se retrouve à être complexe... -

[alveric]

Si ton code a une complexité supérieure à O(n^3), prends cette solution.

Justement,je ne me souviens plus de la complexité du pivot... Et j'ai un peu la flemme de la recalculer

[Matthieu Brucher]

Tout dépend comment on calcule ! La méthode Houseolder fait intervenir une multiplication par un vecteur puis le vecteur transposé. C'est la matrice de Housolder. Si on joue à l'idiot et qu'on calcule d'abord la matrice, on se retrouve avec une multplication matricielle pour chaque colonne du tableau, donc du O(n^4), tandis que si on fait d'abord le vecteur puis le vecteur transposé, ce ne sera plus que du O(n^3).

[DrTopos]

Bonjour.

(vu que le determinant est aussi invariant par permutation de lignes)

Si tu en trouves un, tu permutes les deux lignes et passes a la suite.

PermutterLigne(LignePivot, LignePermutation)

Juste une petite remarque, qui évitera peut-être un bug: s'il est vrai que le déterminant est invariant par ajout à une ligne d'une combinaison linéaire des autres lignes, il n'est pas invariant par permutation de deux lignes. Dans ce cas, il change de signe (sauf si on permute une ligne avec elle-même, bien sûr). La même chose vaut pour les colonnes. En d'autres termes, le déterminant n'est pas seulement multilinéaire. Il est multilinéaire alterné.

Cordialement.

[alveric]

Bonjour,

En d'autres termes, le déterminant n'est pas seulement multilinéaire. Il est multilinéaire alterné.

...et meeeeeeerde........
Voila ce que c'est de dire des choses sans verifier dans son cours de math...

[Matthieu Brucher]

J'avais pas vu cette ânerie non plus...

[Rafy]

La methode du pivot de gauss pour triangulariser la matrice est efficace, mais elle peut être employée de deux manières...
Tu peut prendre le plus grand terme pour pivot, alors ta précision sera plus grande mais les calculs plus lourd. Avec le terme le plus petit en pivot, c'est l'inverse... Tu peux aussi essayer de trier les colonnes pour voir s'il n'y a pas de zéro bien placé, et aussi si la matrice est symétrique.
Dans le cas symétrique, c'est super !!!!! Car tu peux mettre ta matrice sous la forme :

Code :

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

1
2
 
A = (B)*(^tB)

(Comprendre tansposée)
avec A ta matrice, et B une matrice colonne....

[Matthieu Brucher]

...
Si A est symétrique, tu ne peux pas la mettre sous cette forme à moins qu'elle soit de rang 1 !
Ton écriture est sans doute celle de Cholesky où B est triangulaire ?

Au fait, pourquoi les calculs sont plus lourds en prenant le pivot l'élément le plus important ?

[Rafy]

Oui je suis allé trop vite effectivement.. Mais B n'est pas obligé d'être triangulaire...
Et oui pour les matrices de rang 1 c'est nickel !!! Pardon trop rapide.
Allez-y
Les calculs sont plus lourd car il faut diviser les coefficients, dans l'autre cas il faut les multiplier... C'est pas pareil

[alveric]

Dans le cas symétrique, c'est super !!!!! Car tu peux mettre ta matrice sous la forme :

Code :

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

1
2
 
A = (B)*(^tB)

(Comprendre tansposée)
avec A ta matrice, et B une matrice colonne....

Autrement dit, tu passes d'une matrice symetrique d'ordre n, donc un element d'un espace de dimension n*(n+1)/2, a un vecteur element d'un espace de dimension n. Il n'y aurait pas une erreur ? Je suis plutot de l'avis de Miles.
Et idem pour la "lourdeur" des calculs avec l'element le plus "important" (en valeur absolue, je suppose ?).

EDIT: mes reponses m'ont devance de peu...

[Rafy]

Ben ouais en valeur absolue... Sinon ça n'a pas de sens.
Il faut savoir que le calcul d'un déterminant c'est d'ordre !n (par la téchnique standard de développement par rapport à une ligne ou colonne), donc presque toutes les methodes sont mieux !

[Rafy]

Si les matrices dont il faut déterminer le déterminant sont des matrices de type directX (Transformation spaciale) il y a déjà des methodes pour le faire. (En plus si les matrices sont orthogonales ! Leur déterminant vaut 1 en valeur absolue... iark).

[Matthieu Brucher]

Oui je suis allé trop vite effectivement.. Mais B n'est pas obligé d'être triangulaire...
Et oui pour les matrices de rang 1 c'est nickel !!! Pardon trop rapide.
Allez-y
Les calculs sont plus lourd car il faut diviser les coefficients, dans l'autre cas il faut les multiplier... C'est pas pareil

Ah ? pour moi, il y a toujours une division quand même...

Oui, B n'est pas forcément triangulaire, mais c'est parce que ça rappelle beaucoup la décomposition de cholesky.

[alveric]

Oui je suis allé trop vite effectivement.. Mais B n'est pas obligé d'être triangulaire...
Et oui pour les matrices de rang 1 c'est nickel !!! Pardon trop rapide.
Allez-y
Les calculs sont plus lourd car il faut diviser les coefficients, dans l'autre cas il faut les multiplier... C'est pas pareil

Ah ? pour moi, il y a toujours une division quand même...

Pour moi aussi. Je vois comment reduire le nombre total de divisions a (n-1) pour un determinant d'ordre n, mais de la a s'en passer...

[Rafy]

Heu dans la page tout le monde me fouette !!!!! Ca fait mal.
Attendez, je réfléchi....
hum....
C'est vrai, que le nombre de division n'est pas réduit à zéro.
Le truc ça vient de la précision, voila c'est ca.
Si on fait la division, puis la multiplication, on a pas la même précision que si on fait l'inverse... Voila. Ce coup ci c'est bon... Pas de fouet.
De toute manière, ça coute cher de calculer un déterminant...
Es ce que l'appel est fréquent ou pas ?
C'est pour un jeu, dans chaque frame... Es ce que des lignes ou colonnes de la matrice restent les mêmes entre deux calculs ?