Gauss seidellllll

[said2808]

la theorie de gauss seidel

introduction
La méthode de Gauss-Seidel est une méthode itérative de résolution d'un système linéaire (de dimension finie) de la forme , 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 est symétrique définie positive). L'algorithme suppose que la diagonale de 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, 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

le système linéaire à résoudre, que l'on suppose écrit sous forme matricielle avec et , ce qui signifie que l'on cherche tel que le produit matriciel soit égal à .
On note les éléments de et ceux de :

La méthode de Gauss-Seidel résout le système linéaire de manière itérative, ce qui veut dire qu'elle génère une suite de vecteurs , pour . On interrompt le calcul de la suite lorsque l'itéré courant, disons , est jugé suffisamment proche d'une solution, par exemple parce que le résidu est petit.
Soit l'itéré courant. L'itéré suivant se calcule en étapes, comme suit.

• ةtape 1. Si l'on suppose que et connaissant , on peut calculer au moyen de la première équation du système linéaire . De manière plus précise, est pris comme solution de
  
  ce qui est possible si .
• ةtape 2. Si l'on suppose que et connaissant , on peut calculer au moyen de la deuxième équation du système linéaire . De manière plus précise, est pris comme solution de
  
  ce qui est possible si .
• ةtape (cas général). Si l'on suppose que et connaissant , on peut calculer au moyen de la -ième équation du système linéaire . De manière plus précise, est pris comme solution de
  
  ce qui est possible si .

En résumé, pourvu que les éléments diagonaux de soient non nuls, on calcule les composantes de de manière séquentielle pour par

La formule fait intervenir les éléments () calculés dans les étapes précédentes

Expression matricielle
.

L'expression matricielle de l'algorithme suppose que la matrice se décompose comme suit

où est la partie diagonale de , (pour lower) sa partie triangulaire inférieure stricte et (pour upper) sa partie triangulaire supérieure stricte.
Une itération de la méthode de Gauss-Seidel, celle passant de à , consiste alors à résoudre le système triangulaire inférieur

de « haut en bas », c'est-à-dire en déterminant successivement , , ..., .

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 pour le calcul d'un point fixe de l'application

Les propriétés de convergence de la méthode vont donc dépendre du spectre de la matrice .
On sait que la méthode de Gauss-Seidel converge, quels que soient le vecteur et le point initial , dans les situations suivantes :

• si la matrice est symétrique définie positive1,
• si A est strictement diagonalement dominante

Erreur▲

A chaque itération, le vecteur trouvé x(k+1) comporte une certaine erreur :
On pose P = D +L -1U . Il vient alors :

• 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 par des sous-matrices de , appelées ici des blocs.
  On suppose que l'ensemble des indices est partitionné en sous-intervalles (non vides et deux-à-deux disjoints) :
  
  
  La matrice et le vecteur sont alors décomposés comme suit
  
  
  où est la sous-matrice de obtenue en sélectionnant les éléments avec indices de ligne dans et indices de colonnes dans , tandis que est le sous-vecteur de obtenu en sélectionnant les éléments avec indices dans .
  La méthode de Gauss-Seidel par blocs suppose que les sous-matrices principales , avec , sont inversibles.
  Une itération de la méthode de Gauss-Seidel par blocs, celle passant de à , s'écrit de la même manière que la méthode élément par élément, à savoir
  
  
  mais avec des définitions différentes de , et :
  
  
  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
• , , ..., .
  
• 
  .

Remarques

1. Si l'on applique ce résultat au cas où et est la fonction quadratique , on retrouve le résultat affirmant que la méthode de Gauss-Seidel par blocs pour résoudre le système linéaire converge, quels que soient le vecteur et le point initial, pourvu que soit définie positive.
2. 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 dans chaque problème intermédiaire et ces minimisations doivent être réalisées à chaque itération. Son application est donc restreinte au cas où le nombre de blocs est petit.
3. 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 sur l'ensemble , qui n'est pas le produit cartésien de deux intervalles, tout point de la frontière de est bloquant (c'est-à-dire que l'algorithme ne peut y progresser), alors que seul le point est solution.
4. En l'absence de convexité, la méthode de Gauss-Seidel ne converge pas nécessairement, même pour des fonctions de classe . 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 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▲

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

Le système à résoudre peut alors s'écrire :

d'où l'on tire la formule de récurrence :

qui permet de calculer les composantes de x(k+1) lorsque celles de x sont connues :

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
https://m2matlabdb.ma.tum.de/gauss_seidel.m?MP_ID=406

[aymen.dz]

شكراا

لوكانت الترجمة للطريقية أفضل

[Basma Bed]

شكرا جزيلا
بصح على حساب ما سمعت الطريقة غير مقررة علينا

[said2808]

le programme dans matlab avec un example-


https://people.whitman.edu/~hundledr/...aussSeidel.pdf