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

Trouver les Racines d'un polynome de degré n.



  1. #1
    KiChoT

    Lightbulb Trouver les Racines d'un polynome de degré n.


    ------

    Bonjour,

    Pour un cours je dois programmer un programme en C qui effectue différente opérations sur les polynômes (Multiplications, divisions etc.) .

    Je bute un peu sur le problème de trouver l'ensemble des racines d'un polynômes de degré.

    Voici la méthode que je pense utiliser (Source)

    Si j'ai un polynôme de la forme suivante:


    Je peux construire la matrice suivante:


    Ainsi en trouvant l'inverse des valeurs propres de la matrice, j'obtiens les racines du polynômes.

    Est-ce que cette méthode vous parait bonne ?

    Si oui quel méthode me conseillez vous pour déterminer les valeurs propres de la matrice ?

    Merci!
    Jonathan

    -----

  2. Publicité
  3. #2
    Ksilver

    Re : Trouver les Racines d'un polynome de degré n.

    Salut !


    ba si tu as une bonne methode pour trouver les vp d'une matrices pourquoi pas... mais moi personellement pour tourver les vp d'une matrices, je calcule son polynome charactéristique et je cherche ces racines... donc on est ramené au problème de la recheche des racines


    à mon avi le moyen le plus simple pour trouver les racines d'un polynome P, c'est :

    1) s'assurer qu'il n'as pas de racine double en calculant le pgcd de P' et P.
    2) trouver une racine par la methode de newton (cf wikipédia si tu ne connais pas)
    3) factoriser la racine en question et recommencer.

  4. #3
    pecheur2savon

    Re : Trouver les Racines d'un polynome de degré n.

    Salut,
    Je ne comprends pas d'où vient cette matrice.
    Ses valeurs propres sont 1 et -a1/a0 car elle est triangulaire donc ses vals propres sont les éléments diagonaux, non?
    La dernière ligne n'est probablement pas nulle, sinon elle n'est pas inversible.

  5. #4
    pecheur2savon

    Re : Trouver les Racines d'un polynome de degré n.

    http://fr.wikipedia.org/wiki/Matrice_compagnon
    me parait plus clair et en français!
    Désolé pour le méssage précédent elle est pas triangulaire et
    la dernière ligne n'est pas nulle

  6. A voir en vidéo sur Futura
  7. #5
    KiChoT

    Re : Trouver les Racines d'un polynome de degré n.

    Oui en France ca

  8. #6
    KiChoT

    Re : Trouver les Racines d'un polynome de degré n.

    Oui en Français ca marche aussi ... Ac cette matrice aussi...
    Il reste a calculer les valeurs propres de cette matrice?
    Quelqu'un a une proposition ?

  9. Publicité
  10. #7
    pecheur2savon

    Re : Trouver les Racines d'un polynome de degré n.

    Salut,

    J'ai eu un cours portant là dessus cette année.

    Un résumé équivalent serait:
    www-math.univ-poitiers.fr/~pierre/AGREG/TP2_M1.pdf
    la partie "calcul numérique de valeurs propres"

    math.univ-lyon1.fr/~filbet/Teach/chap02.pdf
    Parait très complet mais long!

    D'une manière générale ses méthodes applicable à l'informatique
    (Jacobi, QR, puissance, puissance avec décalage;
    par ordre croissant d'efficacité, et donc probablement de complexité
    à incrémenter)
    se trouvent dans un bon cours d'Analyse Numérique dans la sous-partie "calcul de valeurs propres" de la partie "résolution de systèmes linéaires".

    J'avoue ne pas les avoir immédiatement en tête mais si tu bloque je peux m'y replonger...

    La méthode la plus simple à incrémenter est certainement la simple méthode de Newton sur ton polynôme.

  11. #8
    pecheur2savon

    Re : Trouver les Racines d'un polynome de degré n.

    La seule de celle dont je te parle qui permet d'avoir toutes les valeurs propres est QR. (peut-etre aussi Jacobi)

    http://eric.cabrol.free.fr/AnalyseNumerique/an3.html est très clair, je trouve.


    http://cedric.pradalier.free.fr/algonu/index.html
    pour la QR et en particulier:
    http://cedric.pradalier.free.fr/algonu/Algonu.pdf

  12. #9
    fderwelt

    Re : Trouver les Racines d'un polynome de degré n.

    Bonjour,

    Il y a plein d'algorithmes détaillés et implémentés dans "Numerical Recipes" (de plusieurs auteurs, chez Cambridge University Press). Existent "Numerical Recipes in Fortran" et "Numerical Recipes in C", ce sont les mêmes algorithmes avec des langages différents. Quoi que, la version C n'est guère qu'un décalque pas très propre de la version Fortran (tableaux indexés à partir de 1 via un artifice crado...)

    Et le danger est la tentation de recopier froidement (et bêtement) les sources, alors qu'il est bien plus intéressant de comprendre ce que l'on fait.

    Cordialement,

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

  13. #10
    Artanis

    Re : Trouver les Racines d'un polynome de degré n.

    bonjour, je n'ai pas tout suivi en detail, mais pour trouver les racines d'un polynome d'un degré n, si tu n'est pas obligé d'utiliser une tel matrice, tu peux toujours utiliser les suites de Sturm et de la dichotomie.
    Enfin, ceci marche bien tant que tu as des racines simples...

    P.S : pour les valeurs propres d'une matrice, tu as la méthode des puissances pour les determiner...(dsl si quelqu'un en a deja parler ^^)

  14. #11
    KiChoT

    Re : Trouver les Racines d'un polynome de degré n.

    Bon a la lecture de NR l'implémentation de la méthode de la matrice ac les valeurs propres parait assez compliqué...

    Je crois que je vais essayer de programmer la méthode de newton, puis factoriser le poly par la racine trouver etc.

    Ca semble etre la meilleur solution

  15. #12
    acx01b

    Re : Trouver les Racines d'un polynome de degré n.

    salut

    même si c'est très intéressant d'un point de vue mathématique/algorithmique d'essayer de comprendre,

    d'une manière générale c'est toujours pas mal d'utiliser une libraire au lieu de "réinventer la roue" :
    gsl (GNU) par exemple, ou les .mex32 de matlab qui permettent d'avoir toutes les possibilités de calcul de matlab en librairie dynamique

  16. Publicité

Discussions similaires

  1. Racines d'un polynôme du troisième degré
    Par aurk dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 30/10/2008, 12h15
  2. Trouver les racines d'un polynôme
    Par etiennelec dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 24/02/2008, 19h34
  3. condition sur les racines d'un polynome ...
    Par 范des数学 dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 27/11/2006, 09h01
  4. racines d'un polynome de degre 4
    Par ushu dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 04/11/2006, 09h04
  5. Racines d'un polynome du 30e degré
    Par Eric78 dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 22/05/2006, 21h57