Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

décomposition LU

Posté par helmut perchut (invité) 16-08-04 à 11:39

bonjour, j'ai d'énormes problèmes en ce qui concerne la décomposition LU d'une matrice.
Je ne connais pas la méthode qui me permet de trouver les deux matrices triangulaire L et U, et je n'arrive pas à obtenir d'exemple précis sur le net.
Donc si quelqu'un voulait bien m'aider et si possible avec un exemple pour mieux comprendre.
Au pire si vous voulez j'ai un exo de ce type que je pourrais mettre sur le forum si quelqu'un voulait bien m'aider la dessus.
Merci d'avance.

Posté par Ghostux (invité)re : décomposition LU 16-08-04 à 13:53

hum ... c'est quel niveau ? (prépa ou fac?)
Je pense qu'un exercice ne ferait pas de mal, si tu pouvais en mettre un.

Ghostux

Posté par
dad97 Correcteur
re : décomposition LU 16-08-04 à 14:02

Bonjour,
moi personnellement j'ai fait ça en licence mais pour l'instant je n'arrive pas à retrouver mes cours à ce sujet (ils sont archivés dans des cartons) mais je cherche...

Posté par
dad97 Correcteur
re : décomposition LU 16-08-04 à 14:19

Bon j'ai trouvé quelque chose sur le net :
http://www.iro.umontreal.ca/~mignotte/IFT2421/Chapitre3.pdf
ça se passe page 16 du document pdf.

A noter que je n'ai pas vérifier l'exactitude des calculs mais vu tout ce qui est abordé dans ce document cela m'étonnerait que ce soit un rigolo qui est écrit cela.

salut

Posté par helmut perchut (invité)decomposition LU(suite) 16-08-04 à 14:29

c'est du niveaux DEUG (MIAS 2ème année pour être plus précis).
Donc j'ai eu ce type d'exo pour un partiel:
on a donc une matrice A

0  4  5  4  -5
3  -10  8  -11  -10
1  -4  2  -4  -2
2  -10  1  -10  -1
-5  24  -7  20  0
1)Dire pourquoi An'admet pas de factorisation LU(là je suppose qu'il faut prouver que A n'est pas inversible)

2) on pose P
0  0  1  0  0
0  1  0  0  0
1  0  0  0  0
0  0  0  1  0
0  0  0  0  1

Montrer que la matrice PA admet une décomposition LU et la déterminer.En déduire la valeur du déterminant de A.

Donc voilà si quelqu'un arrive à le faire.
Merci


*** message déplacé ***

Posté par
dad97 Correcteur
re : décomposition LU 16-08-04 à 14:53

bonjour,

il n'était pas nécessaire de créer un nouveau topic pour ton exemple, il te suffisait de le mettre à la suite de l'autre.

D'autre part si tu rentres ta matrice A dans une calculatrice tu pourras t'apercevoir qu'elle inversible puisque de déterminant non nul.


j'ai trouvé un théorème sur le net
http://www.unige.ch/ses/metri/gilli/Teaching/MNE-Cours.pdf page 40

théorème6.1 : Existence : une matrice A d'ordre n admet une factorisation LU si elle vérifie
det(A1:k,1:k)0 pour k=1,...,n-1.
Unicité : si la factorisation existe et A est non-singulière alors elle est unique...

A mon avis c'est le théorème que tu dois utiliser


*** message déplacé ***

Posté par
Nightmare
re : décomposition LU 16-08-04 à 16:09

Salut Helmut Perchut

Voici un site que je te propose :



Dans la parti Mpsi , Calcul matriciel

Je sais pas trop si il y a ce que tu cherche mais ça doit avoir un rapport

Bon surf

Posté par Ghostux (invité)re : décomposition LU 16-08-04 à 16:23

Sinon tu as aussi le site du lycee charlemagne qui propose des cours en pdf gratuitement, premiere et deuxieme annee. Pour les cours de MPSI,
 <a href = "http://perso.wanadoo.fr/lavau/mpsi2003/mpsi2003.htm"> C'est ici </a>

