Algorithme de Gauss-Seidel et décomposition de Cholesky

Bonjour à tous,

J'ai vu en cours d'analyse (numérique) l'algorithme de Gauss-Seidel et la décomposition de Cholesky et j'aurais une question pour ces deux méthodes. Quelles sont les conditions d'applications ? Si j'ai bien compris, pour Gauss-Seidel, il faut que le système soit dominant c'est-à-dire que le terme sur la diagonale est strictement supérieur en valeur absolue à la somme des autres termes. Par exemple, pour le système

Concernant la décomposition de Cholesky, la condition est que ma matrice soit définie positive. Pour le montrer, suis-je obligé de calculer ses valeurs propres ? (Je suppose que oui…) D'ailleurs, si on a une matrice symétrique avec les coefficients sur la diagonale qui sont positifs, y a pas quelque chose à dire encore?

Merci ! Edit: Plus besoin de réponse. J'ai eu la mienne par quelqu'un.

Ce dont je me souviens:

Gauss-Seidel est une méthode itérative de résolution avec une complexité de " $ O(N^{2}) $ " par étape. Elle converge relativement rapidement (d'autant plus si une des valeurs propres est grande) et est surtout efficace avec des matrices creuses. Cette méthode est analogue à Jacobi et nécessitent toutes deux qu'il y ait une diagonale dominante stricte et, il me semble que Gauss-Seidel converge également pour les matrices définies positives et symétriques et est plus rapide que Jacobi.

Une matrice est à diagonale dominante (stricte si ce sont des $ \gt $) si:

• $ | a_{ii} | \geq \sum_{j=1, j \neq i}^{n} | a_{ij} | $ (par ligne)
• $ | a_{ii} | \geq \sum_{j=1, j \neq i}^{n} | a_{ji} | $ (par colonne) Donc, ta matrice est bien dominante (par colonne) car $ 5 > 1 $ et $ 2 > -5 $.

Quant à Cholesky, elle s'applique aux matrices symétriques et définies positives. Cette condition est respectée si une des ces propriétés est vraie:

• $ (Ax, x) > 0 \forall x \in \mathbb{R^{n}} x \neq 0 $.
• Les valeurs propres des sous-matrices principales sont toutes positives (critère de Sylvester).
• Les mineurs principaux sont tous positifs.
• Il existe une matrice inversible telle que $ A = H H^{T} $ qui est utilisée dans l'algorithme.

Le bénéfice principale de cette méthode est qu'elle est plus rapide que LU ou Gauss " $ O(N^{3}/3) $ " et qu'elle consomme moins de mémoire. Reste qu'il est peu pratique de déterminer si une matrice est positive … Seulement, il existe le théorème de Gerschgorin qui donne une bonne approximation des valeurs propres; À ma connaissance, il n'existe pas de moyen simple, le mieux est de connaître le problème originel ou d'appliquer bêtement l'algorithme qui risque de planter si il doit calculer la racine carrée d'un nombre négatif ;-). Si les coefficients sur la diagonale sont positifs, il y a d'autant plus de chance qu'elle soit définie positive. Je ne vois pas ce qu'on pourrait en dire de plus ?

Une technique pour vérifier que tu peux appliquer Cholesky est de vérifier que le déterminant de toutes les sous matrices construites en enlevant successivement la premiere colonne et la premiere ligne est positif.