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.

[Kromagg]

En fait c'est surtout pour mettre en pratique ce que je peux apprendre en 3D.

J'ai acheté récemment ce livre http://www.amazon.fr/Math-Primer-Gra.../dp/1556229119 et je voulais coder ma propre matrice 4x4. Comme je ne suis pas encore arrivé au chapitre sur les quaternions, je code dans l'ordre du livre. J'ai bien un petit projet de système de particules pour me mettre un peu plus à la 3D et mettre mes connaissances en pratique, mais rien de bien concret pour le moment.

Apparemment l'utilisation des quaternions facilite le travail.

J'ai aussi regardé les tuto de Loulou sur son moteur 3D, le Yes::Engine et j'ai vu que dans ça classe Matrix4 il calculé le déterminant et l'inverse de sa matrice.

Autre question

Toutes les opérations se font sur les translations

Qu'est ce que ça signifie exactement ?

Kromagg

[plegat]

En fait c'est surtout pour mettre en pratique ce que je peux apprendre en 3D.

J'ai acheté récemment ce livre http://www.amazon.fr/Math-Primer-Gra.../dp/1556229119 et je voulais coder ma propre matrice 4x4.

Ok, c'est vraiment applicatif... dans ce cas, essaye la décomposition alors. Teste aussi la formule de Laplace en plus de Kramer (les cofacteurs de matrice 4x4 étant des déterminants de matrice 3x3)

Apparemment l'utilisation des quaternions facilite le travail.

La mise en oeuvre et l'utilisation sont un peu laborieux au départ, mais ça facilite, oui...

Qu'est ce que ça signifie exactement ?

Que l'inverse d'une translation est la translation opposée, et que l'inverse d'un quaternion est le même quaternion avec l'angle opposé (ou le vecteur opposé). Ca se calcule très facilement... plus facilement qu'une décomposition LU
Ensuite tu construis ta matrice 4x4 à partir du vecteur translation et de ton quaternion.

[Kromagg]

En effet les quaternions semblent vraiment plus simple à utiliser.
En tout cas merci beaucoup Plegat d'avoir pris le temps de répondre à toutes mes questions, bien que le sujet fut un peu long.

Le sujet est pour moi résolu

Kromagg

[plegat]

En effet les quaternions semblent vraiment plus simple à utiliser.

Ca fait très peur quand on ne connait pas, mais ce n'est jamais qu'un vecteur avec un angle associé! Donc en gros "je tourne autour de cet axe avec cet angle". Rien de compliqué!

En tout cas merci beaucoup Plegat d'avoir pris le temps de répondre à toutes mes questions, bien que le sujet fut un peu long.

Y'a pas d'quoi. En plus ça m'a permis de réviser la décomposition LU

[Kromagg]

Je bloque un peu sur ton explication

et on va construire le vecteur L(n) tel que toutes les colonnes soient à 0 excepté leur terme diagonal à 1

Tu peux être plus clair sur ce point ?

Kromagg

[plegat]

On va faire un exemple numérique, ça sera plus parlant...

Matrice de départ: celle de wikipédia (voir lien plus haut)

Code :

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

1
2
3
4
 
        | 2 -1  0 |
A=A(0)= |-1  2 -1 |
        | 0 -1  2 |

Pour n=1, on a a(n,n)=a(1,1)=2 (1ere ligne, 1ere colonne). On va construire notre matrice L(1) en faisant:
1) tous ses termes à 0
2) la diagonale à 1
3) pour la première colonne, pour les termes sous la diagonale, on prend celui correspondant dans A(0), on multiplie par -1 et on divise par a(n,n)=a(1,1)=2, donc:

Code :

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

1
2
3
4
 
     |  1   0  0 | | 1  0  0 |
L(1)=| 1/2  1  0 |=|0.5 1  0 |
     |-0/2  0  1 | | 0  0  1 |

La matrice inverse L(1)^-1 est alors:

Code :

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

1
2
3
4
 
        |  1  0  0 |
L(1)^-1=|-0.5 1  0 |
        |  0  0  1 |

puis tu calcules A(1)=L(1)*A(0):

Code :

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

1
2
3
4
 
               |  1   0  0 | | 2 -1  0 | | 2 -1  0 |
A(1)=L(1)*A(0)=| 1/2  1  0 |*|-1  2 -1 |=| 0 1.5 -1|
               |-0/2  0  1 | | 0 -1  2 | | 0 -1  2 |

on passe à n=2, en calculant L(2) en faisant:
1) tous ses termes à 0
2) la diagonale à 1
3) pour la deuxième colonne (vu qu'on est à n=2), pour les termes sous la diagonale, on prend celui correspondant dans A(1), on multiplie par -1 et on divise par a(n,n)=a(2,2)=1.5, donc:

Code :

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

1
2
3
4
 
     | 1   0   0 | | 1  0  0 |
L(2)=| 0   1   0 |=| 0  1  0 |
     | 0 1/1.5 1 | | 0 2/3 1 |

et ainsi de suite...

ne m'en demande pas plus, c'est la galère pour faire des matrices dans le forum!

[Kromagg]

Super Plegat j'en demandais pas tant
Non je t'en demanderais pas plus
Je teste ça dès que possible et je redonne des nouvelles

Kromagg