Gradient conjugué : convergence

Magnus · May 2021

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.

bd2017 · May 2021

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.

Magnus · May 2021

Oui, mais n'oublions pas que A est symétrique définie positive

gebrane · May 2021

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

bd2017 · May 2021

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.

Magnus · May 2021

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.

Magnus · May 2021

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.

ev · May 2021

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.

bd2017 · May 2021

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$...

Borelline · May 2021

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.