Calcul déterminant et complexité [Résolu]

[21did21]

salut tous,

j'ai quelques infos à vous demandez :

1°) si je comprends bien le calcul de déterminant fait intervenir autant de boucle que la taille de la matrice ?

du coup si je veux calculer un determinant de 1e6*1e6 comment dois je faire ? les temps de calcul vont être enorment ?

(meme chose pour le calcul d'une matrice inverse puisqu'il y a un determiant ?)

2°) comment calcul t on la complexité d'un algorithme, pourriez vous me donner deux exemples simples s'il vous plait ?

- cas du déterminant
- cas de la resolution d'une matrice triangulaire.

je vous remercie d'avance pour l'aide pour que vous pourrez m'apportez

[FR119492]

Salut!
A quoi cela sert-il de calculer le déterminant d'une grosse matrice?
Jean-Marc Blanc

[Franck Dernoncourt]

Envoyé par 21did21

1°) si je comprends bien le calcul de déterminant fait intervenir autant de boucle que la taille de la matrice ?

du coup si je veux calculer un determinant de 1e6*1e6 comment dois je faire ? les temps de calcul vont être enorment ?

(meme chose pour le calcul d'une matrice inverse puisqu'il y a un determiant ?)

Voici les complexités des algorithmes habituels : http://en.wikipedia.org/wiki/Computa...Matrix_algebra

Envoyé par 21did21

2°) comment calcul t on la complexité d'un algorithme, pourriez vous me donner deux exemples simples s'il vous plait ?

- cas du déterminant
- cas de la resolution d'une matrice triangulaire.

je vous remercie d'avance pour l'aide pour que vous pourrez m'apportez

Je n'ai pas de bons liens sous la main, mais peut-être que http://www.algo-class.org/ t'intéressera (ils vont probablement étudier la complexité à un moment). Sinon, en matière d'études d'algorithmes, le livre de référence est http://algo.developpez.com/livres/#L9782100545261

[21did21]

Envoyé par Franck Dernoncourt

Voici les complexités des algorithmes habituels : http://en.wikipedia.org/wiki/Computa...Matrix_algebra

Je n'ai pas de bons liens sous la main, mais peut-être que http://www.algo-class.org/ t'intéressera (ils vont probablement étudier la complexité à un moment). Sinon, en matière d'études d'algorithmes, le livre de référence est http://algo.developpez.com/livres/#L9782100545261

merci Franck mais je n'ai pas vraiment trouvé de démonstration/explications simple dans ces liens.... (pour cette question à priori simple également...)

en fait je cherche une explication pour une personne débutante là dedans, j'aimerai plus une explication de la demarche à suivre pour calculer la complexité des algo..

[Franck Dernoncourt]

Envoyé par 21did21

merci Franck mais je n'ai pas vraiment trouvé de démonstration/explications simple dans ces liens.... (pour cette question à priori simple également...)

Oui je sais, mais je répondais à ta question :

Envoyé par 21did21

1°) si je comprends bien le calcul de déterminant fait intervenir autant de boucle que la taille de la matrice ?

du coup si je veux calculer un determinant de 1e6*1e6 comment dois je faire ? les temps de calcul vont être enorment ?

(meme chose pour le calcul d'une matrice inverse puisqu'il y a un determiant ?)

Pour les démonstration/explications du calcul de la complexité des algorithmes permettant de calculer l'inverse ou le déterminant, il faut simplement les chercher sur Google en espérant qu'il y existe des documents clairs.

Envoyé par 21did21

en fait je cherche une explication pour une personne débutante là dedans, j'aimerai plus une explication de la demarche à suivre pour calculer la complexité des algo..

Désolé, hormis les liens que je t'ai mentionnés précédemment (dont j'ai conscience qu'ils ne sont pas pratiques pour comprendre rapidement l'étude de la complexité), je n'ai pas de ressources simples en tête

[21did21]

Envoyé par Franck Dernoncourt

Oui je sais, mais je répondais à ta question :
Pour les démonstration/explications du calcul de la complexité des algorithmes permettant de calculer l'inverse ou le déterminant, il faut simplement les chercher sur Google en espérant qu'il y existe des documents clairs.

Désolé, hormis les liens que je t'ai mentionnés précédemment (dont j'ai conscience qu'ils ne sont pas pratiques pour comprendre rapidement l'étude de la complexité), je n'ai pas de ressources simples en tête

d'accord, merci quand même de ton aide Franck

A+

[Franck Dernoncourt]

