Discussion :

[amine31000]

Bonjour.

J'ai commencé à implémenter l'algorithme d'analyse en composantes principales (ACP) jusqu’à où je me suis arrivé au calcule des valeurs propres et des vecteurs propres, c'est à ce niveau que je suis bloqué.

j'ai une matrice symétrique de 3X3 et j’arrive pas à trouvé la solution pour calculer les valeurs propres et par la suite les vecteurs propres.

est ce que quelqu'un pourrai m 'aider et me donner l'algorithme qui résous ce problème.

Merci d'avance .

[pseudocode]

est ce que quelqu'un pourrai m 'aider et me donner l'algorithme qui résous ce problème.

Wikipedia doit pouvoir t'aider.

[amine31000]

Wikipedia doit pouvoir t'aider.

Merci l'ami, j'ai une question ?? pour la solution j'ai entendu parler de l'algorithme de JACOBI est-ce -que c'est bien ce lui là l'algorithme de JACOBI.Wikipedia

[pseudocode]

Merci l'ami, j'ai une question ?? pour la solution j'ai entendu parler de l'algorithme de JACOBI est-ce -que c'est bien ce lui là l'algorithme de JACOBI.Wikipedia

Non. La méthode citée par wikipedia est la résolution de l'équation caractéristique de degré 3 par des formules de trigo (formules de Viète).

[amine31000]

Non. La méthode citée par wikipedia est la résolution de l'équation caractéristique de degré 3 par des formules de trigo (formules de Viète).

ok. donc cette méthode ne fait pas trop l'affaire car je doit calculer aussi les vecteur propres, j'aimerai bien si vous connaissez d'autres solution ou bien une suite de l'algorithme citer par wiki qui calcule les vecteur propres, S.V.P les amis j'en ai vraiment besoin de la solution (un algorithme qui calcule les valeurs propres et les vecteurs propres d'une matrice symétrique de taille 3X3).

Merci d'avance.

[ToTo13]

Bonjour,

dans le cadre de matrice symétriques, il faut justement utiliser l'algorithme de Jacobi, tu en as une implémentation C dans l'incontournable "Numerical Recipes".
Sinon il y deux exemples de calcul d'ACP dans le rubrique Contribuez.

[pseudocode]

D'accord avec Toto13 : utiliser l'algo "généraliste" de Jacobi est sans doute le plus simple. De plus il y a plein d'implémentations dispo sur le net.

Sinon, on peut aussi continuer dans les méthodes spécifiques aux matrices symétriques 3x3.

[Alexis.M]

Pour des matrices symétriques 3x3 il est tout à fait possible de résoudre le problème de manière exacte.

si tu as la valeur propre v alors le vecteur:

Code :

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

1
2
3
4
u = [ a12 * a23 - a13 * (a22 - v)
       a12 * a13 - a23 * (a11 - v)
      (a11 - v) * (a22 - v)  - a12 * a12
]

(où aij sont les coefficient de la matrice symétrique A)
est un vecteur propre de A. Il faudra ensuite sans doute le normaliser et gérer la
possible multiplicité des valeurs propres

[Aleph69]

Bonsoir,

pour des petites matrices, autant utiliser la méthode QR, ou éventuellement la méthode QZ si le problème est généralisé : c'est beaucoup plus robuste et c'est justement fait pour avoir toutes les valeurs propres et vecteurs propres normalisés d'un coup!

[amine31000]

Bonsoirs,

Je vous remerciés tous, de votre intervention et votre aide concernant mon problème posé sur ce merveilleux forum

Pour des matrices symétriques 3x3 il est tout à fait possible de résoudre le problème de manière exacte.

si tu as la valeur propre v alors le vecteur:

Code :

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

1
2
3
4
u = [ a12 * a23 - a13 * (a22 - v)
       a12 * a13 - a23 * (a11 - v)
      (a11 - v) * (a22 - v)  - a12 * a12
]

