diagonalisation de matrice NxN

**seifdev** · 25/03/2007, 17h47

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

**jobherzt** · 25/03/2007, 18h04

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.

**Zavonen** · 25/03/2007, 18h44

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

**millie** · 25/03/2007, 22h16

Envoyé par Zavonen

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

.

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

**Zavonen** · 25/03/2007, 23h03

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

**jobherzt** · 25/03/2007, 23h06

euh, si, C est algebriqement clos, donc factoriser un polynome en facteurs lineaires c'est toujours possible. sauf si tu voulais dire "sans repetition"..

**millie** · 25/03/2007, 23h10

Envoyé par Zavonen

Oui, pour moi 'diagonaliser' c'est ça et rien d'autre (trouver une base formée de vecteurs propres).

Oui oui, pour moi aussi. Mais la question là, elle était pas pour toi

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ù

**ToTo13** · 25/03/2007, 23h35

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.

**seifdev** · 26/03/2007, 00h00

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

**Ulmo** · 26/03/2007, 11h44

Envoyé par Zavonen

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

Que penser de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Diagonalisable ou pas ?

**millie** · 26/03/2007, 13h04

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)

**seifdev** · 26/03/2007, 13h58

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

**Ulmo** · 26/03/2007, 15h51

@ millie : Tu as de bon souvenirs

Zavonen confondait peut-être avec le polynôme minimal.

@ seifdev : Il faut lire la page :

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)

**ToTo13** · 26/03/2007, 18h02

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.

**Zavonen** · 26/03/2007, 20h20

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

OUI ! C'est cela le bon théorème.
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...)

**seifdev** · 26/03/2007, 20h53

salu j'ai réussi a ouvrire le lien je vais voir si je peut tiré qlq chose merci pour votre aide

**seifdev** · 27/03/2007, 02h23

si tu trouve tous les vecteur propres d'une matrice diagonalisable tu peut trouvé la matrice semblable est diagonale n'est ce pas ???

**seifdev** · 27/03/2007, 03h33

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

**Ulmo** · 27/03/2007, 11h15

Envoyé par Zavonen

Cela dit, il s'agit bien du polynome CARACTERISTIQUE et non du polynôme MINIMAL, comme il est dit dans l'ennoncé rappelé.

Je pensais au théorème :
Polynôme minimal scindé à racines simples <=> diagonalisable
En me disant que tu parlais peut-être de ça ici :

Envoyé par Zavonen

C'est à dire que le polynôme caractéristique est factorisable en éléments du premier degré.

Mais en fait même pas

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

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