Discussion :

[nadal1991]

Bonjours,

pour les besoin d'un projet j'applique l'algorithme PCA sur une base d'images, mais voila arrivé a l'étape du calcul des vecteur propres (et valeur propres) je bloque, j'ai chercher sur internet et j'ai trouvé pas mal d'algorithme qui implémentait ca mais je ne comprend pas très bien a chaque fois, alors je demande si on peut m'aiguiller sur un algorithme efficace(pas trop lent ), et aussi qui soit compréhensible et donc pas extrêmement difficile à implémenter, enfin je voudrait des avis.

Merci.

NB : La matrice est Symétrique et d'une taille de (50x50).

[FR119492]

Salut!
Dans "Numerical Recipes", section 11.0.4, on lit ceci:

You have probably gathered by now that the solution of eigensystems ia a fairly complicated business. It is. It is one of the few subjects covered in this book for which we do not recommend that you avoid canned routines.

Je te recommande donc d'utiliser des sous-programmes tous faits. Alors, commence par regarder si tu trouves ce dont tu as besoin dans la librairie LAPack, gratuite sur le site www.netlib.org, ou dans Matlab (cher), ou dans Scilab ou Octave (gratuits).
Jean-Marc Blanc

[nadal1991]

merci pour votre réponse, j'utilise OpenCv en C++ pour réaliser mon projet et j'ai déjà trouvé des algo tous-fait déjà implémenté dans OpenCv, Mais bon voila moi j'ai vraiment envie d’enrichir mes connaissance, et donc je veux comme même essayer de réaliser moi même l'algorithme de calcul ou en moins en faire une partie. En parlant de cela j'ai vu que les meilleur algorithme concernant les matrice Symétrique était la méthode de Jacobi, et j'ai aussi trouvé de bon retour par rapport a la méthode QR, ou encore la Décomposition en valeur Singulière.

donc voila de ces méthode pouvais vous me conseillé une qui serait efficace et pas trop trop difficile a programmer !

Merci Beaucoup.

[FR119492]

Salut!
Au chapitre 11 de "Numerical Recipes", tu trouveras les listings des sous-programmes écrits en C++. Que te faut-il de plus?
Jean-Marc Blanc

[Aleph69]

Bonsoir,

si tu souhaites enrichir tes connaissances dans le domaine, je te conseille la lecture de deux livres totalement gratuits :

- numerical methods for large eigenvalue problems :
http://www-users.cs.umn.edu/~saad/books.html

- templates for the solution of algebraic eigenvalue problems :
http://www.cs.ucdavis.edu/~bai/ET/contents.html

Si tu souhaites te procurer un livre payant sur le sujet, je peux aussi t'indiquer des ouvrages de référence.

[ToTo13]

Salut!
Au chapitre 11 de "Numerical Recipes", tu trouveras les listings des sous-programmes écrits en C++. Que te faut-il de plus?
Jean-Marc Blanc

+1 et petite précision... pour les matrices symétriques le meilleur algorithme est celui de Jacobi (dont tu as les sources).

[nadal1991]

Bonsoir,

si tu souhaites enrichir tes connaissances dans le domaine, je te conseille la lecture de deux livres totalement gratuits :

- numerical methods for large eigenvalue problems :
http://www-users.cs.umn.edu/~saad/books.html

- templates for the solution of algebraic eigenvalue problems :
http://www.cs.ucdavis.edu/~bai/ET/contents.html

Si tu souhaites te procurer un livre payant sur le sujet, je peux aussi t'indiquer des ouvrages de référence.

Merci beaucoup je verrai ca, enfin sachant que l'algorithme de jacobi est le plus performant je vais me concentrer a fond pour bien le comprendre et le faire, si j'ai un problème je reviendrait .

Merci pour ta réponse et sinon en ce qui concerne les livre payant, je suis algérien et malheureusement ici on a aucun moyen pour se procurer de telle livre.

[Aleph69]

Bonjour,

si tu es dans l'impossibilité de te procurer des livres payants, tu peux toujours en consulter certains (partiellement) en allant sur http://books.google.fr.

LE livre de référence sur les problèmes aux valeurs propres symétriques :
http://books.google.fr/books?id=mWin...page&q&f=false

Bonne continuation!

[Matthieu Brucher]

merci pour votre réponse, j'utilise OpenCv en C++ pour réaliser mon projet et j'ai déjà trouvé des algo tous-fait déjà implémenté dans OpenCv, Mais bon voila moi j'ai vraiment envie d’enrichir mes connaissance, et donc je veux comme même essayer de réaliser moi même l'algorithme de calcul ou en moins en faire une partie. En parlant de cela j'ai vu que les meilleur algorithme concernant les matrice Symétrique était la méthode de Jacobi, et j'ai aussi trouvé de bon retour par rapport a la méthode QR, ou encore la Décomposition en valeur Singulière.

donc voila de ces méthode pouvais vous me conseillé une qui serait efficace et pas trop trop difficile a programmer !

Merci Beaucoup.

Seule solution, prendre un bon livre tel que le Golub pour comprendre les problématiques. Attention, c'est de l'anglais.

[nadal1991]

rebonsoir,

