Méthode de Gauss-Seidel (convergence)

Bonjour à tous,

J'ai un petit problème dans la preuve de la convergence de la méthode de Gauss-Seidel (cas ou $A$ est symétrique définie positive) ; il s'agit d'abord de démontrer le lemme suivant (qui constitue la quasi-totalité de la preuve) :

Lemme : Soit $A\in S_n^{++} (\mathbb{R} )$. Alors la méthode itérative associée à la décomposition $(M,N)$ (i.e. telle que $A=M-N$) vérifie ${}^t M+N \in S_n (\mathbb{R} )$. Si de plus ${}^t M+N \in S_n^{++} (\mathbb{R} )$, alors la méthode converge.

Démonstration : Montrer que ${}^t M+N \in S_n (\mathbb{R} )$ ne présente aucune difficulté. On suppose maintenant que ${}^t M+N \in S_n^{++} (\mathbb{R} )$. Comme $A$ est définie positive, on considère son produit scalaire associé $<\cdot , \cdot >_A = <A \cdot , \cdot >$ et $|| \cdot ||_A$ sa norme. Prenant $v\in \mathbb{R}^n$ tel que $||v||_A=1$, on trouve en remplaçant N par M puis en développant et simplifiant avec $w=AM^{-1}v$ :

$$||M^{-1}Nv||_A=AM^{-1}v]=1-<({}^t M+N)w,w>$$

Le terme $<({}^t M+N)w,w>$ étant strictement positif puisqu'on a supposé que ${}^t M+N \in S_n^{++} (\mathbb{R} )$, on a alors $||M^{-1}Nv||_A<1$ , $ \forall v \in \mathbb{R}^n$ tel que $||v||_A=1$.
Seulement pour conclure il faudrait avoir $|||M^{-1}N|||_A <1$ (dans quel cas on montre rapidement, par multiplicativité d'une norme subordonnée, que l'erreur tend vers 0 et donc la méthode converge) mais sauf erreur de ma part, passer au sup transforme les inégalités strictes en larges, donc $|||M^{-1}N|||_A^k$ ne tend plus vers 0 lorsque $k\rightarrow + \infty$.
Il me semble qu'on peut cependant bel et bien montrer de cette façon que $|||M^{-1}N|||_A <1$ donc si quelqu'un sait comment, merci de partager :-D

P.S : J'ai regardé la démonstration (à peu près similaire) faite dans Analyse numérique - Algorithme et étude mathématique, F. Filbet (p.42) mais il me semble que la preuve comporte une erreur puisque on y utilise que $\sup (1-f(x))=1-\sup( f(x) )$ (à noter que l'erreur peut aussi venir de mon éventuelle mauvaise lecture et que je ne remet en aucun cas en question les qualités de l'auteur !)

Réponses

  • Tout simplement tu as choisis une mauvaise norme, il faut choisir une norme matricielle |||.||| tel que $|||M^{-1}N|||<1$ ( une autre façon pour démontrer la convergence est de démontrer que le rayon spectrale de $M^{-1}N$ est <1)
    Le 😄 Farceur


  • Dans ce cas auriez-vous une norme vérifiant cette inégalité svp ? Oui on peut aussi avec le rayon spectral mais en montrant que la norme est $<1$ on peut directement montrer que l'erreur tend vers 0 sans utiliser le théorème de convergence en fonction du rayon spectral (c'est juste pour avoir une preuve auto-suffisante un peu plus courte).
  • Tu peux prendre cette norme: si $B=b_{ij}$ $$ ||B||=\max_{1\leq i\leq n}\sum_{j=1}^n |b_{ij}|$$
    Si $B=M^{-1}N$, démontre $\forall 1\leq i\leq n$ que $$\sum_{j=1}^n |b_{ij}|<1$$ et passe au $\max$ :-)
    Le 😄 Farceur


  • Ok super merci :-D bonne soirée !
Connectez-vous ou Inscrivez-vous pour répondre.