salut tous le monde
j'ai un probléme qlq connai t'il un algorithme qui permet de diagonaliser des matrice de dimension NxN existe t'il d'agorithme directe et non itérative
merci
Version imprimable
salut tous le monde
j'ai un probléme qlq connai t'il un algorithme qui permet de diagonaliser des matrice de dimension NxN existe t'il d'agorithme directe et non itérative
merci
1/ pas de langage SMS
2/ a priori ca aurait plus sa place dans le forum algorithme
3/ c'est quoi un algorithme "direct" ? une formule magique qui e sort l'inverse ?
4/ sinon, la methode la plus simple reste le pivot de gauss, me semble t il.
Je sais que dans certains cas il est possible de trigonaliser les matrices (par exemple celles à coefficients complexes), voir de les réduire à la forme de Jordan, mais diagonaliser je ne savais pas...
En fait, tout matrice carrée à coefficient dans C est trigonalisable (mais les valeur propre peuvent être dans C), mais tu dois le savoir :D .Citation:
Envoyé par Zavonen
Par contre, quand tu dis diagonaliser, tu veux les 3 matrices P, P^1 et D tel que M = PDP^-1, ou tu souhaites quelque chose de moins fort (par exemple juste les vecteurs propres).
Oui, pour moi 'diagonaliser' c'est ça et rien d'autre (trouver une base formée de vecteurs propres). C'est à dire que le polynôme caractéristique est factorisable en éléments du premier degré. Et bien, en général ce n'est pas possible, même dans C.Citation:
Par contre, quand tu dis diagonaliser, tu veux les 3 matrices P, P^1 et D tel que M = PDP^-1, ou tu souhaites quelque chose de moins fort (par exemple juste les vecteurs propres).
Donc deux possibilités:
Soit il y a une erreur de terminologie, l'auteur a voulu dire 'trigonaliser' auquel cas il y a beaucoup de méthodes, soit il s'agit bien de 'diagonaliser'. Dans ce cas, il faut des conditions supplémentaires. Si elles sont remplies, il n'y a qu'à exploser le polynôme caractéristique et chercher pour chaque valeur propre le sous-espace propre correspondant en résolvant des systèmes.
euh, si, C est algebriqement clos, donc factoriser un polynome en facteurs lineaires c'est toujours possible. sauf si tu voulais dire "sans repetition"..
Citation:
Envoyé par Zavonen
Oui oui, pour moi aussi. Mais la question là, elle était pas pour toi :mouarf: Il arrive des fois que les gens demandent un algorithme complexe alors qu'ils auraient eu besoin d'un algorithme moins fort. Je lui demandais juste au cas où ;)
Bonjour,
un cours complet sur le sujet se trouve dans "numerical recipes" : http://www.nrbook.com/a/bookcpdf.php
Tu y trouvera tout ce qu'il te faut en fonction du type de matrice que tu as.
oui il s'agit bien de diagonaliser c'est de trouvé une matrice semblable a cette matrice dans une base tel que la diagonale contient les valeurs propres et le reste des zéro l'algorithme dois donné cette matrice moi j'y connai aucun ...
Que penser de :Citation:
Envoyé par Zavonen
Diagonalisable ou pas ? ;)Code:
2
Ca faisait longtemps que je n'avais plus fait ça (enfin, longtemps, façon de parler) :
Le polynome caractéristique vaut : (1-lambda)².
et le sous espace propre associé à 1 (la seule valeur propre) n'est que de dimension 1 (il suffit de calculer Ker(A-I), et trouve que tout élément X =(x1, x2) tel que x2 est nul vérifie AX=X). Donc, ce n'est pas diagonalisable.
Ce qui nous fait rappeler le vrai théorème :
A est diagonalisable si et seulement si :
- Le polynome caractéristique est scindé sur le corps où l'on travaille
- Pour chaque valeur propre lambda de A, la dimension du sous espace propre associé à lambda est égale à l'ordre de multiplicité de lambda (dans le polynome caractéristique). ;)
Mais, A est trigonalisable si et seulement si le polynome caractéristique est scindé sur le corps. Ce qui est le cas si l'on travaille dans C (cf. théorème de d'Alembert)
je suis allé sur le lien mais le document pdf ne s'ouvre pas j'ai trouver dans les titres qlq chose qui ressemble a diagonalistation j'obtien un message d'erreur aucune mise a jour n'est disponible pour le moment peut étre qu'il me fau la nouvelle version d'acrobat reader
@ millie : Tu as de bon souvenirs ;)
Zavonen confondait peut-être avec le polynôme minimal.
@ seifdev : Il faut lire la page :Citation:
IMPORTANT Announcement for Windows® Users:
Effective 1/1/07, you will need the free FileOpen plugin for Adobe [Acrobat] Reader® to use this free resource. If you are getting blank pages, or error boxes, instead of Numerical Recipes chapter sections, then you probably have not installed the plugin. Please see:
How to download and install the plugin
Frequently asked questions about the plugin
Discussion forum for getting help (see Plugin Problems forum)
Bonjour,
si tu parles des liens que j'ai donné, ils marchent très bien, donc c'est que ça provient de ta version de acrobat reader.
Pour ce qui est de trouver les valeurs propres à partir des racines du polynome caractéristiques, attention il s'agit de la méthode la plus instable.
J'en ai fait l'expérience avec avec des matrices symétriques.
Tout est expliqué sur numerical recipes.
OUI ! C'est cela le bon théorème.Citation:
Ce qui nous fait rappeler le vrai théorème :
A est diagonalisable si et seulement si :
- Le polynome caractéristique est scindé sur le corps où l'on travaille
- Pour chaque valeur propre lambda de A, la dimension du sous espace propre associé à lambda est égale à l'ordre de multiplicité de lambda (dans le polynome caractéristique).
Pour le reste, trouver des matrices non diagonalisables c'est facile.
Prenez par exemple une rotation d'angle non multiple de pi, on voit mal comment l'image d'un vecteur (non nul) pourrait lui être colinéaire.
Donc, pas besoin, d'aller loin pour les contre-exemples.
Cela dit, il s'agit bien du polynome CARACTERISTIQUE et non du polynôme MINIMAL, comme il est dit dans l'ennoncé rappelé. Le polynôme caractéristique est défini, a priori pour une matrice, mais c'est un invariant de similitude, donc il est défini pour l'application linéaire représentée par cette matrice.
Polynôme minimal c'est autre chose: c'est défini dans le cas d'une extension de corps K1 extension de K2, x élément de K1 albébrique sur K2 ssi racine d'un pol à coefficients ds K2, parmi tous les polynomes de K2[X] dont x est racine, il en existe un de plus petit degré possible (défini à un coeff près) c'est lui le polynôme minimal. Cette notion, je crois, n'interviens pas ici.
Bon, maintenant, pour diagnaliser une matrice dont on sait a priori qu'elle est diagonalisable, il faut commencer par 'splitter' le polynome caractéristique. Puis il faut dans chaque sous-espace propre déterminer une base. Il s'agit donc de déterminer r vecteurs linéairement indépendants dans un sous-espace de dimension r défini comme le noyau d'une application linéaire ( r est ici la multiplicité de la v.p. comme racine du pol. car.)
On trouve des algos à la rubrique "résolution de systèmes linéaires". Il s'agit ici de systèmes généraux, de rang quelconque et non seulement des systémes dits de Kramer.
En résumé, il suffit de mettre bout à bout des algos 'classiques' (résolution d'équation, factorisation de polynomes, résolution de systèmes linéaires). Pas besoin de tout réecrire.
On peut aussi reprendre la démonstration du théorème de JORDAN, qui fournit l'algo de 'Jordanisation'. Dans le cas où la matrice est diagonalisable, il n'y a que des zéros immédiatemment au dessus de la diagonale, dans le cas général on peut trouver des 0 ou des 1. (Il s'agit ici de matrices à coeffs complexes...)
salu j'ai réussi a ouvrire le lien je vais voir si je peut tiré qlq chose merci pour votre aide
si tu trouve tous les vecteur propres d'une matrice diagonalisable tu peut trouvé la matrice semblable est diagonale n'est ce pas ???
merci pour le lien j'ai trouvé un truc intéressant j'y bosse dedans si j'arrive a enfaire un algorithme en c je lemmetrrai sur le forum merci de votre aide a tous
Je pensais au théorème :Citation:
Envoyé par Zavonen
Polynôme minimal scindé à racines simples <=> diagonalisable
En me disant que tu parlais peut-être de ça ici :Mais en fait même pasCitation:
Envoyé par Zavonen
Passer par le polynôme caractéristique n'est a priori pas très efficace pour trouver des vecteurs propres; il y a des algorithmes plus adaptés (méthode QR si je me rappelle bien), en particulier si la matrice est symétrique (ou hermitienne).Citation:
Bon, maintenant, pour diagnaliser une matrice dont on sait a priori qu'elle est diagonalisable, il faut commencer par 'splitter' le polynome caractéristique. Puis il faut dans chaque sous-espace propre déterminer une base. Il s'agit donc de déterminer r vecteurs linéairement indépendants dans un sous-espace de dimension r défini comme le noyau d'une application linéaire ( r est ici la multiplicité de la v.p. comme racine du pol. car.)
On trouve des algos à la rubrique "résolution de systèmes linéaires". Il s'agit ici de systèmes généraux, de rang quelconque et non seulement des systémes dits de Kramer.
En résumé, il suffit de mettre bout à bout des algos 'classiques' (résolution d'équation, factorisation de polynomes, résolution de systèmes linéaires). Pas besoin de tout réecrire.
On peut aussi reprendre la démonstration du théorème de JORDAN, qui fournit l'algo de 'Jordanisation'. Dans le cas où la matrice est diagonalisable, il n'y a que des zéros immédiatemment au dessus de la diagonale, dans le cas général on peut trouver des 0 ou des 1. (Il s'agit ici de matrices à coeffs complexes...)
Bonjour,
tu as également les codes sources en C... donc c'est quasiment directement applicable...