Discussion :

[membreComplexe12]

Bonjour tous,

en lisant à droite et à gauche j'ai cru comprendre que l'algorithme du gradient conjugué et le plus performant pour résoudre des systèmes linéaire, es ce que je me trompe ?

j'ai regardé sur le net et je n'ai pas vraiment trouvé de cours ou autre document qui font un comparatif des solveurs linéaire :
- connaissez vous un lien qui donne un comparatif de la vitesse de convergence (où de la complexité) des algo les plus classiques car je ne sais pas pourquoi utiliser l'un plutôt que l'autre....

Ma deuxième question porte sur l'algorithme de resolution de système tridiagonal de Thomas. Il a une complexité en O(n) ce qui est super faible donc si on un système tridiagonal on ne peut pas faire plus rapide que ceci ?

Si on a un système tridiagonal es ce qu'il y a un intérêt à utiliser autre chose que cette algo ? Es ce que le gradient conjugué et plus rapide ?

merci pour les réponses que vous pourrez m'apportez

[Aleph69]

Bonjour,

en lisant à droite et à gauche j'ai cru comprendre que l'algorithme du gradient conjugué et le plus performant pour résoudre des systèmes linéaire, es ce que je me trompe ?

Oui, mais qu'est-ce que tu entends par là?

- connaissez vous un lien qui donne un comparatif de la vitesse de convergence (où de la complexité) des algo les plus classiques car je ne sais pas pourquoi utiliser l'un plutôt que l'autre....

Personne ne le sait!

Ma deuxième question porte sur l'algorithme de resolution de système tridiagonal de Thomas. Il a une complexité en O(n) ce qui est super faible donc si on un système tridiagonal on ne peut pas faire plus rapide que ceci ?

Si, en ajoutant des hypothèses supplémentaires sur le système par exemple.

Si on a un système tridiagonal es ce qu'il y a un intérêt à utiliser autre chose que cette algo ?

Oui, à cause de la réponse précédente.

Es ce que le gradient conjugué et plus rapide ?

Aucune chance car les gradients conjugués sont basés sur une tridiagonalisation (Lanczos) et une factorisation LU (~Thomas).

[membreComplexe12]

Bonjour Aleph69 et merci de ton aide

Oui, mais qu'est-ce que tu entends par là

