La méthode multigrille pour la résolution des EDP

INTRODUCTION

La méthode multigrille a été conçue au milieu des années 60. C’est seulement au milieu des années 70 qu’elle a commencé à être mise en œuvre de façon plus efficace .
A l’origine, elle ne s’appliquait qu’à la résolution des systèmes linéaires de type :
A u = b (1.1) provenant de la discrétisation d’équations aux dérivées partielles modélisant des phénomènes physiques sur des domaines bornés.
Il est bien connu que les méthodes itératives classiques pour la résolution des systèmes de type (1.1) convergent très lentement et on fait souvent recours aux méthodes multigrilles pour accélérer la convergence. Les méthodes multigrilles sont basées sur l’idée que les méthodes de relaxation sont rapides pour les composantes d’erreurs oscillatoires, mais convergent lentement pour les composantes lisses. Ainsi, après un certain nombre de relaxation, on calcule un résidu qui est lisse. On projette ensuite ce résidu sur une grille grossière. A ce niveau, on forme une équation résiduelle dont la solution est la correction d’erreur grille grossière. On interpole ensuite cette solution de la grille grossière sur la grille fine et on l’ajoute à la solution approchée. On note l’utilisation d’un opérateur de restriction grille fine – grille grossière et un opérateur d’interpolation grille grossière – grille fine. La méthode décrite ci-dessus est la méthode bi-grille. Il est à noter que l’équation résiduelle de la grille grossière peut avoir la même structure que le problème originale sur la grille fine. La méthode multigrille est l’utilisation récursive de la méthode bi grille. Ce processus qui commence sur la grille la plus fine peut aller jusqu’à la grille la plus grossière ou un lisseur direct est utilisé pour obtenir la solution. Les solutions sont interpolées de grille en grille jusqu’à ce que la grille la plus fine soit utilisée pour corriger la solution approchée. Cette procédure est appelée V-cycle. Dans l’algorithme multigrille V(v1, v2) – cycle, on réalise v1 fois la relaxation sur une grille fine donnée avant d’aller sur une grille grossière v2 fois de relaxation après ajout de la correction. Il ressort de cette description que l’efficacité des méthodes multigrilles dépend de deux facteurs. Le premier est sur la qualité de la méthode de relaxation [1, 2, 3, 13] et le second est sur la qualité de la correction grille grossière. On pourra noter que là aussi, deux voies se présentent :
La première est portée sur le choix des opérateurs de transfert intergrilles, et la deuxième consiste à multiplier par un facteur approprié le résidu de la grille fine avant sa restriction sur la grille grossière ou après l’étape de correction. C’est la technique de paramétrisation résiduelle.

METHODE MULTIGRILLE

Idée générale

Dans la méthode utilisant deux grilles, on a vu qu’il fallait réaliser les opérations suivantes au cours d’un cycle :
– effectuer quelques itérations d’un lisseur itératif sur la grille fine de pas h .
– calculer le résidu sur la grille fine.
– restreindre ce résidu sur la grille grossière de pas H = 2h.
– résoudre le système d’équations aux différences finies sur la grille grossière pour obtenir une approximation de la correction.
– Interpoler cette correction sur la grille fine pour corriger la solution approchée que l’on avait obtenue sur la grille fine.
A la fin de la dernière étape si le résidu sur la grille fine est trop grand, on recommence un autre cycle.
A la quatrième étape, pour résoudre (avec une approximation suffisante) le système d’équations sur la grille grossière H = 2h, on peut de nouveau utiliser la méthode à deux grilles, en définissant un problème sur une grille plus grossière de pas 2H.
Par conséquent la méthode multigrille est l’application récursive de la méthode à deux grilles. On utilise une méthode directe voir [4] pour résoudre le système sur la grille la plus grossière ne contenant plus que quelques points.
Ce processus récursif permet en réalité d’approcher la solution exacte Uh sur la grille fine, par le calcul de corrections approchées sur des grilles plus grossières et sa performance dépend essentiellement de la méthode itérative utilisée.