bon voila j'ai réussi a implémenter la méthode de Jacobi pour le calcul des valeur et vecteur propre, j'ai fait des test sur des matrice a petit nombre et elle marche bien ! mais voila la je me retrouve face a un problème, quand j'essaye d'appliquer JACOBI a une matrice (de n'importe qu'elle dimension ) mais avec des coefficient très grands ( de l'ordre de 10^6) je me retrouve avec l'algorithme qui boucle et qui ne fini pas, donc je voulais savoir si la méthode de Jacobi avait un problème avec les coefficients très très grand ? et aussi si c'était possible de par exemple diviser la matrice sur un grand nombre pour réduire la taille des coefficient et après application de l'algorithme de Jacobi pouvoir récupérer les valeur et vecteur propre de la matrice d'origine !

merci.

[Matthieu Brucher]

Grand nombre ou petit nombre, ce n'est pas ça qui est problématique, mais petit conditionnement ou grand conditionnement !

[nadal1991]

Bonsoir,

dans mon cas je pense que si ca pose un probleme la grandeur des coefficient sinon comment expliquer que ca donne une réponse rapide et juste pour des matrice a coefficient normaux et que la methode boucle sans fin pour des matrice a coefficient très grand?? (et je parle des coefficient pas de la taille de la matrice )

et sinon tu voulais dire quoi par "conditionnement" j'ai pas saisi ?

Merci

[Matthieu Brucher]

Le conditionnement, c'est super important, c'est le rapport entre la valeur propre la plus grande et la plus faible. Si tu dépasses la précision du type que tu utilises, tu auras des imprécisions et potentiellement le problème que tu as de stabilité.
De manière générale, il faut mettre une limite en nombre d'itérations et sortir une erreur si la méthode ne converge pas.

[nadal1991]

je vient de un peux me documenter sur le conditionnement et avec ce que t'a dit je comprend un peux mieux ce probleme, mais:" faire une condition pour sortir si on boucle trop " ca m'aide pas moi, j'ai pas envie de gérer, j'ai besoin d'avoir ces vecteur et valeur propre; alors y'a t'il une chose a faire avant ou pendant l'algorithme pour bien conditionner notre matrice et faire que l'algorihtme marche ?

merci.

[Matthieu Brucher]

Non, il n'y a rien à faire. Si ta matrice est mal conditionnée, elle est mal conditionnée.

Et toutes les routines sortent et retournent une erreur en cas de défaut de convergence.

[Aleph69]

Bonsoir,

il faut préconditionner le problème pour améliorer son conditionnement. Dans les cas des problèmes aux valeurs propres, l'approche la plus simple consiste à équilibrer les lignes et colonnes de ta matrice à l'aide d'une matrice diagonale : A <- DAD, où D est diagonale. On choisit la même matrice diagonale à gauche et à droite de A pour préserver la propriété de symétrie. Si ta matrice est à diagonale dominante, tu peux choisir D égale à la matrice formée par les racines carrées des inverses des coefficients diagonaux de A. En théorie, A devrait aussi vérifier la propriété A de Young mais le temps d'essayer de vérifier ça tu auras déjà eu le temps de tester si ce préconditionnement fonctionne ou pas! Si ça ne marche pas bien, tu peux aussi prendre D égale à la matrice formée par les racines carrées des normes infinies des lignes de A. Si ça ne marche toujours pas, essaye les préconditionneurs décrits dans ce document :
http://www.google.fr/url?sa=t&source...0gRsBtEcT-FWqQ

Si rien ne fonctionne, il faudra utiliser des méthodes plus sophistiquées et vérifier que tu as correctement codé tes algorithmes.

[Aleph69]

Non, il n'y a rien à faire. Si ta matrice est mal conditionnée, elle est mal conditionnée.

Beaucoup des matrices que l'on rencontre en pratique sont mal conditionnées et heureusement il y a toujours quelque chose à faire pour y remédier (préconditionnement). Dans le cas présent, c'est plutôt au conditionnement des paires propres de la matrice auquel il faut s'intéresser.

[Invité]

Deux petits trucs si ta matrice est mal conditionnée...

1- si c'est en fait une matrice de variance covariance, le mieux est d'utiliser une SVD sur la donnée initiale. En général c'est nettement plus robuste. Mais tu peux aussi essayer une SVD directement sur la matrice (la décomposition en valeurs singulières, c'est robuste à la base).

2- ajoute à ta matrice l'identité fois une petite valeur (la plus grande valeur propre fois 1e-6 quelque chose du genre: A + e Id, e petit), ca va mécaniquement améliorer le conditionnement, sans trop modifier les vecteurs propres "principaux" (portés par les grosse valeurs propres). Ca revient, implicitement, à régulariser la recherche des vecteurs propres.

Francois

[FR119492]

Salut!
Il y a une question qui n'a pas été abordée dans cette discussion, à savoir si tu cherches toutes les valeurs propres ou seulement quelques-unes (les plus grandes ou les plus petites). Dans ce dernier cas, la méthode de la puissance itérée mériterait d'être envisagée.
Jean-Marc Blanc

[prgasp77]

Bonjour,
mes souvenirs d'algèbre linéaire sont un peu poussiéreux mais il me semble que :

Soit une matrice symétrique réelle. Soit la matrice diagonale telle que (voir algos de diagonalisation d'une matrice). Alors, est orthogonale et ses colonnes sont les vecteurs propres de .

Des vecteurs propres de il est facile d'en déduire les valeur propres. Me tromperais-je ?