Comparatif résolution d'un système linéaire ?
Comparatif résolution d'un système linéaire ?
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.
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.
Re: Comparatif résolution d'un système linéaire ?
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.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.
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.
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+,
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+,
Merci
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...
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...
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+,
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+,
GPL et LGPL
Oui, mais à condition de fournir le code source à qui le demande, si la librairie est en licence GNU GPL...manut a écrit :non tu as le droit de les utiliser librement, meme pour les inclure dans un programme commercial.
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
"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.
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.
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
-
- Sujets similaires
- Réponses
- Vues
- Dernier message