Recherche de valeurs propres

**petdelascar** · 21/02/2006, 18h46

Bonjour,

J'aimerai obtenir en langage C les valeurs propres d'une matrice carrée réelle. J'ai donc cherché des fonctions qui pouraient le faire dans des bibliothèques existantes en C mais ne trouve que des algos trouvant les valeurs propres de matrices symétriques ou hermitiennes et non carrées quelconques.
Quelqu'un pourait donc t il m'aider à trouver une solution à mon problème, ma bibliothèque comprend des fonctions d'algèbre linéaire (dont la décomposition QR) et de recherche de valeurs propres sur matrices symétriques et hermitiennes, il s'agit de la bibliothèque GNU.

Merci beaucoup

**xxiemeciel** · 21/02/2006, 19h14

Salut,

Pour tout les traitement matricielles la livrairie la plus performante est LAPACK qui est gratuite (MATLAB utilise LAPACK). Elle est en FORTRAN mais il existe une libraire en C qui s'appelle CLAPACK je crois.

par contre je te previens c pas evident a utiliser.

XXiemeciel

**j.p.mignot** · 21/02/2006, 20h02

le kit "Numerical Recipes" permet ce genre de calcul. Il coûte environ 100 US$. Je conseille fortement l'acquisition ce ce kit d'outils et surtout du livre qui l'accompagne.
Toutefois si on veut uniquement résoudre le problème proposé on peut le programmer soit même à partir du système d'équations M.U = Lambda.U
donc det(M-l.I)=0
si le degré est <= 4 alors une solution analytique existe et s'exprime sans difficultés, si non il n'y a pas de solution analytique de façcon générale ( théorie des groupes de gallois) et une méthode par approximations successives est necessaire.
le théorème de Gerschgorin (par exemple pour situer ce théorème voir http://www.math-info.univ-paris5.fr/~pastre/meth-num/MN/9-val-pro/cours-valeurspropres.pdf) tout comme des considérations du type det(M) = Produit ( Li) i=1..n doivent permettre d'initialiser le problème et de faciliter sa convergeance

**petdelascar** · 22/02/2006, 01h10

Merci grandement, ça se trouve on se connait :-)

**petdelascar** · 22/02/2006, 01h44

L'algo Algorithme de Rutishauser semble m'interresser, mais où sont les valeurs propres?

**j.p.mignot** · 22/02/2006, 04h33

Algorithme de Rutishauser
On décompose la matrice A en 2 matrices L (Low) et U (Up),
L etant une matrice triangulaire inferieure dont les éléments
diagonaux sont 1 et U une matrice triangulaire superieure
telles que A = L . U
On calcule A1 =L^-1 . A . L = U . L
qui a les mêmes valeurs propres que A
- On décompose alors A1 en A1 = L1 . U1
- On calcule A2 = U1 . L1 ...
Dans certaines conditions, la suite de matrices Ak
converge vers une matrice triangulaire superieure
où les valeurs prores sont les éléments diagonaux.

voir l'article

http://www.math-info.univ-paris5.fr/~pastre/meth-num/MN/9-val-pro/cours-valeurspropres.pdf

pages 6 à 8

Il existe un code en C disponible sur
http://progfrance.tuxmania.org/index.php/Projet_Outils_Math%E9matiques

Un autre source code est disponible sur
http://membres.lycos.fr/teledev/log/src/srcidx.htm
sous la rubrique "Mathematics, numerical methods"

Mais je ne les ai pas testé.
J'utilise personnellement mon propre code basé sur le livre de Numerical Recipes. ( aussi à partir décomposition LU )

**Matthieu Brucher** · 22/02/2006, 09h42

Tu peux bidiagnonaliser ta matrice, comme pour les matrices symétriques que tu tridiagonalises, puis tu fais des mini-rotations autour de 2 axes et tu propages ces modifs dans la matrice en gardant toujours la bidiagonalité. C'est comme ça que je fais pour mes algos de calculs de racine carré par exemple.

**petdelascar** · 22/02/2006, 15h18

