Discussion :

[membreComplexe12]

Bonjour tous,

une question bête :
=> pourquoi utilise t on en general des methodes iteratives pour resoudre des syst. lineaire ?

car c'est methode ne sont pas sensible au probleme de conditionnement du systeme ?
=> si mon syst. est mal conditionné ma methode iterative va mettre plus longtemps à converger mais elle va quand même trouver la solution (à une tolerence pres fixée par l'utilisteur ?)

j'ai une autre question :
=> connaissant les methodes suivantes :
1) gradient conjugué
2°) gradient bi conjugué
3°) GMRESH

quelle est la différence entre ces méthodes et pourquoi sont elles beaucoup utilisée ? pouvez vous m'expliquer en 2 mots le fonctionnement de ces 3 methodes ?

merci beaucoup

[Aleph69]

Bonjour

une question bête :
=> pourquoi utilise t on en general des methodes iteratives pour resoudre des syst. lineaire ?

Il y a deux approches possibles : les méthodes itératives et les méthodes directes. En général, on utilise les méthodes directes tant que c'est possible et que ça ne coûte pas trop cher en temps de calcul. Sinon, à défaut, on utilise les méthodes itératives.

car c'est methode ne sont pas sensible au probleme de conditionnement du systeme ?
=> si mon syst. est mal conditionné ma methode iterative va mettre plus longtemps à converger mais elle va quand même trouver la solution (à une tolerence pres fixée par l'utilisteur ?)

Tout algorithme de résolution de système linéaire est sensible au conditionnement. La question c'est plutôt de quelle manière. Si le système est mal conditionné, la méthode itérative peut converger lentement ou diverger ou stagner, et l'erreur sur la solution peut être grande. En particulier, la tolérance fixée par l'utilisateur porte généralement sur la norme du résidu et par sur la norme de l'erreur sur solution, les deux quantités étant proportionnelles avec pour coefficient le conditionnement de la matrice justement. De plus, le solveur itératif peut ne pas réussir à passer en-dessous du seuil de tolérance de l'utilisateur à cause des erreurs d'arrondis qui ont été amplifiées par le conditionnement de la matrice.

j'ai une autre question :
=> connaissant les methodes suivantes :
1) gradient conjugué
2°) gradient bi conjugué
3°) GMRESH

quelle est la différence entre ces méthodes et pourquoi sont elles beaucoup utilisée ? pouvez vous m'expliquer en 2 mots le fonctionnement de ces 3 methodes ?

merci beaucoup

Le gradient conjugué (cg) s'applique aux matrices hermitiennes et on sait qu'elle converge pour les matrices hermitiennes définies positives. Pour les autres matrices hermitiennes, on préfère généralement utiliser l'algorithme minres. L'algorithme cg est basé sur le procédé d'orthogonalisation de Lanczos et de ce fait est peut coûteuse en stockage.

Pour les matrices non-hermitiennes, deux choix de procédés d'orthogonalisation sont possibles : la version non-hermitienne de la méthode de Lanczos ou la méthode d'Arnoldi. La première présente l'avantage d'être peu coûteuse en stockage, contrairement à la seconde qui nécessite de faire du redémarrage. Les gradients bi-conjugués (bicg) correspondent à Lanczos et GMRES à Arnoldi. Le principal défaut de bicg est de faire intervenir explicitement l'adjoint de la matrice; on lui préfère généralement d'autres solveurs à cause de cela, comme par exemple bicgstab, qmr ou tfqmr. D'après mes expériences, tfqmr est certainement l'un des meilleurs choix mais cela dépend bien sûr des problèmes que tu as à résoudre. GMRES a la réputation d'être plus robuste que les méthodes précédentes mais à vrai dire sans fondement. Elle souffre en particulier de problèmes de stagnation et on ne sait pas caractériser sa convergence pour les matrices non-normales (on ne sait pas non plus le faire pour les autres solveurs non-hermitiens d'ailleurs).

[membreComplexe12]

Merci beaucoup Aleph d'avoir pris le temps de repondre !!!!!!!!! tes réponses sont super intéressantes !

Il y a deux approches possibles : les méthodes itératives et les méthodes directes. En général, on utilise les méthodes directes tant que c'est possible et que ça ne coûte pas trop cher en temps de calcul. Sinon, à défaut, on utilise les méthodes itératives.

