Méthodes stationnaires et de relaxation

Les méthodes itératives stationnaires résolvent un système linéaire en décomposant la matrice et en appliquant de manière répétée une règle de mise à jour fixe ; les schémas classiques de Jacobi, de Gauss-Seidel et de surrelaxation successive en sont les exemples fondamentaux.

Definition

Une méthode itérative stationnaire est une méthode dont la mise à jour applique la même matrice d'itération à chaque étape, dérivée d'une décomposition de la matrice des coefficients en une partie facilement inversible et un reste ; la convergence est régie par le rayon spectral de la matrice d'itération résultante.

Scope

Ce sujet aborde le cadre de la décomposition matricielle, les itérations de Jacobi et de Gauss-Seidel, la surrelaxation successive et le choix du paramètre de relaxation optimal, le critère du rayon spectral pour la convergence, ainsi que le rôle que jouent aujourd'hui ces itérations simples en tant que lisseurs (smoothers) au sein des méthodes multigrilles et en tant que préconditionneurs.

Core questions

• Comment la décomposition de la matrice conduit-elle à une itération de point fixe pour le système linéaire ?
• En quoi les méthodes de Jacobi et de Gauss-Seidel diffèrent-elles, et pourquoi Gauss-Seidel est-elle généralement plus rapide ?
• Comment la surrelaxation accélère-t-elle la convergence, et comment le paramètre optimal est-il choisi ?
• Sous quelles conditions sur la matrice ces itérations convergent-elles ?

Key theories

Décomposition matricielle et critère du rayon spectral

Écrire la matrice comme une partie facilement inversible moins un reste définit une itération stationnaire dont l'erreur est multipliée par une matrice d'itération à chaque étape ; l'itération converge pour toute estimation initiale si et seulement si le rayon spectral de cette matrice d'itération est inférieur à un.

Surrelaxation successive

En sur-corrigeant la correction de Gauss-Seidel avec un facteur de relaxation, la surrelaxation successive peut réduire considérablement le rayon spectral ; pour certaines matrices structurées, un paramètre de relaxation optimal est connu analytiquement et permet une accélération spectaculaire.

Mechanisms

La méthode de Jacobi met à jour simultanément toutes les inconnues en utilisant uniquement les valeurs de l'itération précédente, ce qui équivaut à isoler la diagonale. La méthode de Gauss-Seidel utilise les valeurs les plus récemment mises à jour au cours de la même itération, en isolant la partie triangulaire inférieure, ce qui tend à converger plus rapidement. La surrelaxation successive forme une moyenne pondérée de l'ancienne valeur et de la mise à jour de Gauss-Seidel, régie par un paramètre de relaxation ; choisir ce paramètre supérieur à un accélère la convergence pour des matrices appropriées. La convergence pour les trois méthodes est garantie pour des classes de matrices telles que les matrices à diagonale strictement dominante ou symétriques définies positives, et est quantifiée par le rayon spectral de la matrice d'itération.

Clinical relevance

Bien que généralement trop lentes pour être des solveurs autonomes compétitifs pour les grands systèmes, les méthodes stationnaires demeurent importantes en tant que lisseurs (smoothers) au cœur des méthodes multigrilles, en tant que préconditionneurs simples pour les méthodes de Krylov, et en tant qu'éléments constitutifs facilement parallélisables ; Gauss-Seidel et Jacobi pondéré en particulier sont omniprésents dans les solveurs multiniveaux modernes.

History

Les itérations de Jacobi et de Gauss-Seidel remontent au XIXe siècle, tandis que la surrelaxation successive et sa théorie rigoureuse de la convergence ont été développées par David Young et Richard Varga dans les années 1950 ; bien que par la suite éclipsées par les méthodes de Krylov et multigrilles en tant que solveurs principaux, ces itérations ont été réactivées en tant que composants essentiels des schémas multiniveaux et préconditionnés.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

Pourquoi Gauss-Seidel est-elle généralement plus rapide que Jacobi ?

Gauss-Seidel utilise immédiatement les valeurs mises à jour au cours de la même itération, de sorte que l'information se propage plus rapidement à travers les inconnues, réduisant généralement de moitié le nombre d'itérations par rapport à Jacobi, qui n'utilise que les valeurs de l'itération précédente.

Si ces méthodes sont lentes, pourquoi sont-elles encore étudiées ?

Ce sont d'excellents lisseurs (smoothers) et de simples préconditionneurs. Au sein des méthodes multigrilles, quelques itérations de Gauss-Seidel ou de Jacobi pondéré éliminent efficacement l'erreur oscillatoire, ce qui est précisément le rôle requis par les méthodes multigrilles ; ainsi, ces itérations classiques perdurent en tant que composants de solveurs modernes rapides.