Discussion :

[le_voisin]

salut,

je suis pas tout a fait certain de poster le message sur le bon forum (j hesitais avec le forum c++), enfin si c est pas le bon il sera deplace !

J ai donc fait un algorithme de decomposition LU et j observe un drole de truc (à mes yeux en tout cas) :

mon algorithme me sort une matrice triangulaire superieure avant que l algorithme arrive au bout (je veux dire par la avant d avoir fait la multiplication par L associe à la derniere colonne par exemple)

J ai mis mon code, si jamais ca peut :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
 
matrix<float> decomp_lu(matrix<float> m)
{
	matrix<float> l(m.size1(), m.size1());
	cout << "dimension de la matrice soumise au LU :"<<m.size1()<<"\n";
 
	for(int i=0; i<=m.size1()-2; i=i+1)//calcul de L
	{
		//coef à 0 de la matrice L
		for(int c=0; c<m.size1(); ++ c)
		for(int d=0; d<m.size2(); ++ d)
		l(c,d)=0;
		//coef à 1 sur la diagonale de la matrice L
		for(int c=0; c<m.size1(); ++ c)
		l(c,c)=1;
 
		//calcul des coef non nuls de la matrice L
		for(int j=i; j<=m.size1()-2; ++ j)
		l(j+1,i)=-m(j+1,i)/m(i,i);
 
		cout << "operation numero "<< i <<", L : "<< l <<"\n";
		m=prod(l, m);
		cout << "operation numero "<< i <<", U : "<< m <<"\n";
	}
	return(m);
}

bon il est fini, je pense notamment stocke L et U dans un tableau de matricepour pouvoir les sortir de la fonction et les manipuler eventuellement apres...enfin ca c est autre chose....

Merci, j attend vos remarques !

[Mike85]

C'est quoi un algorithme de décomposition LU ??

[plegat]

C'est quoi un algorithme de décomposition LU ??

Décomposition d'une matrice inversible en un produit de deux matrices triangulaires, une triangulaire inférieure L (pour "low") et une triangulaire supérieure U (pour "up").

Voir wikipedia pour les détails.

Je suis en train de me faire une classe Java pour la manipulation de matrice, mais je n'ai pas attaqué la décomposition LU. Je regarde ça dès que j'y suis.

[Matthieu Brucher]

Ca peut arriver, je ne vois pas le problème

[le_voisin]

ok, c est ce que je pensais mais je me demandais si il n y avait pas de probleme avec mon algorithme,mais finalement j ai trouve des matrices ou il faut utiliser l algorithme jusqu'au bout !
Merci

[Mike85]

Dans quels applications peut servir cet algorithme ??
Car moi, j'ai rien pigé.

[Matthieu Brucher]

Calculer un déterminant, par exemple.

[Mike85]

Mais, pour un simple déterminant je crois qu'une seule formule suffit, pas tout un algorithme.

[HanLee]

Mais, pour un simple déterminant je crois qu'une seule formule suffit, pas tout un algorithme.

Oui, mais l'algorithme avec la formule du développement par exemple... il est super lent.

Si tu as une matrice triangulaire, tu as juste à faire le produit des termes diagonaux.

[j.p.mignot]

En + de la lenteur, un calcul du det par récursion présente d'énormes problèmes numériques de par toutes ses * et +-.
La méthode LU est parmi les + efficaces. Pour son implémentation et sa comparaison avec d'autres technique voir l'excellent livre de Numerical recipes

voir http://www.library.cornell.edu/nr/cbookcpdf.html
et + spécifiquement le chapitre 2 ( LU sous 2.3 )

[Mike85]

Donc, cet algorithme permet d'optimiser le temp d'exécution.

[HanLee]

Donc, cet algorithme permet d'optimiser le temp d'exécution.

Et d'éviter les problèmes de précision du fait des calculs avec des flottants, comme a dit j.p.mignot.

Tu peux avoir des algorithmes super rapides, mais niveau perte de précision du calcul, ça pourra être inadapté, c'est important comme aspect aussi.