Merci, j'ai compris.

**petdelascar** · 24/02/2006, 02h35

Au sujet de CLAPACK, XXIMECIEL:

Tu me parles de CLAPACK, je parviens à le faire fonctionner mais j'ai un pb lorsque je l'insère dans un long code utilisant d'autres librairies, à parrament j'ai un conflit de librairie du type:

Code :

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

1
2
 
MSVCRTD.lib(MSVCRTD.dll) : error LNK2005: _printf already defined in LIBC.lib(printf.obj)

Donc j'ignore la librairie libc.lib comme demandé par le compilateur mais après j'ai le pb du type suivant:

Code :

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

1
2
 
libtsp.lib(STfindToken.obj) : error LNK2001: unresolved external symbol ___mb_cur_max

libtsp est une autre librairie dont je me sert. Je me suis dit que le second type d'erreur était du à la librairie ignorée.

Bref as tu déja eu ce type de pb en utilisant LAPACK?

Merci

**Matthieu Brucher** · 24/02/2006, 10h03

T'es sous Windows ? Si oui, fait gaffe à quelles libs tu utilises dans quel mode - debug, release, ... -

**petdelascar** · 24/02/2006, 14h44

Je ne parviens vraiment pas à inclure CLAPACK dans mon projet, ayant juste besoin de trouver les valeurs propres possiblement complexes d'une matrice quelconque quelqu'un pourait il m'indiquer une autre librairie ou un bout de code réalisant cette tache, merci grandement.

**Matthieu Brucher** · 24/02/2006, 15h23

T'es sous Windows ou pas ? Tu as quel compilateur ? Tu utilises quelle version de CLAPACK ? ... ?

**petdelascar** · 24/02/2006, 15h59

Je suis sous windows, visual C++ 6.0, CLAPACK.

**petdelascar** · 24/02/2006, 16h00

CLAPACK v3

**Matthieu Brucher** · 27/02/2006, 09h33

Et CLAPACK a été compilé comment ?

**petdelascar** · 28/02/2006, 18h40

Je suis parvenu à programmer l'algo de Rutishauser.
Il trouve bien les valeurs propres complexes d'une matrice complexe.
Mais si je lui entre une matrice réelle, les valeurs sont réelles alors que sous matlab et de façon mathématique, elles peuvent être réelles.
Je vais devenir fou si je ne parviens pas à trouver une solution...
Merci

**petdelascar** · 28/02/2006, 18h45

Et CLAPACK a été compilé comment ?

Compilé à partir du projet visual c++ compris dans le repertoire racine de la librairie CLAPACK. Je suis aprvenu à le faire fonctionner sous un petit projet, mais dès que je l'insère à un plus gros projet, ça bug au build.
On m'a dit que ça pouvait être lié au mode multi thread ou single thread, j'ai tout tenté, j'ai biensur tenté de faire cohabiter toutes les librairies, 2 sur 3 supportent le multi thread et une le single thread, j'ai donc compilé en multi thread, j'ai tj des pb. J'ai tout tenté, ignorer la librairie qui pose conflit mais rien ne va.

**j.p.mignot** · 01/03/2006, 08h29

les valeurs propres etant les solutions - non nulle - de
det(M - l. I ) =0

on recherche les zéros du polynôme caractéristique qui est de degré n ( si M est nXn )
Bien entendu dans le corps C, cela donne n racines ( eventuellement doubles, triples, ...)

si on se limite au corp R des Réels, on peut bien entendu avoir bien moins de zéros pour le polynôme caractéristique.

Si on veut avoir toutes les racines, alors même si M est réelle, il faut la concidérer comme complexe. Des zéros conjugués complèterons les valeurs manquantes.

Attention, du aux arrondis de calculs, je pense que même les solutions réelles vont avoir ( numériquement UNIQUEMENT! ) une partie imaginaire non nulle.

**petdelascar** · 01/03/2006, 17h11

Donc l'algoriyhme de Rutishauser n'est pas applicable aux matrices complexes?

Recherche de valeurs propres

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager