AlgèbreMéthode · Glossaire
méthode de Seidel
La méthode de Seidel, ou méthode de Gauss-Seidel, résout itérativement un système d’équations linéaires dont les coefficients diagonaux utilisés sont non nuls. Chaque nouvelle valeur d’une inconnue est réutilisée immédiatement pour calculer les suivantes du même tour, ce qui accélère souvent la convergence. Celle-ci est notamment garantie si la matrice est strictement à diagonale dominante ou symétrique définie positive.
Sommaire
Ce que vous allez apprendre
- Identifier la différence entre les mises à jour de Gauss-Seidel et de Jacobi.
- Appliquer les formules à un système de deux équations et contrôler le résidu.
- Reconnaître deux classes de matrices qui garantissent la convergence.
- Repérer une diagonale nulle, une divergence et un critère d'arrêt trompeur.
En clair
Imaginez plusieurs inconnues liées par des équations. On part d'une estimation, puis on recalcule les inconnues l'une après l'autre. Dès qu'une nouvelle valeur est obtenue, elle sert au calcul suivant, sans attendre la fin du tour.
Ces corrections successives forment la méthode de Seidel, ou méthode de Gauss-Seidel. Si les conditions de convergence sont réunies, les estimations se rapprochent tour après tour de la solution du système linéaire.
Définition
La méthode de Seidel, aussi appelée méthode de Gauss-Seidel, est une méthode itérative pour résoudre un système linéaire dont la matrice des coefficients est notée A, le vecteur inconnu x et le second membre b. On écrit A comme la somme de sa diagonale D, de sa partie triangulaire inférieure stricte L et de sa partie triangulaire supérieure stricte U.
À l'itération numérotée k + 1, la composante d'indice i du vecteur est calculée avec les nouvelles composantes d'indices inférieurs et les anciennes composantes d'indices supérieurs :
Le coefficient diagonal aii doit être non nul dans l'ordre choisi. Sous forme matricielle, cela revient à résoudre à chaque tour un système triangulaire inférieur :
La convergence est garantie notamment si A est strictement diagonalement dominante, ou si A est symétrique définie positive. L'emploi immédiat des valeurs nouvelles conduit souvent à une convergence plus rapide que celle de Jacobi, mais ce n'est pas une garantie universelle de rapidité.
Le principe
Choisissez un vecteur initial. Pour chaque tour, parcourez les équations dans un ordre fixé. Isolez l'inconnue portée par la diagonale, puis remplacez les inconnues déjà parcourues par leurs valeurs du tour courant et les autres par celles du tour précédent.
Arrêtez lorsque la norme du résidu, c'est-à-dire du vecteur Ax − b, ou la norme de la variation entre deux vecteurs successifs devient inférieure à une tolérance choisie. Ce critère indique la précision numérique atteinte ; il ne remplace pas une condition assurant la convergence.
Quand l'utiliser
La méthode s'applique à un système linéaire carré Ax = b, avec une estimation initiale et un ordre de parcours des inconnues. Chaque coefficient diagonal utilisé comme diviseur doit être non nul. Une permutation des équations ou des inconnues peut parfois rétablir cette propriété.
La convergence est assurée si la matrice est strictement diagonalement dominante : dans chaque ligne, la valeur absolue du coefficient diagonal dépasse la somme des valeurs absolues des autres coefficients. Elle l'est aussi pour une matrice symétrique définie positive.
Si la matrice n'appartient à aucune de ces classes, la méthode peut encore converger, mais ce n'est plus garanti. Si les itérés oscillent ou si le résidu augmente, il faut tester un autre ordre, employer une relaxation adaptée ou choisir une méthode directe.
Un exemple, pas à pas
Résolvons le système suivant à partir de x(0) = 0 et y(0) = 0. Les coefficients diagonaux 4 et 3 dominent strictement les autres coefficients de leur ligne.
Les formules de mise à jour sont :
1. Au premier tour, x(1) = 9/4 = 2,25.
2. La valeur 2,25 sert aussitôt : y(1) = (7 − 2,25)/3 = 19/12 ≈ 1,5833.
3. Au deuxième tour, x(2) = (9 − 19/12)/4 = 89/48 ≈ 1,8542, puis y(2) = (7 − 89/48)/3 = 247/144 ≈ 1,7153.
4. Au troisième tour, x(3) = 1049/576 ≈ 1,8212, puis y(3) = 2983/1728 ≈ 1,7263.
2. La valeur 2,25 sert aussitôt : y(1) = (7 − 2,25)/3 = 19/12 ≈ 1,5833.
3. Au deuxième tour, x(2) = (9 − 19/12)/4 = 89/48 ≈ 1,8542, puis y(2) = (7 − 89/48)/3 = 247/144 ≈ 1,7153.
4. Au troisième tour, x(3) = 1049/576 ≈ 1,8212, puis y(3) = 2983/1728 ≈ 1,7263.
La solution exacte est x = 20/11 ≈ 1,8182 et y = 19/11 ≈ 1,7273. Après trois tours, la seconde équation est satisfaite exactement par construction ; l'écart dans la première vaut 4x(3) + y(3) − 9 = 19/1728 ≈ 0,0110. Ce résidu fournit un contrôle refaisable de l'approximation.
En pratique
Pour un grand système contenant beaucoup de coefficients nuls, on effectue les mises à jour sans former d'inverse de matrice. Ce faible besoin en mémoire rend la méthode utile comme solveur simple. Une factorisation directe reste préférable si le système est petit et qu'une solution très précise est requise en une seule résolution.
Dans un calcul répété, on surveille le résidu après chaque tour et l'on fixe une tolérance cohérente avec la précision recherchée. Si la diminution est trop lente, la méthode de relaxation successive peut accélérer le calcul grâce à un paramètre choisi avec soin.
La méthode sert aussi de lisseur ou de préconditionneur dans des algorithmes plus élaborés. Lorsque les mises à jour doivent être calculées simultanément sur de nombreux processeurs, la méthode de Jacobi est souvent plus simple à paralléliser.
À ne pas confondre
Méthode de Jacobi. Jacobi calcule toutes les composantes d'un nouveau tour à partir des seules valeurs du tour précédent. Gauss-Seidel réemploie immédiatement les composantes déjà recalculées. Dans l'exemple, Jacobi calculerait y(1) avec x(0) = 0, tandis que Gauss-Seidel utilise x(1) = 2,25.
Élimination de Gauss. L'élimination transforme le système en un nombre fini d'opérations pour obtenir la solution, à l'arrondi près. Gauss-Seidel produit une suite d'approximations et exige un critère d'arrêt. Pour une matrice dense de taille modérée, l'élimination est généralement le choix direct.
Limites et pièges
Diagonale nulle. Si un coefficient diagonal vaut 0, la formule correspondante divise par zéro. Il faut permuter les équations ou les inconnues lorsque c'est possible, sinon changer de méthode.
Convergence non garantie. Hors des classes strictement diagonalement dominantes et symétriques définies positives, une suite peut diverger ou osciller. Un résidu qui ne décroît pas après plusieurs tours est un symptôme, pas une preuve générale ; il faut analyser la matrice ou employer un autre solveur.
Ordre des inconnues. Changer l'ordre modifie la matrice d'itération et peut donc changer la vitesse, voire le comportement de convergence. Le résultat exact du système ne change pas, mais le chemin numérique oui.
Petit incrément trompeur. Deux itérés presque identiques ne suffisent pas toujours à garantir une bonne solution, notamment pour un système mal conditionné. Il faut aussi contrôler le résidu Ax − b et interpréter sa taille selon la précision recherchée.
Pour aller plus loin
La méthode de Jacobi éclaire le rôle de la mise à jour immédiate : comparer les deux schémas montre comment le choix des valeurs anciennes ou nouvelles transforme l'itération.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres