AnalyseMéthode · Glossaire
Relaxation (méthode de)
La méthode de relaxation est une technique itérative pour résoudre des systèmes linéaires ou des équations aux dérivées partielles. Elle consiste à mettre à jour une à une les composantes du vecteur solution en résolvant chaque équation par rapport à une inconnue. La méthode de Gauss-Seidel en est une variante, et la sur-relaxation successive (SOR) introduit un paramètre omega pour accélérer la convergence. Le choix optimal du paramètre de sur-relaxation peut réduire considérablement le nombre d'itérations nécessaires.
Sommaire
Ce que vous allez apprendre
- Relier la relaxation à la mise à jour composante par composante.
- Effectuer trois balayages de Gauss-Seidel sur un système 2 × 2.
- Interpréter le paramètre omega de SOR et contrôler l’arrêt avec le résidu.
- Reconnaître des conditions suffisantes de convergence et des causes d’échec.
En clair
Imaginez plusieurs nombres liés par autant d’équations. Au lieu de chercher tous les nombres d’un seul coup, on en choisit un, on le recalcule avec les valeurs disponibles, puis on passe au suivant. Chaque nouvelle valeur sert aussitôt au calcul suivant.
Un balayage complet produit une approximation. On recommence jusqu’à ce que les corrections deviennent assez petites. La relaxation transforme ainsi un gros calcul direct en une suite de mises à jour simples.
Définition
Pour un système linéaire dont la matrice des coefficients est notée A, le vecteur inconnu x et le second membre b, la méthode de relaxation construit une suite d’approximations de la solution de . Chaque équation est isolée par rapport à sa composante inconnue. Pendant un balayage, les composantes sont mises à jour l’une après l’autre jusqu’à satisfaire un critère d’arrêt. Une discrétisation d’équation aux dérivées partielles peut conduire au même type de système.
Gauss-Seidel emploie immédiatement les valeurs déjà recalculées pendant le balayage. La sur-relaxation successive, abrégée SOR, combine l’ancienne valeur et la valeur proposée par Gauss-Seidel. Son paramètre réel, noté , vaut 1 pour Gauss-Seidel ; entre 1 et 2, il extrapole la correction. Un choix bien adapté à la matrice peut réduire fortement le nombre d’itérations, sans qu’une même valeur soit optimale pour tous les systèmes.
Le principe
Pour une ligne i dont le coefficient diagonal aii est non nul, on calcule d’abord la valeur proposée par Gauss-Seidel. Les composantes déjà visitées portent l’indice d’itération k + 1 ; les autres gardent l’indice k.
Après chaque balayage, on mesure le résidu . On s’arrête lorsque sa norme respecte la tolérance fixée, ou lorsque la limite d’itérations est atteinte.
Quand l'utiliser
La méthode demande un système linéaire, une approximation initiale, un ordre de parcours, une tolérance et un nombre maximal d’itérations. Chaque coefficient diagonal utilisé comme diviseur doit être non nul ; une permutation des équations ou des inconnues peut parfois rétablir cette condition.
Une convergence est notamment garantie pour Gauss-Seidel lorsque la matrice est symétrique définie positive, ou lorsqu’elle est strictement dominante par lignes. Pour une matrice symétrique définie positive, SOR converge si . Ces conditions sont suffisantes, pas nécessaires dans tous les cas. Si le résidu stagne ou augmente, il faut changer le paramètre, réordonner le système, employer un préconditionnement ou choisir une autre méthode.
Un exemple, pas à pas
On résout le système suivant par Gauss-Seidel, donc avec , en partant de x0 = 0 et y0 = 0. La tolérance choisie pour cet exemple est 0,01 sur chaque composante du résidu.
1. On isole les inconnues : x = (9 − y) / 4 et y = (6 − x) / 3.
2. Premier balayage : x1 = 2,25, puis y1 = 1,25.
3. Deuxième balayage : x2 = 1,9375, puis y2 ≈ 1,35417.
4. Troisième balayage : x3 ≈ 1,91146, puis y3 ≈ 1,36285.
2. Premier balayage : x1 = 2,25, puis y1 = 1,25.
3. Deuxième balayage : x2 = 1,9375, puis y2 ≈ 1,35417.
4. Troisième balayage : x3 ≈ 1,91146, puis y3 ≈ 1,36285.
Avec la troisième approximation, le résidu de la première équation vaut environ −0,00868 et celui de la seconde vaut exactement 0 à la précision du calcul non arrondi. Le critère est donc satisfait. La solution exacte, x = 21/11 et y = 15/11, confirme les valeurs approchées. Le tracé des mises à jour rend visible leur alternance et leur rapprochement de cette solution.
En pratique
Pour un grand système creux, stocker et éliminer tous les coefficients peut coûter cher. Un balayage de relaxation exploite directement les rares coefficients non nuls. Une méthode directe reste souvent préférable pour un petit système dense lorsque l’on veut une solution en un nombre fini d’opérations.
Après la discrétisation d’une équation aux dérivées partielles, chaque valeur sur une grille dépend souvent de quelques voisines. La relaxation met alors à jour les points de la grille successivement. On surveille le résidu, plutôt que la seule petitesse d’une correction.
Si Gauss-Seidel converge mais lentement, SOR peut l’accélérer. On teste des valeurs admissibles de et l’on compare le nombre de balayages pour une même tolérance ; une méthode préconditionnée devient préférable si le gain reste faible.
À ne pas confondre
Méthode de Jacobi. Elle calcule toutes les nouvelles composantes avec les seules valeurs du balayage précédent. Gauss-Seidel réutilise au contraire une composante dès sa mise à jour. Sur l’exemple, le calcul de y1 emploie x1 = 2,25 : il s’agit donc de Gauss-Seidel, pas de Jacobi.
Méthode directe. Une élimination algébrique vise la solution après une suite finie d’opérations, hors effets d’arrondi. La relaxation produit des approximations successives et s’arrête selon une tolérance. Pour le système 2 × 2 de l’exemple, la règle de Cramer donne directement les fractions exactes 21/11 et 15/11.
Limites et pièges
Un paramètre plus grand n’accélère pas toujours. Pour SOR appliquée à une matrice symétrique définie positive, la zone garantie est . À , on retrouve Gauss-Seidel ; près de 2, les oscillations peuvent s’amplifier. Il faut comparer les résidus à tolérance identique.
Une petite correction ne prouve pas une bonne solution. Des composantes peuvent changer très peu alors que le résidu reste trop grand, notamment avec un système mal conditionné. Le test d’arrêt doit donc porter sur le résidu, avec une échelle adaptée aux données.
L’ordre des équations compte. Un coefficient diagonal nul bloque la division, et un ordre défavorable peut ralentir ou empêcher la convergence. Avant d’abandonner la méthode, on peut permuter les lignes et les inconnues, puis vérifier de nouveau l’évolution du résidu.
Pour aller plus loin
Pour comparer l’approche itérative à une résolution directe, l’article Gabriel Cramer et la règle des déterminants : une découverte mathématique du XVIIIe siècle présente la règle de Cramer et son cadre algébrique.
L’étude de la relaxation se prolonge naturellement par le rayon spectral de la matrice d’itération, qui caractérise la convergence, puis par le préconditionnement des grands systèmes creux.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres