Répondre à la discussion
Affichage des résultats 1 à 18 sur 18

Valeurs propres et racines d'un polynome...



  1. #1
    evariste_galois

    Valeurs propres et racines d'un polynome...


    ------

    Bonjour à toutes et à tous

    Dans le cadre d'un cours informatique en langage C (niveau 2ième année), chaque élève doit présenter un projet de son choix faisant appel aux notions d'algorithmique abordées jusqu'à présent.

    Dans un soucis d'originalité, j'ai décidé de m'attacher à la diagonalisation et le calcul des puissances n-ième des matrices carrées.

    Mais voilà le langage C c'est pratique, sauf que ça fait pas tout (c'est là qu'on se rend compte à quel point Maple et compagnie sont puissants et pratiques!).

    J'ai bien réussi à faire des fonctions donnant le déterminant de matrices carrées sur lR, calculant l'inverse d'une matrice, la trace (pas très dure celle-là!!)...
    Mais dès qu'il s'agit de créer une fonction permettant le calcul du polynome caractéristique, c'est tout autre chose. Je bloque, je bloque...

    J'aurais donc aimé savoir s' il existe des algorithmes permettant de calculer des approximations des valeurs propres d'une matrice, et de racines d'un polynome à coefficients réels.

    Merci d'avance.

    -----

  2. Publicité
  3. #2
    Sigmar

    Re : Valeurs propres et racines d'un polynome...

    Si tu es capable de calculer des déterminants, pourquoi tu ne serais pas capable de déterminer le polynome caractéristique.
    (dans le cas ou tu ne peux faire que des calculs de déterminants sans paramètres, ne lis pas la suite).
    sinon, je te rappelle que le polynome caractéristique n'est que le déterminant de ta matrice (de taille n finie) moins le paramètre voulu multiplié par la matrice identité de même dimension.
    P(X)=det(M-X*In)
    Sinon tu dois pouvoir faire des déterminants avec des paramètres (c'est impossible sinon).
    Pour ce qui est des racines, tu peux toujours faire par tatonement en remplaçant la valeur testée dans le polynome et en minorant le résultat (si jamais la valeur absolue du résultat est <0.0001 alors ce résultat est satisfaisant), sinon on teste une autre valeur. C'est assez long mais ça marche. Après tu peux aussi faire des fonctions qui accèlèrent tout ça.
    Sinon tu peux essaye de trouver une solution pour dans un premier temps factoriser le polynome (en essayant des racines simples telle que 1 ou -1, 2 ou -2).
    J'ai fait tout ce qui était en mon maigre pouvoir.
    "I have to understand the world, you see." (Richard P. Feynman)

  4. #3
    evariste_galois

    Re : Valeurs propres et racines d'un polynome...

    Merci pour ton aide Sigmar.

    Simplement je ne peux calculer, comme tu en fais mention, le déterminant d'une matrice possédant des variables, toutes les valeurs de la matrice doivent être définies précisément.
    C'est pas pour tout de suite le calcul formel pour moi

    Donc j'oublie le polynome caracréristique pour l'instant et j'essaye de trouver une méthode d'approximation des valeurs propres d'une matrice, ce qui j'espère existe!

    La recherche par tatonement a ses avantages, ms montre très vite ses limites, et donne le plus souvent des résultats peu constructifs, donc j'espère éviter cette voie.
    Quand à la méthode par majoration et minoration des racines itérées, je la trouve intéressante.
    Je vais tenter d'en tirer quelque chose.

  5. #4
    Sigmar

    Re : Valeurs propres et racines d'un polynome...

    Je crois cependant que tu vas être obligé de passer pas des paramètres :/.
    Ca doit pas être si compliqué que ça.
    Tu peut aussi tester les valeurs propres directement sur ta matrice par itération...
    Tu vérifie que det(M) est différent de 0. Si oui alors 0 est valeur propre.
    Tu fais det(M-1*In)
    Tu fais det(M-2*In)
    .
    .
    .
    Tu fais det(M-k*In)
    Tu testes si ces déterminants sont nuls.
    Tu trouveras donc déja pas mal de valeur propres. Ensuite tu peux comparer le nombre de valeurs propres à la dimension de ta matrice pour évaluer le nombre de valeurs propres manquantes (en effet le nombre de valeurs propres est égale à la dimension de ta matrice carrée).
    Ca peut t'avancer un peu.
    Si jamais tes valeurs propres ne sont pas forcément entières (ce qui est souvent le cas), cette méthodes est déja beaucoup plus longue.
    Après pour les valeurs propres doubles :/
    Ca risque d'être plus chaud.

    C'est vrai que tu t'es lancé dans pas facile.
    Mais cherche sur la piste des paramètres, c'est surement faisable (je suis pas un bon en C++ aussi^^).
    Dernière chose : cherche aussi du côté de résolution des polynomes en C++, ça a surement déja été fait (du moins de degré 2).
    Après pour les degrés supérieurs, ça devient vite très lourd.
    "I have to understand the world, you see." (Richard P. Feynman)

  6. #5
    evariste_galois

    Re : Valeurs propres et racines d'un polynome...

    En fait tu as raison Sigmar, le calcul du déterminant à l'aide de paramètre n'est pas si compliqué que ça.
    Le seul problème est que le résultat est totalement désordonné et pas tres intuitif, donc difficilement manipulable (peut etre une fonction de tri arrangerait les choses)...
    Cependant je ne dois pas sortir du cadre du cours, et par exemple les algo de tris on les voit qu'au 4-ième semestre....
    En fait le plus simple serait de choper des bibliothèques de fonctions déjà toutes faites, mais où serait l'interet!

    Pour la résolution des équations polynomiales, j'ai fixé le degré maximal à 5, ms je pense qu'il vaudrait mieux le ramener à un degré inférieur.

    Merci pour toutes ces indications

  7. A voir en vidéo sur Futura
  8. #6
    Stephen

    Re : Valeurs propres et racines d'un polynome...

    Si le degré maximal que tu t'autorises est 4 ou 5, un truc tout bête est de te donner sur le papier une matrice de taille 2 avec des a_ij, de calculer formellement son polynôme caractéristique (avec la méthode des cofacteurs), et de faire pareil pour les degrés 3 et 4. Sinon hors calcul formel ce n'est pas évident.

    Pour certaines matrices, on sait placer les valeurs propres dans un compact particulier (cherche "Disque de Gershgorin" dans Google), mais c'est pas la panacée...

  9. Publicité
  10. #7
    evariste_galois

    Re : Valeurs propres et racines d'un polynome...

    Trouver une solution génèrale pour chaque degré est une bonne idée effectivement.
    Merci Stephen

    Pour ce qui du Disque de Gershgorin, me recherche sur le net ne donne rien de concret, et aparemment ça s'apparente à de l'analyse matricielle, bien loin de mon niveau de 2ième année

    En tout cas merci pour votre aide.

    Petite question totalement hors-sujet (j'ai pas envie de créer un topic juste pour ça): pourquoi appelle-t-on {Somme de 1 à n de 1/n}
    la série Harmonique?
    Y a-t-il un rapport avec la musique?

  11. #8
    Evil.Saien

    Re : Valeurs propres et racines d'un polynome...

    Saut,
    j'ai peut-etre une solution a ce problème, probablement loin d'être la plus rapide mais qui marcherait avec n'importe quelle taille...
    Mais pour cela, il faudrait utiliser un tableau de tableau:
    Dans les sous tableaux, tu mets les coeff des puissances de x.

    Par exmple, la matrice
    ((a | b-x)
    (5x^2+c | x^5-x^3+8))
    pourrait s'écrire:
    Dim1:
    ((0,0,0,0,0,a) | (0,0,0,0,-1,b)
    (0,0,0,5,0,c) | (1,0,-1,0,0,8))

    Maintenant il ne reste "plus qu'à" faire une fonction qui multiplie les polynomes, puisque tu as deja la fonction qui fait le determinant... Au final tu obtiendrais un polynome deja ordonné, pas besoin de fonction tri

    J'éspère que tu vas en voir le bout
    ++

  12. #9
    Oakenshield

    Lightbulb Re : Valeurs propres et racines d'un polynome...

    Bonjour à tous,

    Il est extrêmement simple de calculer des approximations des valeurs propres d'une matrice carrée ainsi que les vecteurs propres associés : il suffit d'utiliser par exemple la méthode de la puissance itérée (qui calcule une approximation de la valeur propre de plus grand module), et de généraliser le procédé (méthode de déflation de Wielandt)...

    Fais une petite recherche Google sur "puissance itérée", et tu trouveras sans problème !

  13. #10
    evariste_galois

    Re : Valeurs propres et racines d'un polynome...

    Evil.Saien, merci pour ton aide, en fait j'avais déjà pensé à définir une fonction qui multiplie les polynomes, mais j'ai de sérieux problème parce que je suis limité au niveau des outils manipulables (les profs insistent pour qu'on se serve uniquement de ce qui a été vu en cours, donc pas de classes, donc pas de surchage des fonctions, donc pas d'héritage,..enfin pas grand chose lol!).

    Oakenshield merci pout ton aide, je vais essayer de me renseigner sur les puissances itérées (meme si je sens que ça va etre difficile à comprendre...simple intuition ).
    "Au train où vont les choses, les choses où vont les trains ne seront plus des gares."

  14. #11
    Evil.Saien

    Re : Valeurs propres et racines d'un polynome...

    A la limite y'a meme pas besoin de créer une classe polynome, il suffit juste de faire une fonction qui multiplie 2 polynomes a a laquelle tu passe 2 matrices 1xN comme argument... T'as le droit de faire des fonctions ?

  15. #12
    catrina

    Re : Valeurs propres et racines d'un polynome...

    salut
    j'ai un probleme je ne sais pas ecrire un programme en langage c qui montre comment calculer les racines d'un polynome de troisième degré

  16. Publicité
  17. #13
    matthias

    Re : Valeurs propres et racines d'un polynome...

    Tu veux calculer quoi ? La forme exacte des racines ou juste une approximation ?
    Si tu cherches la forme exacte tu peux aller voir ici : http://villemin.gerard.free.fr/ThNbDemo/Eqa3d.htm

    Si tu veux le faire par approximation, tu peux commencer par trouver une valeur sur laquelle ta fonction est positive, une autre ou elle est négative (toujours possible avec un polynôme du troisième degré) et faire une bête dichotomie. Ca te donne une racine, tu factorises et tu te ramènes à un binôme.

  18. #14
    med007

    Re : Valeurs propres et racines d'un polynome...

    Bonjour tout le monde,
    Je suis un étudiant en 1ère année en une formation d'ingénieurie en informatique.
    J 'ai comme projets durant le second sem de réaliser les programmes de tout les chapitres qu'on fait en algèbre multilinéaire:
    .Réduction des endomorphisme (Jordan);
    .Réduction en carré des formes quadratiques
    .Trouver des bases orthogonales associée à ces formes quadratiques
    .Trouver des bases orthonormales des éspaces euclidiens ....
    Alors j'aimerais que vous m'aider à cela je vous remercie d'avance...
    J'aimerai bien un programme qui traite toute matrice de toute taille car mon prob est de trouver les racines du polynôme caractéristique...

  19. #15
    fderwelt

    Re : Valeurs propres et racines d'un polynome...

    Bonjour,

    Juste un grain de sel: il existe des brouettées d'algorithmes de diagonalisation numérique de matrices, y compris de très grande taille (voir p.ex. www.nr.com, pas le meilleur, mais le principal y est).
    Et jusqu'à nouvel ordre, diagonaliser, c'est bien trouver les valeurs propres? Même les plus bourrins des algorithmes peuvent (être arrangés pour) donner les valeurs propres en ordre décroissant... La plupart reposentsur des rotations pour trouver les axes propres, mais il y a pas mal de variantes.

    -- françois
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  20. #16
    rvz

    Re : Valeurs propres et racines d'un polynome...

    Salut,
    Pour rajouter ma pierre à l'édifice, je vous conseille d'aller faire un tour sur la page de Bruno Desprès, du master d'analyse numérique de Paris 6, et notamment son cours d'analyse numérique matricielle.

    __
    rvz

  21. #17
    indian58

    Re : Valeurs propres et racines d'un polynome...

    Bonjour,

    voilà ma contribution avec un algorithme permettant de calculer assez simplement les coefficients du polynôme caractéristique d'une matrice: c'est la méthode de Faddeev

    http://homeomath.imingo.net/faddeev.htm

    http://www-fourier.ujf-grenoble.fr/~...eve/alglin.pdf

    http://fr.wikipedia.org/wiki/Algorit...deev-Leverrier

  22. #18
    Ksilver

    Re : Valeurs propres et racines d'un polynome...

    sinon je te propore une idee de methode pour diagonaliser une matrice numeriquement "directement" (je sais pas si cette methode a un nom preci... mais c'est comme sa que je procede moi...)

    dans les grandes lignes :
    on veut diagonaliser une matrice M.

    on pose Po = M

    Pn+1 = (Pn)^2/trace(Pn^2)

    'en general' Pn converge tres rapidement (quadratiquement en fait) vers une matrice L

    si c'est le cas, P=L/trace(L²) est la matrice d'un projecteur, qui projete dans le sous-espace propres associé a la plus grande valeur propre de M. on connait la dimension de cette espace : rg P, et comme P est un projecteur rg P = trace P qui est assez facile a calculer ^^

    on peut donc extraire une base de l'espace propre, calculer simplement la valeur propre associé lambda, et recommencer le processus avec M-P*lambda.

    quand sa fonctione, c'est assez rapide : la multiplication matricielle est en O(n^3), ( O(n^2,3) sous sa forme la plus optimiser), le nombre d'iteration avant convergence est assez faible et n'augmente aps avec n, et il faut recommencer le processu n fois, sa fait un temps de calcule en O(n^4)... ce qui est tres acceptable si on considere que les fonction de diagonalisation de maple par exemple sont meme aps en temps polynomial !!


    pour les cas ou Pn ne converge pas :

    on peut par exemple recommencer avec la matrice complexe M+I*In (mais il faut programer les calcules sur les nombres complexes) et la en general, sa marchera ! (M+I*In, ayant les meme vecteur propres que M, et les meme valeur propre a "-I" pres)

  23. Publicité

Discussions similaires

  1. Racines d'un polynôme
    Par AriesSith dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 22/05/2009, 20h32
  2. valeurs et vecteurs propres d'un endomorphisme.
    Par rasengan dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 16/07/2007, 16h26
  3. Valeurs et vecteurs propres d'un opérateur linéaire
    Par Bleyblue dans le forum Mathématiques du supérieur
    Réponses: 49
    Dernier message: 07/06/2007, 00h18
  4. Valeurs propres d'un endomorphisme antisymétrique.
    Par Gpadide dans le forum Mathématiques du supérieur
    Réponses: 15
    Dernier message: 24/03/2007, 13h21
  5. Simplicité des valeurs propres d'un opérateur intégrale
    Par dhahri dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 20/01/2007, 09h40