Gradient conjugué : convergence — Les-mathematiques.net The most powerful custom community solution in the world

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.

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.pdf
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Ok Merci @Gebrane.

    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.
  • 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.
  • 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.
Success message!