Salut tous,

je m'intéresse aux algo de resolution de systemes lineaire:
- il existe des methodes directes (gauss, LU, QR...)
- les iteratives (jacobi, gradient...)
on choisi notre algo en fonction de :
- utilisation memoire, temps calcul, precision...

mais comment on relit le type d'algo à ces critères ? par exemple comment savoir si un algo est plus precis qu'un autre, comment savoir si il utilise + de memoire...?

merci pour l'aide que vous pourrez m'apporter

Des tonnes de documents ont été écrit sur le sujet. Il y a essentiellement deux options :
1) tu regardes l'algo et tu fais toi même les calcules, méthode la plus efficace pour bien comprendre ce que l'on fait (et même la seule)
2) tu trouves des papiers sur les algos.

merci pour cette première réponse, aurais tu quelques lien destinés au novices comme moi ?

merci

pour ce qui est rapidité d'exécution et mémoire, je te conseille
de jeter un coup d'oeil sur la complexité algorithmique , il y a meme un tuto sur le sdz à propos.

merci pour vos réponses, pouvez vous me donner le lien vers le tuto en question ?

http://www.siteduzero.com/tutoriel-3-5 [...] mplexite.html
mais comme son nom l'indique, il est fait pour les novices
donc il doit être un peu pauvre en information peut-etre

merci

Il faut aussi penser aux conditions d'application de tes algo (par exemple pour les méthodes de descentes, il te faut une matrice symétrique définie positive, ce qui n'est pas le cas de Gauss-Seidel), la stabilité numérique, etc.
Il faut aussi savoir si tu veux une solution exacte ou pas.
(sachant que les méthodes de descentes sont exactes en n itérations mais que l'on obtient de très bonnes approximations en moins par exemple).

Tu peux aussi regarder si tu veux faire du calcul distribué. Le gradient conjugué préconditionné s'y prête très bien par exemple.

merci pour ta reponse interessante

Citation : Hod

Il faut aussi penser aux conditions d'application de tes algo (par exemple pour les méthodes de descentes, il te faut une matrice symétrique définie positive, ce qui n'est pas le cas de Gauss-Seidel),

=> à oui, en effet, merci pour cette remarque je n'y avais pas pensé

Citation : Hod

stabilité

=> en general on cherche toujours à utiliser un algo stable ? sinon il n'y a pas d'intérêt puisque la solution sera plein d'erreur amplifiées...?

Citation : Hod

Il faut aussi savoir si tu veux une solution exacte ou pas.

=> avec un algo numerique la solution n'est jamais exacte ???

Citation : Hod

Tu peux aussi regarder si tu veux faire du calcul distribué. Le gradient conjugué préconditionné s'y prête très bien par exemple.

=> je n'ai pas compris par contre ce passage. Qu'appel tu un calcul distribué ? je ne connais pas le gradient conjugué quelle est la différence avec la méthode du gradient classique ?

enfait tu l'as mal compris

Citation

=> avec un algo numerique la solution n'est jamais exacte ???

il voulait dire par exemple, pour l'équation x^2 = 2,
tu veux <math>\(\sqrt{2}\)</math> ou bien 1.41 ?

Citation

=> en general on cherche toujours à utiliser un algo stable ? sinon il n'y a pas d'intérêt puisque la solution sera plein d'erreur amplifiées...?

je te renvoie ici pour mieux comprendre ce que veut dire "un algorithme stable"
http://fr.wikipedia.org/wiki/Algorithm [...] 3.A8re_stable

Citation : ZeRa

enfait tu l'as mal compris

Citation

=> avec un algo numerique la solution n'est jamais exacte ???

il voulait dire par exemple, pour l'équation x^2 = 2,
tu veux <math>\(\sqrt{2}\)</math> ou bien 1.41 ?

=> je sais que l'algo ne trouvera jamais racine(2) c'est pour cela que je dis que l'on trouvera jamais une solution exacte...

Citation : ZeRa

=> en general on cherche toujours à utiliser un algo stable ? sinon il n'y a pas d'intérêt puisque la solution sera plein d'erreur amplifiées...?

je te renvoie ici pour mieux comprendre ce que veut dire "un algorithme stable"
<lien </citation>

je t’avoues que j'ai pas trop compris... un algo instable n'est pas un algo qui amplifie les erreurs au cours du calcul ?

Citation : 21did21

=> en general on cherche toujours à utiliser un algo stable ? sinon il n'y a pas d'intérêt puisque la solution sera plein d'erreur amplifiées...?

Pas nécessairement. Il y a un compromis entre stabilité, vitesse de convergence et indice d'efficacité.
Je vais m'éloigner des systèmes linéaires pour te donner un exemple sur les systèmes non-linéaires.
La méthode de Newton est stable et converge de manière quadratique (pour une racine simple) avec 2 évaluations de fonctions à chaque itération. Son indice d'efficacité est donc de <math>sqrt{2}</maths> tandis que la méthode Regula Falsi dite de la sécante, converge plus lentement, en <math>1+sqrt{5} / 2</maths> si mes souvenirs sont bons, mais ne nécessite qu'une évaluation par itération et est donc plus rapide en théorie que la méthode de Newton.

Maintenant, si tu as une suite qui converge linéairement (par exemple Newton dans le cas d'une racine double), alors tu peux appliquer un processus appelé delta 2 d'Aitken qui permet de trouver une suite qui va converger plus rapidement... sauf que ce n'est pas stable numériquement du tout.
Il existe des petites astuces pour transformer l'écriture pour le calcul de manière à ce que cela soit stable, mais en gros, il faut faire un choix entre rapidité, stabilité, efficacité.

Citation : Hod

=> avec un algo numerique la solution n'est jamais exacte ???

Les méthodes de descentes dont le gradient, richardson et quelques autres font parties, converge vers la solution exacte en au plus n itération. Tu n'auras qu'une représentation machine, c'est à dire avec une précision limitée (10^-7 ou 10^-14 selon que tu sois en simple ou double précision) mais ça sera la solution exacte.
Maintenant, elles donnent de très bonnes approximations en dessous. Si tu peux te contenter de 10^-3 qu'elles donnent en 3 itérations par exemple, alors tu auras une solution approchée qui correspondra à tes besoins.
C'est encore une fois, une histoire de choix et de contexte.

Citation

=> je n'ai pas compris par contre ce passage. Qu'appel tu un calcul distribué ? je ne connais pas le gradient conjugué quelle est la différence avec la méthode du gradient classique ?

La méthode du gradient est plus un ensemble de méthode, que j'appelle méthode de descente de par leur représentation géométrique.
Maintenant, il y a une méthode qui s'appelle le gradient conjugué dont tu as peut-être entendu parlé, et enfin, il existe un processus d'accélération de convergence appelé le préconditionnement (SSOR, grace à la matrice d'Evans, etc).

EDIT : je parle bien de stabilité numérique et non algorithmique. La propagation des erreurs est dû en grande partie au conditionnement de ta matrice et le préconditionnement te permet justement de le faire baisser.

merci beaucoup Hod pour ces explications très intéressantes ! je vais garder ça de coté ça va bien m'aider
A+