Discussion :

[Regex184]

Bonjour, j'ai implémenté récemment l'algorithme des gradients conjugués sur matlab pour résoudre des systèmes d'équations Ax = b où la matrice A est symétrique et définie positive.

Code MATLAB :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function [sol,k] = gradientsConjugues_2(A,b,x0,tol)
    r = A*x0-b;
    p = -r;
    k = 0;
    x = x0;
    n = length(x0);
    rr = r'*r;
    while norm(r) > tol && k < n
        Ap = A*p;
        alpha = rr/(p'*Ap);
        x = x + alpha.*p;
        r = r + alpha.*Ap;
        rrtemp = r'*r;
        beta = rrtemp/rr;
        rr = rrtemp;
        p = -r + beta.*p;
        k = k + 1;
    end
    sol = x;
end

La théorie dit que la méthode doit converger vers la solution en aux plus n étapes. n étant la dimensions de la matrice A : n*n. Seulement, j'ai essayer l'algorithme sur la matrice d'Hilbert : a_{ij} = 1/(i+j-1) et B = (1,1,...,1). J'ai donc appliqué l'algo sur les matrices d'Hilbert de différentes tailles n. J'ai remarqué que pour certaines valeurs de n, le résultat était erroné (grande erreur), pour les autres valeur de n, la solution étaient aussi erronées mais moindres. Voici un graphique représentant en abscisses la taille de la matrice d'Hilbert et en ordonnées, la valeur de l'erreur sur la solution après n itérations de l'algorithme. (regarder la courbe rouge seulement).



J'aimerais savoir pourquoi dans ces cas là, la méthode des gradients conjugués ne trouve pas la solution en au plus n étapes (prédit par la théorie). Est-ce à cause d'erreurs d'arrondis qui se propagent dans le calcul par l'ordinateur, ... Existe t-il des solutions pour éviter ces erreurs, ...

Merci de votre aide !

[yahiko]

Si l'algorithme des gradients conjugués fonctionne mal avec les matrices de Hilbert, c'est que ces dernières se prêtent assez mal en général à la la résolution numérique (mal conditionnées).
Cela ne remet pas en cause l'algorithme, simplement qu'il ne fonctionne pas dans certains cas, dont celui des matrices de Hilbert.

[Regex184]

ok merci mais du coup si j'ai bien compris, les erreurs sont du au fait que la méthode des gradients conjugués propagent assez facilement (dans le cas mal conditionné d'Hilbert) les erreurs d'arrondis,... commise par l'ordinateur pendant les différentes itérations ?