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

Discussions générales concernant les mathématiques.
[ce forum est modéré par les modérateurs globaux du site]
Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Pour obtenir de l'aide sur un exercice ou un problème, consulter cette section. (ce forum est destiné aux discussions plutôt théoriques)

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

Messagepar RGB » Vendredi 22 Septembre 2006, 15:17

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.
RGB
Hecto-utilisateur
 
Messages: 83
Inscription: Vendredi 22 Septembre 2006, 15:12

Publicité

Messagepar Arnaud » Vendredi 22 Septembre 2006, 15:22

Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar jobherzt » Vendredi 22 Septembre 2006, 16:09

si tu cherches une librairie efficace qui sache faire ca, regarde du cote de la gnu scientific librairie
jobherzt
Méga-utilisateur
 
Messages: 433
Inscription: Vendredi 13 Janvier 2006, 13:13

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

Messagepar la main gauche » Vendredi 22 Septembre 2006, 18:01

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
la main gauche
Méga-utilisateur
 
Messages: 274
Inscription: Jeudi 30 Mars 2006, 07:44
Localisation: selon l'idéal de la liberté

Messagepar manut » Samedi 30 Septembre 2006, 16:52

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+,
manut
Déca-utilisateur
 
Messages: 18
Inscription: Jeudi 03 Août 2006, 19:57

Merci

Messagepar RGB » Samedi 30 Septembre 2006, 23:41

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...
RGB
Hecto-utilisateur
 
Messages: 83
Inscription: Vendredi 22 Septembre 2006, 15:12

Messagepar manut » Dimanche 01 Octobre 2006, 08:55

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+,
manut
Déca-utilisateur
 
Messages: 18
Inscription: Jeudi 03 Août 2006, 19:57

GPL et LGPL

Messagepar RGB » Vendredi 06 Octobre 2006, 22:47

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
RGB
Hecto-utilisateur
 
Messages: 83
Inscription: Vendredi 22 Septembre 2006, 15:12

Messagepar Pythales » Mercredi 11 Octobre 2006, 11:22

"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$$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.
Pythales
Kilo-utilisateur
 
Messages: 129
Inscription: Samedi 30 Septembre 2006, 15:06
Statut actuel: Post-bac | Ecole d'ingénieur

Messagepar manut » Mercredi 11 Octobre 2006, 17:50

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$$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
manut
Déca-utilisateur
 
Messages: 18
Inscription: Jeudi 03 Août 2006, 19:57


Retourner vers Tribune des mathématiques

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 1 invité