Discussion :

[Carew]

Bonjour à tous

dans le but de transcrire la méthode du gradient conjugue en C, je souhaiterai avoir plus d'explications sur l'algorithme de la méthode du gradient conjugue ... et la résoltion de systèmes linéaires Ax = b .. où A est une matrice, b un vecteurs, tous 2 connus, et x le vecteur cherché

j'ai eu beau chercher sur le net, j'ai des difficulés à en comprendre le principe et son algorithme

si quelqu'un pouvait m'aider, voir me dire où je peux trouver un code C ... puisque le but ets en fait de comparer les vitesses d'exécution avec la méthode de Gauss, ...


merci d'avance

[larnicebafteur]

Pas simple d'expliquer cette méthode en quelques lignes !!

C'est une méthode itérative, c'est à dire qu'on part d'un vecteur X initial, qu'on "améliore" étape après étape, contrairement à une méthode directe de type Gauss qui donne toute de suite la bonne solution.

On choisit une méthode plutot qu'une autre en fonction de la taille du système à résoudre ; tout dépend du problème, le nombre d'équations peut varier de quelques unes à quelques dizaines de milliers ...
Ensuite, la "tete" de la matrice A peut influencer le choix de la méthode : matrice symétrique ou non, matrice creuse (qui contient très peu de termes autour de la diagonale), ...

On peut trouver quelques méthodes décrites ainsi que quelques programmes en C dans les Numerical Recipes : http://www.library.cornell.edu/nr/cbookcpdf.html (voir chapitre 2)

[Carew]

Pas simple d'expliquer cette méthode en quelques lignes !!

C'est une méthode itérative, c'est à dire qu'on part d'un vecteur X initial, qu'on "améliore" étape après étape, contrairement à une méthode directe de type Gauss qui donne toute de suite la bonne solution.

On choisit une méthode plutot qu'une autre en fonction de la taille du système à résoudre ; tout dépend du problème, le nombre d'équations peut varier de quelques unes à quelques dizaines de milliers ...
Ensuite, la "tete" de la matrice A peut influencer le choix de la méthode : matrice symétrique ou non, matrice creuse (qui contient très peu de termes autour de la diagonale), ...

On peut trouver quelques méthodes décrites ainsi que quelques programmes en C dans les Numerical Recipes : http://www.library.cornell.edu/nr/cbookcpdf.html (voir chapitre 2)

ce serait pour l'appliquer sur une matrice bande (je sais pas si ça se dit comme ça) : une matrice où on a seulement quelques diagonales au milieu qui sont remplies de valeurs non nulles ... les autres étant donc nulles

genre :

7 8 12 0 00 0 0 ..
0 7 34 9 13 0 0 ..
0 0 97 8 ... .. ..
0 0 00 6 ...
0 0 00 0 9 ...
...

ect ...

matrice définie et pas nécessairement symétrique

si tu peux me donner une page du web qui donne une bonne définition de l'algo, je t'en remercie

[notalp]

Si je peux te donner un petit conseil de fénéant dans MAPPLE (gratuit pour les étudiants mais limité) Tu as une option qui te convertit directement en C (et d'autre)
Donc tu pourras Facilement trouver ton bonheur

[notalp]

Voici quelques liens :
Algo : http://www.essi.fr/~leroux/moindrescarresbis/node9.html
http://www.eudil.fr/eudil/jbeuneu/Systemes01.html (dans Méthodes Itératives)

Algo Codé en C : http://www.eudil.fr/eudil/jbeuneu/progrc.html (il y a un lien Javascript)

Exemple en Java : http://www.eudil.fr/eudil/jbeuneu/gr.../gradient.html

Si tu as besoin n'hésite pas ..

[Carew]

Voici quelques liens :
Algo : http://www.essi.fr/~leroux/moindrescarresbis/node9.html
http://www.eudil.fr/eudil/jbeuneu/Systemes01.html (dans Méthodes Itératives)

Algo Codé en C : http://www.eudil.fr/eudil/jbeuneu/progrc.html (il y a un lien Javascript)

Exemple en Java : http://www.eudil.fr/eudil/jbeuneu/gr.../gradient.html

Si tu as besoin n'hésite pas ..

T'es un Dieu

Le premier lien c'est celui sur lequel j'allais commencer à taper en C ... du coup plus besoin si les codes C fonctoinnent ... en plus je vais pouvoir tester toutes les méthodes résolution et laquelle résoud le plus vite et la plus précise

MERCI !!

[notalp]

T'es un Dieu
[...]
MERCI !!

Mais je t'en prie
N'hesite si besoin

[samachi]

j'ai deux questions pour un expert dans la matière, prenons l'équation : A*x=b et cherchons à approximer la solution x, A et b étant connues.

1) Pourquoi la méthode des Directions Conjuguées, en prenant comme base de départ la base canonique, offre-t-elle en pratique si peu d’intérêt ?

2) Soit l’équation (1): r(i+1)=r(i)-alpha(i)*A*d(i) où les r(i)=b-A*x(i) sont les vecteur résiduels, et d(i) et alpha(i) ceux que définie l'algorithme du Gradient Conjugué : x(i+1)=x(i)+alpha(i)*d(i)
Dans l’algorithme du Gradient Conjugué, l'équation (1) est utilisée pour calculer le nouveau résidu. L’utilisation de cette équation à chaque itération n’est-elle pas un danger ?

merci d'avance pour la concision et la clarté de vos réponses que j'espère ne sauront tarder.

[benDelphic]

cette méthode sert à déterminer une solution pour les problème d'optimisation opt f(x) sans contraintes où f(x) est généralement une fonction vectorielle.elle fait partie des méthodes de descente itératives . le principe est de construire une suite X(k) améliorant à chaque itération la fonction .
il y a différents algorithmes : Fletcher-Reeves;les gradient conjuguées ( conjuguées car on construit deux vecteurs linéairement indépendants et de produit nul)...etc.
si cela t 'intéresse je peut te donner mon cours , il est très simple .

[john491]

Salut;
une implementation en Scilab de la methode :

Code :

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
//*********************************************//
//        Méthode du gradient conjugué         //
//*********************************************//
 
 
//declaration de la matrice Q 
Q=2*eye(20,20);
for k=1:19,Q(k,k+1)=-1;end;
for j=2:20,Q(j,j-1)=-1;end;
//declaration des vecteurs b et x0
for k=1:20,b(k)=1;end;
for k=1:20,x(k)=0;end;
n=0;
eps=10^(-6);
r=b-Q*x;
d=r;
delta=r'*r;
bool=%t;
test=eps;
 
 
if sqrt(delta)<=test then , 
	bool=%f;
	end;
while (bool==%t)&(n<100), 
	n=n+1;
	a=Q*d;
	rho=delta/(d'*a);
	x=x+rho*d;
	r=r-rho*a;
	delta1=r'*r;
	l=delta1/delta;
	delta=delta1;
	d=r+l*d;
	if sqrt(delta1)<=test then , 
	bool=%f;
	end;
end;
x
n

[sihamnet]

Voici quelques liens :
Algo Codé en C : http://www.eudil.fr/eudil/jbeuneu/progrc.html (il y a un lien Javascript)

Bonjour notalp , j'ai le même problème que Carew, j'aimerai bien voir l'algorithme codé en C que mais je n'arrive pas à atteindre les liens que vous proposez

Merci d'avance