Si quelqu'un passant ici connaît une bonne ressource (site Internet, pdf, etc) expliquant clairement la méthode pour déterminer la complexité d'un algorithme, svp faites-le nous savoir !
Personnellement j'ai appris les bases par transmission orale (c'est assez simple au final une fois que l'on trouve une source claire) et perfectionné essentiellement sur http://algo.developpez.com/livres/#L9782100545261 (version anglaise et deuxième édition pour être précis, c'est une mauvaise idée de l'acheter en français)

[FR119492]

Salut!

Le calcul d'un déterminant peut être utile dans l'étude des quadripôles, mais on a affaire à des matrices de taille 2*2, le plus souvent à coefficients complexes. On a alors det(A)=A11*A22-A12*A21; on a donc toujours 2 multiplications et une soustraction et la notion de complexité ne s'applique pas dans ce cas.

Dans certains problèmes de géométrie, un volume peut aussi être calculé à l'aide du déterminant d'une matrice, mais la taille de celle-ci ne dépassera pas 3*3, parce que nous vivons dans un espace tridimensionnel.

En revanche, on sait qu'une matrice est singulière si et seulement si son déterminant est nul. Cela a pour conséquence que beaucoup de débutants commencent par essayer de calculer le déterminant par la méthode de Sarrus généralisées pour savoir si la matrice est singulière. Or la complexité de cette méthode est O(n!); pour le commun des mortels, il suffit de savoir qu'elle est catastrophique. Lorsqu'on doit résoudre un système linéaire ou, ce qui est beaucoup plus rare, inverser une matrice, il est beaucoup plus sage de faire une factorisation LU (méthode de Crout), dont la complexité est O(N^3), en vérifiant avant chaque division que le dénominateur n'est pas nul.

Pour voir comment ça se passe en pratique, je te recommande de regarder comment fonctionnent les routines SGEFA, SGESL et SGEDI de la librairie LinPack (disponible sur www.netlib.org).

Jean-Marc Blanc

[Aleph69]

Bonjour,

pour calculer le déterminant d'une matrice inversible A, on considère sa factorisation LU à une permutation près :

P*A=L*U,

où P est une matrice de permutation, L est une matrice triangulaire inférieure à diagonale unité et U est une matrice triangulaire supérieure U. Le déterminant de A est alors donné par la formule :

det(A) = det(L) * det(U) /det(P).

Par définition, P est unitaire et det(P)=1. Par ailleurs, le déterminant d'une matrice triangulaire est égal au produit de ses termes diagonaux. Puisque L est à diagonale unité, on a det(L)=1. Finalement,

det(A) = det(U) = u_11 * u_22 * ... * u_nn,

où u_ii désigne le terme diagonale de U situé en ligne et colonne d'indice i, pour i allant de 1 à n, n désignant la taille de A.

Bref, il suffit de calculer les termes diagonaux de U : on utilise pour cela la méthode d'élimination de Gauss en la simplifiant grandement puisqu'on a ni besoin de stocker L, ni besoin de stocker les termes extra-diagonaux de U. Je ne me suis jamais amusé à calculer la complexité de cette approche mais il est possible qu'elle soit d'un ordre inférieur à celle de la version "complète" de l'algorithme de Gauss qui est en O(n^3).
Si la matrice est hermitienne définie positive, on utilise l'algorithme de Cholesky mais l'approche est sensiblement la même.

[21did21]

merci pour ces reponses intéressante

[Franck Dernoncourt]

Envoyé par Aleph69

Je ne me suis jamais amusé à calculer la complexité de cette approche mais il est possible qu'elle soit d'un ordre inférieur à celle de la version "complète" de l'algorithme de Gauss qui est en O(n^3).

Le record à battre est O(n^2.376)

[Aleph69]

Ah oui? Avec quelle approche obtient-on cette borne?

[Franck Dernoncourt]

Envoyé par Aleph69

Ah oui? Avec quelle approche obtient-on cette borne?

Envoyé par Franck Dernoncourt

Voici les complexités des algorithmes habituels : http://en.wikipedia.org/wiki/Computa...Matrix_algebra

(je sais que l'on s'y perd avec tous ses liens )

[Franck Dernoncourt]

Je t'avouerai cependant que je ne me suis jamais penché en détail sur les meilleurs algorithmes (ce n'est pourtant pas la curiosité qui me manque, mais comme toujours le temps), donc aucune idée de leur fonctionnement !

[Aleph69]

Pour les cas pratiques, ce n'est pas très intéressant d'utiliser ces algorithmes : ils sont numériquement instables.