Donc si je comprends bien l'utilsation de méthode itérative ce justifie seulement par le temps de calcul ?
=> la méthode de Gauss (ou Cholesky) est plus lente que la plupart des méthodes itératives ?
=> (par hasard tu n'aurais pas un lien qui fait un comparatif de ceci en expliquant la complexité de chacun des algo ?)
=> si le temps de calcul n'est pas un problème pour nous alors ça veut dire que une méthode direct est mieux qu'une méthode itérative ?

Tout algorithme de résolution de système linéaire est sensible au conditionnement. La question c'est plutôt de quelle manière. Si le système est mal conditionné, la méthode itérative peut converger lentement ou diverger ou stagner, et l'erreur sur la solution peut être grande.

=> d'accord, je suis assez étonné je pensais que les méthodes itératives permettait de s'affranchir des problèmes de conditionnement
=> le seul avantage alors c'est la rapidité, il n'y en a pas d'autres ?
=> j'ai entendu parlé de la méthode QR pour résoudre des système linéaire. j'ai cru comprendre que cette méthode permettait de s'affranchir des problème de conditionnement, es ce bien ça ?

En particulier, la tolérance fixée par l'utilisateur porte généralement sur la norme du résidu et par sur la norme de l'erreur sur solution,

=> là je n'ai pas saisi ça ne revient pas au même ? si le résidu est nul l'erreur est nul

les deux quantités étant proportionnelles avec pour coefficient le conditionnement de la matrice justement.

=> pourrais tu me montrer ceci ?

De plus, le solveur itératif peut ne pas réussir à passer en-dessous du seuil de tolérance de l'utilisateur à cause des erreurs d'arrondis qui ont été amplifiées par le conditionnement de la matrice.

=> ça veut donc dire que dans le meilleur des cas la solution itérative sera égale à la solution direct ??
=> pour conclure avec le conditionnement, on ne peut rien faire si le systeme est mal conditionné ? notre solution sera forcement pourrie ?
la seul solution consiste à utiliser un préconditionneur ?

Le gradient conjugué (cg) s'applique aux matrices hermitiennes et on sait qu'elle converge pour les matrices hermitiennes définies positives. Pour les autres matrices hermitiennes, on préfère généralement utiliser l'algorithme minres. L'algorithme cg est basé sur le procédé d'orthogonalisation de Lanczos et de ce fait est peut coûteuse en stockage.
Pour les matrices non-hermitiennes, deux choix de procédés d'orthogonalisation sont possibles : la version non-hermitienne de la méthode de Lanczos ou la méthode d'Arnoldi. La première présente l'avantage d'être peu coûteuse en stockage, contrairement à la seconde qui nécessite de faire du redémarrage. Les gradients bi-conjugués (bicg) correspondent à Lanczos et GMRES à Arnoldi. Le principal défaut de bicg est de faire intervenir explicitement l'adjoint de la matrice; on lui préfère généralement d'autres solveurs à cause de cela, comme par exemple bicgstab, qmr ou tfqmr. D'après mes expériences, tfqmr est certainement l'un des meilleurs choix mais cela dépend bien sûr des problèmes que tu as à résoudre. GMRES a la réputation d'être plus robuste que les méthodes précédentes mais à vrai dire sans fondement. Elle souffre en particulier de problèmes de stagnation et on ne sait pas caractériser sa convergence pour les matrices non-normales (on ne sait pas non plus le faire pour les autres solveurs non-hermitiens d'ailleurs).

d'accord, merci beaucoup pour ces explications !
=> tu n'aurais pas un cours la dessus ou un lien intéressant qui explique un peu les différences (avec les démonstrations...) ?

[Aleph69]

Merci beaucoup Aleph d'avoir pris le temps de repondre !!!!!!!!! tes réponses sont super intéressantes !

Merci! Je suis content si cela t'aide!

Donc si je comprends bien l'utilisation de méthode itérative ce justifie seulement par le temps de calcul ?

Pas seulement. Si la matrice n'est pas inversible, tu auras beaucoup de mal à la factoriser avec précision. Les problèmes de convergence des méthodes itératives apparaissent surtout pour les matrices indéfinies et les matrices non-normales. Dans ces cas, si tu peux utiliser une méthode directe, c'est plus sûr. Il y a aussi des problèmes de convergence avec les matrices mal conditionnées mais on sait les contourner avec des préconditionneurs.

