MÉTHODE GAUSS-SEIDEL: EXPLICATION, APPLICATIONS, EXEMPLES - MATEMATIQUES - 2025

La méthode de 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 choisie arbitrairement. 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.

Figure 1. La méthode de Gauss-Seidel converge rapidement pour obtenir la solution d'un système d'équations. Source: F. Zapata.

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:

Explication à l'aide d'un cas simple

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

Pas à suivre

1- En premier lieu, il faut 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-

2- Les variables X et Y sont effacées:

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 de mathématiques en ligne.

Analyse de la méthode

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 comme 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.

Applications

La méthode de Gauss-Seidel ne se limite pas à un système d'équations linéaires 2 × 2. La procédure précédente peut être généralisée pour résoudre un système linéaire de n équations avec n inconnues, qui est représenté dans une matrice comme celle-ci:

A X = b

Où A est une matrice nxn, tandis que X est le vecteur n composantes des n variables à calculer; et b est un vecteur contenant les valeurs des termes indépendants.

Pour généraliser la séquence d'itérations appliquées dans le cas illustratif à un système nxn, à partir duquel la variable Xi veut être calculée, la formule suivante sera appliquée:

Dans cette équation:

- k est l'indice de la valeur obtenue à 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 à l'itération k + 1 diffère de celle obtenue immédiatement avant, d'un montant ε qui est précisément la précision souhaitée.

Exemples de la méthode Gauss-Seidel

- Exemple 1

Ecrire un algorithme général qui permet de calculer le vecteur de solutions approchées X d'un système linéaire d'équations nxn, étant donné la matrice de coefficients A, le vecteur de termes indépendants b, le nombre d'itérations (i ter) et la valeur initiale ou "seed « du vecteur X.

Solution

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 ∊

Pour je ∊

X: = (1 / A) * (b - ∑ _{j = 1} ⁿ (A * X) + A * X)

- Exemple 2

Vérifiez le fonctionnement de l'algorithme précédent via son application dans le logiciel mathématique gratuit et gratuit SMath Studio, disponible pour Windows et Android. Prenons comme exemple le cas de la matrice 2 × 2 qui nous a aidés à illustrer la méthode de Gauss-Seidel.

Solution

Figure 2. Solution du système d'équations de l'exemple 2 x 2, à l'aide du logiciel SMath Studio. Source: F. Zapata.

- Exemple 3

Appliquez l'algorithme de Gauss-Seidel pour le système d'équations 3 × 3 suivant, qui a été précédemment ordonné de manière à ce 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 graine et considérez cinq itérations. Commentez le résultat.

Solution

Figure 3. Solution du système d'équations de l'exemple 3 résolu, à l'aide de SMath Studio. Source: F. Zapata.

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.

- Exemple 4

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.

Solution

Figure 4. Solution du système d'équations de l'exemple résolu 4, à l'aide de SMath Studio. Source: F. Zapata.

En comparant avec l'itération suivante (numéro 11), le résultat est identique. Les différences les plus importantes 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.

Références

1. Méthodes de solution itérative. Gauss-Seidel. Récupéré de: cimat.mx
2. Méthodes numériques. Gauss-Seidel. Récupéré de: test.cua.uam.mx
3. Numérique: méthode Gauss-Seidel. Récupéré de: aprendeenlinea.udea.edu.co
4. Wikipédia. Méthode Gauss-Seidel. Récupéré de: en. wikipedia.com
5. Wikipédia. Méthode Gauss-Seidel. Récupéré de: es.wikipedia.com