Introduction A La Methode Multigrille

Introduction à la Méthode Multigrille GUENAIZI ABDELKADER ENAGEO E-mail :[email protected] ______________________________________________________________ Résumé- Les méthodes itératives sont très rapides, mais leur inconvénient réside dans leur incapacité à réduire les composantes basses fréquences de l’erreur. En utilisant les grilles grossières, les composantes fréquentielles lisses acquièrent un caractère haut fréquent et quelques itérations de la méthode itérative suffisent à régler le problème. L’approche de la méthode multigrille se base sur l'utilisation de deux ou plusieurs grilles de différentes résolutions. De cette façon, les composantes fréquentielles lisses sont efficacement résolues sur les grilles grossières, cependant les fréquences oscillatoires sont bien manipulées sur les grilles fines. Différents types de méthodes multigrilles existent utilisant différents cycles restrictions/prolongements : ce sont les schémas de type V-cycles et W-cycles qui sont déjà utilisées en industrie. L’application des méthodes multigrilles aux données géophysiques semble intéresser la communauté scientifique et quelques recherches seront conduites sur la migration, modélisation, tomographie et l’inversion dans un avenir proche.

___________________________________________________________ 1. Introduction On considère l’équation de Poisson à 1D : -∆ u = f (1) définie dans l’intervalle [0,1] avec les conditions aux limites u(0)=0 et u(1)=0. En appliquant le schéma des différences finies du second ordre correspondant à l’équation (1), on obtient le système linéaire suivant: -u(i+1)+2 u(i)- u(i-1) = fi (2) h² Où h pas de maillage, qu’on peut également l’écrire sous forme matricielle : A u = f (3) T

où

u = (u1, u2,......, uN-1)

où

T

signifie la transposée

T

f = (f1, f2,......, fN-1) avec u (0)=u (N)=0 L’équation (3) sous forme discrétisée s’écrit comme un système linéaire de la forme : Ah uh = fh (4)

2. Méthodes Itératives Les méthodes itératives (Jacobi, Gauss-Seidel) ont une approche commune à la résolution des problèmes linéaires de la forme Au = f. la solution du système pour la ième composante de u est : u(i) = (u (i+1) + u (i-1) + h² fi) / 2 (5) La méthode de Gauss-Seidel [1] ne diffère de celle de Jacobi que par l’emploi immédiat des valeurs estimées et la mise à jour des valeurs u pour chaque itération jusqu’à ce que la convergence soit atteinte. En posant f=0 dans l’équation (3), on obtient : A u =0 (6) Le système admet une solution exacte u =0 et pour chaque approximation v, l‘erreur est e= u- v Pour étudier le comportement du schéma itératif avec les différentes composantes fréquentielles de l’erreur [2], les modes de Fourier avec différentes fréquences k=1, 3 et 6 ont été introduits comme estimées initiales pour le calcul de l’itération de Gauss-Seidel (fig.1).

Fig.1 Différents modes de Fourier k=1,3 et 6 La convergence de l’algorithme de Gauss-Seidel pour les modes de Fourier k=1,3,6 en fonction du nombre d’itérations est montrée sur la Fig.2. On observe que l’erreur décroît rapidement avec l’accroissement du nombre k et croît avec les petites valeurs de k

Fig.2 Erreur || e || en fonction du nombre ∞

d’itérations pour k=1, 3,6

3. METHODE MULTIGRILLE

Le principe de la méthode multigrille repose sur deux observations : -Les méthodes itératives classiques fonctionnent par effet de lissage de l’erreur au cours des itérations ; si on décompose l’erreur en série de Fourier, on s’aperçoit généralement que les hautes fréquences relatives à un maillage donné d’un pas h sont amorties beaucoup plus que les basses fréquences. -Les basses fréquences de l’erreur sur le maillage fin apparaîtront comme de hautes fréquences sur le maillage grossier de pas 2h et peuvent être bien amorties par la méthode itérative. 3.1 Méthode à deux grilles

La base des algorithmes multigrilles est un procédé à deux grilles appliqué récursivement. Un cycle à deux grilles [3] peut être décrit comme suit : Sur la grille fine, quelques itérations de prélissage sont appliquées pour atténuer les hautes fréquences de l’erreur. Le résidu, une fois calculé ; est alors projeté sur la grille grossière où les basses fréquences peuvent être capturées et l’équation de l’erreur grossière est résolue. L’erreur grossière est interpolée de nouveau sur la grille fine pour corriger la solution approchée qu’on a obtenu dans l’étape de prélissage sur la grille fine. Ceci peut être représenté par la procédure suivante : 1. On effectue quelques itérations de Gauss-Seidel Ah uh = fh pour obtenir une approximation vh sur la grille fine de pas h (étape de prélissage). 2. Calcul du résidu r h = f h – Ah vh 3. restreindre ce résidu sur une grille grossière de pas 2h à l’aide d’un opérateur de restriction R. 4. On résout l’équation A2h e2h = r2h pour une approximation de l’erreur e2h sur la grille grossière (on pose e2h=0). 5. On effectue un prolongement de la correction e2h sur la grille fine à l’aide d’un opérateur de prolongement ou (interpolation) I pour avoir eh. 6. on ajoute eh à la solution approchée obtenue vh dans l’étape de prélissage vh ← vh + eh. 7. On effectue quelques itérations de Gauss-Seidel Ah uh = fh avec pour solution initiale vh (étape

de postlissage sur la grille fine.

3.2 Différents types de multigrilles

L’idée de la multigrille est de reconnaître les basses fréquences de l’erreur et de pouvoir les bien amortir sur une grille grossière. L’application récursive de cette idée à chaque système consécutif de l’équation da la grille grossière conduit à la méthode multigrille v cycle (fig.3). Si les composantes de v cycle sont définies convenablement, le résultat est une méthode qui amortit toutes les fréquences uniformément. Fig.3 a) v-cycle b) w-cycle c) complète