=> la méthode de Gauss (ou Cholesky) est plus lente que la plupart des méthodes itératives ?

Très grossièrement, pour un système carré de taille n, n suffisamment grand :
1. les méthodes directes nécessitent O(n^3) opérations;
2. les méthodes itératives nécessitent O(mn^2) opérations pour m itérations.
Le point 2 est facile à comprendre : par itération, l'opération la plus chère est le produit matrice-vecteur qui est en O(n^2).

=> (par hasard tu n'aurais pas un lien qui fait un comparatif de ceci en expliquant la complexité de chacun des algo ?)

je te donne une biblio à la fin de ce message

=> si le temps de calcul n'est pas un problème pour nous alors ça veut dire que une méthode direct est mieux qu'une méthode itérative ?

Le temps de calcul est toujours un problème!
On cherche toujours un compromis entre rapidité de calcul, coût de stockage et précision. Grossièrement, tu peux garder en tête que le produit de ces trois quantités est constant : quand l'un diminue, un autre augmente et réciproquement (ce n'est pas un théorème, c'est juste un principe grossier). Autrement dit, ce que tu gagnes quelque part, tu le perds ailleurs.

=> d'accord, je suis assez étonné je pensais que les méthodes itératives permettait de s'affranchir des problèmes de conditionnement

En fait, c'est le contraire : les méthodes itératives sont plus sensibles au conditionnement que les méthodes directes. Mais, de toute façon, l'erreur sur la solution est bornée par un terme dépensant du conditionnement quel que soit l'algorithme de résolution employé.

=> le seul avantage alors c'est la rapidité, il n'y en a pas d'autres ?

Non. Le premier critère de choix d'un solveur est la régularité de la matrice. Si elle n'est pas inversible, alors il faut une méthode itérative. Sinon, on peut utiliser une méthode directe ou itérative. Si la taille du système est trop grande pour pouvoir utiliser une méthode directe, alors on utilise une méthode itérative. Si la taille est suffisamment petite, alors on utilise une méthode directe. Définir ce qui est suffisamment grand ou petit dépend de ton problème et ton expérience. Cela varie. En particulier, c'est assez difficile à définir pour les matrices creuses.

=> j'ai entendu parlé de la méthode QR pour résoudre des système linéaire. j'ai cru comprendre que cette méthode permettait de s'affranchir des problème de conditionnement, es ce bien ça ?

On peut effectivement utiliser la méthode QR (Householder, Givens) mais on préfère LU en pratique (Cholesky, Gauss) car cela nécessite moins d'opérations. Comme je te l'ai dit, tu ne t'affranchiras jamais du problème de conditionnement car il ne dépend pas du choix de l'algorithme.

=> là je n'ai pas saisi ça ne revient pas au même ? si le résidu est nul l'erreur est nul

Uniquement si la matrice est inversible. Mais il faut raisonner avec un seuil. Si le résidu est inférieur à un seuil s, cela n'implique pas que l'erreur est inférieure à s.

=> pourrais tu me montrer ceci ?

Soit un système Ax=b inversible, une vectorielle ||.|| et une norme matricielle subordonnée à ||.||, également notée ||.||. Soit y la solution calculée. Le résidu calculé est r=b-Ay et l'erreur est e=x-y. On note Z l'inverse de A. On a

e=Z(Ax-Ay)=Z(b-Ay)=Zr(

Avec les normes, on obtient

Ax=b => ||x|| >= ||b||/||A||
||e|| <= ||Z||*||r||

Par conséquent, on a

||e||/||x|| <= ||A||*||Z||*||r||/||b||.

En d'autres termes, l'erreur relative sur la solution est majorée par le produit du conditionnement de A et de la norme relative de r. Ainsi, dans le cas d'une méthode itérative avec un seuil s choisi par l'utilisateur, on impose généralement ||r||<=s*||b||. Cela implique

||e||/||x|| <= ||A||*||Z||*s.

En d'autres termes, l'erreur relative sur la solution n'est pas bornée par s mais par le produit du conditionnement de A et de s. Plus A est mal conditionnée, plus cette borne est grande.

=> ça veut donc dire que dans le meilleur des cas la solution itérative sera égale à la solution direct ??

Non, ça veut juste dire qu'il n'y a pas convergence au sens du critère d'arrêt de l'utilisateur.

=> pour conclure avec le conditionnement, on ne peut rien faire si le systeme est mal conditionné ? notre solution sera forcement pourrie ?
la seul solution consiste à utiliser un préconditionneur ?

La matrice peut être mal conditionnée et l'erreur sur la solution très petite. On a juste une borne supérieure sur l'erreur, rien de plus. L'idée est de faire en sorte que cette borne soit la plus petite possible pour assurer de calculer une solution la plus précise possible. La solution consiste à utiliser un préconditionneur pour que ||A||*||Z|| soit le plus petit possible, et un algorithme le plus stable (backward stable) possible pour que ||r||/||b|| soit aussi petit que possible.

=> tu n'aurais pas un cours la dessus ou un lien intéressant qui explique un peu les différences (avec les démonstrations...) ?

Sur les méthodes itératives, la référence en la matière est de très loin le livre (gratuit!) de Youssef Saad. Ce livre, également gratuit, est aussi très bien.

Sur les méthodes directes et la stabilité numérique en général, je ne peux que te conseiller son excellent livre qui n'a pas d'équivalent, si ce n'est peut-être le livre de Wilkinson qui est une référence historique en analyse numérique mais que je déconseille fortement en première lecture.

Quelques articles de référence : Cholesky, Gauss, sur les systèmes linéaires, une thèse intéressante sur les méthodes de Krylov, et enfin un résultat fondamental concernant GMRES.

Mon conseil : commence par lire le livre de Saad et amuse-toi à coder les algorithmes sous matlab et à les comparer sur des systèmes linéaires, par exemple ceux du MatrixMarket. Ensuite, tu pourras lire le livre ou les articles d'Higham sur Cholesky, Gauss et les systèmes linéaires. C'est un peu plus ardu mais ça vaut vraiment la peine d'y consacrer du temps car tu comprendras ensuite beaucoup de choses à l'algorithmique numérique en général. Pour le reste, à toi de voir le temps que tu comptes consacrer à ce sujet, ce ne sont que des indications sur des résultats à ne pas rater ou des documents sur lesquels on ne tombe pas forcément et qui sont pourtant bien supérieurs à la moyenne en qualité de contenu.

[membreComplexe12]

Magnifique! Merci beaucoup!!!

Juste deux derniere questions a propos des methode directes :
1) qd utilise t on QR ? Je ne l'ai jamais vu utilisee... Il n'y a pas d'avantages?
2) en pratique comment calcul t on un conditionnement? (Ds le cas d'une matrice symetrique c la plus grande valeure propre mais le cas generale on utilise quoi comme algo?)

[Aleph69]

1) qd utilise t on QR ? Je ne l'ai jamais vu utilisee... Il n'y a pas d'avantages?

On l'utilise pour la résolution des systèmes linéaires rectangulaires (moindres carrés) et des problèmes aux valeurs propres. Parmi les avantages de QR, on peut citer le fait qu'elle s'applique aux matrices non-carrées et qu'on connaît des algorithmes numériquement stables pour la calculer (Givens, Householder).

2) en pratique comment calcul t on un conditionnement? (Ds le cas d'une matrice symetrique c la plus grande valeure propre mais le cas generale on utilise quoi comme algo?)

Ce que tu écris entre parenthèses n'est pas vrai. A mon avis, tu penses à un résultat concernant le conditionnement en norme 2 d'une matrice symétrique qui est égal au rapport entre la plus grande valeur propre et la plus petite valeur propre. Plus généralement, il faut d'abord choisir une norme, puis une mesure de l'erreur rétrograde, ce qui définit un nombre de conditionnement. Ensuite, la manière dont on calcule le conditionnement varie en fonction de la définition. Pour la définition "classique", la seule difficulté est d'estimer la norme de l'inverse de la matrice. L'approche standard est décrite dans cet article.

[membreComplexe12]

merci enormement pour tout !!!

[soft001]

Je suis vraiment très impressionné par les réponses de Aleph69 et j'ai voté pertinent pour tous tes messages