( C'est pas des chaptaliens qui feraient ca :-/ ...)
 Avec tout ce qu'on ta proposé, t'auras de la lecture, si jamais tu as toujours besoin d'un coup de main supplémentaire, refais nous signe.

Ghostux

Posté par
dad97 Correcteur
re : décomposition LU 16-08-04 à 18:46

Rebonjour,

en utilisant le théorème que je t'ai donné
posté le 16/08/2004 à 14:53
Il est clair que A ne possède pas de décomposition LU

D'autre part
PA = 1 -4 2 -4 -2
3 -10 8 -11 -10
0 4 5 4 -5
2 -10 1 -10 -1
-5 24 -7 20 0

En appliquant ce même théorème on montre que la décomposition LU existe.

En utilisantle lien que j'ai proposé
posté le 16/08/2004 à 14:19

Et en appliquant la méthode proposé on arriva a

L= 1 0 0 0 0
3 2 0 0 0
0 4 1 0 0
2 -2 -1 1 0
-5 4 -1 0 1

U= 1 -4 2 -4 -2
0 1 1 0,5 -2
0 0 1 2 3
0 0 0 1 2
0 0 0 0 1

Pour ce qui est du déterminant de A :
Det P =-1 detL=2 et detU = 1
DetA=detL*detU/detP=-2 donc detA=-2

Salut

Posté par Ghostux (invité)re : décomposition LU 16-08-04 à 19:39

  Je me permets une touche tardivement théorique, en partie prise sur mon livre d'algèbre, et guidée par d'autres tenors en maths.

La théorie:  on peut écrire toute matrice n x n en 4 parties comme
ceci:
A= (a11 w)( v A')
où a11 est le premier élément,
w est un vecteur ligne de dimension n-1,
v est un vecteur colonne de dim n-1,
et A' est une sous-matrice (n-1)x(n-1).

Si elle est non singulière, on peut la factoriser ainsi:
A= (1 0 )(a11 w )
(v/a11 Id) (0 A'-v*w/a11)
où les 0 sont des vecteurs ligne(matrice 1) et colonne(matrice 2) de
dim n-1,  
v/a11 est toujours le vecteur colonne de dim n-1,
Id est la matrice identité de (n-1)x(n-1),
et v*w/a11 est le produit extérieur.  Le résultat de A'-v*w/a11 est
donc une sous-matrice de dim (n-1)x(n-1).  

On peut vérifier que le produit de ces deux matrices donne bien A.

Ensuite on continue recursivement pour la sous-matrice A'-v*w/a11.
Fin de la théorie.
  *****
Exemple avec une matrice 4x4:

( 2 3  1   5 )
( 6 13 5  19 )
( 2 19 10 23 )
( 4 10 11 31 )

a- Traiter la ligne 1 et colonne 1:
1-L'élément pivot est [1,1] donc 2. Diviser les éléments de la colonne
1 qui sont sous le pivot par 2:
( 2 3 1 5 )
( 3 13 5 19 )
( 1 19 10 23 )
( 2 10 11 31 )

La sous-matrice 3x3 est formée des éléments qui se trouvent sous la
ligne en traitement et à droite de la colonne en traitement c'est la
sous-matrice

13 5 19
19 10 23
10 11 31

2- pour chaque élément de cette sous-matrice 3x3 faire
element-colonne1*ligne1:
13-3*3=4
5-3*1=2
19-3*5=4
19-1*3=16
10-1*1=9
23-1*5=18
10-2*3=4
11-2*1=9
31-2*5=21
Résultat:
( 2 3 1 5 )
( 3 4 2 4 )
( 1 16 9 18 )
( 2 4 9 21 )

Ensuite on fait la meme chose pour la ligne 2, colonne 2:
1-L'élément pivot est [2,2] donc 4. Diviser les éléments de la colonne
2 qui sont sous le pivot par 4:
( 2 3 1 5 )
( 3 4 2 4 )
( 1 4 9 18 )
( 2 1 9 21 )

la sous-matrice est maintenant formée des éléments à droite de la
colonne 2 et sous la ligne 2:
9  18
9  21
2- pour chaque élément de cette sous-matrice 2x2 faire
élément-colonne2*ligne2:
9-4*2=1
18-4*4=2
9-1*2=7
21-1*4=17
Résultat:
( 2 3 1 5 )
( 3 4 2 4 )
( 1 4 1 2 )
( 2 1 7 17 )

Ensuite on fait la meme chose pour la ligne 3, colonne 3:
1-L'élément pivot est [3,3] donc 1. Diviser les éléments de la colonne
3 qui sont sous le pivot par 1, la matrice est inchangée.

La sous-matrice est simplement l'élément 17, donc faire element
-ligne3*colonne3: 17-7*2=3
Résultat:
( 2 3 1 5 )
( 3 4 2 4 )
( 1 4 1 2 )
( 2 1 7 3 )

Cette représentation est la forme compacte, on la sépare en L et U en
placant les éléments au-dessus de la diagonale principale (y compris
cette diagonale) dans U:

( 2 3 1 5 )
( 0 4 2 4 )
( 0 0 1 2 )
( 0 0 0 3 )
et les éléments sous la diagonale principale dans L, avec des 1 sur sa
diagonale:
( 1 0 0 0 )
( 3 1 0 0 )
( 1 4 1 0 )
( 2 1 7 1 )

Ca c'est sans faire de pivot, mais avec pivot ce ne serait pas
beaucoup plus difficile.

Cette version s'appelle algorithme de Dolittle.  Il y a aussi
l'algorithme de Crout, c'est la meme chose sauf que ce sont les
éléments de la ligne qui sont divisés par le pivot et non ceux de la
colonne en traitement, et c'est la matrice U qui contient des 1 sur sa
diagonale principale.

En esperant avoir gardé la cohérence fu fil.
@ bientot
Ghostux

--
Take a walk on the wild side.

Posté par helmut perchut (invité)désolé j avais oublié de remercier toutes ces personnes. 18-08-04 à 15:41

bonjour, comme me l'a fait remarquer dad97, j'ai effectviement oublié de remercier toutes les personnes qui ont eu la gentillesse de m'aider et en particulier monsieur dad97.
Promis la prochaine fois j'oublierais pas

Posté par
dad97 Correcteur
re : décomposition LU 18-08-04 à 15:45

Ce n'est pas moi en particulier qu'il faut remercier (ce n'est sans aucun doute pas moi qui t'es le plus aidé) mais pour les autres intervenants aussi je pense que c'est agréable aussi de ne pas se sentir comme des machines à faire des maths.

Salut

Posté par Ghostux (invité)re : décomposition LU 18-08-04 à 16:15




Amicalement

Ghostux

Posté par jb (invité)mais qu est ce que c est que ca? 21-08-04 à 15:16

lut! je suis a la recherche de la théorie de la décomposition LU mais qui soit SIMPLE a comprendre parce que j'ai beau chercher je capte rien...
en fait si vous aviez un exenple du genre
"
(4 7 1)
(5 2 1)
(6 3 9)
on multiplie la ligne 1 par 4 ... etc...
"
ca m'arrrangerai!!!

Posté par Ghostux (invité)re : décomposition LU 21-08-04 à 16:41

Ben, je trouve que ce que j'ai mis est un peu long, mais relativement simple non ? Aussi etait-ce une approche un peu pragmatique.

Ghostux

Posté par jb (invité)Decompostion LU 23-08-04 à 23:40

Salut a tous!!
Je cherche a savoir comment on utilise la décomposition LU, je trouve pleins de trucs sur pleins de sites mais ca reste toujours peu clair!!
Si on pouvait me dire comment on fait ou me donner un lien vers un cour bien fait ca serait cool!!
Mici


*** message déplacé ***

Posté par jb (invité)oups!!!!!!! 23-08-04 à 23:47

mince j'avais oublié que j'avais deja demandé ca...

Posté par
Tom_Pascal Webmaster
re : décomposition LU 23-08-04 à 23:49

eh eh, pas moi

Posté par jb (invité)euhhhhh??? 23-08-04 à 23:57

ben en fait Ghostux j'ai 2,3 questions sur le tout début:
a- Traiter la ligne 1 et colonne 1:
1-L'élément pivot est [1,1] donc 2. Diviser les éléments de la colonne
1 qui sont sous le pivot par 2:
( 2 3 1 5 )
( 3 13 5 19 )
( 1 19 10 23 )
( 2 10 11 31 )

La sous-matrice 3x3 est formée des éléments qui se trouvent sous la
ligne en traitement et à droite de la colonne en traitement c'est la
sous-matrice

13 5 19
19 10 23
10 11 31

2- pour chaque élément de cette sous-matrice 3x3 faire
element-colonne1*ligne1:
ca veut dire element-element[ligne1][colone1]???

Posté par jb (invité)mais je suis trop nul... je lis rien... fo ke j dorme lol 23-08-04 à 23:59

g capté!!! c la ligne ou sont les elements!

Posté par Ghostux (invité)re : décomposition LU 24-08-04 à 00:02

Bonsoir jb
Et bien tu vois , quand on veut !!

Ghostux



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !