Discussion :

[arthy]

salut

je suis à la recherche d'aun algorithme pour la détermination des valeurs propres et vecteurs propres d'une matrice.

Pour mon problème, la matrice est définie positive et donc toujours diagonalisable. Je suis passé par plusieurs méthodes notamment la déflation de la matrice (voir http://lumimath.univ-mrs.fr/~jlm/tra...ab/node21.html) mais je n'"ai toujours pas pu obtenir de solutions.

Quelqun pourrait-il m'aider?

[Prof]

Bonjour.

Une solution consiste à calculer le polynôme caractéristique de la matrice, puis à en chercher les racines ( ce qui donne les valeurs propres ) et enfin à calculer les vecteurs propres correspondants.

Calculer le polynôme caractéristique d'une matrice se fait simplement et efficacement par l'algorithme de Le Verrier.

Calculer les racines d'un polynôme se fait simplement pas dichotomie, après avoir localisé ces racines.

Résoudre un système linéaire se fait simplement et efficacement par la méthode du pivot ( partiel ou global ) qui est la mise en oeuvre informatique de la méthode de Gauss.

Une recherche sur le web devrait donner plus de détails sur chacune de ces étapes ...

[Prof]

Ma réponse précédente s'applique à une matrice quelconque.

Pour les matrices symétriques réelles, qu'elles soient ou non définies positives, les valeurs propres et les vecteurs propres peuvent se trouver grâce à la méthode de Jacobi.

Pour ces mêmes matrices, les valeurs propres seules peuvent se trouver par la méthode de Givens-Householder.

Voir sur le web pour plus de détails.

[ol9245]

La décomposition de Cholesky n'est-elle pas une solution à ton problème ?
OL

[ToTo13]

Bonjour,

la meilleure source de réponse pour ce genre de problème se trouve dans "Numerical recipes", en plus tu as les codes sources C, Fortran, ...
Tu pourras choisir ta méthode en fonction de la forme de la matrice :
- Polynome caractéristique, donne souvent un solution dans C, il vaut mieux l'éviter.
- Décomposition QR ET LU, très bien dans le cas général, mais il me semble que l'on obtient que les valeurs propres.
- Jacobi, parfaite pour des matrices symmétriques
- ...

[ol9245]

Effectivement, j'avais oublié que l'incontournable Numerical recipes fait ""aussi"" un peu d'agèbre linéaire. A la sortie de la version C++, ils avaient mis en ligne leur code C dont je me sert toujours. Il semble qu'ils l'aient maintenant retiré Il est distribué avec la version (payante) C++. Quoi qu'il en soit, c'est pas de l'argent perdu, je peux en témoigner. Le livre est excellent. Très pédagogique.
OL

[arthy]

Merci aux uns et aux autres pour vos réponses.

Prof, pour mon travail, je ne peux utiliser la méthode de leverrier car après le calcul du polynome caractéristique, il me faudra obtenir déterminer des intervalles dans lesquels ledit polynome admet une racine unique (c'est à dire les localiser: ce qui n'est pas facile) et la méthode de dichotomie est très lente (je parle de la convergence)

J'ai essayé d'avoir amples information sur "numerical recipes" sur le net et je n'arrive pas à ouvrir le code source des fonctions car il doit avoir été retiré comme l'a souligné ol9245 et toto13.

Je dispose du logiciel turbo C++, Seraitil possible de pouvoir accéder à ces lignes de codes dans l'aide? si oui comment? Ou alors si vous pouvez me communiquer directement l'algorithme en question, ce serait parfait.

Pour l'instant, je vais essayer de comprendre la méthode householder pour l'utiliser. Seulement, il y a un principe non encore acquis. Si j'ai déjà une valeurs propre, comment obtenir le vecteur propre associé? La méthode de gauss ou de jacobi est-elle applicable dans ces conditions? Pour une valeur propre, on a à un coefficioent multiplicatif près une infinité de solution et les méthodes dont vous parlez sont à ma connaissance utilisées pour trouver la solution unique d'un système d'équations linéaires.

Merci

[Prof]

Effectivement, la méthode de Gauss permet de résoudre les systèmes de Cramer à solution unique.
Elle n'est donc peut-être pas adaptée à la recherche d'un vecteur propre puisque dans ce cas le système possède une infinité de solutions.

Je conseille donc d'utiliser la méthode de Jacobi, car elle est spécifique aux matrices symétriques réelles et qu'elle donne à la fois les valeurs propres et les vecteurs propres.

[Ulmo]

Encore une fois, sauf en dimension 2 ou 3, on ne passe pas par le polynôme caractéristique pour calculer les VP d'une matrice. On fait même l'inverse, on passe par une matrice compagnon pour trouver les racines d'un polynôme.

[ToTo13]

Pour ce qui est de numerical recipes, le code C est gratuit.
Cela ne devrait pas poser trop de problèmes de le tradure en C++.

[ol9245]

Pour ce qui est de numerical recipes, le code C est gratuit.
Cela ne devrait pas poser trop de problèmes de le tradure en C++.

Je suis repassé hier par le site officile des NR. Aparemment ils ont changé de politique. ils annoncent que le code C fait partie d'un bundle "C, C++". Je ne l'ai pas trouvé gratuit (colle en 2002 à la sortie de la version C++). Si tu as un lien vers le code C libre et gratuit, merci de le poster.

Sinon, google trouve assez facilement des copies de ce code si on attaque avec les noms des fonctions. Je suppose que ces codes ont été mis en ligne au temps ou le code C était libre et gratuit, et que donc aspirer des copies qui datent de cette époque est plus ou moins légal. Au mois moralement disons....

Ces considarations étant faites, je ne peux que répéter que l'achat des NR (livre + code) est un des meilleurs rapports qualités prix que j'ai jamais faits, juste derrière ma cafetière. J'ai lu le livre dans le train, comme un roman, et je me sert du code en permanence.

edit : le code C est meilleur que le C++
le code original est en fortran; le C est une transcription littérale du fortran; le c++ est une transcription déplorable du C. malgré ces critiques, NR reste un must.

OL

[arthy]

Le véritable problème est que j'ignore le nom de ces fonctions et donc je ne peux pas procéder par une recherche avec une dénomination explicite du nom de la fonction. Si quelqun dispose du code source, je souhaiterai qu'il le mette à ma disposition ( par mail par exemple ou alors par fichier joint sur le forum ).

La traduction du langage C en pascal ne sera pas un problème pour moi

A +

[ol9245]

Pour les NR, désolé, je suis en déplacement et je n'ai pas les codes sous la main. et je ne connais pas le nom de la fonction non plus.

sinon, tu as probablement déja regardé wikipedia http://fr.wikipedia.org/wiki/Algorit...deev-Leverrier

mais ils ne donne pas le pseudocode....

[ToTo13]

Bonjour,

le code source est dans les fichiers pdf des bouquins !!!
Donc lits la partie qui t'intéresses et après la théorie il y a les sources.

[ol9245]

J'ai relu les NR sur un PDF du livre que j'ai retrouvé au fond de mon DD en attendant de rentrer à la maison pour consulter la version papier. En gros, ils disent :
"bon cette fois-ci, on arrête de jouer.
pour 90% des algos de ce livre, on vous a toujours conseillé de mettre les mains sous le capot pour les adapter à vos besoins et comprendre ce qui se passe.
Mais là, on est dans du sérieux de chez sérieux. Le seul bon conseil qu'on vous donne pour trouver les valeurs propres et vecteurs propres, c'est de cabler une bonne routine toute faite."
Que NR tienne ce langage, c'est à prendre en considération...
OL

[FR119492]

Salut.

Comme déjà souligné par Ulmo, il ne faut surtout pas passer par le polyôme caractéristique; en effet, il n'existe pas de bonne méthode pour calculer les zéros d'un polynôme de degré supérieur à 2; il n'en existera même jamais!

Maintenant, le choix de la méthode dépend de la forme de la taille et de la forme de la matrice, et de ce que tu veux en faire, en particulier du nombre de valeurs propres dont tu as besoin.

Si tu ne veux que la plus grande ou la plus petite valeur propre, ainsi que le vecteur propre correspondant, la méthode de la puissance itérée est la plus simple, mais elle ne converge que très lentement si les deux premières valeurs propres sont très voisine, et pas du tout si elles sont confondues.

Si tu ne veux qu'un petit nombre de valeurs propres, à partir de la plus grande ou de la plus petite, et les vecteurs propres correspondants, tu peux essayer la méthode de la déflation de la matrice, mais attention, au delà d'un certain nombre de valeurs propres, elle devient instable, comme tu sembles l'avoir remarqué toi-même. Il est à noter que cette instabilité n'est pas seulement d'origine numérique, mais provient aussi du fait que ces valeurs propres n'ont pas de signification physique, mais représentent un "bruit" parasite.

Si tu veux toutes les valeurs propres, je souscris entièrement à la recommendation de "Numerical Receipes": utilise un sous-programme tout fait. Tu trouveras ce dont tu as besoin dans les bibliothèques EisPack ou LAPack qui sont téléchargeables gratuitement depuis www.netlib.org.

Si ta matrice est de type "bande", tiens-en compte pour le choix du sous-programme que tu utiliseras.

Enfin une dernière remarque: une prochaine fois, précise de quel problème physique ou autre provient ta matrice. Cela me permettra de te conseiller de manière plus appropriée.

Bonne chance.
Jean-Marc Blanc