Un solveur itératif hiérarchique qui accélère la convergence pour des EDP discrétisées (linéaires et certaines non linéaires) en opérant sur une séquence de niveaux de discrétisation : lisser l'erreur haute fréquence sur des maillages fins, transférer les résidus vers des maillages plus grossiers pour éliminer l'erreur basse fréquence, corriger les approximations et interpoler les corrections vers les niveaux plus fins.

Principe

Utiliser des relaxations complémentaires (lissages) sur les maillages fins et la correction sur maillage grossier pour cibler les composantes d'erreur à leur échelle naturelle : l'erreur haute fréquence est réduite par des relaxations locales tandis que l'erreur basse fréquence est traitée efficacement sur des représentations plus grossières, produisant une convergence globale rapide souvent indépendante de la taille du problème.

Démonstration

Résolution d'une équation de Poisson sur une grille uniforme : appliquer quelques relaxations de Gauss–Seidel (lisseur) sur la grille fine pour amortir l'erreur oscillatoire, restreindre le résidu sur une grille plus grossière et y résoudre approximativement, prolonger la correction vers la grille fine et itérer en cycles en V ou W jusqu'à atteinte de la tolérance du résidu.

Mauvaise application

Utiliser le multigrille avec un lisseur inapproprié (par ex. une relaxation qui n'amortit pas les modes haute fréquence pour la discrétisation donnée), ou transférer entre discrétisations incompatibles sans opérateurs de restriction/prolongation cohérents, conduisant à une stagnation ou une divergence au lieu d'une accélération.

Conséquence

Conçu correctement, le multigrille obtient des taux de convergence indépendants de la maille et souvent une complexité optimale O(N) pour les opérateurs elliptiques, permettant de résoudre des systèmes EDP discretisés très grands de manière efficace en temps et mémoire.

Inversion

Méthodes itératives mono-niveau sans correction grossière : se reposer uniquement sur la relaxation (par ex. Jacobi, Gauss–Seidel) qui réduit typiquement l'erreur haute fréquence mais converge lentement pour les composantes lisses (basse fréquence), entraînant un ralentissement dépendant de la maille avec la croissance du problème.

Limite

Champ d'application : EDP elliptiques discrétisées et de nombreux problèmes paraboliques où des lisseurs et opérateurs d'intergrille peuvent être définis ; exclut les problèmes avec couplage fortement non local empêchant une correction grossière efficace, les discrétisations mal conditionnées sans lisseurs appropriés et les configurations où les modèles de maillage grossier sont incohérents ou indisponibles.

Tension sémantique

Tension entre complexité des opérateurs inter-niveaux et robustesse : des opérateurs de transfert et des modèles de maillage grossier sophistiqués améliorent la robustesse et la convergence dépendante de l'opérateur mais augmentent le coût d'implémentation et le travail par cycle, tandis que des choix plus simples donnent des cycles moins coûteux mais peuvent échouer sur des problèmes complexes.

Synthèse

La Méthode Multigrille est un algorithme multiniveau combinant lissage local sur maillages fins et correction sur maillage grossier via restriction et prolongation pour réduire efficacement toutes les fréquences d'erreur, produisant une convergence rapide et souvent indépendante de la maille pour une large classe d'EDP discrétisées.