le Méthode Gauss-Seidel est une procédure itérative pour trouver des solutions approchées à un système d'équations algébriques linéaires avec une précision arbitrairement choisie. La méthode est appliquée à des matrices carrées avec des éléments non nuls dans leurs diagonales et la convergence est garantie si la matrice est diagonalement dominante.
Il a été créé par Carl Friedrich Gauss (1777-1855), qui a donné une démonstration privée à l'un de ses étudiants en 1823. Il a ensuite été officiellement publié par Philipp Ludwig von Seidel (1821-1896) en 1874, d'où le nom des deux mathématiciens.
Pour une compréhension complète de la méthode, il faut savoir qu'une matrice est diagonalement dominante lorsque la valeur absolue de l'élément diagonal de chaque ligne est supérieure ou égale à la somme des valeurs absolues des autres éléments de cette même ligne..
Mathématiquement, il est exprimé comme ceci:
Index des articles
Pour illustrer en quoi consiste la méthode de Gauss-Seidel, nous prendrons un cas simple, dans lequel les valeurs de X et Y peuvent être trouvées dans le système d'équations linéaires 2 × 2 présenté ci-dessous:
5X + 2Y = 1
X - 4Y = 0
1- Premièrement, il est nécessaire de déterminer si la convergence est sûre. On observe immédiatement que, en effet, il s'agit d'un système diagonalement dominant, puisque dans la première ligne le premier coefficient a une valeur absolue plus élevée que les autres dans la première ligne:
| 5 |> | 2 |
De même, le deuxième coefficient de la deuxième rangée est également dominant en diagonale:
| -4 |> | 1 |
deux- Les variables X et Y sont résolues:
X = (1 - 2Y) / 5
Y = X / 4
3- Une valeur initiale arbitraire est placée, appelée "seed": Xo = 1, I = 2.
4-L'itération commence: pour obtenir la première approximation X1, Y1, la graine est substituée dans la première équation de l'étape 2 et le résultat dans la deuxième équation de l'étape 2:
X1 = (1 - 2 I) / 5 = (1 - 2 × 2) / 5 = -3/5
Y1 = X1 / 4 = (-3/5) / 4 = -3/20
5- On procède de manière similaire pour obtenir la seconde approximation de la solution du système d'équations:
X2 = (1 - 2 Y1) / 5 = (1 - 2x (-3/20)) / 5 = 13/50
Y2 = X2 / 4 = (13/50) / 4 = 13/200
6- Troisième itération:
X3 = (1 - 2 Y2) / 5 = (1 - 2 (13/200)) / 5 = 87/500
Y3 = X3 / 4 = (87/500) / 4 = 87/2000
7- Quatrième itération, comme dernière itération de ce cas illustratif:
X4 = (1 - 2 Y3) / 5 = (1 - 2 (87/2000)) / 5 = 913/5000
Y4 = X4 / 4 = (913/5000) / 4 = 913/20000
Ces valeurs concordent assez bien avec la solution trouvée par d'autres méthodes de résolution. Le lecteur peut le vérifier rapidement à l'aide d'un programme mathématique en ligne.
Comme on peut le voir, dans la méthode de Gauss-Seidel, les valeurs approchées obtenues pour la variable précédente dans cette même étape doivent être substituées dans la variable suivante. Cela le différencie des autres méthodes itératives telles que celle de Jacobi, dans laquelle chaque étape nécessite les approximations de l'étape précédente..
La méthode Gauss-Seidel n'est pas une procédure parallèle, contrairement à la méthode Gauss-Jordan. C'est aussi la raison pour laquelle la méthode Gauss-Seidel a une convergence plus rapide - en moins d'étapes - que la méthode Jordan..
Quant à la condition de matrice diagonalement dominante, elle n'est pas toujours satisfaite. Cependant, dans la plupart des cas, il suffit de permuter les lignes du système d'origine pour que la condition soit remplie. De plus, la méthode converge presque toujours, même lorsque la condition de dominance diagonale n'est pas remplie..
Le résultat précédent, obtenu par quatre itérations de la méthode Gauss-Seidel, peut s'écrire sous forme décimale:
X4 = 0,1826
Y4 = 0,04565
La solution exacte du système d'équations proposé est:
X = 2/11 = 0,1818
Y = 1/22 = 0,04545.
Donc, avec seulement 4 itérations, vous obtenez un résultat avec un millième de précision (0,001).
La figure 1 illustre comment les itérations successives convergent rapidement vers la solution exacte.
La méthode de Gauss-Seidel ne se limite pas uniquement à un système 2 × 2 d'équations linéaires. La procédure ci-dessus peut être généralisée pour résoudre un système linéaire de n équations avec n inconnues, qui sont représentées dans une matrice comme celle-ci:
À X = b
Où À est une matrice n x n, alors que X est le vecteur n composantes des n variables à calculer; Oui b est un vecteur contenant les valeurs des termes indépendants.
Généraliser la séquence d'itérations appliquées dans le cas illustratif à un système n x n, à partir duquel la variable doit être calculée Xi, la formule suivante sera appliquée:
Dans cette équation:
- k est l'indice de la valeur obtenue dans l'itération k.
-k + 1 indique la nouvelle valeur dans ce qui suit.
Le nombre final d'itérations est déterminé lorsque la valeur obtenue dans l'itération k + 1 diffère de celui obtenu immédiatement avant, d'un montant ε qui est précisément la précision souhaitée.
Ecrire un algorithme général pour calculer le vecteur de solutions approchées X d'un système linéaire d'équations nxn, étant donné la matrice de coefficients À, le vecteur des termes indépendants b, le nombre d'itérations (iter) et la valeur initiale ou "germe" du vecteur X.
L'algorithme se compose de deux cycles «To», l'un pour le nombre d'itérations et l'autre pour le nombre de variables. Ce serait comme suit:
Pour k ∊ [1… iter]
Pour i ∊ [1… n]
X [i]: = (1 / A [i, i]) * (b [i] - ∑j = 1n(A [i, j] * X [j]) + A [i, i] * X [i])
Vérifier le fonctionnement de l'algorithme précédent en l'appliquant dans un logiciel mathématique Studio SMath gratuit à utiliser, disponible pour Windows et Android. Prenons comme exemple le cas de la matrice 2 × 2 qui nous a permis d'illustrer la méthode de Gauss-Seidel.
Appliquez l'algorithme de Gauss-Seidel pour le système d'équations 3 × 3 suivant, qui a été précédemment ordonné de telle sorte que les coefficients de la diagonale soient dominants (c'est-à-dire d'une valeur absolue supérieure aux valeurs absolues des coefficients de la même ligne):
9 X1 + 2 X2 - X3 = -2
7 X1 + 8 X2 + 5 X3 = 3
3 X1 + 4 X2 - 10 X3 = 6
Utilisez le vecteur nul comme valeur de départ et considérez cinq itérations. Commentez le résultat.
Pour le même système avec 10 itérations au lieu de 5, les résultats suivants sont obtenus: X1 = -0,485; X2 = 1,0123; X3 = -0,3406
Cela nous indique que cinq itérations suffisent pour obtenir trois décimales de précision et que la méthode converge rapidement vers la solution.
En utilisant l'algorithme de Gauss-Seidel donné ci-dessus, trouvez la solution au système d'équations 4 × 4 donné ci-dessous:
10 x1 - x2 + 2 x3 + 0 x4 = 6
-1 x1 + 11 x2 - 1 x3 + 3 x4 = 25
2 x1 - 1 x2 + 10 x3 - 1 x4 = -11
0 x1 + 3 x2 - 1 x3 + 8 x4 = 15
Pour démarrer la méthode, utilisez cette graine:
x1 = 0, x2 = 0, x3 = 0 et x4 = 0
Considérez 10 itérations et estimez l'erreur du résultat, en comparant avec l'itération numéro 11.
En comparant avec l'itération suivante (numéro 11), le résultat est identique. Les plus grandes différences entre les deux itérations sont de l'ordre de 2 × 10-8, ce qui signifie que la solution affichée a une précision d'au moins sept décimales.
Personne n'a encore commenté ce post.