Comparatif résolution d'un système linéaire ?

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
RGB

Comparatif résolution d'un système linéaire ?

Message non lu par RGB »

Bonjour,

Je cherche la méthode la plus rapide pour résoudre un système linéaire de taille 20x20 (à peu près) avec un ordinateur.

Auriez-vous des liens ou des informations sur un comparatif entre différentes méthodes (Gauss, Lu...) et sur les structures de données à utiliser pour implémenter ces algorithmes (en C++) ?

Merci.
Arnaud
Modérateur honoraire
Modérateur honoraire
Messages : 7097
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne
Contact :

Message non lu par Arnaud »

Pour un début de réponse :

viewtopic.php?t=974
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

si tu cherches une librairie efficace qui sache faire ca, regarde du cote de la gnu scientific librairie
la main gauche

Re: Comparatif résolution d'un système linéaire ?

Message non lu par la main gauche »

RGB a écrit :Je cherche la méthode la plus rapide pour résoudre un système linéaire de taille 20x20 (à peu près) avec un ordinateur.
Le plus facile est d'utiliser une bibliohtèque toute faite, je ne connais pas la GNU scientific library, il y a aussi LAPACK et ATLAS, qui sont des bibliothèques, et il y a aussi scilab (intria). Il est possible d'interface scilab avec un programme C, i.e. de l'utiliser comme bibliothèque, on peut aussi l'utiliser en écrivant un programme qui écrit des programmes pour scilab et en récupère les résultats.

Pour un problème numérique, le pivot de Gauss est bien, les QR est compagnie en sont de vagues améliorations. En réalité tout dépend de la forme de la matrice, dans certain cas, cela vaut le coup de mettre au point un algorithme spécialement adapté à cette forme de matrices, pour gagner du temps et/ou réduire l'erreur numérique.
manut

Message non lu par manut »

Pour une matrice 20*20 franchement, cela ne vaut guere le coup de se poser la question...

Mais bon, la main gauche a raison, le meilleur compromis est la methode du pivot de Gauss, tout simplement. C'est comme ca que sont implementees les routines de base dans scilab ou matlab.
Bien sur, tu as des raffinements quand les matrices ont des proprietes speciales (symetriques, tridiagonales, creuses, etc) : LU, QR, Householder, Cholevsky, etc.

Si tu veux en savoir plus sur ce sujet, je te conseille un tres bon livre de reference :

Algebre lineaire numerique, G. Allaire, M. Kaber.
Plus son complement Scilab.

a+,
RGB

Merci

Message non lu par RGB »

Merci pour toutes ces réponses !

En fait je voudrais implémenter cet algorithme dans un programme commercial.

Et donc si j'utilise la "GNU scientific library", je suppose que cela implique que je laisse mon code ouvert ? (je ne veux pas).

Sinon ma matrice est plutôt creuse avec des termes sur et autour de la diagonale...
manut

Message non lu par manut »

resalut,
non tu as le droit de les utiliser librement, meme pour les inclure dans un programme commercial.
Cf aussi le site "netlib" ou tu trouves toutes ces routines standards en fortran (librement egalement).

Si ta matrice est tridiagonale, il peut etre judicieux d'utiliser une methode de type Cholevsky (celle de base reclame une matrice symetrique), je t'encourage a faire quelques essais sous scilab ou matlab, ou ces routines sont implementees, pour tester laquelle est la plus rapide.
Et si besoin, consulter le bouquin d'Allaire, vraiment un tres bon livre sur ce sujet.

a+,
RGB

GPL et LGPL

Message non lu par RGB »

manut a écrit :non tu as le droit de les utiliser librement, meme pour les inclure dans un programme commercial.
Oui, mais à condition de fournir le code source à qui le demande, si la librairie est en licence GNU GPL...

Si la librairie est en licence GNU LGPL par contre, plus besoin de montrer le source...

Merci pour les conseils et pour le livre de Grégoire Allaire "Algèbre linéaire numérique / Cours et exercices / ISBN 2-7298-1001-3", aux éditions Ellipses
Pythales

Message non lu par Pythales »

"Sinon ma matrice est plutôt creuse avec des termes sur et autour de la diagonale..."
J'ai une méthode itérative qui marche très bien dans ce cas, et que j'ai expérimentée professionnellement sur une matrice de 300 X 300.
Avec le pivot de Gauss, le calcul durait 8h. Avec cette méthode, il ne durait plus que quelques minutes.
De mémoire, pour résoudre $AX=B$, on pose $A=D+E$ où $D$ est la diagonale de $A$, ce qui donne $DX=B-EX$ soit $X=D^{-1}(B-EX)$
$D^{-1}$ est facile à calculer, et on itère sur $X_{n+1}=D^{-1}(B-EX_n)$ qui converge d'autant plus vite que $E$ est "petite"
Si tu peux attendre la semaine prochaine, je tâcherai de retrouver ladite méthode pour plus de précisions.
manut

Message non lu par manut »

Pythales a écrit :"Sinon ma matrice est plutôt creuse avec des termes sur et autour de la diagonale..."
J'ai une méthode itérative qui marche très bien dans ce cas, et que j'ai expérimentée professionnellement sur une matrice de 300 X 300.
Avec le pivot de Gauss, le calcul durait 8h. Avec cette méthode, il ne durait plus que quelques minutes.
De mémoire, pour résoudre $AX=B$, on pose $A=D+E$ où $D$ est la diagonale de $A$, ce qui donne $DX=B-EX$ soit $X=D^{-1}(B-EX)$
$D^{-1}$ est facile à calculer, et on itère sur $X_{n+1}=D^{-1}(B-EX_n)$ qui converge d'autant plus vite que $E$ est "petite"
Si tu peux attendre la semaine prochaine, je tâcherai de retrouver ladite méthode pour plus de précisions.

salut,
oui la méthode que tu cites est en fait une méthode de préconditionnement. Elle marche bien si la matrice est à diagonale dominante, ce qui est peut-être le cas dans la matrice creuse en question.
En fait il y a deux grands types de résolution de système linéaire :
- méthodes directes : Gauss est alors principalement la meilleure méthode (en termes de complexité),
- méthodes itératives : là c'est les méthodes de gradient qui sont le plus efficaces. Mais la méthode dont tu parles ci-dessus est la méthode de Gauss-Seidel (ou de Jacobi ? Je ne me rappelle pas, et je n'ai pas le bouquin d'Allaire sous les yeux).

Pour plus de détails, cf le chapitre sur les méthodes itératives dans le bouquin d'Allaire - Kaber : Algèbre linéaire numérique. Les détails de preuve et les variantes d'algo y sont donnés.

a+, manut
Répondre
  • Sujets similaires
    Réponses
    Vues
    Dernier message