Valeurs propres et racines d'un polynome...

[invitea77054e9]

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

[invite5e5dd00d]

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.

[invitea77054e9]

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.

[invite5e5dd00d]

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.

[A voir en vidéo sur Futura]

[invitea77054e9]

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

[invite51f4efbf]

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

[invitea77054e9]

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?

[Evil.Saien]

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

[invite9565d975]

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 !

[invitea77054e9]

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

[Evil.Saien]

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 ?

[invitecb0217e0]

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é

[matthias]

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.

[invite72592872]

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

[invite6de5f0ac]

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

[invite6b1e2c2e]

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

[indian58]

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

[invite4ef352d8]

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)