said2808
2014-04-04, 18:20
la theorie de gauss seidel
introduction
La méthode de Gauss (http://fr.wikipedia.org/wiki/Gauss)-Seidel (http://fr.wikipedia.org/wiki/Philipp_Ludwig_von_Seidel) est une méthode itérative (http://fr.wikipedia.org/wiki/M%C3%A9thode_it%C3%A9rative) de résolution d'un système linéaire (http://fr.wikipedia.org/wiki/Syst%C3%A8me_d%27%C3%A9quations_lin%C3%A9aires) (de dimension finie) de la forme http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png, ce qui signifie qu'elle génère une suite qui converge vers une solution de cette équation, lorsque celle-ci en a une et lorsque des conditions de convergence sont satisfaites (par exemple lorsque http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png est symétrique définie positive (http://fr.wikipedia.org/wiki/Matrice_d%C3%A9finie_positive)). L'algorithme suppose que la diagonale de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png est formée d'éléments non nuls.
La méthode se décline en une version « par blocs ».
Le principe de la méthode peut s'étendre à la résolution de systèmes d'équations non linéaires et à l'optimisation (http://fr.wikipedia.org/wiki/Optimisation_%28math%C3%A9matiques%29), mais avec des conditions d'efficacité moins claires. En optimisation, l'utilité de cette approche dépendra beaucoup de la structure du problème. Le principe gauss-seidelien permet aussi d'interpréter d'autres algorithmes.
L'algorithme
Principe
Soit
http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png
le système linéaire à résoudre, que l'on suppose écrit sous forme matricielle avec http://upload.wikimedia.org/math/f/e/c/fec898e5dc450dfb6dbfd022f645c474.png et http://upload.wikimedia.org/math/d/c/7/dc74c04af586c3f949ea5f937d4e52db.png, ce qui signifie que l'on cherche http://upload.wikimedia.org/math/4/a/a/4aa201b107abcf4fd598de23c60de147.png tel que le produit matriciel http://upload.wikimedia.org/math/b/0/c/b0ccc5b307c4fbd404351d1c78b3546b.png soit égal à http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png.
On note http://upload.wikimedia.org/math/5/f/e/5fe0de05a0584639c658a0815efccce9.png les éléments de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png et http://upload.wikimedia.org/math/c/9/f/c9f6d8557ce40f989fa727b5c0bb1ddf.png ceux de http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png :
http://upload.wikimedia.org/math/9/d/3/9d35636a322eac1983477f347c0931d2.png
La méthode de Gauss-Seidel résout le système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png de manière itérative (http://fr.wikipedia.org/wiki/M%C3%A9thode_it%C3%A9rative), ce qui veut dire qu'elle génère une suite de vecteurs http://upload.wikimedia.org/math/3/e/3/3e304031a5e96a9650a89ff270ff1699.png, pour http://upload.wikimedia.org/math/6/b/3/6b30ae7e10662df13902e832c3db2353.png. On interrompt le calcul de la suite lorsque l'itéré (http://fr.wikipedia.org/wiki/M%C3%A9thode_it%C3%A9rative) courant, disons http://upload.wikimedia.org/math/c/6/2/c625f384a03b783ea943d1eba4e32877.png, est jugé suffisamment proche d'une solution, par exemple parce que le résidu http://upload.wikimedia.org/math/e/f/5/ef51ffb9d5e56a3286e628e59da15b2c.png est petit.
Soit http://upload.wikimedia.org/math/f/6/8/f68bc8be02f05678ad6e0bc0392812f7.png l'itéré courant. L'itéré suivant http://upload.wikimedia.org/math/0/e/f/0ef90dfae5638a2b08633c2a0eed7628.png se calcule en http://upload.wikimedia.org/math/7/b/8/7b8b965ad4bca0e41ab51de7b31363a1.png étapes, comme suit.
Étape 1. Si l'on suppose que http://upload.wikimedia.org/math/d/0/d/d0d81a26af74dd9ed4421b56fa09a0a2.png et connaissant http://upload.wikimedia.org/math/a/3/0/a30704567b72064157666825851025c9.png, on peut calculer http://upload.wikimedia.org/math/5/1/b/51bca777dba9546f4c929bb02141bddc.png au moyen de la première équation du système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png. De manière plus précise, http://upload.wikimedia.org/math/5/1/b/51bca777dba9546f4c929bb02141bddc.png est pris comme solution de
http://upload.wikimedia.org/math/b/9/1/b91692960922999b85f1204a825e64eb.png
ce qui est possible si http://upload.wikimedia.org/math/d/0/d/d0d81a26af74dd9ed4421b56fa09a0a2.png.
Étape 2. Si l'on suppose que http://upload.wikimedia.org/math/c/c/9/cc96ea49f0753d3672fdf070455f50cf.png et connaissant http://upload.wikimedia.org/math/6/c/8/6c8138159010836db0f8c10ba3421315.png, on peut calculer http://upload.wikimedia.org/math/b/9/a/b9ab359a6f1b210aebc77492830fa76f.png au moyen de la deuxième équation du système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png. De manière plus précise, http://upload.wikimedia.org/math/b/9/a/b9ab359a6f1b210aebc77492830fa76f.png est pris comme solution de
http://upload.wikimedia.org/math/4/f/9/4f9be571ad19ecb99eb01e38781ac19d.png
ce qui est possible si http://upload.wikimedia.org/math/c/c/9/cc96ea49f0753d3672fdf070455f50cf.png.
Étape http://upload.wikimedia.org/math/4/6/b/46b136e3a4f7751130e28399b4ee24d5.png (cas général). Si l'on suppose que http://upload.wikimedia.org/math/8/0/9/809556c7175b4aac7de9530b19e1d650.png et connaissant http://upload.wikimedia.org/math/d/a/0/da0aeab2436f9f4bf8910150a6c3ba48.png, on peut calculer http://upload.wikimedia.org/math/1/7/0/17064a86bc2cbf01a01255fb489ed6fb.png au moyen de la http://upload.wikimedia.org/math/8/6/5/865c0c0b4ab0e063e5caa3387c1a8741.png-ième équation du système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png. De manière plus précise, http://upload.wikimedia.org/math/1/7/0/17064a86bc2cbf01a01255fb489ed6fb.png est pris comme solution de
http://upload.wikimedia.org/math/9/1/b/91bb7374b019a7197e765a9123cae484.png
ce qui est possible si http://upload.wikimedia.org/math/8/0/9/809556c7175b4aac7de9530b19e1d650.png.
En résumé, pourvu que les éléments diagonaux de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png soient non nuls, on calcule les composantes http://upload.wikimedia.org/math/1/7/0/17064a86bc2cbf01a01255fb489ed6fb.png de http://upload.wikimedia.org/math/8/d/0/8d004c3b4dd121d954c21074c7a2055c.png de manière séquentielle pour http://upload.wikimedia.org/math/0/c/c/0ccf5455d21e83c396573de9c87adc07.png par
http://upload.wikimedia.org/math/4/e/a/4eac1d335750c936e3efd5cbc5544225.png
La formule fait intervenir les éléments http://upload.wikimedia.org/math/2/e/c/2ec74392e7cc73d0bb6d3d4a3972f6a8.png (http://upload.wikimedia.org/math/3/a/a/3aa20632eb8a938a921a8f3fd20e0149.png) calculés dans les étapes précédentes
Expression matricielle
.
L'expression matricielle de l'algorithme suppose que la matrice http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png se décompose comme suit
http://upload.wikimedia.org/math/d/a/a/daaa227d203763c8a8b359991e5f680b.png
où http://upload.wikimedia.org/math/f/6/2/f623e75af30e62bbd73d6df5b50bb7b5.png est la partie diagonale (http://fr.wikipedia.org/wiki/Matrice_diagonale) de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png, http://upload.wikimedia.org/math/d/2/0/d20caec3b48a1eef164cb4ca81ba2587.png (pour lower) sa partie triangulaire (http://fr.wikipedia.org/wiki/Matrice_triangulaire) inférieure stricte et http://upload.wikimedia.org/math/4/c/6/4c614360da93c0a041b22e537de151eb.png (pour upper) sa partie triangulaire supérieure stricte.
Une itération de la méthode de Gauss-Seidel, celle passant de http://upload.wikimedia.org/math/c/6/2/c625f384a03b783ea943d1eba4e32877.png à http://upload.wikimedia.org/math/8/d/0/8d004c3b4dd121d954c21074c7a2055c.png, consiste alors à résoudre le système triangulaire inférieur
http://upload.wikimedia.org/math/2/b/0/2b05158d1356e76df600c7b1532b9a75.png
de « haut en bas », c'est-à-dire en déterminant successivement http://upload.wikimedia.org/math/5/1/b/51bca777dba9546f4c929bb02141bddc.png, http://upload.wikimedia.org/math/b/9/a/b9ab359a6f1b210aebc77492830fa76f.png, ..., http://upload.wikimedia.org/math/7/b/e/7be6ab85ecf86b813d4b6b74b6688751.png.
Convergence
La formule de mise à jour des itérés dans la méthode de Gauss-Seildel montre que ceux-ci sont des approximations successives (http://fr.wikipedia.org/wiki/Application_contractante#Approximations_successive s) pour le calcul d'un point fixe (http://fr.wikipedia.org/wiki/Point_fixe) de l'application
http://upload.wikimedia.org/math/0/0/9/0096b61589fb3c833c1f95c1bd44501b.png
Les propriétés de convergence de la méthode vont donc dépendre du spectre (http://fr.wikipedia.org/wiki/Spectre_d%27un_op%C3%A9rateur_lin%C3%A9aire) de la matrice http://upload.wikimedia.org/math/7/4/4/744564aa28aa7c8fc0bee28774c574a0.png.
On sait que la méthode de Gauss-Seidel converge, quels que soient le vecteur http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png et le point initial http://upload.wikimedia.org/math/5/9/b/59b95a7f867ce9d4e0f0b5f86f1260ff.png, dans les situations suivantes :
si la matrice http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png est symétrique définie positive (http://fr.wikipedia.org/wiki/Matrice_d%C3%A9finie_positive)1 (http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Gauss-Seidel#cite_note-1),
si A est strictement diagonalement dominante (http://fr.wikipedia.org/wiki/Matrice_%C3%A0_diagonale_dominante)
Erreur▲ (http://jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4#)
A chaque itération, le vecteur trouvé x(k+1) comporte une certaine erreur :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01007.gif On pose P = D +L -1U . Il vient alors :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01008.gif
Généralisations
Méthode par blocs
La version par blocs de la méthode de Gauss-Seidel procède de manière similaire à la méthode élément par élément, mais en remplaçant l'utilisation des éléments de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png par des sous-matrices de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png, appelées ici des blocs.
On suppose que l'ensemble des indices http://upload.wikimedia.org/math/1/5/e/15e8ad5c5ac20817faaaa2b8eb085121.png est partitionné en http://upload.wikimedia.org/math/8/3/8/83878c91171338902e0fe0fb97a8c47a.png sous-intervalles (non vides et deux-à-deux disjoints) :
http://upload.wikimedia.org/math/e/8/f/e8f7500ea39cf6bc4e3e0b797a0ca516.png
La matrice http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png et le vecteur http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png sont alors décomposés comme suit
http://upload.wikimedia.org/math/4/1/e/41ec86ba42b7d6c09e2d2e6f48893234.png
où http://upload.wikimedia.org/math/d/7/6/d7655c36ed7f2bf0df666b83410ff1c7.png est la sous-matrice de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png obtenue en sélectionnant les éléments avec indices de ligne dans http://upload.wikimedia.org/math/d/d/7/dd7536794b63bf90eccfd37f9b147d7f.png et indices de colonnes dans http://upload.wikimedia.org/math/f/f/4/ff44570aca8241914870afbc310cdb85.png, tandis que http://upload.wikimedia.org/math/9/6/a/96aa1cc74c4fb6f18ae0f4b7fbc079a8.png est le sous-vecteur de http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png obtenu en sélectionnant les éléments avec indices dans http://upload.wikimedia.org/math/d/d/7/dd7536794b63bf90eccfd37f9b147d7f.png.
La méthode de Gauss-Seidel par blocs suppose que les sous-matrices principales http://upload.wikimedia.org/math/8/2/2/82253ae69887553bbc6e94049e476ccf.png, avec http://upload.wikimedia.org/math/a/a/f/aafbf2ef2fb783c41f4809b5f7b20942.png, sont inversibles.
Une itération de la méthode de Gauss-Seidel par blocs, celle passant de http://upload.wikimedia.org/math/c/6/2/c625f384a03b783ea943d1eba4e32877.png à http://upload.wikimedia.org/math/8/d/0/8d004c3b4dd121d954c21074c7a2055c.png, s'écrit de la même manière que la méthode élément par élément, à savoir
http://upload.wikimedia.org/math/2/b/0/2b05158d1356e76df600c7b1532b9a75.png
mais avec des définitions différentes de http://upload.wikimedia.org/math/d/2/0/d20caec3b48a1eef164cb4ca81ba2587.png, http://upload.wikimedia.org/math/f/6/2/f623e75af30e62bbd73d6df5b50bb7b5.png et http://upload.wikimedia.org/math/4/c/6/4c614360da93c0a041b22e537de151eb.png :
La résolution du système triangulaire par blocs ci-dessus, se fait également de « haut en bas », c'est-à-dire en déterminant successivement
http://upload.wikimedia.org/math/6/6/d/66de92db43b3ff0e116e5aad90a5537c.png, http://upload.wikimedia.org/math/c/4/5/c452a621c88db4f7b07927f074880969.png, ..., http://upload.wikimedia.org/math/a/3/5/a35daffe4fcf394a1e8820ce869f06ad.png.
.
Remarques
Si l'on applique ce résultat au cas où http://upload.wikimedia.org/math/2/2/9/229293d442f08bdc40c7b605828e2e5d.png et http://upload.wikimedia.org/math/8/f/a/8fa14cdd754f91cc6554c9e71929cce7.png est la fonction quadratique http://upload.wikimedia.org/math/8/4/f/84f86b920fd7098d226404cc5e92fb0c.png, on retrouve le résultat affirmant que la méthode de Gauss-Seidel par blocs pour résoudre le système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png converge, quels que soient le vecteur http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png et le point initial, pourvu que http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png soit définie positive.
La méthode de Gauss-Seidel est un algorithme lent (il requiert beaucoup d'itérations), dont la mise en œuvre est coûteuse (chaque itération peut demander beaucoup de temps de calcul, selon les cas). Tel qu'il est présenté, il requiert en effet la minimisation exacte de http://upload.wikimedia.org/math/8/f/a/8fa14cdd754f91cc6554c9e71929cce7.png dans chaque problème intermédiaire et ces http://upload.wikimedia.org/math/8/3/8/83878c91171338902e0fe0fb97a8c47a.png minimisations doivent être réalisées à chaque itération. Son application est donc restreinte au cas où le nombre de blocs est petit.
L'algorithme de Gauss-Seidel ne s'étend pas aisément à des ensembles admissibles plus complexes qu'un produit cartésien d'ensembles convexes. Par exemple si l'on cherche à minimiser composante par composante la fonction linéaire http://upload.wikimedia.org/math/1/4/5/145952e247cf18b9b5631f9bc14b4ec0.png sur l'ensemble http://upload.wikimedia.org/math/7/f/f/7ff4d8984fa5e6e83a57e237124e1b20.png, qui n'est pas le produit cartésien de deux intervalles, tout point de la frontière de http://upload.wikimedia.org/math/0/2/1/02129bb861061d1a052c592e2dc6b383.png est bloquant (c'est-à-dire que l'algorithme ne peut y progresser), alors que seul le point http://upload.wikimedia.org/math/1/8/7/1877765384614f8203dc3ac82c78fe33.png est solution.
En l'absence de convexité, la méthode de Gauss-Seidel ne converge pas nécessairement, même pour des fonctions de classe http://upload.wikimedia.org/math/0/c/5/0c582a21481872f0a89dcc6a3c224581.png. Powell (1973) a en effet construit plusieurs fonctions conduisant à la non-convergence de la méthode de Gauss-Seidel composante par composante, notamment une fonction http://upload.wikimedia.org/math/0/c/5/0c582a21481872f0a89dcc6a3c224581.png de trois variables pour laquelle les itérés générés ont un cycle limite formé de 6 points auxquels le gradient n'est pas nul.
D'autres résultats de convergence sont donnés par Luo et Tseng (1992
)
Methode de gauss seidel dans Matlab
;
L'algorithme et le programme de methode de gauss seidel dans Matlab;
:
Algorithme▲ (http://jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4#)
Un vecteur initial x(0) étant donné, l'algorithme suivant permet de déterminer les éléments successifs de la suite.
On décompose la matrice A en trois matrices L , D et U . La matrice L est constituée des termes qui se trouvent au-dessous de la diagonale principale de A(j < i) ; la matrice D contient les termes diagonaux de A(j = i) ; la matrice U est constituée des termes qui se trouvent au-dessus de la diagonale principale de A(j > i) .
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01003.gif (http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01003.gif)
Le système à résoudre peut alors s'écrire :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter02001.gif
d'où l'on tire la formule de récurrence :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter02002.gif
qui permet de calculer les composantes de x(k+1) lorsque celles de x sont connues :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01006.gif
On remarquera que chaque composante de x(k) n'est utilisée que jusqu'au calcul de la composante correspondante de x(k+1) . Ces deux vecteurs peuvent donc être stockés dans le même tableau.
le programme
function gauss_seidel(A, b, N)
Gauss_seidel (A, b, N) résoudre itérativement un système d'équations linéaires
de sorte que A est la matrice de coefficients, et b est le vecteur colonne de droite.
N est le nombre maximum d'itérations
Le procédé mis en oeuvre est le Gauss-Seidel itératif.
Le vecteur de départ est le vecteur nul, mais peut être ajustée à ses besoins.
La forme itérative est basée sur la matrice de transition / itération de Gauss-Seidel
Tg = inv (DL) * U et les constantes vecteur cg = inv (DL) * b.
La sortie est le vecteur solution x
. Ce fichier suit les directives données algorithmiques dans le livre
http://m2matlabdb.ma.tum.de/gauss_seidel.m?MP_ID=406
introduction
La méthode de Gauss (http://fr.wikipedia.org/wiki/Gauss)-Seidel (http://fr.wikipedia.org/wiki/Philipp_Ludwig_von_Seidel) est une méthode itérative (http://fr.wikipedia.org/wiki/M%C3%A9thode_it%C3%A9rative) de résolution d'un système linéaire (http://fr.wikipedia.org/wiki/Syst%C3%A8me_d%27%C3%A9quations_lin%C3%A9aires) (de dimension finie) de la forme http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png, ce qui signifie qu'elle génère une suite qui converge vers une solution de cette équation, lorsque celle-ci en a une et lorsque des conditions de convergence sont satisfaites (par exemple lorsque http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png est symétrique définie positive (http://fr.wikipedia.org/wiki/Matrice_d%C3%A9finie_positive)). L'algorithme suppose que la diagonale de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png est formée d'éléments non nuls.
La méthode se décline en une version « par blocs ».
Le principe de la méthode peut s'étendre à la résolution de systèmes d'équations non linéaires et à l'optimisation (http://fr.wikipedia.org/wiki/Optimisation_%28math%C3%A9matiques%29), mais avec des conditions d'efficacité moins claires. En optimisation, l'utilité de cette approche dépendra beaucoup de la structure du problème. Le principe gauss-seidelien permet aussi d'interpréter d'autres algorithmes.
L'algorithme
Principe
Soit
http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png
le système linéaire à résoudre, que l'on suppose écrit sous forme matricielle avec http://upload.wikimedia.org/math/f/e/c/fec898e5dc450dfb6dbfd022f645c474.png et http://upload.wikimedia.org/math/d/c/7/dc74c04af586c3f949ea5f937d4e52db.png, ce qui signifie que l'on cherche http://upload.wikimedia.org/math/4/a/a/4aa201b107abcf4fd598de23c60de147.png tel que le produit matriciel http://upload.wikimedia.org/math/b/0/c/b0ccc5b307c4fbd404351d1c78b3546b.png soit égal à http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png.
On note http://upload.wikimedia.org/math/5/f/e/5fe0de05a0584639c658a0815efccce9.png les éléments de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png et http://upload.wikimedia.org/math/c/9/f/c9f6d8557ce40f989fa727b5c0bb1ddf.png ceux de http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png :
http://upload.wikimedia.org/math/9/d/3/9d35636a322eac1983477f347c0931d2.png
La méthode de Gauss-Seidel résout le système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png de manière itérative (http://fr.wikipedia.org/wiki/M%C3%A9thode_it%C3%A9rative), ce qui veut dire qu'elle génère une suite de vecteurs http://upload.wikimedia.org/math/3/e/3/3e304031a5e96a9650a89ff270ff1699.png, pour http://upload.wikimedia.org/math/6/b/3/6b30ae7e10662df13902e832c3db2353.png. On interrompt le calcul de la suite lorsque l'itéré (http://fr.wikipedia.org/wiki/M%C3%A9thode_it%C3%A9rative) courant, disons http://upload.wikimedia.org/math/c/6/2/c625f384a03b783ea943d1eba4e32877.png, est jugé suffisamment proche d'une solution, par exemple parce que le résidu http://upload.wikimedia.org/math/e/f/5/ef51ffb9d5e56a3286e628e59da15b2c.png est petit.
Soit http://upload.wikimedia.org/math/f/6/8/f68bc8be02f05678ad6e0bc0392812f7.png l'itéré courant. L'itéré suivant http://upload.wikimedia.org/math/0/e/f/0ef90dfae5638a2b08633c2a0eed7628.png se calcule en http://upload.wikimedia.org/math/7/b/8/7b8b965ad4bca0e41ab51de7b31363a1.png étapes, comme suit.
Étape 1. Si l'on suppose que http://upload.wikimedia.org/math/d/0/d/d0d81a26af74dd9ed4421b56fa09a0a2.png et connaissant http://upload.wikimedia.org/math/a/3/0/a30704567b72064157666825851025c9.png, on peut calculer http://upload.wikimedia.org/math/5/1/b/51bca777dba9546f4c929bb02141bddc.png au moyen de la première équation du système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png. De manière plus précise, http://upload.wikimedia.org/math/5/1/b/51bca777dba9546f4c929bb02141bddc.png est pris comme solution de
http://upload.wikimedia.org/math/b/9/1/b91692960922999b85f1204a825e64eb.png
ce qui est possible si http://upload.wikimedia.org/math/d/0/d/d0d81a26af74dd9ed4421b56fa09a0a2.png.
Étape 2. Si l'on suppose que http://upload.wikimedia.org/math/c/c/9/cc96ea49f0753d3672fdf070455f50cf.png et connaissant http://upload.wikimedia.org/math/6/c/8/6c8138159010836db0f8c10ba3421315.png, on peut calculer http://upload.wikimedia.org/math/b/9/a/b9ab359a6f1b210aebc77492830fa76f.png au moyen de la deuxième équation du système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png. De manière plus précise, http://upload.wikimedia.org/math/b/9/a/b9ab359a6f1b210aebc77492830fa76f.png est pris comme solution de
http://upload.wikimedia.org/math/4/f/9/4f9be571ad19ecb99eb01e38781ac19d.png
ce qui est possible si http://upload.wikimedia.org/math/c/c/9/cc96ea49f0753d3672fdf070455f50cf.png.
Étape http://upload.wikimedia.org/math/4/6/b/46b136e3a4f7751130e28399b4ee24d5.png (cas général). Si l'on suppose que http://upload.wikimedia.org/math/8/0/9/809556c7175b4aac7de9530b19e1d650.png et connaissant http://upload.wikimedia.org/math/d/a/0/da0aeab2436f9f4bf8910150a6c3ba48.png, on peut calculer http://upload.wikimedia.org/math/1/7/0/17064a86bc2cbf01a01255fb489ed6fb.png au moyen de la http://upload.wikimedia.org/math/8/6/5/865c0c0b4ab0e063e5caa3387c1a8741.png-ième équation du système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png. De manière plus précise, http://upload.wikimedia.org/math/1/7/0/17064a86bc2cbf01a01255fb489ed6fb.png est pris comme solution de
http://upload.wikimedia.org/math/9/1/b/91bb7374b019a7197e765a9123cae484.png
ce qui est possible si http://upload.wikimedia.org/math/8/0/9/809556c7175b4aac7de9530b19e1d650.png.
En résumé, pourvu que les éléments diagonaux de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png soient non nuls, on calcule les composantes http://upload.wikimedia.org/math/1/7/0/17064a86bc2cbf01a01255fb489ed6fb.png de http://upload.wikimedia.org/math/8/d/0/8d004c3b4dd121d954c21074c7a2055c.png de manière séquentielle pour http://upload.wikimedia.org/math/0/c/c/0ccf5455d21e83c396573de9c87adc07.png par
http://upload.wikimedia.org/math/4/e/a/4eac1d335750c936e3efd5cbc5544225.png
La formule fait intervenir les éléments http://upload.wikimedia.org/math/2/e/c/2ec74392e7cc73d0bb6d3d4a3972f6a8.png (http://upload.wikimedia.org/math/3/a/a/3aa20632eb8a938a921a8f3fd20e0149.png) calculés dans les étapes précédentes
Expression matricielle
.
L'expression matricielle de l'algorithme suppose que la matrice http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png se décompose comme suit
http://upload.wikimedia.org/math/d/a/a/daaa227d203763c8a8b359991e5f680b.png
où http://upload.wikimedia.org/math/f/6/2/f623e75af30e62bbd73d6df5b50bb7b5.png est la partie diagonale (http://fr.wikipedia.org/wiki/Matrice_diagonale) de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png, http://upload.wikimedia.org/math/d/2/0/d20caec3b48a1eef164cb4ca81ba2587.png (pour lower) sa partie triangulaire (http://fr.wikipedia.org/wiki/Matrice_triangulaire) inférieure stricte et http://upload.wikimedia.org/math/4/c/6/4c614360da93c0a041b22e537de151eb.png (pour upper) sa partie triangulaire supérieure stricte.
Une itération de la méthode de Gauss-Seidel, celle passant de http://upload.wikimedia.org/math/c/6/2/c625f384a03b783ea943d1eba4e32877.png à http://upload.wikimedia.org/math/8/d/0/8d004c3b4dd121d954c21074c7a2055c.png, consiste alors à résoudre le système triangulaire inférieur
http://upload.wikimedia.org/math/2/b/0/2b05158d1356e76df600c7b1532b9a75.png
de « haut en bas », c'est-à-dire en déterminant successivement http://upload.wikimedia.org/math/5/1/b/51bca777dba9546f4c929bb02141bddc.png, http://upload.wikimedia.org/math/b/9/a/b9ab359a6f1b210aebc77492830fa76f.png, ..., http://upload.wikimedia.org/math/7/b/e/7be6ab85ecf86b813d4b6b74b6688751.png.
Convergence
La formule de mise à jour des itérés dans la méthode de Gauss-Seildel montre que ceux-ci sont des approximations successives (http://fr.wikipedia.org/wiki/Application_contractante#Approximations_successive s) pour le calcul d'un point fixe (http://fr.wikipedia.org/wiki/Point_fixe) de l'application
http://upload.wikimedia.org/math/0/0/9/0096b61589fb3c833c1f95c1bd44501b.png
Les propriétés de convergence de la méthode vont donc dépendre du spectre (http://fr.wikipedia.org/wiki/Spectre_d%27un_op%C3%A9rateur_lin%C3%A9aire) de la matrice http://upload.wikimedia.org/math/7/4/4/744564aa28aa7c8fc0bee28774c574a0.png.
On sait que la méthode de Gauss-Seidel converge, quels que soient le vecteur http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png et le point initial http://upload.wikimedia.org/math/5/9/b/59b95a7f867ce9d4e0f0b5f86f1260ff.png, dans les situations suivantes :
si la matrice http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png est symétrique définie positive (http://fr.wikipedia.org/wiki/Matrice_d%C3%A9finie_positive)1 (http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Gauss-Seidel#cite_note-1),
si A est strictement diagonalement dominante (http://fr.wikipedia.org/wiki/Matrice_%C3%A0_diagonale_dominante)
Erreur▲ (http://jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4#)
A chaque itération, le vecteur trouvé x(k+1) comporte une certaine erreur :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01007.gif On pose P = D +L -1U . Il vient alors :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01008.gif
Généralisations
Méthode par blocs
La version par blocs de la méthode de Gauss-Seidel procède de manière similaire à la méthode élément par élément, mais en remplaçant l'utilisation des éléments de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png par des sous-matrices de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png, appelées ici des blocs.
On suppose que l'ensemble des indices http://upload.wikimedia.org/math/1/5/e/15e8ad5c5ac20817faaaa2b8eb085121.png est partitionné en http://upload.wikimedia.org/math/8/3/8/83878c91171338902e0fe0fb97a8c47a.png sous-intervalles (non vides et deux-à-deux disjoints) :
http://upload.wikimedia.org/math/e/8/f/e8f7500ea39cf6bc4e3e0b797a0ca516.png
La matrice http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png et le vecteur http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png sont alors décomposés comme suit
http://upload.wikimedia.org/math/4/1/e/41ec86ba42b7d6c09e2d2e6f48893234.png
où http://upload.wikimedia.org/math/d/7/6/d7655c36ed7f2bf0df666b83410ff1c7.png est la sous-matrice de http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png obtenue en sélectionnant les éléments avec indices de ligne dans http://upload.wikimedia.org/math/d/d/7/dd7536794b63bf90eccfd37f9b147d7f.png et indices de colonnes dans http://upload.wikimedia.org/math/f/f/4/ff44570aca8241914870afbc310cdb85.png, tandis que http://upload.wikimedia.org/math/9/6/a/96aa1cc74c4fb6f18ae0f4b7fbc079a8.png est le sous-vecteur de http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png obtenu en sélectionnant les éléments avec indices dans http://upload.wikimedia.org/math/d/d/7/dd7536794b63bf90eccfd37f9b147d7f.png.
La méthode de Gauss-Seidel par blocs suppose que les sous-matrices principales http://upload.wikimedia.org/math/8/2/2/82253ae69887553bbc6e94049e476ccf.png, avec http://upload.wikimedia.org/math/a/a/f/aafbf2ef2fb783c41f4809b5f7b20942.png, sont inversibles.
Une itération de la méthode de Gauss-Seidel par blocs, celle passant de http://upload.wikimedia.org/math/c/6/2/c625f384a03b783ea943d1eba4e32877.png à http://upload.wikimedia.org/math/8/d/0/8d004c3b4dd121d954c21074c7a2055c.png, s'écrit de la même manière que la méthode élément par élément, à savoir
http://upload.wikimedia.org/math/2/b/0/2b05158d1356e76df600c7b1532b9a75.png
mais avec des définitions différentes de http://upload.wikimedia.org/math/d/2/0/d20caec3b48a1eef164cb4ca81ba2587.png, http://upload.wikimedia.org/math/f/6/2/f623e75af30e62bbd73d6df5b50bb7b5.png et http://upload.wikimedia.org/math/4/c/6/4c614360da93c0a041b22e537de151eb.png :
La résolution du système triangulaire par blocs ci-dessus, se fait également de « haut en bas », c'est-à-dire en déterminant successivement
http://upload.wikimedia.org/math/6/6/d/66de92db43b3ff0e116e5aad90a5537c.png, http://upload.wikimedia.org/math/c/4/5/c452a621c88db4f7b07927f074880969.png, ..., http://upload.wikimedia.org/math/a/3/5/a35daffe4fcf394a1e8820ce869f06ad.png.
.
Remarques
Si l'on applique ce résultat au cas où http://upload.wikimedia.org/math/2/2/9/229293d442f08bdc40c7b605828e2e5d.png et http://upload.wikimedia.org/math/8/f/a/8fa14cdd754f91cc6554c9e71929cce7.png est la fonction quadratique http://upload.wikimedia.org/math/8/4/f/84f86b920fd7098d226404cc5e92fb0c.png, on retrouve le résultat affirmant que la méthode de Gauss-Seidel par blocs pour résoudre le système linéaire http://upload.wikimedia.org/math/8/1/e/81e6d45a28385d9454465ee4551bd9c7.png converge, quels que soient le vecteur http://upload.wikimedia.org/math/9/2/e/92eb5ffee6ae2fec3ad71c777531578f.png et le point initial, pourvu que http://upload.wikimedia.org/math/7/f/c/7fc56270e7a70fa81a5935b72eacbe29.png soit définie positive.
La méthode de Gauss-Seidel est un algorithme lent (il requiert beaucoup d'itérations), dont la mise en œuvre est coûteuse (chaque itération peut demander beaucoup de temps de calcul, selon les cas). Tel qu'il est présenté, il requiert en effet la minimisation exacte de http://upload.wikimedia.org/math/8/f/a/8fa14cdd754f91cc6554c9e71929cce7.png dans chaque problème intermédiaire et ces http://upload.wikimedia.org/math/8/3/8/83878c91171338902e0fe0fb97a8c47a.png minimisations doivent être réalisées à chaque itération. Son application est donc restreinte au cas où le nombre de blocs est petit.
L'algorithme de Gauss-Seidel ne s'étend pas aisément à des ensembles admissibles plus complexes qu'un produit cartésien d'ensembles convexes. Par exemple si l'on cherche à minimiser composante par composante la fonction linéaire http://upload.wikimedia.org/math/1/4/5/145952e247cf18b9b5631f9bc14b4ec0.png sur l'ensemble http://upload.wikimedia.org/math/7/f/f/7ff4d8984fa5e6e83a57e237124e1b20.png, qui n'est pas le produit cartésien de deux intervalles, tout point de la frontière de http://upload.wikimedia.org/math/0/2/1/02129bb861061d1a052c592e2dc6b383.png est bloquant (c'est-à-dire que l'algorithme ne peut y progresser), alors que seul le point http://upload.wikimedia.org/math/1/8/7/1877765384614f8203dc3ac82c78fe33.png est solution.
En l'absence de convexité, la méthode de Gauss-Seidel ne converge pas nécessairement, même pour des fonctions de classe http://upload.wikimedia.org/math/0/c/5/0c582a21481872f0a89dcc6a3c224581.png. Powell (1973) a en effet construit plusieurs fonctions conduisant à la non-convergence de la méthode de Gauss-Seidel composante par composante, notamment une fonction http://upload.wikimedia.org/math/0/c/5/0c582a21481872f0a89dcc6a3c224581.png de trois variables pour laquelle les itérés générés ont un cycle limite formé de 6 points auxquels le gradient n'est pas nul.
D'autres résultats de convergence sont donnés par Luo et Tseng (1992
)
Methode de gauss seidel dans Matlab
;
L'algorithme et le programme de methode de gauss seidel dans Matlab;
:
Algorithme▲ (http://jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4#)
Un vecteur initial x(0) étant donné, l'algorithme suivant permet de déterminer les éléments successifs de la suite.
On décompose la matrice A en trois matrices L , D et U . La matrice L est constituée des termes qui se trouvent au-dessous de la diagonale principale de A(j < i) ; la matrice D contient les termes diagonaux de A(j = i) ; la matrice U est constituée des termes qui se trouvent au-dessus de la diagonale principale de A(j > i) .
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01003.gif (http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01003.gif)
Le système à résoudre peut alors s'écrire :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter02001.gif
d'où l'on tire la formule de récurrence :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter02002.gif
qui permet de calculer les composantes de x(k+1) lorsque celles de x sont connues :
http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01006.gif
On remarquera que chaque composante de x(k) n'est utilisée que jusqu'au calcul de la composante correspondante de x(k+1) . Ces deux vecteurs peuvent donc être stockés dans le même tableau.
le programme
function gauss_seidel(A, b, N)
Gauss_seidel (A, b, N) résoudre itérativement un système d'équations linéaires
de sorte que A est la matrice de coefficients, et b est le vecteur colonne de droite.
N est le nombre maximum d'itérations
Le procédé mis en oeuvre est le Gauss-Seidel itératif.
Le vecteur de départ est le vecteur nul, mais peut être ajustée à ses besoins.
La forme itérative est basée sur la matrice de transition / itération de Gauss-Seidel
Tg = inv (DL) * U et les constantes vecteur cg = inv (DL) * b.
La sortie est le vecteur solution x
. Ce fichier suit les directives données algorithmiques dans le livre
http://m2matlabdb.ma.tum.de/gauss_seidel.m?MP_ID=406