On a pas la même précision ? Ah bon...
D'ailleurs, je ne vois pas pourquoi on n'a pas le même ordre, tu peux un peu développer stp ?
On a pas la même précision ? Ah bon...
D'ailleurs, je ne vois pas pourquoi on n'a pas le même ordre, tu peux un peu développer stp ?
Envoyé par RafyEnvoyé par Rafy
C'est possible...Envoyé par Rafy
Ca causerait combien de difference entre calculer d'abord le 1/akk, puis faire les multiplications (dont la multiplication par 1/akk), et faire toutes les multiplications suivies de la division par akk ? Ca doit dependre des ordres de grandeur des valeurs, je suppose...
Bonne question, faudrait pas non plus perdre deux semaines a optimiser une fonction qui ne prend que 0,01% du temps de l'appli...Envoyé par Rafy
Bonjour à tous.
Vous ne seriez pas un peu en train de jouer aux shadocks ?
J'ai du mal à comprendre pourquoi tout le monde veut diviser pour calculer un déterminant (surtout 4x4). Le déterminant est un polynôme par rapport aux coefficients de la matrice, et dans un polynôme il n'y a que des additions et des multiplications. Je sais qu'on enseigne des tas de recettes de cuisine à base de pivot de Gauss, mais franchement pour le déterminant ce n'est pas très utile.
Si on applique la formule du développement par rapport à la première colonne récursivement, et qu'on fait attention de ne pas calculer deux fois les déterminants 2x2 que je note ci-dessous D_12, D_13, D_14, D_23, D_24, D_34, et qui sont tous ceux qu'on obtient en rayant les deux première colonnes, et les deux lignes indiquées en indices:
le déterminant de la matrice est simplement:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 D_12 = a_33a_44 - a_34a_43 D_13 = a_23a_44 - a_24a_43 D_14 = a_23a_34 - a_24a_33 D_23 = a_13a_44 - a_14a_43 D_24 = a_13a_34 - a_14a_33 D_34 = a_13a_24 - a_14a_23
(Vérifiez quand même mes calculs, je ne suis pas infaillible.)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 D = a_11(a_22D_12 - a_32D_13 + a_42D_14) - a_21(a_12D_12 - a_32D_23 + a_42D_24) + a_31(a_12D_13 - a_22D_23 + a_42D_34) - a_41(a_12D_14 - a_22D_24 + a_32D_34)
Finalement, on fait 28 multiplications, 17 additions ou soustractions, et c'est tout. Pas de test, pas de boucle, pas de recopiage, pas de division. Je crois que cet algo tient la route en vitesse et en simplicité.
Il faudrai essayer de voir avec le pivot de gauss combien il y a d'opérations, mais je pense qu'il y en a moins...
Certe c'est une methode bête et méchante, elle marche, je suis d'accord.
Mais si c'est pour calculer 1000 déterminants par frames, il vaut mieux optimiser un peu, un déterminant c'est lourd
28 multiplications, ça fait mal quand même.Envoyé par DrTopos
Je vais faire le calcul du nombre d'opération avec le pivot. je vous tiens au courant.
Ben en fait ça dépend de plein de choses :Envoyé par alveric
Le type de donnée utilisé (float ou double ou long double)
Ca dépend des ordres de grandeurs (si on est proche de 0 vaut mieux multiplier puis diviser car on s'écarte de 0 => plus grande présicion... Je m'explique ensuite)
Première grosse démo en construction :
http://bitbucket.org/rafy/exo2/
Si on a un nombre qui est déjà petit, (donc on a un certain nombre de chiffre après la virgule), on le divise par un nombre grand. On va avoir un nombre encore plus petit. (on va être encore plus près de 0 donc moins de chiffre.) Si on remultiplie par un nombre, les chiffres qu'on a perdu ne vont pas revenir.Envoyé par Rafy
Il vaut donc mieux multiplier d'abord, s'écarter de 0, décaller vers la gauche nos chiffres (par rapport à la virgule), avant de repartir vers la droite en divisant...
Je sais pas si vous avez tout compris, dite moi.
Je vais regarder avec le pivot combien on a d'opérations.
Première grosse démo en construction :
http://bitbucket.org/rafy/exo2/
Ca m'étonnerait que 28 multiplications fassent moins de mal que 4 divisions et 6 multiplications.
Sinon pourquoi diviser ? C'était dans le cas où on avait un déterminant plus gros à calculer et effectivement c'est pas le cas ici...
Alors voila, pour le pivot de gauss, si tous mes calculs sont bon :
multiplications = 18
divisions = 14
soustractions = 14
additions = 0
en version bourine (recalcul du coefficient multiplicateur d'une ligne à chaque appel)
multiplication = 18
divisions = 6
soustractions = 14
additions = 0
en version un peu mieux.
Première grosse démo en construction :
http://bitbucket.org/rafy/exo2/
Je suppose que faire une soustraction ca prend autant de temps qu'une addition.
Par contre je ne sais pas pour une divison par rapport à une multiplication.
Si c'est le même temps, ca marche mieux que la technique littérale de DrTopos.
Je suppose que tu parles de la complexité de l'algorithmeEnvoyé par Miles
Si c'est le cas, la complexité est moins grande quand tu fais des methodes qui amène à faire des factorisations, car il y a moins de calculs.
Dans notre cas, le pivot est puissant car on est psa obligé de connaitre tous les termes de la matrices pour pouvoir calculer son déterminant (des qu'elle est triangulaire c'est gagné !) Ca évite donc les calculs des coéfficients du triangle qui est dans la matrice. Moins de calculs => Moins de complexité.
Première grosse démo en construction :
http://bitbucket.org/rafy/exo2/
Dans la methode de DrTopos, on a besoin de tous les coefficients. pas pour le pivot (enfin si mais indirectement).
Première grosse démo en construction :
http://bitbucket.org/rafy/exo2/
Sans connaitre le nombre de cycles machines habituellement necessaires pour l'un ou l'autre, il me semble qu'une division est plus lourde qu'une multiplication.Envoyé par Rafy
En recomptant pour un pivot de Gauss d'ordre 4 un petit peu optimise, j'ai 23 multiplications, 3 divisions, 14 soustractions, et 23 affectations. Mais c'est dans le cas optimal, il faut ajouter les tests de nullite (au moins 3) et les permutations eventuelles qui alourdissent la complexite...
Et, de plus, cela vaut dans le cas ou les boucles sont deroulees. Si on fait les boucles "pour" et autres, il faut ajouter d'autres tests, affectations et additions...
Du coup la methode de DrTopos est bien evidemment la meilleure a l'ordre 4, sans appel.
Mais on a bien le droit de s'amuser a reinventer la roue, non ?
Et je rappelle que le sujet a vite devie sur l'ordre quelconque des la premiere page
EDIT: mais c'est vrai que, pour une telle fenetre d'ordres, il serait plus efficace de creer des sous-fonctions optimisees pour chaque ordre jusqu'a 5 ou 6, puis une sous-fonction generale pour les ordres superieurs...Envoyé par Peltchag
ben je ne sais pas comment tu as fais pour trouver autant d'opérations !Envoyé par alveric
Je viens de le refaire, je trouve comme j'ai dit tout à l'heure...
Alors 23 multiplications je ne trouve pas ça... 3 divisions, non plus je ne vois pas comment tu fais ça....
Première grosse démo en construction :
http://bitbucket.org/rafy/exo2/
Envoyé par Rafy[*]1/a22[*]a33 = ...[*]idem jusqu'a a44 = a44 - a43/a33 * a34[/list:u:ec7f398d05]Pour la seconde etape: 1 division, 2*3 = 6 multiplications et 2*2 = 4 soustractions.
- premiere iteration:[list:ec7f398d05]
- 1/a11 soit une division
- pour la deuxieme ligne: a21 * (1/a11)
- a22 = a22 - (a21/a11) * a12
- a23 = a23 - (a21/a11) * a13
- a24 = a24 - (a21/a11) * a14
- idem pour les 3e et 4e lignes, soit 4 multiplications, 3 soustractions par ligne (pas de calcul de a21 qu'on negligera de toute facon apres...), d'ou 1 division, 12 multiplications et 9 soustractions pour la premiere etape
Pour la troisieme etape: 1 divison, puis deux multiplications et une soustraction.
Et enfin les trois multiplications pour calculer le produit de la diagonale.
D'ou 3 divisions, 12 + 6 + 2 + 3 = 23 multiplications, et 9 + 4 + 1 = 14 soustractions.
Mais evidemment on perd en precision par rapport a calculer d'abord les multiplications puis faire les divisions... C'est un compromis (inutile pour l'ordre 4, comme vu precedemment).
Oui, 3 divisions, je suis d'accord, une par pivot - d'ailleurs ou stock toujours l'inverse du pivot pour ne pas avoir à le recalculer -
Je ne parlais pas de l'ordre de complexité, je parlais de l'ordre par rapport à ce que tu disais multiplication puis division ou division puis multiplication ! La complexité, je sais ce que c'est merci !
Entre ce que j'ai proposé et la méthode du pivot, il n'y a pas seulement une question de performances. Ce qui me chagrine encore une fois est que le déterminant étant un polynôme, le fait d'introduire des divisions est un peu comme passer par New York pour aller de Châtelet à Saint-Lazare.
De toute façon, les résultats risquent de ne pas être les mêmes. Le problème avec le pivot, en plus de la division, est qu'il faut tester la nullité de coefficients. Or ce test est loin d'être rigoureux, car comme cela a été dit précédemment, c'est une comparaison avec un nombre petit et assez arbitraire. Il est possible que le pivot soit plus rapide (j'en doute beaucoup), mais sur le plan de la justesse il laisse un peu à désirer (encore que cela dépende de l'application qu'on a en vue).
Note: la méthode que j'ai proposée peut se généraliser en toute dimension. En particulier jusqu'à 6 ça ne pose pas de problème.
Je suis d'accord. La methode du pivot etait la premiere qui m'etait venue a l'idee (avec le fait d'ecrire la formule complete), mais je n'avais pas etudie sa complexite ni sa precision.Envoyé par DrTopos
J'aimerais bien avoir l'algorithme qui fait ca, pour m'instruire... Ca se trouve ou ? Au moins, que je connaisse d'autres methodes que celles vues lors de mes cours...Envoyé par DrTopos
C'est une question d'algèbre extérieure. Je fais d'abord remarquer que le point important dans ce que j'ai proposé pour la dimension 4 est le fait que les 6 déterminants 2x2 ne sont calculés qu'une fois (et utilisés 2 fois chacun). Dans le cas d'une matrice 5x5, si on applique brutalement la méthode récursive de développement par rapport à une colonne, on calcule deux fois les déterminants 3x3 et 6 fois les déterminants 2x2. Dans le cas d'une matrice 6x6, on calcule 2 fois les déterminants 4x4, 6 fois les déterminants 3x3 et 24 fois les déterminants 2x2. Evidemment, c'est du gachis.Envoyé par alveric
Donc toute la question est de savoir quoi calculer à l'avance pour le réutiliser plusieurs fois, et c'est là que l'algèbre extérieure intervient. On trouve des exposés d'algèbre extérieure dans les bouquins d'algèbre évidemment, mais aussi dans les bouquins de géométrie différentielle, car ces notions sont cruciales pour la définition des formes différentielles. Toutefois, pour ce qui nous occupe, il y a peu de choses à savoir.
Si E est un espace vectoriel de dimension n (disons sur le corps des réels), dans lequel on a choisi une base (e_1,...,e_n), et si k est un entier naturel, on peut considérer la k-ième puissance extérieure de E, qui est un espace vectoriel noté /\k(E) (c'est un lambda majuscule) ayant naturellement pour base toutes les parties à k éléments de l'ensemble {1,...,n}. Sa dimension est donc C(n,k) (coefficient du binôme de Newton). Par exemple en dimension 4, la dimension de /\2(R^4) est 6, et c'est pour cela qu'on devait stoker les 6 valeurs D_12, D_13, etc... Une base de /\2(R^4), pourrait être notée (e_12,e_13,e_14,e_23,e_24,e_34), mais elle est plutot notée:
où x^y n'est pas x à la puissance y, mais le produit extérieur des vecteurs x et y. Le produit exterieur est en fait une application de Ex...xE (produit cartésien de k facteurs) vers /\k(E) qui est multilinéaire alternée. En fait, ceci peut être vu comme la généralisation du calcul du déterminant aux matrices qui ne sont pas carrées.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 (e_1^e_2, e_1^e_3, e_1^e_4, e_2^e_3, e_2^e_4, e_3^e_4)
Il est facile de calculer un produit extérieur par exemple celui des vecteurs (a,b) et (c,d) de R^2. Comme (a,b) = ae_1 + be_2, et (c,d) = ce_1 + de_2, la multiilinéarité, et l'antisymétrie (e_1^e_1 = e_2^e_2 = 0, e_2^e_1 = -e_1^e_2, etc...) donnent (a,b)^(c,d) = (ad-bc)(e_1^e_2). Tiens, revoila le déterminant ! Dans le cas de /\2(R^4), si on calcule (a_13,a_23,a_33,a_43)^(a_14,a_24,a_34,a_44) on trouve le vecteur de coordonnées D_12, D_13, etc... Donc dans la méthode que j'ai proposée, on commence par calculer le produit extérieur des deux dernière colonnes.
La méthode générale, pour une matrice nxn, dont les colonnes sont les vecteurs (de R^n) v_1,...,v_n, consiste à calculer le produit extérieur:
Dans le cas de la dimension 4, comme /\4(R^4) est de dimension 1 (car C(4,4) = 1), le produit ci-dessus est de la forme d(e_1^....^e_4), où d est un réel. En fait, d est tout simplement le déterminant de notre matrice. Ceci peut d'ailleurs ête considéré comme une définition du déterminant.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 v_1^v_2^...^v_n
On voit donc, par exemple dans le cas d'une matrice 6x6, c'est à dire du produit extérieur v_1^...^v_6, qu'il faut commencer par calculer u = v_5^v_6 (15 coordonnées), puis w = v_4^u (20 coordonnées), puis t = v_3^w (15 coordonnées), puis s = v_2^t (6 coordonnées) et enfin v_1^s qui a une seule coordonnée qui est le déterminant cherché. On sait donc exactement compien de tableaux de nombres on doit réserver pour le calcul et de quelle taille.
J'espère avoir été clair, même si mon texte contient quelques affirmations non démontrées.
Je ne connaissais pas... On apprend tous les joursEnvoyé par DrTopos
Fouia, ca m'a l'air interessant tout ca ! Il faudra que je relise a tete reposee, mais ca m'a l'air bien explique Merci !Envoyé par DrTopos
La méthode se généralise à n'importe quelle dimension si on ne stocke pas les valeurs des 'petits' déterminant dans des variables mais dans un tableau.Envoyé par DrTopos
L'explication donnée par DrTopos est très mathématique. Un aspect plus algorithmique de sa solution est qu'elle fait appel à la programmation dynamique, dont le principe est de résoudre un problème en le décomposant en sous problèmes plus faciles à résoudre, en stockant les solutions de ces sous problèmes dans un tableau pour éviter à les résoudre plusieurs fois (beaucoup de fois!).
J'ai pas calculé comme ça... C'est pour ça quer je ne trouve pas le même nombre d'opérations :
-> Je calcul a11/a21, je multiplie chaque terme de la seconde ligne par ça.
Je fais la différence avec la première ligne (1 /, 3*, 3-)
-> De même avec la seconde ligne et la troisième (en tout 3/, 9*, 9-)
-> Je recommence au cran en dessous donc (2/, 4*, 4-)
-> Encore une fois (1/, 1*, 1-)
En tout 6/, 17*, 14-
Comme je l'avais dit au coup d'avant (je m'étais trompé sur la dernière multiplication j'en avais compté 4 au lieu de 3), donc j'ai moins d'opérations que toi Alveric, et aussi moins que DrTopos.
Même résultat, mais pas même démarche...
Première grosse démo en construction :
http://bitbucket.org/rafy/exo2/
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager