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

Discussions générales concernant les mathématiques.
[forum modéré par les modérateurs globaux du site]
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
Utilisateur confirmé
Utilisateur confirmé
Messages : 83
Inscription : vendredi 22 septembre 2006, 16:12

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

Message 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 global
Modérateur global
Messages : 7095
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne

Message 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 par jobherzt »

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

la main gauche
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 274
Inscription : jeudi 30 mars 2006, 08:44
Localisation : selon l'idéal de la liberté

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

Message 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.
la Main Gauche

manut
Utilisateur confirmé
Utilisateur confirmé
Messages : 18
Inscription : jeudi 03 août 2006, 20:57

Message 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
Utilisateur confirmé
Utilisateur confirmé
Messages : 83
Inscription : vendredi 22 septembre 2006, 16:12

Merci

Message 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
Utilisateur confirmé
Utilisateur confirmé
Messages : 18
Inscription : jeudi 03 août 2006, 20:57

Message 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
Utilisateur confirmé
Utilisateur confirmé
Messages : 83
Inscription : vendredi 22 septembre 2006, 16:12

GPL et LGPL

Message 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
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 128
Inscription : samedi 30 septembre 2006, 16:06

Message 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
Utilisateur confirmé
Utilisateur confirmé
Messages : 18
Inscription : jeudi 03 août 2006, 20:57

Message 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