1. Gradient Conjugué
Objectifs
- Implémenter la méthode du Gradient Conjugué
- Ajouter un éventuel préconditionneur
- Comparer les performances
Méthode du Gradient Conjugué
Pseudo-code
Remarque : (z,r) représente le produit scalaire en z et r.
x_0 = 0
r_0 = b - A*x_0
p_0 = r_0
k = 0
while (|r| / |b| > tolerance && k < nmax)
k++
alpha_k = |r_k|²/(p_k, A*p_k)
x_{k+1} = x_k + alpha_k * p_k
r_{k+1} = r_k - alpha_k*(A*p_k)
beta_k = |r_{k+1}|²/|r_k|²
p_{k+1} = r_{k+1} + beta_k*p_k
end
return x_{k+1}
Implémentation
Implémentez la méthode du Gradient Conjugué. Validez ensuite votre code la sur la matrice du Laplacien.
Comparaison des performances
Entre solveurs
Pour une tolérance de 0.1, une taille de matrice N = 1000 et un nombre maximal d’itérations égal à N, affichez les historiques de convergence du gradient conjugué et des autres méthodes itératives. Comparez également le temps CPU entre les différentes méthodes.
Vous devriez obtenir des résultats similaires à ceux ci-dessous (sauf pour le temps CPU !) :
| Méthode | ||||
|---|---|---|---|---|
| Nombre d’itérations | ||||
| Temps CPU (s) |
En fonction de la taille de la matrice
Pour une tolérance de 0.001 et une taille N = 100, 200, …, 1000, affichez le nombre d’itérations requises par le gradient conjugué ainsi que le temps CPU.
Vous devriez obtenir des résultats proches de ceux-ci (sauf pour le temps CPU) :
| N | 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 | 1000 |
|---|---|---|---|---|---|---|---|---|---|---|
| Nombre d’itérations | 50 | 100 | 150 | 200 | 250 | 300 | 350 | 400 | 450 | 500 |
| Temps CPU (s) | 0.0534 | 0.178 | 0.613 | 1.429 | 3.303 | 7.485 | 11.771 | 15.939 | 24.415 | 34.409 |