en fait je parle en terme de rapidité (car la precision sera fixée par la tolérance que l'on fixe). J'ai cru comprendre que le conditionnement peut faire que l'algo converge lentement mais si on utilise un préconditionneur alors on aura plus de problèmes et on aura toujours une vitesse de résolution très rapide donc ?

connais tu un algo plus rapide que le gradient conjugué ? j'ai entendu vaguement parlé de GMRES mais je ne connais pas du tout...

Personne ne le sait!

ouahou, c'est dingue ça ....
ça veut dire personne ne connais la complexité de la majorité des solveur linéaire ? pourtant j'ai fouillé sur le net et il semblerait que le gradient conjugué soit en "O(n.log(n))" pour les autres algo on ne sait pas ?

Si, en ajoutant des hypothèses supplémentaires sur le système par exemple.

je ne vois pas ce que tu veux dire....

Aucune chance car les gradients conjugués sont basés sur une tridiagonalisation (Lanczos) et une factorisation LU (~Thomas).

OK, je comprends merci.

[Aleph69]

la precision sera fixée par la tolérance que l'on fixe.

Par le produit de la tolérance et du conditionnement!

J'ai cru comprendre que le conditionnement peut faire que l'algo converge lentement mais si on utilise un préconditionneur alors on aura plus de problèmes et on aura toujours une vitesse de résolution très rapide donc ?

Tu confonds vitesse de converge et vitesse de résolution. Résoudre Ax=b avec un solveur itératif et l'inverse de A pour préconditionneur conduit à un algorithme qui converge en moins d'une itération mais dont le calcul du préconditionneur peut coûter très cher.

connais tu un algo plus rapide que le gradient conjugué ? j'ai entendu vaguement parlé de GMRES mais je ne connais pas du tout...

Les gradients conjugués s'appliquent aux matrices hermitiennes et on sait qu'ils convergent lorsqu'elles sont définies positives. Ainsi, ils peuvent ne pas converger pour les matrices hermitiennes indéfinies. Pour ces dernières, il existe des solveurs itératifs qui peuvent être plus performants que les gradients conjugués. C'est typiquement le cas de MinRes qui est une version hermitienne de GMRes. Mais, même dans le cas des matrices hermitiennes définies positives, il existe des algorithmes pouvant dépasser les gradients conjugués en performances : c'est par exemple le cas de l'algorithme de Cholesky. De manière générale, il n'existe pas de solveur qui soit absolument plus performant que les autres. Cela se démontre. On appelle cela les théorème "no free lunch".

ça veut dire personne ne connais la complexité de la majorité des solveur linéaire ? pourtant j'ai fouillé sur le net et il semblerait que le gradient conjugué soit en "O(n.log(n))" pour les autres algo on ne sait pas ?

Je suis curieux de connaître la source qui donne la complexité des gradients conjugués en O(n.log(n)). De manière générale, les solveurs itératifs se comportent grossièrement en O(mn²) où m est le nombre d'itérations. Le problème est que ce dernièrement dépend des données du problème. La seule chose dont on est sûr, c'est que m est inférieur ou égal à n : dans le pire cas, on est en O(n^3). Ce qui importe c'est le taux de convergence. Dans le cas des gradients conjugués, il dépend des valeurs propres de la matrice. Dans le cas de GMRES, on ne sait rien dire dessus quand la matrice est non-normale.

je ne vois pas ce que tu veux dire....

Une matrice tridiagonale peut être diagonale, bidiagonale, symétrique, etc. Pour chaque cas, on peut simplifier telle ou telle méthode.

[membreComplexe12]

merci, j'ai tout compris à présent.

sauf ceci :

Par le produit de la tolérance et du conditionnement!

c'est surement trivial mais je ne vois pas trop pourquoi....

le résidu est défini par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

{R}=[A]{x}-{b}

si je prends un "x" quelconque et que j'effectue cette opération j'obient un "R".
Si je vois que toutes les composantes de ce "R" sont < 1e-9 alors ça veut dire que ma précision est de 1e-9 .... car je n'ai pas de conditionnement qui intervient puisque je ne résous pas de système linéaire pour faire cette vérification ??


Une question générale :
tu as l'air d'avoir un très niveau sur ce genre de choses, aurais tu un livre à me conseiller où l'on trouve toutes ces choses (et plus..) détaillé de façon clair ?

[Aleph69]

le résidu est défini par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

{R}=[A]{x}-{b}

si je prends un "x" quelconque et que j'effectue cette opération j'obient un "R".
Si je vois que toutes les composantes de ce "R" sont < 1e-9 alors ça veut dire que ma précision est de 1e-9 .... car je n'ai pas de conditionnement qui intervient puisque je ne résous pas de système linéaire pour faire cette vérification ??

On a Ax=b. On note cond(A)=||A||*||A^{-1}|| le conditionnement de A, y la solution calculée, e=x-y l'erreur et r=Ae=b-Ay le résidu. Alors ||x||>=||b||/||A|| et ||e||<=||A^{-1}||*||r||. Par conséquent,

||e||/||x||<=cond(A)*||r||/||b||,

c'est-à-dire que l'erreur relative sur la solution est majorée par le produit du conditionnement de A et la norme relative du résidu calculé.

aurais tu un livre à me conseiller où l'on trouve toutes ces choses (et plus..) détaillé de façon clair ?

1. Iterative methods for sparse linear systems, Youssef Saad (téléchargeable gratuitement).

2. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, Collectif (téléchargeable gratuitement)

3. Computer Solution of Large Linear Systems, Gérard Meurant.

4. Matrix Computation, Golub et Von Loan.

5. Accuracy and stability of numerical algorithms, Higham.

Commentaires : les 1. et 2. ont l'intérêt d'être gratuits mais ne traitent pas en profondeur des solveurs directs. Concernant les solveurs itératifs, c'est très complet. Le 3. traite des solveurs directs et itératifs et de plein d'autres choses. Il est orienté recherche. Le 4. est une référence en analyse numérique : il y a une nouvelle qui vient ou va sortir. Le 5. traite les questions de stabilité numérique (conditionnement, backward error) pour plein d'algorithmes dont les solveurs directs et les solveurs itératifs stationnaires (jacobi, gauss-seidel, etc). Avec ça, tu as tout ce qu'il faut!

[membreComplexe12]

merci j'ai tout compris à présent.

et merci beaucoup pour les références