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 !)
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.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres