Gradient conjugué : convergence
Bonjour tout le monde
Afin de résoudre le problème : $\quad
A x=b
$
Avec $A$ matrice symétrique définie positive, on pose
$$
\Phi(x):=\frac{1}{2}\langle A x, x\rangle-\langle b, x\rangle.
$$ Alors $\Phi(\ell)=\min \Phi(x) \Leftrightarrow A \ell=b.$
J'ai trouvé un théorème qui dit qu'en appliquant la méthode du gradient conjugué sur $\Phi$, le nombre d'itérations pour converger est égal au nombre des valeurs propres distinctes de $A$.
Pour cela je cherche a savoir comment démontrer un tel résultat.
Afin de résoudre le problème : $\quad
A x=b
$
Avec $A$ matrice symétrique définie positive, on pose
$$
\Phi(x):=\frac{1}{2}\langle A x, x\rangle-\langle b, x\rangle.
$$ Alors $\Phi(\ell)=\min \Phi(x) \Leftrightarrow A \ell=b.$
J'ai trouvé un théorème qui dit qu'en appliquant la méthode du gradient conjugué sur $\Phi$, le nombre d'itérations pour converger est égal au nombre des valeurs propres distinctes de $A$.
Pour cela je cherche a savoir comment démontrer un tel résultat.
Réponses
-
Es-tu certain de ce théorème ? Car de mémoire, il me semble que la convergence n'est pas très bonne si la matrice est mal conditionnée.
-
Oui, mais n'oublions pas que A est symétrique définie positive
-
C'est évident lorsque on sait notre cours. Si ta matrice est d'ordre n et si ces valeurs propres sont distinctes deux à deux, elles sont en nombres n. Le théorème 1 répond à ta question http://perso.unifr.ch/ales.janka/numeroptim/07_conjgrad.pdfLe 😄 Farceur
-
Oui c'est bien évident lorsque tous ses valeurs propres sont distinctes, mais le plus intéressant c'est comment assurer la convergence en nombres d'itérations égal au cardinal du spectre de $A$ sachant que ce dernier n'est pas toujours égal a l'ordre de $A$.
Pourtant je vous remercie pour ce document, j'ai trouver dans le théorème 6 une démonstration qui me parait intéressante. -
Je pense pas que je n'ai pas bien compris cette notion de conditionnement, mais pour moi une matrice définie positive est inversible donc notre solution existe et unique.
-
Un exemple (Ciarlet)
\[ A =
\begin{pmatrix}
10 & 7 & 8 & 7\\ 7 & 5 & 6 & 5 \\ 8 & 6 & 10 & 9 \\7 & 5 & 9 & 10
\end{pmatrix}, \qquad
b =
\begin{pmatrix}
32 \\ 23 \\ 33 \\ 31
\end{pmatrix}
, \qquad
\delta b =
\begin{pmatrix}
0,1 \\ -0,1 \\ 0,1 \\ -0,1
\end{pmatrix}. \]
Résoudre \( A X = b \) et \( A X = b+\delta b \).
e.v.Personne n'a raison contre un enfant qui pleure. -
Effectivement, très bon exemple: la matrice précédente est définie positive et
$ \lambda_{max}/\lambda_{min} \approx 2984.09$ alors que $n=4$... -
Bonjour,
Le conditionnement d'une matrice définie positive n'est effectivement pas forcément bon.
Mais la convergence de la méthode du gradient conjugué n'en dépend pas ( théoriquement ).
C'est pour la méthode du gradient à pas optimal que le conditionnement ( par rapport à la norme $2$ intervient ), avec une convergence en :
$O\left(\frac{c(A)-1}{c(A)+1}\right)^k$.
La méthode de gradient conjugué épouse la géométrie de la matrice, les directions de gradient sont $A$-conjuguées
Dans le cadre de la méthode de gradient à pas optimal, elle se place dans le cadre euclidien : les directions de gradient sont orthogonales au sens de la norme $2$ ce qui peut être illustré par le fait que pour une matrice orthogonale, de conditionnement $1$, la convergence est très bonne. -
Bonjour
Avez-une idée sur comment on peut trouver un(des) préconditionneur(s) pour de telles matrices avec scilab?
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 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
- 65 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
- 314 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
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres