Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

A propos gradient conjugué


Sujet :

Mathématiques

  1. #1
    Membre éclairé
    A propos gradient conjugué
    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

  2. #2
    Membre expérimenté
    Bonjour,

    Citation Envoyé par membreComplexe12 Voir le message
    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à?

    Citation Envoyé par membreComplexe12 Voir le message

    - 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!

    Citation Envoyé par membreComplexe12 Voir le message

    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.

    Citation Envoyé par membreComplexe12 Voir le message

    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.

    Citation Envoyé par membreComplexe12 Voir le message

    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).

  3. #3
    Membre éclairé
    Bonjour Aleph69 et merci de ton aide
    Citation Envoyé par Aleph69 Voir le message
    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...
    Citation Envoyé par Aleph69 Voir le message
    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 ?
    Citation Envoyé par Aleph69 Voir le message
    Si, en ajoutant des hypothèses supplémentaires sur le système par exemple.
    je ne vois pas ce que tu veux dire....
    Citation Envoyé par Aleph69 Voir le message
    Aucune chance car les gradients conjugués sont basés sur une tridiagonalisation (Lanczos) et une factorisation LU (~Thomas).
    OK, je comprends merci.

  4. #4
    Membre expérimenté
    Citation Envoyé par membreComplexe12 Voir le message
    la precision sera fixée par la tolérance que l'on fixe.
    Par le produit de la tolérance et du conditionnement!

    Citation Envoyé par membreComplexe12 Voir le message

    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.

    Citation Envoyé par membreComplexe12 Voir le message

    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".

    Citation Envoyé par membreComplexe12 Voir le message

    ç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.

    Citation Envoyé par membreComplexe12 Voir le message

    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.

  5. #5
    Membre éclairé
    merci, j'ai tout compris à présent.

    sauf ceci :
    Citation Envoyé par Aleph69 Voir le message
    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 ?

  6. #6
    Membre expérimenté
    Citation Envoyé par membreComplexe12 Voir le message
    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é.

    Citation Envoyé par membreComplexe12 Voir le message
    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!

  7. #7
    Membre éclairé
    merci j'ai tout compris à présent.

    et merci beaucoup pour les références

###raw>template_hook.ano_emploi###