(où aij sont les coefficient de la matrice symétrique A)
est un vecteur propre de A. Il faudra ensuite sans doute le normaliser et gérer la possible multiplicité des valeurs propres

Alexis.M donc si je doit suivre cette méthode (le V est la valeur propre) et comme j’utilise trois vecteur propres au minimum j'attribue à chaque vecteur propre sa valeur propre c'est-a-dire (Vecteur 1-->valeur propre 1{V1}), (Vecteur 2-->valeur propre 2{V2}), (Vecteur 3-->valeur propre 3{V3}), d'ou

Code :

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

1
2
3
4
5
6
7
8
9
10
11
u1 = [ a12 * a23 - a13 * (a22 - v1)
       a12 * a13 - a23 * (a11 - v1)
      (a11 - v1) * (a22 - v1)  - a12 * a12]

u2 = [ a12 * a23 - a13 * (a22 - v2)
       a12 * a13 - a23 * (a11 - v2)
      (a11 - v2) * (a22 - v2)  - a12 * a12]

u3 = [ a12 * a23 - a13 * (a22 - v3)
       a12 * a13 - a23 * (a11 - v3)
      (a11 - v3) * (a22 - v3)  - a12 * a12]

Reste juste que je doit prouvé cette méthode pour que je puisse l'utilisé, genre qu'il a inventé, le nom de la méthode, ....

Récape :

1- Pour les valeurs propres je vais utilisé la méthode cité par pseudocode Wikipedia .

2- Pour les vecteurs propres j’implémente l'algorithme cité par Alexis.M

Code :

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

1
2
3
4
u = [ a12 * a23 - a13 * (a22 - v)
       a12 * a13 - a23 * (a11 - v)
      (a11 - v) * (a22 - v)  - a12 * a12
]

Veuillez les amis me confirmez si par ces deux algorithme (1 et 2) je peut calculer les valeurs propres et les vecteurs propres avec des résultats précise.

[Aleph69]

Reste juste que je doit prouvé cette méthode pour que je puisse l'utilisé, genre qu'il a inventé, le nom de la méthode, ....

Preuve simple : calculer analytiquement le produit A*u et retrouver v*u. Ceci prouvera que u est un vecteur propre associé à v.

Preuve constructive : calculer toi-même le noyau de la matrice A-v*I.

[Alexis.M]

Il faut juste traiter explicitement le cas des valeurs propres dégénérées.

Si tu as plusieurs fois la même valeur propre, la formule que je t'ai donnée
ne calculera qu'un vecteur propre.

Il y a 3 cas à envisager:
1) Toutes les valeurs propres sont distinctes, dans ce cas pas de problème
2) il y une valeur propre de multiplicité 2: calculer le vecteur propre pour
la valeur propre non dégénérée et un vecteur propre pour la valeur propre
dégénérée. Le troisième vecteur propre étant orthogonal aux deux autre tu
peux le trouver en calculant le produit vectoriel des deux premiers
3) il n'y a qu'une valeur propre de multiplicité 3: n'importe quelle base
de l'espace 3D fait l'affaire.

[pseudocode]

Code :

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

1
2
3
u1 = [ a12 * a23 - a13 * (a22 - v1)
       a12 * a13 - a23 * (a11 - v1)
      (a11 - v1) * (a22 - v1)  - a12 * a12]

Ca ne fonctionne que si les deux lignes/colonnes utilisées sont linéairement indépendantes. Sinon ca donne (0,0,0)

Auquel cas, il faut prendre 2 autres lignes/colonnes pour faire le calcul

Code :

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

1
2
3
u1 = [a11-v1, a12, a13] ^ [a21, a22-v1, a23] // ligne 1 et ligne 2
u1 = [a11-v1, a12, a13] ^ [a31, a32, a33-v1] // ligne 1 et ligne 3
u1 = [a21, a22-v1, a23] ^ [a31, a32, a33-v1] // ligne 2 et ligne 3

idem pour u2 et u3.

