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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Néanmoins il s'agit d'une convergence théorique qui ne tient pas compte des erreurs numériques.
De plus à ma connaissance rien ne dit qu'une matrice symétrique définie positive est bien conditionnée.
Pourtant je vous remercie pour ce document, j'ai trouver dans le théorème 6 une démonstration qui me parait intéressante.
\[ 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.
$ \lambda_{max}/\lambda_{min} \approx 2984.09$ alors que $n=4$...
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.
Avez-une idée sur comment on peut trouver un(des) préconditionneur(s) pour de telles matrices avec scilab?
Merci.