OUTILS SUR LES MATRICES

Commentaire de vasyfrancky le 04/10/2003 19:21:43

Super code !!
Très clair et bien documenté, bravo !!

Commentaire de stb2680 le 06/10/2003 10:12:32

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

Commentaire de stb2680 le 08/10/2003 13:20:36

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+

Commentaire de Taquilla le 14/02/2004 22:19:56

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+

Commentaire de thekwint le 13/05/2004 22:22:51

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é)

Commentaire de thekwint le 14/05/2004 00:28:45

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;
}  

Commentaire de Dobel le 14/05/2004 11:14:19

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+

Commentaire de thekwint le 14/05/2004 12:31:08

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!

Commentaire de Dobel le 14/05/2004 13:48:23

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+