Les modèles de résolution des systèmes d’équations linéaires

Méthode des sous espaces de krylov et ses variantes

Les méthodes itératives de type de krylov sont employées depuis une vingtaine d’années. En 1952, la méthode de krylov a commencé à apparaitre dans les travaux de Lanczos, Hestenes et Stiefel qui introduisent indépendamment la méthode de Gradient Conjugué(G.C) [7, 10, 16] pour les systèmes symétriques et définis positifs. Après une dizaine d’années, on trouve des extensions de la méthode de (G.C) aux systèmes de grande taille telles que la méthode de Bi-conjugate Gradient (BICG) [10, 24] développé par Fletcher en 1974 et les méthodes Minimum Residual(MINRES) [10, 24] et Symetric LQ (SYMMLQ) [10] introduites par Paige et Saunders en 1975. Le traitement des systèmes non symétriques a donné lieu aux méthodes ORTHOMIN [22] en 1976 introduit par Vinsome, ORTHODIR [22]en 1980 introduit par Jea et Young, GCR(Generalized Congugate Residual) [22, 11, 24] en 1983 développé par Eisenstat, Elman et Schultz et CGS( Generalized Congugate Squared) [10, 24] en 1984 par Sonneveld. Des nouvelles méthodes intéressantes ont été proposées durant les années 80 et au début des années 90, la méthode de GMRES ( Generalized Minimum Residual) [11, 10, 7, 24] est développée en 1986 par Saad et Schultz, QMR ( Quasi Minimum Residual) [24] est introduite en 1990 par Freund et Nachtigal, et en 1992 Van der Vorst a proposé la méthode BICGSTAB [10] (Bi-conjugate Gradient Stabilized).[11, p18]. Dans ce chapitre, nous nous limiterons à l’étude de deux méthodes, la méthode de GCR(Generalized Conjugate Residual) pour des systèmes généraux et la méthode du Gradient Conjugué pour des systèmes à matrice définie positive.Donnons tout d’abord le cadre général d’une méthode de krylov. Les méthodes de krylov consistent à construire une suite de sous espaces emboités de taille croissante qui vont contenir à la limite la solution recherchée .Elles sont basées sur une technique de projection sur un sous espace de krylov de dimension (m n) plus petite que la taille du problème. En remplaçant dans l’équation (1.5) la matrice M par la matrice identité I, nous retrouvons la récurrence de Richardson[11, p17].

L’algorithme de GC

L’algorithme ci-dessus donne l’explication la plus simple de la méthode du gradient conjugué. Cependant, il nécessite le stockage de toutes les directions précédentes recherchées et les vecteurs des résidus, ainsi que de nombreuses multiplications vecteur de la matrice, et donc peut être couteuse en ressources informatiques. Dans le pratique, on modifie légèrement la condition d’obtention du vecteur dernier résidu, ne pas minimiser la métrique suivant la direction de la recherche, mais au lieu d’en faire orthogonale au résidu précédent. Minimisation de la métrique le long de la direction de la recherche sera obtenue automatiquement dans ce cas. On peut alors obtenir un algorithme qui ne nécessite que le stockage des deux derniers vecteurs de résidus et la direction dernière recherchée, et un seul vecteur de multiplication matricielle. Noter que l’algorithme décrit ci-après correspond à la procédure précédemment simple [16, p197]. L’algorithme est détaillé ci-dessous pour résoudre Ax = b. Le vecteur d’entrée x0 peut être une solution approchée initiale ou 0.

Factorisation LU incomplète et Factorisation de Cholesky incomplète

Les méthodes de factorisations incomplètes ont été introduites vers 1960 séparément par Buleev et Varga [12, p19]. L’existence théorique des factorisations incomplètes peut être vérifiée pour certaines classes de matrices mais pour des matrices quelconques, les factorisations incomplètes peuvent échouer. Le principe d’une factorisation incomplète (ILU) est de limiter en cours de factorisation le remplissage des facteurs en ignorant une partie des coefficients des facteurs. Une telle factorisation peut être utilisée comme un préconditionneur d’une méthode itérative, sous la forme M = LU, où L et U sont les facteurs approchés d’une factorisation de A. Le but est d’obtenir une bonne approximation de A, au moindre cout en temps et en mémoire [12, p19]. Une factorisation est dit incomplète si pendant que le processus de factorisation progresse, certains éléments de remplissage sont ignorés. Pour certaines applications ou certains algorithmes itératifs, il est intéressant d’utiliser cet algorithme pour chercher une matrice triangulaire inférieure creuse L à diagonale unité et une matrice triangulaire supérieure creuse U telles que la matrice R = LU + A vérifie certaines contraintes, par exemple, LU soit aussi proche de A en imposant que R soit petit [14, p23], ou bien en imposant la contrainte sur les positions des éléments non nuls de R qui doivent appartenir à une configuration donnée. Plusieurs algorithmes de factorisation incomplète pour calculer les facteurs L et U sont connus et largement utilisés, notamment ILU (0), ILU (k), ILUT [12, p26].

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Table des figures
Remerciements
Dédicace
Introduction
1 Les méthodes de relaxations
1.1 Généralités
1.1.1 Critère de convergence
1.1.2 Test d’arrêt d’algorithme
1.1.3 Méthode de décomposition ou » Spliting »
1.2 Les méthodes de Jacobi, de Gauss-Seidel et de relaxation
1.2.1 Méthodes de Jacobi et de sur-relaxation
1.2.2 Méthodes de Gauss Seidel et de sur-relaxation successive
1.2.3 Convergence
1.2.4 Taux de convergence d’une méthode itérative
2 Les méthodes de projection
2.1 Méthodes de projection. Approche géométrique
2.1.2 Méthodes de projection pour systèmes symétriques
2.1.2.1 Généralités
2.1.2.2 Construction géométrique du processus
2.2 Méthodes de projection. Approche algébrique
2.2.1 Généralités
2.2.1.1 Les projections
2.2.2 Méthode de projection
2.2.2.1 Projection orthogonale
2.2.2.2 Projection oblique
2.3 Méthode des sous espaces de krylov et ses variantes
2.3.1 Méthode de gradient conjugué
2.3.1.1 Description de la méthode
2.3.1.2 Convergence de GC
2.3.2 La méthode de GCR
2.3.2.1 Description de la méthode
2.3.2.2 La convergence de GCR
Conclusion
3 Préconditionement des systèmes linéaires
3.1 Principe général
3.2 Quelques préconditionneurs classiques
4 Applications aux systèmes à matrices creuses
4.1 Matrices creuses
4.1.1 Représentation des matrices creuses
4.2 Matrices symétriques définies positives
4.2.1 Complément de Schur
4.2.2 Caractérisation des matrices symétriques définies positives par le complément de Schur
Conclusion
Bibliographie