Trigonaliser une matrice

Version imprimable

Bonjour,voilà mon problème est assez simple je veux trigonaliser une matrice sauf que mon programme ne fait que le début de la trigonalisation et ne veut pas faire le reste. je m'explique il commence bien en faisant L3-coef(L1) L1 etant la ligne 1. Mais cependant après il ne veut pas soustraire la L3 et la L2 entre elles pour supprimer le coef a(3,2) coef à la ligne 3 et colonne 2. Un exemple simple est:
M=(1 2 3)
(4 5 6)
(7 8 9)
Ainsi on fait L2<-L1-4L2 et L3<-L1-7L2 jusqu'à là le programme marche d'où:
M=(1 2 3)
(0 -3 -6)
(0 -6 -12)

Ensuite il ne veut pas faire L3<-L3-2L2 ce qui me donnerait:
M=(1 2 3)
(0 -3 -6)
(0 0 -12)

Voici mon programme en détail merci de m'expliquer mon erreur et de ne pas me donner un programme tout fait qui trigonalise. C'est en se corrigeant que l'on progresse non en copiant et puis j'ai vu plusieurs programme pour ça et je ne les avais pas compris. Tréve de bavardage.
Code:

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 28 29 30 31 32 33 34 35 36 37 double Matrice::tri_mat(Matrice a)//Triangularisation de la matrice {int x=0,y=0,k=0; Matrice G; if(a.get_ligne()==a.get_colonne()) {for(int y=1; y<=a.get_colonne() ; y++) {G.M[1][y]=a.M[1][y]; } for(int x=2; x<=a.get_ligne(); x++) {for(int y=1; y<=a.get_colonne() ; y++) { G.M[x][y]=a.M[x][y]-((a.M[x][1]*a.M[1][y])/a.M[1][1]); } } for(int k=2; k<=(a.get_ligne()-1) ; k++) {for(int x=k+1; x<=a.get_ligne(); x++) for(int y=2; y<=a.get_colonne() ; y++) G.M[x][y]+=-((G.M[x][k]*G.M[k][y])/G.M[k][k]); } for(int x=1; x<=a.get_ligne() ; x++)//Affiche la matrice traingularisé { for(int y=1; y<=a.get_colonne() ; y++) { cout<<G.M[x][y]<<""; } cout<<endl; } } else {cout<<"impossible!!"<<endl; } };
J'espère que vous pourrez m'aider car ça fait plus de 5 heures que je bosse dessus je suis perséverant mais j'ai mes limites aussi:aie:

29/03/2009, 10h58
Invité

salut,

d'apres bibmath :
le pivot de gauss sert aussi a faire des trigonalisation

Le but est de faire apparaitre des 0 sous la diagonale (resp au dessus).
Dans notre cas, ta matrice est :
M=(1 2 3)
M=(4 5 6)
M=(7 8 9)

On procede donc ainsi :
L2 <- L2 - 4L1
L3 <- L3 - 7L1
M=(1 2 3)
M=(0 -3 -6)
M=(0 -6 -12)

puis :
L3<- L3 - 2*L2
M=(1 2 3)
M=(0 -3 -6)
M=(0 0 0)

Tu peux verifier ca en calculant le determinant de ta matrice qui vaut 0.
Dans ton exemple, tu obtiens une matrice triangulaire dont les coefficients diagonaux sont tous différents de 0. Or, tes trois vecteurs sont liés, donc c'est pas cohérent.

Pour l'algo, sauf erreur, en gros tu fais comme ca :
tu tarranges pour faire apparaitre des 0 sur la premiere colonne grace a l'ajout de a*L1 a la ligne courante.
Ensuite, tu t'arranges pour faire apparaitre des 0 sur la seconde colonne de la matrice grace a l'ajout de b*L2 a la ligne courante.
Etc...

du coup, on peut pondre un truc pas mega optimisé :
tant que indiceLigneCourante != 0
..pour toutes les lignes L inférieure a indiceLigneCourante Faire
..CoeffMultiplicateur = L[indiceLigneCourante]/LigneCourante[indiceLigneCourante]//ici ya un probleme pour la division par zero
....pour toutes les colonnes y de L Faire
......L[y] = L[y] - coeffMultiplicateur*L[y]
....Fin Fait
..indiceLigneCourante = indiceLigneCourante -1
..Fin Fait

ya juste une condition a verifier pour pas diviser par zero...:aie:
29/03/2009, 19h35
samex88

En fait je voulais écrire (0 0 0) en L3 je me suis gouré en copiant. Sinon j'ai rajouté dans mon programme le fait que le pivot pouvait être nul.

Cependant la matrice que j'obtiens au final c'est bien la dernière matrice que j'ai écrit càd:

M=( 1 2 3)
( 0 -3 -6)
(0 0 -12)

Au lieu de :
M=( 1 2 3)
( 0 -3 -6)
(0 0 0)

Pourriez-vous jeter un oeil sur mon programme s'il-vous-plaît.
Parfois plusieurs yeux valent mieux que 2 paires. Peut-être que j'ai commis une étourderie. Merci d'avance
29/03/2009, 20h33
Invité

ben, pour etre franc ton code est pas tres beau :
pas d'indentation, pas de commentaires (sauf pour dire qu'on affiche une matrice lol), les variables x et y et de manière plus générale les autres qu'on ne sait pas (du moins moi) a quoi elles correspondent.

Donc c'est assez chaud pour ma part de t'aider même si ca m'interesse
29/03/2009, 20h48
samex88

Je suis désolé pour mon code qui ne ressemble à rien mais c'est pas vraiment ma faute car on fait du C++ depuis peu. Sinon a.get_lignes sert à récupérer le nombre de ligne de la matrice a et pareil pour a.get_colonne sauf que c'est pour les colonnes.

