Discussion :

[Kromagg]

Bonjour à tous

Est-ce que vous pourriez m'expliquer le principe d'une décomposition LU ?
Ca serait pour calculer le déterminant et l'inverse d'un matrice 4x4. Pour le moment j'utilise les règles de Kramer comme j'ai pu le lire sur la faq matrices et quaternions mais il est précisé qu'il faut mieux utiliser une décomposition LU.

Pour le moment je n'ai pu trouver qu'un aspect purement théorique de la décomposition LU et comme je ne suis pas un grand matheux, je m'adresse à vous

Merci d'avance
Kromagg

[plegat]

Salut

comme je ne suis pas un grand matheux

Bon, ben alors un conseil, laisse tomber!

Deux choix maintenant:
1) soit tu utilises une bibliothèque mathématique qui l'implémente déjà (colt par exemple, ou jscience qui ne me semble pas faire de décomposition LU directement mais qui possède les opérations matricielles de base)

2) soit tu restes aux méthodes simple avec kramer, laplace, comatrice et transformations inverses. Une matrice 4x4 est tout de même relativement simple pour ces opérations, la décomposition LU est plus rentable sur les grosses matrices. Et pour tes matrices inverses, tu auras plus vite fait de décomposer en translation et quaternion et de faire la manip inverse puis reconstruire la matrice (enfin, avis personnel, j'ai fait comme ça moi).

[Kromagg]

Bon, ben alors un conseil, laisse tomber!

J'ai quand même posté ici pour apprendre, si à chaque fois qu'il s'agit de math on s'arrête à des considérations comme celles-ci on ne peut pas progresser. Même si je dois passer une semaine la dessus au moins j'aurais appris la théorie et ce sera toujours un plus

[plegat]

J'ai quand même posté ici pour apprendre, si à chaque fois qu'il s'agit de math on s'arrête à des considérations comme celles-ci on ne peut pas progresser.

Disons que c'était essentiellement pour souligner le peu d'intérêt que je porte à une décomposition LU sur une matrice 4x4... avec beaucoup d'implication mathématique, de réflexion et de travail, alors qu'il y a d'autres méthodes plus rapides et plus simples à mettre en oeuvre.

Même si je dois passer une semaine la dessus au moins j'aurais appris la théorie et ce sera toujours un plus

Bon, alors si c'est pour ta culture, on va essayer d'expliquer...
Tout d'abord, le lien wikipedia qui explique la manip.
Notations: * pour le produit matriciel, ^-1 pour l'inverse d'une matrice

Tu prends ta matrice, et on va appliquer dessus un processus itératif.
On considère n, avec n allant de 1 à 4-1=3 (4 étant la dimension de ta matrice).
La matrice courante est appelée A(n-1) (la matrice A de départ peut donc se noter A(0)), et on va construire le vecteur L(n) tel que toutes les colonnes soient à 0 excepté leur terme diagonal à 1, et la n-ième colonne avec tous les termes au-dessus de la diagonale à 0, le terme diagonal à 1, et les termes en-dessous définis par -a(i,n)/a(n,n), avec a(i,j)=terme de la matrice A(n-1) sur la ligne i, colonne j.
Tu calcules ensuite la matrice A(n)=L(n)*A(n-1)

Tu remarqueras que sur la matrice A(n), l'opération que l'on vient de faire à mis à 0 tous les termes en-dessous de la diagonale de la n-ième colonne.

Reste plus qu'à répéter l'opération pour le n suivant.

Quand tu arrives à la fin de l'opération pour n=3, tu te retrouves avec un matrice A(3) qui est triangulaire supérieure, que l'on peut appeler U
Et comme:
A(0)=L(1)^-1*A(1)=L(1)^-1*L(2)^-1*A(2)=L(1)^-1*L(2)^-1*L(3)^-1*A(3)
tu peux écrire:
A(0)=L*A(3) avec L=L(1)^-1*L(2)^-1*L(3)^-1, qui est une triangulaire inférieure
et donc que A(0)=L*U, et tu viens de décomposer ta matrice

Alors attention, pour être rigoureux, vu qu'à un moment tu divises par le terme a(n,n), il faut que celui-ci soit différent de 0. Si jamais tu tombes sur un terme nul, il faut permuter la ligne en cours avec une ligne en dessous dont le terme correspondant n'est pas nul, pour pouvoir faire la division. C'est pour cela qu'en toute rigueur, on fait intervenir une matrice de permutation P qui va permuter les lignes donc afin d'éviter ce problème.
Donc, au final, on a en fait A(0)=P*L*U

Pour calculer l'inverse des matrices L(n), c'est assez simple ici, il suffit d'inverser le signe des termes sous la diagonale.

Voilà... il faut appliquer sur un exemple pour que ce soit bien clair par contre, c'est un peu théorique comme ça!

[Kromagg]

Merci bien pour cette explication je vais essayer de mettre ça en place.

Disons que c'était essentiellement pour souligner le peu d'intérêt que je porte à une décomposition LU sur une matrice 4x4... avec beaucoup d'implication mathématique, de réflexion et de travail, alors qu'il y a d'autres méthodes plus rapides et plus simples à mettre en œuvre.

Quelle(s) méthode(s) tu pourrais me conseiller qui soient plus facile à mettre en œuvre et surtout plus adapter pour une matrice 4x4 ?

Kromagg

[plegat]

Quelle(s) méthode(s) tu pourrais me conseiller qui soient plus facile à mettre en œuvre et surtout plus adapter pour une matrice 4x4 ?

J'en ai cité quelques-uns précédemment

2) soit tu restes aux méthodes simple avec kramer, laplace, comatrice et transformations inverses.

Pourrais-t'on savoir dans quel cadre tu as besoin de faire ces calculs sur des matrices 4x4?
Par exemple, pour mon moteur 3D, j'utilise des matrices 4x4 pour les matrices Opengl. Hors je ne passe jamais par des calculs de déterminant ni d'inverse sur les matrices. Toutes les opérations se font sur les translations et les quaternions (pour lesquels c'est relativement simple d'avoir l'inverse), qui sont ensuite convertis en matrice 4x4.