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

[invitedcd688a2]

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
-----

[invite4ef352d8]

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.

[invite10c0f164]

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.

[invite10c0f164]

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

[A voir en vidéo sur Futura]

[invitedcd688a2]

Oui en France ca

[invitedcd688a2]

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 ?

[invite10c0f164]

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.

[invite10c0f164]

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

[invite6de5f0ac]

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

[invite3a7881fd]

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 ^^)

[invitedcd688a2]

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

[acx01b]

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