Discussion :

[Rniamo]

bonjour,
quelle méthode implémenter pour résoudre A.X=B fiablement.

j'ai testé gauss mais sans réél succès

(c'est mon erreur)

[Zavonen]

Quel rapport entre la question et le graphique ?

[Rniamo]

le graphique représente l'erreur que j'obtient en appliquant Gauss sur une série de test.

Apparemment (d'après mes tests) je perd dès que les nombre ne sont plus entiers :

Code :

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

1
2
3
4
5
6
7
 
for(unsigned i=0;i<s;i++) {
 
		x[i]=i/0.1;
 
		y[i]=1-2*x[i]+3*x[i]*x[i]-4*x[i]*x[i]*x[i]+5*x[i]*x[i]*x[i]*x[i]-6*x[i]*x[i]*x[i]*x[i]*x[i];
	}

me renvoie : [ 0.999947 -1.99836 2.99967 -3.99998 5 -6 ]

[pseudocode]

bonjour,
quelle méthode implémenter pour résoudre A.X=B fiablement.

Tu ne devrais pas mettre "inversion de matrices" en titre de ta question. Tu vas te faire tuer par Jean-Marc Blanc s'il passe par ici.

Je te conseille d'ailleurs la lecture de son article "Résolution des systèmes linéaires".

[Rniamo]

ok, mais au final résoudre un système linéaire c'est inverser une matrice ...

edit : super ce lien, dans mon algo je choisis le plus grand pivot ... que me manque -t- il ?

[Zavonen]

ok, mais au final résoudre un système linéaire c'est inverser une matrice ...

Si tu sais inverser, tu sais résoudre. Mais on peut résoudre sans inverser. L'inversion te donne la résolution de TOUS les systèmes AX=Y qqs Y. C'est donc beaucoup plus puissant que la 'simple' résolution AX=Y pour un Y donné.
Pour la résolution Gauss fonctionne assez bien dans les cas 'standard' . Je te renvoie aussi à la lecture de J-M Blanc.

[Rniamo]

mais la méthode de gauss inverse A même si on le voit pas directement, c'est ce que je voulais dire.

Sinon je voudrais par exemple avoir ces résultats au plus proches :

datas ... mais j'en suis loin :
[ 0.00138 7.23533e-07 1.24444e-14 ] au lieu de
[ 0.673565789473684E-03 0.732059160401003E-06 -0.316081871345029E-14 ]

edit : je ne crois pas l'avoir dit jusqu'à présent : j'utilise les moindres carrés ordinaires.

[Zavonen]

mais la méthode de gauss inverse A même si on le voit pas directement, c'est ce que je voulais dire.

Non, la méthode de Gauss vise à construire un système équivalent (admettant les mêmes solutions) avec une matrice triangulaire. Cependant, cette matrice triangulaire n'est équivalente en rien à la matrice de départ. Si cela était, cela voudrait dire que toutes les matrices sont trigonalisables or on sait que c'est le cas seulement si on est dans un corps algébriquement clos, ce qui n'est pas le cas de R.

[Rniamo]

mais résoudre a.x=b c'est trouver x=a^-1.b non ? donc au final gauss inverse la matrice puiqu'il trouve x, non ?

enfin ça ne résoud pas mon problème

[Zavonen]

Trouver A^-1(b) ne veut pas dire trouver A^-1, de la même façon que connaître f(b) ne veut pas dire connaître la fonction f (on la connaît seulement en un point).

[pseudocode]

mais la méthode de gauss inverse A même si on le voit pas directement, c'est ce que je voulais dire.

Sinon je voudrais par exemple avoir ces résultats au plus proches :

datas ... mais j'en suis loin :
[ 0.00138 7.23533e-07 1.24444e-14 ] au lieu de
[ 0.673565789473684E-03 0.732059160401003E-06 -0.316081871345029E-14 ]

edit : je ne crois pas l'avoir dit jusqu'à présent : j'utilise les moindres carrés ordinaires.

Je ne sais pas comment tu as implémenté ta méthode de gauss car, avec tes données, je trouve:

[6.735657894623159E-4, 7.32059160401017E-7, -3.160818713451407E-15]

Mon implémentation Java est dispo ici:

http://www.developpez.net/forums/d37...emes-lineaires

[Rniamo]

je vérifie mon code. merci

edit :
voici mon code (je ne trouve pas l'erreur ), c'est du C++ mais je pense que ça se comprends :

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
42
43
	int lignePivot;
	unsigned i, j, k;
	double tmp, *copieLigne=NULL;
 
	if (size==0 || !A || !B) return;
	for(i=0;i<size;i++) {
		// 1/ recherce du pivot
		lignePivot=-1;
		for(j=i;j<size;j++) {
			if (A[j][i]!=0 && lignePivot==-1) lignePivot=j;
			else if(A[j][i]!=0 && lignePivot>=0 && abs(A[j][i])>abs(A[lignePivot][i])) lignePivot=j;
		}
 
 
		if (lignePivot==-1) throw int(BAD_MATRIX); // A n'a pas d'invers
		else if (lignePivot!=int(i)) { // inversion des 2 lignes (i et lignePivot)
			// dans A
			for(j=i;j<size;j++) { // because before i it's 0
				tmp=A[lignePivot][j];
				A[lignePivot][j]=A[i][j];
				A[i][j]=tmp;
			}
 
			// et dans B
			tmp=B[lignePivot];
			B[lignePivot]=B[i];
			B[i]=tmp;
		}
 
		// on mets les 0 sous la diagonale
		for(j=i+1;j<size;j++) { // for all lines under the pivot
			tmp=A[j][i]; // save the line
			for(k=i;k<size;k++) A[j][k]-=( tmp*A[i][k]/A[i][i] ); // affect new line
			B[j]-=( B[i]*tmp/A[i][i] ); // affect new second member
		}	
	}	
 
	// résolution du système triangulaire
	for(i=size-1;i<size;i--) { // /!\ i unsigned => i>=0 doesn't work here !!!
		x[i]=B[i];
		for(j=i+1;j<size;j++) x[i]-=( x[j]*A[i][j] );
		x[i]/=A[i][i];
	}

ma matrice triangularisée est (avant résolution finale) :

4.96125e+22 1.215e+17 3.15e+11 ,
0 128571 1
0 0 -7142.86

et le second membre est :
8.89614e+10 , 0.0944057 , -9.85714

je pars de :
A= :
4.96125e+22 1.215e+17 3.15e+11
1.215e+17 3.15e+11 900000
3.15e+11 900000 3

B= :
8.89614e+10 230667 0.65924

edit : quelqu'un pourrait vérifier ces valeurs svp
edit 2 : je calcule A comme suit :

Code :

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

1
2
3
	double aij=0;
	for(unsigned k=0;k<(degres+1);k++) aij+=pow(x[k],(double)( 2*degres-i-j ) );
	return aij;

et B :

Code :

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

1
2
3
	double bi=0;
	for(unsigned i=0;i<degres+1;i++) bi+=(pow(_x[i],_degres-k)*y[i]);
	return bi;

voilà, vous savez tout, moi je ne trouve pas l'erreur du tout

[Rniamo]

pseudocode : dans ton inverse(), tu peux inverser les lignes ... c'est bien légal ça ?

edit : j'ai repris le code en l'allourdissant pas mal et ça marche. merci

je ne ferme pas encore le fil, j'attends la réponse à la question précédente.

[Rniamo]

Je ne sais pas comment tu as implémenté ta méthode de gauss car, avec tes données, je trouve:

[6.735657894623159E-4, 7.32059160401017E-7, -3.160818713451407E-15]

Mon implémentation Java est dispo ici:

http://www.developpez.net/forums/d37...emes-lineaires

maintenant j'ai :

[ 0.00067356578946882462 7.3205916040101105e-07 -3.160818713450432e-15 ]

[pseudocode]

pseudocode : dans ton inverse(), tu peux inverser les lignes ... c'est bien légal ça ?

Bah, l'échange de lignes c'est une combinaison linéaire comme les autres:

New[ i ] = 0*Old[ i ] + 1*Old[ j ]
New[ j ] = 1*Old[ i ] + 0*Old[ j ]

[Rniamo]

pour faire Gauss OK ... mais pour l'inverse j'ai des doutes et même plus que des doutes. m^(-1) *m != I a priori, non ?

[pseudocode]

pour faire Gauss OK ... mais pour l'inverse j'ai des doutes et même plus que des doutes. m^(-1) *m != I a priori, non ?

Lorsqu'on permute les lignes, on permute aussi les résidus. Donc dans la matrice solution il faut aussi permuter les lignes, pour conserver la correspondance.

[Rniamo]

oui pour gauss mais ce n'est plus l'inverse du coup ...

encore merci, ton code m'a bien aidé à reprendre le mien.

[FR119492]

Salut!

Tu ne devrais pas mettre "inversion de matrices" en titre de ta question. Tu vas te faire tuer par Jean-Marc Blanc s'il passe par ici.

Attention! Je suis de retour de vacances.

mais résoudre a.x=b c'est trouver x=a^-1.b non ? donc au final gauss inverse la matrice puiqu'il trouve x, non ?

Non! non! et non! Comment peut-on continuer à enseigner de telles aberrations? x = a^(-1) * b est une convention d'écriture qui signifie que x est la solution du système a * x = b, mais utiliser cette formule pour résoudre numériquement ce système est totalement inefficace: l'inversion de la matrice prend plus de temps que la résolution par une bonne méthode.

Si tu recherches l'efficacité, va sur le site www.netlib.org où tu trouveras les librairies LINPACK (plus ancienne et plus simple à utiliser) et LAPACK (plus récente et probablement plus efficace) qui sont ce qu'on a fait de mieux dans ce domaine.

Si la matrice a des propriétés particulière (symétrique, définie positive, bande, etc.), n'oublie pas d'en tenir compte: ça peut améliorer considérablement les performances.
Jean-Marc Blanc