6.11 Méthode multigrille

6.11.1 principe

On considère le problème de Poisson monodimensionnel avec des conditions aux limites de Dirichlet homogènes:

$$-\frac{d^{2}u}{dx^{2}}=f \mbox{\mbox{}{sur }} \Omega=]0,1[ { avec } u(0)=u(1)=0$$ (6.1)

Pour exposer le plus simplement possible le principe de la méthode multigrille , on commence par présenter la méthode 2-Grilles ; cette dernière combine deux méthodes peu performantes pour finalement obtenir une méthode très efficace. On considère une grille fine de pas h et une grille grossière de pas H = 2h pour résoudre le problème (6.1)

Un cycle de la méthode 2-Grilles se compose de deux phases :

• une méthode de lissage , correspondant à deux ou trois itérations d'une méthode de relaxation (GaussSeidel, Jacobi), permettant de réduire les hautes fréquences de l'erreur lorsque l'on décompose celle-ci dans la base des vecteurs propres de la matrice ; soit $u_{h}$ l'approximation de $U=U_{h}$ solution du système linéaire discret $A U_{h}=F_{h}$
• une méthode de correction sur grille grossière qui traite efficacement les basses fréquences de l'erreur . La correction $V_{h}=U_{h}-u_{h}$ , qu'il faut ajouter à $u_{h}$ (approximation) pour obtenir $U_{h}$ (solution exacte), doit vérifier :

$$A V_{h}=r_{h} \mbox{}{avec } r_{h}=F_{h}-A u_{h}$$

$V_{h}$ est donc la solution d'un problème du même type que celui qui définit $U_{h}$, où le second membre $F_{h}$ a été remplacé par le résidu $r_{h}$ aux points de la grille fine. Le calcul de $V_{h}$ est a priori aussi coûteux que celui de $U_{h}$ . Dans la mesure où l'erreur est lissée, on peut cependant chercher à obtenir une approximation de $V_{h}$ sur la grille grossière de pas $H=2h$ , ce qui nécessitera beaucoup moins de calculs puisque la grille de pas $H$ possède environ deux fois moins de points dans le cas du problème monodimensionnel (quatre fois moins, dans le cas du problème bidimensionnel, huit fois moins dans le cas du problème tridimensionnel) que celle de pas $h$ ; on pourra effectivement obtenir une bonne approximation de $V_{h}$ sur la grille grossière si $V_{h}$ varie lentement, ce qui est effectivement le cas grâce aux itérations de lissage. La seconde phase de chaque cycle de la méthode 2-Grilles consiste alors à :

1. définir la restriction $r_{H}$ de $r_{h}$ sur la grille grossière à l'aide d'un opérateur de restriction ; cet opérateur peut être, tout simplement, l'injection définie en tous points M de la grille grossière, mais on peut également utiliser une restriction par moyenne pondérée ;
2. résoudre le système linéaire $AV_{H}=r_{H}$ , donnant la correction $V_{H}$ sur la grille grossière ;
3. prolonger $V_{H}$ obtenue sur la grille grossière en une fonction obtenue sur la grille fine, par exemple par interpolation bilinéaire.
4. On recommence ensuite un nouveau cycle de la méthode 2-Grilles.

La question principale qui se pose est de savoir si, effectivement, le prolongement de $V_{H}$ est une bonne approximation de $V_{h}$ et, dans ce cas, quel est le gain que l'on va attendre de l'utilisation de la méthode 2-Grilles ; il est à noter que cette méthode 2-Grilles peut s'écrire sous la forme d'une itération de point fixe linéaire du type

$$U_{k+1}=B U_{k}+C \mbox{}{ pour } k=0,1,2,..$$

Pour un lissage correspondant à la méthode de Gauss-Seidel, on montre, par analyse de Fourier, que le facteur de réduction de l'erreur est égal à $\sqrt{5}/5\approx0,447$ ce qui correspond à un excellent taux de réduction.

6.11.2 Méthode multigrille

La méthode multigrille correspond à l'application récursive d'une méthode 2-Grilles. En effet lors de la résolution du système d'équations sur la grille grossière $AV_{H}=r_{H}$ , on peut de nouveau utiliser une méthode 2-Grilles, en définissant un problème sur une grille encore plus grossière de pas 2H , et ainsi de suite pour finalement résoudre un système d'équations sur la grille la plus grossière ne contenant que quelques points, voire même un seul point puisque les pas de discrétisation sont choisis comme des puissances inverses de 2.

Cela nécessite de définir des stratégies de passages intergrilles. Signalons également que cette méthode multigrille est bien adaptée à une utilisation sur des domaines rectangulaires ; il existe cependant des variantes de la méthode multigrille bien adaptées à la résolution numérique d'équations aux dérivées partielles sur des domaines quelconques .

6.11.3 Exemple

à titre illustratif, considérons le problème de Poisson défini sur le carré unité avec conditions aux limites de Dirichlet homogènes :

$$-\Delta u=f \mbox{}{sur }\Omega=]0,1[x]0,1[ \mbox{}{ avec } u_{\Gamma}=0$$

La discrétisation de ce problème par différences finies classiques conduit à résoudre un système linéaire ; considérons un pas de discrétisation h suffisamment fin ainsi qu'une tolérance raisonnable tol pour arrêter les itérations, par exemple :

$$h=1/256 dim(A)=65 025 tol=10^{-4}h^{2}$$

La comparaison des temps de calcul conduit à dresser le tableau 1 .

Les résultats présentés dans le tableau ci dessous permettent de mesurer la différence de performance des algorithmes précédents ; il convient de noter que les méthodes multigrilles sont favorisées dans ce type de problème, dans la mesure où le domaine $\Omega$ est ici le carré unité ; si l'on considère un domaine quelconque, les performances de la méthode multigrille diminueront et la mise en oeuvre de l'algorithme sera moins simple à réaliser.

Méthode

Temps CPU de calcul Gauss-Seidel

Comparaison des temps de calculs de solveurs itératifs classiques