Et comme dit précédemment, il faut gérer le cas des valeurs propres de multiplicité 2 et 3.

[pseudocode]

Calcul des valeurs propres par recherche des racines du polynôme caracteristique.

méthode de wikipedia:

Code java :

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
double[] eigenvaluesOfSymmetric3x3( double[][] M ) {
	double p = Math.pow(M[0][1],2)+Math.pow(M[0][2],2)+Math.pow(M[1][2],2);
 
	if (p==0) { // M is diagonal.
		return new double[] {M[0][0],M[1][1],M[2][2]};
	}
	double q = trace(M)/3;
	p = Math.pow(M[0][0]-q,2) + Math.pow(M[1][1]-q,2) + Math.pow(M[2][2]-q,2) + 2*p;
	p = Math.sqrt(p / 6);
	double[][] B = { // B = (M - q*I); 
			{ (M[0][0]-q),  M[0][1],     M[0][2]    },
			{  M[1][0],    (M[1][1]-q),  M[1][2]    },
			{  M[2][0],     M[2][1],    (M[2][2]-q) }
	};
	double r = det(B) / (2*p*p*p);
 
	double phi = 0;
	if (r<=-1) {phi = Math.PI/3;} else if (r>=1) {phi=0;} else {phi=Math.acos(r)/3;}
 
	double eig1 = q + 2 * p * Math.cos(phi);
	double eig2 = q + 2 * p * Math.cos(phi + 2*Math.PI/3);
	double eig3 = q + 2 * p * Math.cos(phi + 4*Math.PI/3);
 
	return new double[] {eig1,eig2,eig3};
}
 
double trace( double[][] M ) {
	return M[0][0]+M[1][1]+M[2][2];
}
double det( double[][] M ) { // Sarrus formula
	return	M[0][0]*M[1][1]*M[2][2] + M[0][1]*M[1][2]*M[2][0] + M[0][2]*M[1][0]*M[2][1]
	      - M[0][2]*M[1][1]*M[2][0] - M[0][1]*M[1][0]*M[2][2] - M[0][0]*M[1][2]*M[2][1];
}

méthode "Eigensystems for 3x3 Symmetric Matrices (Revisited)" by David Eberly, Geometric Tools, LLC.

Code java :

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
double[] eigenvaluesOfSymmetric3x3(double[][] M) {
 
	// Characteristic Equation: L^3 - c2.L^2 + c1.L - c0 = 0
	double c2 = M[0][0] + M[1][1] + M[2][2];
	double c1 = M[0][0]*M[1][1] - M[0][1]*M[0][1] + M[0][0]*M[2][2] - M[0][2]*M[0][2] + M[1][1]*M[2][2] - M[1][2]*M[1][2];
	double c0 = M[0][0]*M[1][1]*M[2][2] + 2.0*M[0][1]*M[0][2]*M[1][2] - M[0][0]*M[1][2]*M[1][2] - M[1][1]*M[0][2]*M[0][2] - M[2][2]*M[0][1]*M[0][1];
 
	// compute a,b,q,p,theta (see "Eigensystems for 3x3 Symmetric Matrices (Revisited)")
	double a = c1 - (c2*c2)/3;
	if (a>0) a=0;
	double b =(-2*c2*c2*c2 + 9*c1*c2 - 27*c0)/27;
	double q = (b*b)/4 + (a*a*a)/27;
	if (q>0) q=0;
	double p = Math.sqrt(-a/3);
	double theta = Math.atan2( Math.sqrt(-q), -b/2) / 3;
 
	// roots of the polynomial:
	double cosTheta = Math.cos(theta), sinTheta = Math.sin(theta), sqrt3 = Math.sqrt(3);
	double root0 = c2/3 + 2*p*cosTheta;
	double root1 = c2/3 - p*(cosTheta + sqrt3*sinTheta);
	double root2 = c2/3 - p*(cosTheta - sqrt3*sinTheta);
 
	return new double[] {root0,root1,root2};
}