Scribd
Importer
4 vues6 pages

TPP2 2

La méthode du gradient conjugué est appliquée à une fonction quadratique convexe sur R100, avec une fonction coût définie et son gradient calculé. La solution optimale est atteinte par l'algorithme du gradient conjugué, qui montre une convergence efficace vers la solution exacte. Des comparaisons de complexité révèlent que la méthode du gradient conjugué est plus performante que les méthodes directes pour des problèmes de grande dimension.

Transféré par

Ilhame Daoui
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
4 vues6 pages

TPP2 2

La méthode du gradient conjugué est appliquée à une fonction quadratique convexe sur R100, avec une fonction coût définie et son gradient calculé. La solution optimale est atteinte par l'algorithme du gradient conjugué, qui montre une convergence efficace vers la solution exacte. Des comparaisons de complexité révèlent que la méthode du gradient conjugué est plus performante que les méthodes directes pour des problèmes de grande dimension.

Transféré par

Ilhame Daoui
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

1 Mise en œuvre sur un exemple

Dans cette partie, la méthode du gradient conjugué est appliquée à une fonction quadratique
convexe définie sur R100 . La matrice A et le vecteur b sont fournis dans le fichier [Link].

Question 2 : Définition de la fonction coût


La fonction à minimiser est donnée par :
1
J(x) = xT Ax − bT x
2
Le code MATLAB correspondant est :
1 J = @ (x ,A , b ) 0.5* x ’* A * x - b ’* x ;

Question 3 : Calcul du gradient de la fonction coût


Le gradient de la fonction J s’écrit :
∇J(x) = Ax − b
Il est implémenté en MATLAB de la façon suivante :
1 gradJ = @ (x ,A , b ) A * x - b ;

Question 4 : Calcul de la solution exacte


Le minimum de la fonction est atteint lorsque ∇J(x∗ ) = 0, ce qui conduit à :
Ax∗ = b
La solution exacte est calculée par :
1 x_opt = inv ( A ) * b ;

Question 5 : Implémentation du gradient conjugué


L’algorithme du gradient conjugué est implémenté conformément à la Table 1 de l’énoncé.
1 x = zeros (n ,1) ;
2 r = b - A*x;
3 d = r;
4
5 J_values = zeros (n ,1) ;
6 err = zeros (n ,1) ;
7
8 for k = 1: n
9 alpha = (d ’* r ) /( d ’* A * d ) ;
10 x = x + alpha * d ;
11
12 r_new = r - alpha * A * d ;
13
14 J_values ( k ) = J (x ,A , b ) ;
15 err ( k ) = norm ( x - x_opt ) ;
16
17 beta = -(d ’* A * r_new ) /( d ’* A * d ) ;
18 d = r_new + beta * d ;
19 r = r_new ;
20 end

1
Question 6 : Vérification de la convergence
Après n itérations, le vecteur obtenu est très proche de la solution optimale x∗ , ce qui confirme
la convergence de la méthode.
1 norm ( x - x_opt )

Question 7 : Évolution de la fonction J


La figure suivante illustre la décroissance de la fonction J au fil des itérations.

2
Évolution de J(x k
)
8000

7000

6000

5000

4000
J(xk )

3000

2000

1000

-1000
0 20 40 60 80 100
itération k

Figure 1 – Évolution de la fonction J J(xk )

3
Question 7 (suite) : Convergence vers la solution optimale
L’évolution de la norme de l’erreur ∥xk − x∗ ∥ est représentée en échelle logarithmique.

4
Erreur sur la solution
10 2

10 1

10 0
||x k - x * ||

10 -1

10 -2

10 -3

10 -4
0 20 40 60 80 100
itération k

Figure 2 – Convergence vers la solution optimale

5
Question 8 : Vérification des propriétés P1 et P2
Les produits scalaires dTi Adj pour i ̸= j ainsi que dTi rk sont numériquement proches de zéro,
ce qui confirme :
— la conjugaison des directions (P1),
— l’orthogonalité du gradient avec les directions précédentes (P2).
Les écarts observés sont dus aux erreurs d’arrondi numérique.

Question 9 : Comparaison des complexités


Les temps de calcul de la méthode directe et de la méthode du gradient conjugué sont
comparés à l’aide de la fonction tic/toc.
1 tic
2 x_direct = A \ b ;
3 t_direct = toc ;
4
5 tic
6 % Algorithme du gradient c o n j u g u
7 t_cg = toc ;

La méthode du gradient conjugué est plus efficace que l’approche directe pour des problèmes
de grande dimension.

Vous aimerez peut-être aussi