Ce qui est des variables x et y c'est pour faire varier les lignes et les colonnes de ma matrice pour pouvoir les remplacer les valeurs et l'afficher ensuite. Voilà s'il te faut quelque chose d'autre je suis à ton entière disposition. Simple curiosité ça veut dire quoi l'indentation??
Merci pour ton aide.

l'indentation c'est ca :
Code:

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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 double Matrice::tri_mat (Matrice a)//Triangularisation de la matrice { int x = 0, y = 0, k = 0; Matrice G; if (a.get_ligne() == a.get_colonne()) { for (int y = 1; y <= a.get_colonne(); y++) { G.M[1][y] = a.M[1][y]; } for (int x = 2; x <= a.get_ligne(); x++) { for (int y = 1; y <= a.get_colonne(); y++) { G.M[x][y] = a.M[x][y] - ((a.M[x][1] * a.M[1][y]) / a.M[1][1]); } } for (int k = 2; k <= (a.get_ligne() - 1); k++) { for (int x = k + 1; x <= a.get_ligne(); x++) for (int y = 2; y <= a.get_colonne(); y++) G.M[x][y] += -((G.M[x][k] * G.M[k][y]) / G.M[k][k]); } for (int x = 1; x <= a.get_ligne(); x++)//Affiche la matrice traingularisé { for (int y = 1; y <= a.get_colonne(); y++) { cout << G.M[x][y] << ""; } cout << endl; } } else { cout << "impossible!!" << endl; } } ;
plusieurs remarques :
La méthode renvoie un double alors qu'elle renvoie apparemment rien. Prefere un void, ou sinon retourne un booleen pour indiquer que la trigonalisation est faite ou pas
Autant ecrire get_nbLigne, au moins on sait que c'est un nombre de ligne.
Surtout, commente ton code, le but c'est que le mec qui passe derrière toi, il pige du premier coup d'oeil (ou du moins qu'il ait pas a se prendre le choux).
Exemple :
Code:

1 2 3 4 for (int y = 1; y <= a.get_colonne(); y++)//copie de la premiere ligne de a dans G { G.M[1][y] = a.M[1][y]; }
Ensuite
Code:

1 2 3 4 5 6 7 for (int x = 2; x <= a.get_ligne(); x++) { for (int y = 1; y <= a.get_colonne(); y++) { G.M[x][y] = a.M[x][y] - ((a.M[x][1] * a.M[1][y]) / a.M[1][1]); } }
1: bon la ligne picote un peu quand même :mouarf:
2: tu fais une operation dans la boucle a chaque parcourt, alors que c'est pas necessaire
3: j'espere que tes coefficients sont des nombres a virgules, parce que si jamais tu as 7/3, ca sera tronqué.
on peut remplacer en :
Code:

1 2 3 4 5 6 7 8 for (int x = 2; x <= a.get_ligne(); x++) { double coeffMultiplicateur = a.M[x][1]/ a.M[1][1]; for (int y = 1; y <= a.get_colonne(); y++) { G.M[x][y] = a.M[x][y] - coeffMultiplicateur * a.M[1][y]; } }
même chose pour la partie d'apres :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 for(int k=2; k<=(a.get_ligne()-1); k++) { for(int x=k+1; x<=a.get_ligne(); x++) { double coeffMultiplicateur = G.M[x][k]/G.M[k][k]; for(int y=k; y<=a.get_colonne(); y++) //les coefficients precedents y<k sont theoriquement a 0 { G.M[x][y]-=coeffMultiplicateur*G.M[k][y]; } } }
Ensuite, on remarque qu'on peut reunir les deux premieres boucles, il suffit de commencer a partir de k=1 !

Edit : en fait j'ai mal compris ton code ... :aie:

Voila un bout de code qui marche et tres similaire au tiens:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
	//pour toutes les lignes sauf la derniere. iRef represente la ligne de reference qui sert de base pour le pivot
	for(int iRef = 0; iRef < NB_COLONNE-1; iRef++)
		{
			//pour toutes les lignes suivantes
			for(int l=iRef+1;l<NB_LIGNE;l++)
			{
				//si lelement du pivot est non nul
				if(G[iRef][iRef]!=0)
				{
					//coefficient de combinaison lineaire de la ligne iRef vers la ligne l
					double coeffMultiplicateur = G[l][iRef]/G[iRef][iRef];
					//on ajoute la ligne iRef a la ligne l
					//l'indice c commence a iRef, car les valeurs dans les colonnes precedentes
					//sont deja a 0
					for(int c=iRef;c<NB_COLONNE;c++)
					{
						G[l][c]-=coeffMultiplicateur*G[iRef][c];
					}
				}
			}
		}

Les indices de ma matrice G commencent a 0...

30/03/2009, 01h58
samex88

Merci beaucoup galerien69 grâce à toi j'ai pu résoudre mon problème. En fait je devais inverser :

Citation:

{if(G.M[k][k]!=0)
{double coef=(G.M[x][k]/G.M[k][k]);
for(int y=k; y<=a.get_colonne() ; y++)

Ainsi en inversant le if et le for ça marche sinon ça marche pas. De plus merci pour la simplification grâce au "double coefmultiplacateur" ainsi que le y=k j'y avais pas pensé.

Sinon, saurais-tu pourquoi en inversant le programme marche? Simple question de curiosité. En tout cas merci du fond du coeur et c'est sincère :D
30/03/2009, 07h28
Invité

re,

tant mieux si ca marche!;)
Par contre, pour l'inversion des deux lignes je ne vois pas.