$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Algèbre > Algèbre linéaire > Matrices >
Dictionnaire de mathématiques > Analyse > Analyse numérique >

Méthode de Gauss-Seidel

  La méthode de Gauss-Seidel est une méthode pour résoudre les systèmes linéaires Ax=b, où A est une matrice n×n et x,b sont des vecteurs de Rn. Elle consiste en la manipulation suivante : on décompose A comme A=D-E-F, où D est une matrice diagonale, -E est une matrice triangulaire inférieure, et -F est une matrice triangulaire supérieure.
  On peut alors transformer le système en
On définit ensuite une suite de vecteurs (xk) par la formule
et on espère que la suite (xk) converge vers une solution de Ax=b. Sous de bonnes hypothèses concernant la matrice A, c'est effectivement le cas.
Théorème : Si A est une matrice symétrique définie positive, alors la suite (xk) converge vers l'unique solution de Ax=b.
  Cette méthode appelle plusieurs commentaires. Le premier est qu'on peut se demander pourquoi on a besoin d'une méthode qui donne une solution approchée à une équation, alors qu'on dispose d'un algorithme (le pivot de Gauss) qui donne en un temps raisonnable (de l'ordre de n3 opérations) une solution exacte. Il se trouve que le pivot de Gauss est numériquement instable. Les erreurs de calcul de l'ordinateur s'accumulent et font que la solution que l'on calcule est parfois très éloignée de la solution exacte. La convergence de la méthode de Gauss-Seidel est fondée sur le théorème du point fixe, et cette méthode a moins ce défaut.

  Ensuite, il faut vérifier que la suite (xk) est facilement calculable. Mais comme (D-E) est une matrice triangulaire inférieure, elle n'est pas du tout difficile à inverser, et on a la formule suivante pour calculer xk+1 :
Cette formule montre que la méthode de Gauss-Seidel est une amélioration de la méthode de Jacobi. Dans la méthode de Jacobi, la relation de récurrence est :
L'avantage de la méthode de Gauss-Seidel est que, pour calculer xik+1, on utilise les valeurs déjà calculées de xjk+1, pour j<i, au lieu de xjk comme dans la méthode de Jacobi.

  La méthode de Gauss-Seidel est un cas particulier des méthodes de relaxation.
Consulter aussi...