vasyfrancky
Messages postés2Date d'inscriptionjeudi 13 février 2003StatutMembreDernière intervention 4 octobre 2003
-
4 oct. 2003 à 19:21
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005
-
14 mai 2004 à 14:31
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005 14 mai 2004 à 14:31
Dommage.
Si ca intéresse qqn, je peut tjs mettre mon code ici.
Mais je crois que celui réalisé par stb doit être plus ou moins semblable et tout aussi bon. Voila tjs mon code :
(Un jour, j'essaierai de mettre un petit code avec tout ce que j'ai sur les matrices. Mais bon en attendant...)
/**
* Calcule le déterminant d'une matrice.
*
* @pre : matrice est une mattrice carrée de "double" qui n'est pas vide.
* @post : Renvoie le déterminant de la matrice matrice.
*/
public static double detMatrice(double[][] matrice) {
double result = 0;
if (matrice.length == matrice[0].length) {
if (matrice.length == 1) {
result = matrice[0][0];
}
else {if (matrice.length == 2) {
result = ((matrice[0][0] * matrice[1][1]) - (matrice[0][1] * matrice[1][0]));}
else {
for (int i = 0; i < matrice.length; i++) {
result += (((-1)^(i+1)) * matrice[i][0] * detMatrice(subMatrice(matrice, i, 0)));
}
}}
}
else {
new Exception("Le déterminant ne va pas pouvoir être calculé sur cette matrice.").printStackTrace();
System.exit(-1);
}
return result;
}
/**
* Renvoie une matrice qui correspond à la matrice matrice moins la ligne a et la colonne b
*
* @pre : matrice est une mattrice de "double" qui n'est pas vide.
* @post : Renvoie une matrice qui correspond à la matrice matrice moins la ligne a et la colonne b
*/
public static double[][] subMatrice(double[][] matrice, int a, int b) {
///// tenir compte de fait que i et j sois bons et que la taille de matrice > 1
double[][] result = new double[matrice.length - 1][matrice[0].length - 1];
for (int i = 0; i < (matrice.length - 1); i++) {
for (int j = 0; j < (matrice[0].length - 1); j++) {
if (i < a && j < b)
result[i][j] = matrice[i][j];
else if (i < a && j >= b)
result[i][j] = matrice[i][j + 1];
else if (i >= a && j < b)
result[i][j] = matrice [i + 1][j];
else
result [i][j] = matrice[i + 1][j + 1];
}
}
return result;
}
Bonne prog,
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 14 mai 2004 à 14:17
une piqûre de rappel tout de même
(c plus fort que moi, et puis je viens de passer qques concours...)
en notant P le polynome caractèristique d'un endo u ;-p
si P est scindé dans K[X]
alors det(u) est le produit des racines de P
P n'est pas necessairement scindé dans R mais il l'est dans C
(tout polynome est scinde dans C)
ensuite,
u est trigonalisable ssi P est scindé
en gros, toute matrice est trigonalisable dans C, et on a alors le determinant egal au produit des elemets diagonaux
mais dans R, c'est plus delicat
il est envisageable d'obtenir des valeurs approchees des racines réelles de P, mais pour les racines complexes, ca tombe à l'eau
;-p
donc pour obtenir le determinant en trigonalisant la matrice, c'est foutu {;o(
je ne pense pas qu'il y ai beaucoup mieux que le developpement ligne-colone du determinant pour le caluler
dommage ;-p
A+
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 14 mai 2004 à 13:48
Je pense que la seule chose que l'on peut obtenir avec le pivot, c'est le rang de la matrice et donc, si le determinant est nul ;-)
sinon, il faut tout de même trigonaliser la matrice -> sans calcul formel avec Maple, bon courage
A+
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005 14 mai 2004 à 13:07
Définition 1.5.3 Le déterminant d'une matrice carré est défini par le déterminant de ses vecteurs colonnes.
C'est mon cas, mais je ne comprend pas ce qu'ils veulent dire.
Sinon, j'ai ceci qui va m'aider :
Corollaire Soit M une matrice triangulaire ( supérieure ou inférieure ) à coefficients dans un corps k. Alors le déterminant de M est égal au produit des éléments diagonaux de M.
A+
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005 14 mai 2004 à 12:31
En fait, tu te souvient ptet s'il n'y a pas moyen de trouver le determinant d'une matrice par la methode de pivot. J'ai un algorithme qui a mon avis a une sale complexité temporelle et spatiale (j'ai une méthode récursive qui me recoupe chaque fois la matrice ne plus petite matrices) Mais j'ai cru entendre que la méthode du pivot pouvait aider a trouver le determinant. Maintenant, je me suis ptet trompé.
Ne fais pas de recherches pour moi. Mais si t'en souvient, je me ferai une joie d'implementer ca!
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005 14 mai 2004 à 12:01
Un grand merci!
Le seul hic c'est que je me demande si moi-même j'ai bien tenu compte de tous les cas.
D'un autre coté, quand j'essaye de savoir qu'elle matrice pourrait contrer mon (et ton) algorithme, j'arrive pas a en trouver. J'en deduit donc que ca doit être bon.
Merci pour la correction. Je me demande cependant ou étaient mes erreurs.
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 14 mai 2004 à 11:14
Salut
enfin reveillé et la correction est tapée
c'est vrai qu'à la main, on "choisit" son pivot, au lieu de prendre la ligne suivante ;-)
(j'm'en veux)
2 toutes petites erreurs
public static double[][] invMatrice(double[][] matrice) {
int n = matrice.length;
double[][] inv = new double[n][n];
if (matrice.length == matrice[0].length /* && isMatrice(matrice) && detMatrice(matrice) != 0 */) {
// matrice a inverser + matrice identité (accolée a droite)
double[][] matrPlusIdent = new double[n][n*2];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
matrPlusIdent[i][j] = matrice[i][j];
if (i j) matrPlusIdent[i][i+n] 1;
}
}
for (int i = 0; i < n; i++) {
// Vérification qu'il n'y a pas de 0 sur la diagonale pour la colonne étudiée sinon changement de ligne
if (matrPlusIdent[i][i] == 0) {
int ligne = -1;
for (int k = i ; k < matrPlusIdent.length; k++) {
if (matrPlusIdent[k][i] != 0)
ligne = k;
}
if (ligne == -1) {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
for (int k = 0; k < matrPlusIdent[0].length; k++) {
double temp = matrPlusIdent[i][k];
matrPlusIdent[i][k] = matrPlusIdent[ligne][k];
matrPlusIdent[ligne][k] = temp;
}
}
// On veut un sur la diagonale a l'endroit souhaité.
double diviseur = matrPlusIdent[i][i];//!!Variable
for (int k = 0; k < matrPlusIdent[0].length; k++) {
matrPlusIdent[i][k] = (matrPlusIdent[i][k] / diviseur);
}
// Met O par tout d'autre.
for (int k = 0; k < n; k++) {
if (k != i) {
double facteur = matrPlusIdent[k][i];//!!aussi ;-p
for (int l = 0; l <matrPlusIdent[0].length; l++) {
matrPlusIdent[k][l] = (matrPlusIdent[k][l] - (matrPlusIdent[i][l] * facteur));
}
}
}
}
// Reprend l'inverse dans matrPlusIdent
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
inv[i][j] = matrPlusIdent[i][n+j];
}
}
}
else {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
return inv;
}
A+
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 14 mai 2004 à 00:43
lol
toujours pas couché mais je pense avaoir la solution
demain!!
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005 14 mai 2004 à 00:28
eh moi je peut te donner une ebauche de corection mais malheureusement, je comprend pas ou est ma faute mais cela me renvoie chaque fois la matrice identité. Je me suis trompé quelque part mais je veut plus chercher je suis fatigué moi aussi devoir faire dodo.
Merci qd meme pour ce que tu as fait dejà.
/**
* Inverse une matrice. (méthode du pivot).
*
* @pre matrice est une matrice de "double"
* @post la matrice inverse de matrice est retournée
*/
public static double[][] invMatrice(double[][] matrice) {
int n = matrice.length;
double[][] inv = new double[n][n];
if (matrice.length == matrice[0].length /* && isMatrice(matrice) && detMatrice(matrice) != 0 */) {
// matrice a inverser + matrice identité (accolée a droite)
double[][] matrPlusIdent = new double[n][n*2];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
matrPlusIdent[i][j] = matrice[i][j];
if (i j) matrPlusIdent[i][i+n] 1;
}
}
for (int i = 0; i < n; i++) {
// Vérification qu'il n'y a pas de 0 sur la diagonale pour la colonne étudiée sinon changement de ligne
if (matrPlusIdent[i][i] == 0) {
int ligne = -1;
for (int k = i ; k < matrPlusIdent.length; k++) {
if (matrPlusIdent[k][i] != 0)
ligne = i;
}
if (ligne == -1) {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
for (int k = 0; k < matrPlusIdent[0].length; k++) {
double temp = matrPlusIdent[i][k];
matrPlusIdent[i][k] = matrPlusIdent[ligne][k];
matrPlusIdent[ligne][k] = temp;
}
}
// On veut un sur la diagonale a l'endroit souhaité.
for (int k = 0; k < matrPlusIdent[0].length; k++) {
matrPlusIdent[i][k] = (matrPlusIdent[i][k] / matrPlusIdent[i][i]);
}
// Met O par tout d'autre.
for (int k = 0; k < n; k++) {
if (k != i) {
for (int l = 0; l <matrPlusIdent[0].length; l++) {
matrPlusIdent[k][l] = (matrPlusIdent[k][l] - (matrPlusIdent[i][l] * matrPlusIdent[k][i]));
}
}
}
}
// Reprend l'inverse dans matrPlusIdent
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
inv[i][j] = matrPlusIdent[i][n+j];
}
}
}
else {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
return inv;
}
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 14 mai 2004 à 00:20
Salut
merci, pour la remarque
je regarderais ca demain (dodo)
je rappelle que j'ai pensé à ca en Anglais (;-p)
(Disclamer : je decline toute responsabilité quant aux mauvaises idéées et à leurs conséquences dramatiques que je pourrais donner)
c'est juste que j'avais trouvé que c'était une façon élégante de le faire
lol
au fait, perso, j'ai plus confiance dans mon stylo que dans mon pivot
;-))
A demain!!
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005 13 mai 2004 à 22:22
Dobel,
Algorithme utilisant les Pivots n'a pas l'air mauvais dans le cas Général. Mais la ou tu as mis un commentaire disant :
"//normalement, pas besoin de test pour voir si a[i][i] est no nul : il ne doit pas l'être!!"
Je crois que tu t'est trompé, admettont que tu as une matrice
0 5 9
10 8 3
1 4 0
Dans un cas comme ca, a[0][0] sera nul et pourtant, la matrice est inversible. D'autres cas sont evisageables aussi.
Vérifier au départ si les éléments de la diagonale sont ou non égaux a 0 n'est pas suffisant non plus.
En effet, la matrice suivante aurra aussi un problème avec ton programme :
5 5 9
1 1 3
1 0 3
fournira aussi quelques problemes. Alors que 0 n'est présent sur aucun élément de la diagonale.
Facile de critiquer donc mais qu'elle est donc la réponse??
Je vais essayer de trouver ca ce soir. (Je suis bien forcé)
thekwint
Messages postés21Date d'inscriptionmercredi 17 mars 2004StatutMembreDernière intervention29 avril 2005 13 mai 2004 à 22:20
Dobel,
Algorithme utilisant les Pivots n'a pas l'air mauvais dans le cas Général. Mais la ou tu as mis un commentaire disant :
"//normalement, pas besoin de test pour voir si a[i][i] est no nul : il ne doit pas l'être!!"
Je crois que tu t'est trompé, admettont que tu as une matrice
0 5 9
10 8 3
1 4 0
Dans un cas comme ca, a[0][0] sera nul et pourtant, la matrice est inversible. D'autres cas sont evisageables aussi.
Vérifier au départ si les éléments de la diagonale sont ou non égaux a 0 n'est pas suffisant non plus.
En effet, la matrice suivante aurra aussi un problème avec ton programme :
5 5 9
1 1 3
1 0 3
fournira aussi quelques problemes. Alors que 0 n'est présent sur aucun élément de la diagonale.
Facile de critiquer donc mais qu'elle est donc la réponse??
Je vais essayer de trouver ca ce soir. (Je suis bien forcé)
cs_Taquilla
Messages postés8Date d'inscriptionmardi 5 novembre 2002StatutMembreDernière intervention16 avril 2004 14 févr. 2004 à 22:19
Salut,
En ce qui concerne le produit de matrices, la méthode classique est d'ordre 3. Grâce à la méthode de S.Winograd et de D.Coppersmith(la + rapide pour le moment), on peut obtenir un ordre de 2.376. Cette méthode est intéressante que si les matrices sont de l'ordre de 100000x100000 puisque l'on commence à gagner du temps de calcul.
a+
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 8 oct. 2003 à 20:06
voila c'est fait!!
c'est pas évident de voir comment ca marche donc je te conseille d'afficher les tableaux après chaque étape
public double[][] inverseMatrice(double[][] matrice) {
double[][] a, inv=null;
int n = matrice[0].length;
int i,j,k;
if (matrice.length == matrice[0].length /* && iciuntestdeDeterminant*/) {
//on travaille sur une matrice qui est la matrice à inverser avec la matrice identité accolée à droite
a = new double[n][2*n];
//création de cette matrice
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
a[i][j] = matrice[i][j];
if (i==j) a[i][i+n] = 1;
}
}
//première étape du Pivot : on place des 0 dans le triangle inférieur
for (i=1; i<n; i++) {
for (j=i; j<n; j++) {
if (a[j][i-1]!=0) {
double facteur = -a[i-1][i-1]/a[j][i-1];//ne pas se planter dans les indices!!
for (k=0; k<2*n; k++) {
a[j][k] = facteur*a[j][k]+a[i-1][k];
}
}
}
}
//on fait apparaître des 1 sur la diagonale
for (i=0; i<n; i++) {
double facteur = 1/a[i][i];//normalement, pas besoin de test pour voir si a[i][i] est no nul : il ne doit pas l'être!!
for (k=0; k<2*n; k++) {
a[i][k] = a[i][k]*facteur;
}
}
//fin du pivot
for (i=n-2; i>=0; i--) {
for (j=n-1; j>=i+1; j--) {
double facteur = -a[i][j];
for (k=0; k<2*n; k++) {
a[i][k] = a[i][k] + a[j][k]*facteur;
}
}
}
//on se retrouve avec l'identité à gauche et l'inverse de m à droite c'est à dire la situation inverse de lors de la création de a
//récupération de l'inverse dans la partie droite de a
inv = new double[n][n];
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
inv[i][j] = a[i][n+j];
}
}
}
else {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
return inv;
}
ca semble marcher correctement
enfin j'espère...
A+
stb2680
Messages postés9Date d'inscriptionsamedi 4 octobre 2003StatutMembreDernière intervention10 mars 2011 8 oct. 2003 à 13:20
J'ai fait la MAJ pour le constructeur avec un tableau de double, mais je n'ai pas eu le temps de le tester à fond, et je suis pas sûr qu'il soit obtimisé ....
J'ai fait çà vite fait hier soir, donc bug eventuels ....
Sinon j'attend ta proposition avec le pivot car je ne vois pas trop comme tu veux t'y prendre.
A+
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 6 oct. 2003 à 19:13
C'est dommage pour les consignes !!
sinon je pense qu'il suffit juste de rajouter un nouveau constructeur (même si c'est pas dans les consignes) où tu donnes juste un double[][] en paramètre
ca évite de refaire toute la classe et ce serait plus pratique
Et en y repensant (en cours d'Anglais...) je pense qu'une méthode type pivot de Gauss est tout à fait programmable pour inverser la matrice. Ca fait juste un système de n équations et ca évite le calcul extrèmement lourd de la comatrice. (faut pas négliger les cours d'anglais en prépa :-))
Mais c'est juste pour le style vu que le temps de calcul, on s'en fout un peu sur un PC!!!
si j'ai le temps mercredi après midi, je m'y met!!!
salut
stb2680
Messages postés9Date d'inscriptionsamedi 4 octobre 2003StatutMembreDernière intervention10 mars 2011 6 oct. 2003 à 10:12
J'ai fait ce code pour un TP, donc nous avions des consignes bien précises et effectivement l'histoire du boolen valid m'a posé des problemes ! Sinon pour l'initialisation, on devait faire appel a initial() qui fait un random et qui valide valid ;-), mais c'est pas terrible car il faut remettre apres les valeur qu'on veut.
Si j'ai du temps, je ferais une MAJ dans ce sens. Sinon j'attend ta proposition ...
Au plaisir
cs_Dobel
Messages postés333Date d'inscriptiondimanche 25 mai 2003StatutMembreDernière intervention23 novembre 20091 5 oct. 2003 à 22:36
Salut
sûr le code est clair et super bien commenté et marche bien mais sinon la classe est assez maladroite nottament à cause du boolean valid
si j'ai bien suivi, si je veux me créer une matrice avec mes propres valeurs, je fais par ex :
Matrix A = new Matrix(4,4);
A.data = new double[][] {{1,0,0,0}, {0,1,0,0}, {0,0,1,0}, {0,0,0,1}};
A.valid = true;
mais donc c'est dangereux car on peut mettre n'importe quoi dans data (ouais je sais ce serait pas très futé!!)
bon le calcul de l'inverse par la transposée de la comatrice c'est très facile à mettre en place mais c'est super lent (n^2 det à calculer...)
mais c'est vrai qu'on est pas sous Mapple ou un truc du genre et c'est sans doute pas évident de faire autre chose ;-)
je pense que le plus pratique, ca aurait été de créer une classe contenant des méthodes static qui bossent directement sur des double[][]
t'es plus embêté par valid et quand un calcul est impossible tu retournes null ou une exception (ta matrice, soit elle existe, soit elle existe pas mais elle n'est pas valide ou invalide!!)
sinon je reconnais que ta classe marche très bien
c'est juste la "forme" qui est vraiment pas terrible
A+
vasyfrancky
Messages postés2Date d'inscriptionjeudi 13 février 2003StatutMembreDernière intervention 4 octobre 2003 4 oct. 2003 à 19:21
Super code !!
Très clair et bien documenté, bravo !!
14 mai 2004 à 14:31
Si ca intéresse qqn, je peut tjs mettre mon code ici.
Mais je crois que celui réalisé par stb doit être plus ou moins semblable et tout aussi bon. Voila tjs mon code :
(Un jour, j'essaierai de mettre un petit code avec tout ce que j'ai sur les matrices. Mais bon en attendant...)
/**
* Calcule le déterminant d'une matrice.
*
* @pre : matrice est une mattrice carrée de "double" qui n'est pas vide.
* @post : Renvoie le déterminant de la matrice matrice.
*/
public static double detMatrice(double[][] matrice) {
double result = 0;
if (matrice.length == matrice[0].length) {
if (matrice.length == 1) {
result = matrice[0][0];
}
else {if (matrice.length == 2) {
result = ((matrice[0][0] * matrice[1][1]) - (matrice[0][1] * matrice[1][0]));}
else {
for (int i = 0; i < matrice.length; i++) {
result += (((-1)^(i+1)) * matrice[i][0] * detMatrice(subMatrice(matrice, i, 0)));
}
}}
}
else {
new Exception("Le déterminant ne va pas pouvoir être calculé sur cette matrice.").printStackTrace();
System.exit(-1);
}
return result;
}
/**
* Renvoie une matrice qui correspond à la matrice matrice moins la ligne a et la colonne b
*
* @pre : matrice est une mattrice de "double" qui n'est pas vide.
* @post : Renvoie une matrice qui correspond à la matrice matrice moins la ligne a et la colonne b
*/
public static double[][] subMatrice(double[][] matrice, int a, int b) {
///// tenir compte de fait que i et j sois bons et que la taille de matrice > 1
double[][] result = new double[matrice.length - 1][matrice[0].length - 1];
for (int i = 0; i < (matrice.length - 1); i++) {
for (int j = 0; j < (matrice[0].length - 1); j++) {
if (i < a && j < b)
result[i][j] = matrice[i][j];
else if (i < a && j >= b)
result[i][j] = matrice[i][j + 1];
else if (i >= a && j < b)
result[i][j] = matrice [i + 1][j];
else
result [i][j] = matrice[i + 1][j + 1];
}
}
return result;
}
Bonne prog,
14 mai 2004 à 14:17
(c plus fort que moi, et puis je viens de passer qques concours...)
en notant P le polynome caractèristique d'un endo u ;-p
si P est scindé dans K[X]
alors det(u) est le produit des racines de P
P n'est pas necessairement scindé dans R mais il l'est dans C
(tout polynome est scinde dans C)
ensuite,
u est trigonalisable ssi P est scindé
en gros, toute matrice est trigonalisable dans C, et on a alors le determinant egal au produit des elemets diagonaux
mais dans R, c'est plus delicat
il est envisageable d'obtenir des valeurs approchees des racines réelles de P, mais pour les racines complexes, ca tombe à l'eau
;-p
donc pour obtenir le determinant en trigonalisant la matrice, c'est foutu {;o(
je ne pense pas qu'il y ai beaucoup mieux que le developpement ligne-colone du determinant pour le caluler
dommage ;-p
A+
14 mai 2004 à 13:48
sinon, il faut tout de même trigonaliser la matrice -> sans calcul formel avec Maple, bon courage
A+
14 mai 2004 à 13:07
C'est mon cas, mais je ne comprend pas ce qu'ils veulent dire.
Sinon, j'ai ceci qui va m'aider :
Corollaire Soit M une matrice triangulaire ( supérieure ou inférieure ) à coefficients dans un corps k. Alors le déterminant de M est égal au produit des éléments diagonaux de M.
A+
14 mai 2004 à 12:31
Ne fais pas de recherches pour moi. Mais si t'en souvient, je me ferai une joie d'implementer ca!
14 mai 2004 à 12:01
Le seul hic c'est que je me demande si moi-même j'ai bien tenu compte de tous les cas.
D'un autre coté, quand j'essaye de savoir qu'elle matrice pourrait contrer mon (et ton) algorithme, j'arrive pas a en trouver. J'en deduit donc que ca doit être bon.
Merci pour la correction. Je me demande cependant ou étaient mes erreurs.
14 mai 2004 à 11:14
enfin reveillé et la correction est tapée
c'est vrai qu'à la main, on "choisit" son pivot, au lieu de prendre la ligne suivante ;-)
(j'm'en veux)
2 toutes petites erreurs
public static double[][] invMatrice(double[][] matrice) {
int n = matrice.length;
double[][] inv = new double[n][n];
if (matrice.length == matrice[0].length /* && isMatrice(matrice) && detMatrice(matrice) != 0 */) {
// matrice a inverser + matrice identité (accolée a droite)
double[][] matrPlusIdent = new double[n][n*2];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
matrPlusIdent[i][j] = matrice[i][j];
if (i j) matrPlusIdent[i][i+n] 1;
}
}
for (int i = 0; i < n; i++) {
// Vérification qu'il n'y a pas de 0 sur la diagonale pour la colonne étudiée sinon changement de ligne
if (matrPlusIdent[i][i] == 0) {
int ligne = -1;
for (int k = i ; k < matrPlusIdent.length; k++) {
if (matrPlusIdent[k][i] != 0)
ligne = k;
}
if (ligne == -1) {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
for (int k = 0; k < matrPlusIdent[0].length; k++) {
double temp = matrPlusIdent[i][k];
matrPlusIdent[i][k] = matrPlusIdent[ligne][k];
matrPlusIdent[ligne][k] = temp;
}
}
// On veut un sur la diagonale a l'endroit souhaité.
double diviseur = matrPlusIdent[i][i];//!!Variable
for (int k = 0; k < matrPlusIdent[0].length; k++) {
matrPlusIdent[i][k] = (matrPlusIdent[i][k] / diviseur);
}
// Met O par tout d'autre.
for (int k = 0; k < n; k++) {
if (k != i) {
double facteur = matrPlusIdent[k][i];//!!aussi ;-p
for (int l = 0; l <matrPlusIdent[0].length; l++) {
matrPlusIdent[k][l] = (matrPlusIdent[k][l] - (matrPlusIdent[i][l] * facteur));
}
}
}
}
// Reprend l'inverse dans matrPlusIdent
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
inv[i][j] = matrPlusIdent[i][n+j];
}
}
}
else {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
return inv;
}
A+
14 mai 2004 à 00:43
toujours pas couché mais je pense avaoir la solution
demain!!
14 mai 2004 à 00:28
Merci qd meme pour ce que tu as fait dejà.
/**
* Inverse une matrice. (méthode du pivot).
*
* @pre matrice est une matrice de "double"
* @post la matrice inverse de matrice est retournée
*/
public static double[][] invMatrice(double[][] matrice) {
int n = matrice.length;
double[][] inv = new double[n][n];
if (matrice.length == matrice[0].length /* && isMatrice(matrice) && detMatrice(matrice) != 0 */) {
// matrice a inverser + matrice identité (accolée a droite)
double[][] matrPlusIdent = new double[n][n*2];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
matrPlusIdent[i][j] = matrice[i][j];
if (i j) matrPlusIdent[i][i+n] 1;
}
}
for (int i = 0; i < n; i++) {
// Vérification qu'il n'y a pas de 0 sur la diagonale pour la colonne étudiée sinon changement de ligne
if (matrPlusIdent[i][i] == 0) {
int ligne = -1;
for (int k = i ; k < matrPlusIdent.length; k++) {
if (matrPlusIdent[k][i] != 0)
ligne = i;
}
if (ligne == -1) {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
for (int k = 0; k < matrPlusIdent[0].length; k++) {
double temp = matrPlusIdent[i][k];
matrPlusIdent[i][k] = matrPlusIdent[ligne][k];
matrPlusIdent[ligne][k] = temp;
}
}
// On veut un sur la diagonale a l'endroit souhaité.
for (int k = 0; k < matrPlusIdent[0].length; k++) {
matrPlusIdent[i][k] = (matrPlusIdent[i][k] / matrPlusIdent[i][i]);
}
// Met O par tout d'autre.
for (int k = 0; k < n; k++) {
if (k != i) {
for (int l = 0; l <matrPlusIdent[0].length; l++) {
matrPlusIdent[k][l] = (matrPlusIdent[k][l] - (matrPlusIdent[i][l] * matrPlusIdent[k][i]));
}
}
}
}
// Reprend l'inverse dans matrPlusIdent
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
inv[i][j] = matrPlusIdent[i][n+j];
}
}
}
else {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
return inv;
}
14 mai 2004 à 00:20
merci, pour la remarque
je regarderais ca demain (dodo)
je rappelle que j'ai pensé à ca en Anglais (;-p)
(Disclamer : je decline toute responsabilité quant aux mauvaises idéées et à leurs conséquences dramatiques que je pourrais donner)
c'est juste que j'avais trouvé que c'était une façon élégante de le faire
lol
au fait, perso, j'ai plus confiance dans mon stylo que dans mon pivot
;-))
A demain!!
13 mai 2004 à 22:22
Algorithme utilisant les Pivots n'a pas l'air mauvais dans le cas Général. Mais la ou tu as mis un commentaire disant :
"//normalement, pas besoin de test pour voir si a[i][i] est no nul : il ne doit pas l'être!!"
Je crois que tu t'est trompé, admettont que tu as une matrice
0 5 9
10 8 3
1 4 0
Dans un cas comme ca, a[0][0] sera nul et pourtant, la matrice est inversible. D'autres cas sont evisageables aussi.
Vérifier au départ si les éléments de la diagonale sont ou non égaux a 0 n'est pas suffisant non plus.
En effet, la matrice suivante aurra aussi un problème avec ton programme :
5 5 9
1 1 3
1 0 3
fournira aussi quelques problemes. Alors que 0 n'est présent sur aucun élément de la diagonale.
Facile de critiquer donc mais qu'elle est donc la réponse??
Je vais essayer de trouver ca ce soir. (Je suis bien forcé)
13 mai 2004 à 22:20
Algorithme utilisant les Pivots n'a pas l'air mauvais dans le cas Général. Mais la ou tu as mis un commentaire disant :
"//normalement, pas besoin de test pour voir si a[i][i] est no nul : il ne doit pas l'être!!"
Je crois que tu t'est trompé, admettont que tu as une matrice
0 5 9
10 8 3
1 4 0
Dans un cas comme ca, a[0][0] sera nul et pourtant, la matrice est inversible. D'autres cas sont evisageables aussi.
Vérifier au départ si les éléments de la diagonale sont ou non égaux a 0 n'est pas suffisant non plus.
En effet, la matrice suivante aurra aussi un problème avec ton programme :
5 5 9
1 1 3
1 0 3
fournira aussi quelques problemes. Alors que 0 n'est présent sur aucun élément de la diagonale.
Facile de critiquer donc mais qu'elle est donc la réponse??
Je vais essayer de trouver ca ce soir. (Je suis bien forcé)
14 févr. 2004 à 22:19
En ce qui concerne le produit de matrices, la méthode classique est d'ordre 3. Grâce à la méthode de S.Winograd et de D.Coppersmith(la + rapide pour le moment), on peut obtenir un ordre de 2.376. Cette méthode est intéressante que si les matrices sont de l'ordre de 100000x100000 puisque l'on commence à gagner du temps de calcul.
a+
8 oct. 2003 à 20:06
c'est pas évident de voir comment ca marche donc je te conseille d'afficher les tableaux après chaque étape
public double[][] inverseMatrice(double[][] matrice) {
double[][] a, inv=null;
int n = matrice[0].length;
int i,j,k;
if (matrice.length == matrice[0].length /* && iciuntestdeDeterminant*/) {
//on travaille sur une matrice qui est la matrice à inverser avec la matrice identité accolée à droite
a = new double[n][2*n];
//création de cette matrice
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
a[i][j] = matrice[i][j];
if (i==j) a[i][i+n] = 1;
}
}
//première étape du Pivot : on place des 0 dans le triangle inférieur
for (i=1; i<n; i++) {
for (j=i; j<n; j++) {
if (a[j][i-1]!=0) {
double facteur = -a[i-1][i-1]/a[j][i-1];//ne pas se planter dans les indices!!
for (k=0; k<2*n; k++) {
a[j][k] = facteur*a[j][k]+a[i-1][k];
}
}
}
}
//on fait apparaître des 1 sur la diagonale
for (i=0; i<n; i++) {
double facteur = 1/a[i][i];//normalement, pas besoin de test pour voir si a[i][i] est no nul : il ne doit pas l'être!!
for (k=0; k<2*n; k++) {
a[i][k] = a[i][k]*facteur;
}
}
//fin du pivot
for (i=n-2; i>=0; i--) {
for (j=n-1; j>=i+1; j--) {
double facteur = -a[i][j];
for (k=0; k<2*n; k++) {
a[i][k] = a[i][k] + a[j][k]*facteur;
}
}
}
//on se retrouve avec l'identité à gauche et l'inverse de m à droite c'est à dire la situation inverse de lors de la création de a
//récupération de l'inverse dans la partie droite de a
inv = new double[n][n];
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
inv[i][j] = a[i][n+j];
}
}
}
else {
new Exception("Matrice non inversible").printStackTrace();
System.exit(-1);
}
return inv;
}
ca semble marcher correctement
enfin j'espère...
A+
8 oct. 2003 à 13:20
J'ai fait çà vite fait hier soir, donc bug eventuels ....
Sinon j'attend ta proposition avec le pivot car je ne vois pas trop comme tu veux t'y prendre.
A+
6 oct. 2003 à 19:13
sinon je pense qu'il suffit juste de rajouter un nouveau constructeur (même si c'est pas dans les consignes) où tu donnes juste un double[][] en paramètre
ca évite de refaire toute la classe et ce serait plus pratique
Et en y repensant (en cours d'Anglais...) je pense qu'une méthode type pivot de Gauss est tout à fait programmable pour inverser la matrice. Ca fait juste un système de n équations et ca évite le calcul extrèmement lourd de la comatrice. (faut pas négliger les cours d'anglais en prépa :-))
Mais c'est juste pour le style vu que le temps de calcul, on s'en fout un peu sur un PC!!!
si j'ai le temps mercredi après midi, je m'y met!!!
salut
6 oct. 2003 à 10:12
Si j'ai du temps, je ferais une MAJ dans ce sens. Sinon j'attend ta proposition ...
Au plaisir
5 oct. 2003 à 22:36
sûr le code est clair et super bien commenté et marche bien mais sinon la classe est assez maladroite nottament à cause du boolean valid
si j'ai bien suivi, si je veux me créer une matrice avec mes propres valeurs, je fais par ex :
Matrix A = new Matrix(4,4);
A.data = new double[][] {{1,0,0,0}, {0,1,0,0}, {0,0,1,0}, {0,0,0,1}};
A.valid = true;
mais donc c'est dangereux car on peut mettre n'importe quoi dans data (ouais je sais ce serait pas très futé!!)
bon le calcul de l'inverse par la transposée de la comatrice c'est très facile à mettre en place mais c'est super lent (n^2 det à calculer...)
mais c'est vrai qu'on est pas sous Mapple ou un truc du genre et c'est sans doute pas évident de faire autre chose ;-)
je pense que le plus pratique, ca aurait été de créer une classe contenant des méthodes static qui bossent directement sur des double[][]
t'es plus embêté par valid et quand un calcul est impossible tu retournes null ou une exception (ta matrice, soit elle existe, soit elle existe pas mais elle n'est pas valide ou invalide!!)
sinon je reconnais que ta classe marche très bien
c'est juste la "forme" qui est vraiment pas terrible
A+
4 oct. 2003 à 19:21
Très clair et bien documenté, bravo !!