On parle de la multigrille de V-cycle en allant de la grille la plus fine à la plus grossière puis on remonte jusqu’à la grille la plus fine. Il existe des variantes de diverses formes telles que : W-cycle et multigrille complète V-cycle (Full multigrid). Pour Le passage d’un raffinement de grille au suivant, on utilise deux opérateurs : Un opérateur de restriction R (phase montante) et un opérateur de prolongement (interpolation) I (phase montante). 4. RESULTATS NUMERIQUES

La méthode itérative de Gauss-Seidel est appliquée sur une série aléatoire de 33 points prise comme solution initiale pour la solution du Laplacien ∆u = 0.Une série aléatoire de 33 points est introduite comme erreur initiale pour l’itération (fig. 4a).Les figures 4b) ,4c) et 4d) montrent l’erreur restante après 3,10, et 30 itérations de l’application de Gauss-Seidel. Les composantes hautes fréquences (HF) sont rapidement réduites après quelques itérations. Cependant les composantes basses fréquences restent beaucoup plus difficiles à réduire.

Fig.4 a) solution initiale b) erreur après 3 itérations de Gauss-Seidel c) erreur après 10 itérations d) erreur après 30 itérations. La stratégie adoptée pour réduire les composantes basses fréquences est d’utiliser la méthode itérative sur la grille grossière. En effet, on est passé de la grille fine de 33 points à une grille grossière de 5 points. En parcourant les différentes itérations, la réduction de l’erreur est presque totale. L’erreur des Basses fréquences (BF) sur la méthode itérative classique (GaussSeidel) est fortement présente après 30 itérations (Fig. 4d). Pour la méthode itérative multigrille (deux grilles V-cycle, juste après la troisième itération, l’erreur est quasiment nulle (Fig.5)

Fig.5.haut) solution initiale à 33 points /solution restreinte à 5 points Fig5.bas) erreur après 1 itération de GaussSeidel c) erreur après 2 itérations d) erreur après 3 itérations.

une superposition de différents modes de Fourier k=2,16 et 32 est introduite comme erreur initiale pour être itéré 30 fois (figure 6). On constate que les modes oscillatoires sont rapidement amortis, par contre les modes de grande longueur d’onde restent inchangés. Cette propriété est commune à toutes les méthodes itératives. La méthode multigrille comble cette lacune par l’utilisation de plusieurs grilles pour prendre en charge toutes les composantes fréquentielles. Un autre exemple convaincant où la méthode multigrille V-cycle (Fig7) de 3 itérations a permis de montrer clairement son efficacité.

. Fig.6 haut) solution initiale BF +HF à 65 points F Fig.6 bas) erreur restante après 30 itération de GaussSeidel

Fig.7.haut) solution initiale BF+HF à 65 points Fig.7.bas) erreur restante après 3 itération de Multigrille-Vcycle.

Cela ne fait que confirmer la supériorité des méthodes itératives multigrilles sur les méthodes itératives classiques, quelques itérations de la multigrille, ont suffi pour réduire les composantes BF de l’erreur à néant. 5. CONCLUSIONS

Les résultats numériques ont montré que les méthodes multigrilles sont des méthodes efficaces pour réduire toutes les composantes fréquentielles de l’erreur, là où les méthodes itératives classiques ont failli pour amortir les composantes lisses de l’erreur. Il serait très intéressant de voir un jour l’application de la méthode multigrille au calcul des corrections statiques pour résoudre le problème des grandes longueurs d’ondes qui fait apparaître de fausses structures géologiques. REMERCIEMENTS- Je remercie Mr Benkraouche Boudjemaa, chef de département traitement

sismique ENAGEO qui m’a encouragé pour la réalisation de ce travail, et Mr Hocine Saad, ingénieur géophysicien pour l’aide appréciable apportée à la rédaction de cet article. REFERENCES

[1] A. Gourdin, Boumahrat, Méthodes numériques appliquées, opu, 1991 [2] W. L. Briggs, A Multigrid Tutorial, Center for Applied Scientific Computing, 1987 [3] Veselin Dikov, Multigrid for solving differential equations, Ferien Akedemie, 2005 [4] Deconvolution with Multigrid John Millar and John C Bancroft, University of Calgary.2004