Discussion :

[malbarre]

je dois réaliser un code C qui calcule les valeurs propres d'une matrice donnée en utilisant la matrice de householder et la méthode de rotation de givens

je cherche un tutorial ou une aide pour le réaliser

[Déplacé du forum C par Gangsoleil]

[gangsoleil]

Bonjour,

Qu'est-ce qui pose problème ? L'algorithme ? l'implémentation ? autre chose ?

[malbarre]

c plutot l'implémentation

[Nemerle]

encore un étudiant qui veut se faire faire ses exo? Déjà si c'est l'implémentation, c'est pas de l'algorithmique...

[gangsoleil]

Si c'est un problème d'implémentation, alors poste le code que tu as écrit et qui pose problème dans le forum C.

Si c'est un problème au niveau de l'algo, alors il faut que tu poses ta question plus précisément ici.

Ceci dit, une recherche sur google donne pas mal de résultats, comme ceci par exemple : http://www.library.cornell.edu/nr/bookcpdf/c11-2.pdf

[Matthieu Brucher]

Si tu trouves le livre de Van Loan, tout est expliqué dedans !
Premièrement, est-ce une matrice hermitienne ou pas ?
Si c'est une matrice hermitienne, tu commence par tridiagonaliser la matrice avec la même matrice de Houseolder de part et d'autre - à la transposition près - : tu essaies d'éliminer les n-2 dernières cases de la matrice.
A la fin, tu obtiens une première décomposition.
Ensuite, il te faut décomposer la matrice trigonale. Pour cela, tu utiliseras les matrices de givens. Tu commences donc par trouver une sous matrice trigonale. Si elle est de taille 2, ça va, il te faut trouver une matrice de rotation pour essayer d'éliminer les termes non-diagonaux. Si elle est de taille supérieure, tu fais la même chose avec la sous-matrice de taille 2, puis tu élimines les termes que tu auras introduit.
Pour une explication un peu plus claire, je te propose de regarder dans l'extrait de Numerical Recipes in C qui parle de cela, ça se trouve sur le net. Autre chose aussi, regarder l'implémentation de cet algo par la GSL - dossier eigen -> qstep.c -
Le meilleur moyen pour comprendre cette étape est de jeter un oeil au livre de Van Loan, Matrix Computations, où il y a un schéma...
Si la matrice n'est pas hermitienne, il faut la bidiagonaliser, puis avec des étapes QR, on peut la diagonaliser - mais cette méthose a un bruit de 10^-3 avec des flottants tandis que pour les herimitiennes, c'est de l'ordre de l'epsilon -

[Rafy]

Je veux pas mettre le bazzard, mais si c'est juste pour trouver les valeurs propre d'une matrice, le polynôme caractéristique c'est pas bien dans ton cas ?
Tu dois absolument passer par tes matrices de Householder et rotation de Givens ?
Ton algorithme doit-il être performant ou précis, ou les deux ?
Il est ponctuel, ou non (je veux dire par la c'est pour un jeu, qui doit calculer les valeur propres à chaque frame, ou bien tu as "tout ton temps pour calculer") ?

[Matthieu Brucher]

C'est en quelle copmplexité la recherche du polynôme caractéristique ?

[Jedai]

La recherche du polynôme caractéristique c'est "juste" le calcul d'un déterminant... En plus il faut rechercher les racines de ce polynôme !!
Sauf si tu as des documents qui nous prouvent qu'il y a moyen de faire tout ça rapidement, je pense qu'on peut oublier.

--
Jedaï

[Matthieu Brucher]

Le déterminant est le produit des racines, non ? donc le dernier coefficient du polynôme caractéristiques ? - punaise, ça fait 5 ans que je ne m'étais plus posé ce genre de questions, ça fait mal... -

[Rafy]

Ben ca dépend de la taille de la matrice, c'est sur que si on a une matrice 15x15 c'est pas cool le polynome...
Mais on peut se servir de la trace de la matrice (la trace de la matrice est égale à la somme des valeurs propres comptées autant de fois que leur multiplicité..)
Donc on a déjà 2 coefficents du polynome. (3 en comptant le terme dominant) :

Code :

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

1
2
 
(-1)^n * X^n + Tr(A) * X^(n-1) +......+ Det(A)

avec n l'ordre de la matrice, A la matrice
Si la matrice est d'ordre 2 on a tout.
Si elle est d'ordre 3, c'est pas fini.
Mais il est possible d'exprimer les autres coefficients du polynome au moyen des cofacteurs de la matrice.. Il faut rechercher je ne les connais pas.
Si ensuite tu connais tous les coefficients du polynome directement, ça se passe pas trop mal...
En plus on est sur qu'il y a des racines si on est sur qu'il y a des valeurs propres....

Je ne suis pas tout a fait sur des signes dans l'expression littérale du polynome dans le cadre code

[Matthieu Brucher]

Et ensuite, il faut factoriser le polynome... donc le plus rentable est définitivement une série de matrices de Houseolder et une série de rotations de Givens dans le cas hermitien.

[Rafy]

Connait pas la methode avec les matrices...
Mais faire des calculs sur des matrices ça peut être lourd.
Je suis d'accord que le polynôme caractéristique c'est lourd aussi....