- Docente: Martin Jakob Gander
- Docente: Joerg Nick
Semestre d'été: 2 h de cours + 1 h d'exercices
Objectifs:
L'arrivée des ordinateurs a changé fondamentalement notre façon de résoudre des problèmes. D'un point de vue mathématique, il existe des problèmes triviaux, par exemple la résolution d'un système linéaire, qu'on réussit sans difficulté par une élimination de Gauss en un nombre fini d'opérations, et des problèmes insolvables, par exemple la détermination des valeurs propres d'une matrice, car pour une matrice de taille plus que 4 fois 4, la détermination analytique des racines du polynôme caractéristique n'est plus possible.
Tout change si on a accès a un ordinateur: le calcul des valeurs propres d'une matrice devient aussi simple (avec la même complexité en nombre d'opérations) que la résolution du système associé avec la matrice. L'idée fondamentale qui permet cet anéantissement de difficulté mathématique est d'utiliser des méthodes itératives, qui calculent des approximations de plus en plus précises de la solution désirée. Ces méthodes ne trouvent jamais la solution exacte, mais d'excellentes approximation avec une efficacité extraordinaire.
Aujourd'hui, nous sommes arrivés a un point où il peut s'avérer plus avantageux d'utiliser une méthode itérative, même si un algorithme direct existe. Ceci est le cas pour la résolution de systèmes linéaires a grande taille: même si en théorie il est possible de les résoudre en utilisant une élimination de Gauss, les méthodes itératives sont beaucoup plus efficaces.
Ce cours est une introduction aux méthodes itératives pour les systèmes linéaires, un grand domaine de recherches actuel.
J'expliquerai comment les méthodes itératives modernes calculent rapidement des approximations à haute precision et ainsi dépassent largement l'algorithme classique qui trouve la solution exacte en un nombre fini d'opérations.
Contenu (prévu):
1. Les méthodes itératives stationnaires: Jacobi, Gauss-Seidel, SOR.
Convergence et étude du paramètre optimal.
2. Les méthodes itératives de type Krylov: espace de Krylov, meilleure
approximation, la méthode du gradient conjugué et
GMRES. Estimations de convergence.
3. Preconditionnement matriciel: par des méthodes itératives
stationnaires, et par des factorisations approchées du type ILU.
4. Preconditionnement physique: les méthodes multi-grille et
décomposition de domaine.
Pré-requis: cours d'analyse et d'algèbre, un premier cours d'analyse
numérique.
Evaluation: examen oral et série d'exercices