Méthodes itératives

On se propose de résoudre numériquement le système linéaire (1-1). Lorsque la matrice A est inversible, on peut utiliser une méthode directe de résolution qui consiste à écrire que la solution u est égale à A-1 .b. Un problème peut intervenir lors du calcul sur ordinateur de l’inverse de la matrice A est lié à l’inexactitude de A-1 du fait de son état de matrice creuse lorsqu’il s’agit d’un problème de grande taille. On dit que la matrice est mal conditionnée [4]. Il convient alors de développer des méthodes itératives qui proposent de générer à partir d’un vecteur initial uo , une suite (uk)k≥1 telle que : k→+∞ lim uk = u, u étant solution de (1.1). Les méthodes itératives classiques utilisent des schémas de la forme :

Stratégies de passage intergrilles

Dans la méthode multigrille, les changements de grille se font en deux circonstances :
(a) Quand on restreint le résidu d’une grille fine sur une grille plus grossière pour définir le second membre du problème dont la solution est une approximation de la correction à apporter.
(b) Quand on interpole la correction approchée d’une grille grossière à une grille plus fine.
Mais quand doit-on changer de grille ?
Plusieurs stratégies sont possibles. Dans la première, le nombre d’itérations du lisseur sur chaque niveau de grille et l’ordre dans lequel elles sont faites, sont fixés à l’avance. Une autre stratégie consiste à changer le niveau en fonction de valeur du résidu et la rapidité de décroissante de résidu. Tant que le résidu est à peu près divisé par deux d’une itération du lisseur à l’autre, on continue ces itérations . Lorsque cette décroissance se ralentit, on décide de descendre à la grille plus grossière. On poursuit ce processus sur chaque grille jusqu’à ce que le résidu soit suffisamment petit, auquel cas on admet avoir résolu, avec une précision suffisante le problème sur ce niveau de grille et on peut donc remonter pour apporter la correction au niveau de la grille immédiatement supérieur.

Cycles multigrilles

L’existence des cycles est due au fait que les phases de remontée et de descente observées dans une résolution multigrille se font rarement de façon linéaire. Un cycle multigrille peut-être défini comme étant l’ensemble de toutes les étapes parcourues jusqu’à l’apport de la correction à la solution laissée en instance sur la grille la plus fine. Pour construire un cycle multigrille, on considère la suite de pas de discrétisation h1 > h2 > …. > hk > … > hng tel que hk+1 = hk/2 . On notera par la suite Ωk = k Ωh , Ak = k Ah , bk = k bh . Il existe différents types de cycles parmi lesquels :

Le schéma multigrille totale (F.M.G)

Connue sous le nom de multigrille totale, la procédure (F.M.G.) consiste à démarrer un processus multi grille non pas avec une solution quelconque, mais à partir d’une solution issue d’un maillage plus grossier.
Cette solution suffisamment proche de la solution recherchée est interpolée sur la grille fine avant l’application d’un processus multigrille.
Un processus (F.M.G) permet de réduire encore d’avantage le nombre d’opération nécessaire à l’obtention de la solution recherchée puisque ce nombre est o(N) où N est le nombre de nœuds de la grille fine, et peut-être représentée par un schéma de la figure 3.
On part de la grille la plus grossière, la solution obtenue sur celle-ci est transférée sur la grille immédiatement plus fine par l’intermédiaire d’un opérateur de prolongement.
Sur cette nouvelle grille, on résout partiellement par quelques cycles multigrilles le système linéaire correspondant puis on interpole de nouveau sur une grille immédiatement plus fine.

L’algorithme multigrille totale (Full multigrid Algorithm)

C’est une application du kième niveau d’itération au système linéaire de ce niveau. Comme nous le savons, son but est d’obtenir, pour débiter le procédé itératif, une solution initiale la plus proche de la solution sur le niveau fin.
On part d’une solution k k-1 I uk−1  , où uk−1
 est la solution approchée du système linaire sur Gk-1