Matrice de variables

Hello,

Je travaille sur un système d'équations, qui possède une représentation matricielle qui ressemble à ça :

G = P.C

• G est une matrice de taille m x 1 , elle contient des integer connus
• P est une matrice de taille m x n, elle contient des 0, 1 et -1.
• C est une matrice n x 1, elle contient des coefficients que je voudrais approximer Ces trois matrices ne sont pas carrées.

Le système d'équation peut ne pas posséder de solution, c'est pourquoi mon but est de trouver les valeurs des coefficients les plus proches du résultat.

On m'a conseillé de travailler avec des vecteurs, en essayant de minimiser la distance entre G et P.C

D(c) = ‖PC-G‖²

Le problème c'est que je n'ai aucune idée de comment représenter une matrice de variables pour représenter ces coefficients (C). De plus, j'aimerais également trouver une méthode qui détermine ces coefficients automatiquement (une sorte de "solver" d'équation, mais pour un minimum d'écart).

Voici mon code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public ApproxMatrix(List<Game> games, List<Player> players){
     double[][] arrayGames = new double[games.size()][1];
     double[][] arrayPlayers = new double[games.size()][players.size()];
     double[][] coeff = new double[players.size()][1];

     // filling the games array... 
     // filling the players array...
     // how to fill the coeff array ?

     // building matrix
     RealMatrix g = MatrixUtils.createRealMatrix(arrayGames);
     RealMatrix p = MatrixUtils.createRealMatrix(arrayPlayers);
     // RealMatrix c = MatrixUtils.createRealMatrix(coeff); ?

     // building vector from matrix
     RealVector gVector = m.getColumnVector(0);
     RealVector pcVector = ?????
}

Salut,

En gros tu essaies de résoudre un système d'équation avec des matrices qui ne sont pas carrées ? Je te dirais de regarder du coté de la méthode de Householder si tu veux le faire à la main, sinon ce que tu fais ressemble à du java et je pense que tu doit pouvoir trouver des méthodes de résolutions de système déjà implémentées dans ce langage.

Salut @backmachine, effectivement, c'est ce que je veux faire. C'est bien la méthode en JAVA qui permet de résoudre ce système qui m'intérèsse, et un exemple d'utilisation si possible. Malheureusement j'ai du mal à trouver ça sur Apache Commons Math.

j'ai cherché rapidement avec "java householder" et j'ai trouvé ça :
http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/linear/QRDecomposition.html
avec la méthode GetSolver() qui doit être ce que tu recherches

Hello merci beaucoup pour la suggestion ! J'étais déjà tombé sur ce truc il y a quelques jours, malheureusement, cette méthode permet de décomposer (ou de développer) une matrice. Exemple, j'ai une matrice A, je peux la décomposer pour avoir un truc du style QxR.

Ce que je recherche, c'est plutôt à partir d'un A et d'un R, d'obtenir le Q qui soit le plus proche possible de cette égalité.

Salut, je commence à me demander si j'ai bien compris ton problème.

Le principe de ce type de méthode, pour résoudre un système AX=B (tu cherches le X), c'est de décomposer la matrice A sous la forme A = QR pour pouvoir trouver (plus rapidement) le X.
Une fois décomposé, le système obtenu et très facile à résoudre.
Il y a plusieurs type de décompositions plus ou moins efficace selon la forme de A. les méthodes QR (dont Householder fait partie) sont principalement utilisées dans le cas où A n'est pas carrée parce que d'autres décompositions classiques ne fonctionnent pas dans ce cas.
À priori avec ce que je t'ai proposé tu peux tout simplement lui donner ton P et ton G et tu auras la solution.

Hmmm oui je vois, je vais creuser ça, c'est peut-être ce qu'il me faut ! Je viens également de tomber sur ça http://commons.apache.org/proper/commons-math/userguide/linear.html Je te tiens au courant, encore merci pour cette piste !

Effectivement, cette méthode a l'air de ressembler à celle que je recherche. Le seul soucis, c'est que ma matrice P n'est pas carrée, et ça n'a pas l'air de plaire à la méthode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

RealMatrix coefficients =   new Array2DRowRealMatrix(matrixPlayers, false);
DecompositionSolver solver = new LUDecomposition(coefficients).getSolver(); // exception

RealVector constants = new ArrayRealVector(matrixGames, false);
RealVector solution = solver.solve(constants); 


java.lang.reflect.InvocationTargetException
    at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
    at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62)
    at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
    at java.lang.reflect.Constructor.newInstance(Constructor.java:408)
    at StartMenu.ButtonOkListener$1.run(ButtonOkListener.java:113)
Caused by: org.apache.commons.math3.linear.NonSquareMatrixException: matrice non carrée (90x96)
    at org.apache.commons.math3.linear.LUDecomposition.<init>(LUDecomposition.java:87)
    at org.apache.commons.math3.linear.LUDecomposition.<init>(LUDecomposition.java:75)
    at ConcreteProblems.topTeams.Approx.ApproxMatrix.<init>(ApproxMatrix.java:49)
    at ConcreteProblems.topTeams.Approx.ApproxProblem.<init>(ApproxProblem.java:32)
    at ConcreteProblems.topTeams.Approx.ApproxLauncher.<init>(ApproxLauncher.java:21)
    ... 5 more

bizarre parce que c'est justement l'interet des methodes QR, ça s'applique à des systèmes qui ne sont pas carrés.

edit : oh je viens de voir que tu fais de la decomposition LU, ce n'est pas la meme chose et ca ne s'applique qu'à des systèmes carrés. C'est typiquement ce dont je parlais en disant "parce que d'autres décompositions classiques ne fonctionnent pas dans ce cas". J'avais même hésité à citer la décomposition LU comme une de ces méthodes classiques qui ne peuvent pas marcher dans le cas où ta matrice n'est pas carrée.

J'ai 3 mains gauches (qui ressemblent à des pieds) quand il s'agit de Java mais je pense que si tu fais

1
2
3
4
5

RealMatrix coefficients =   new Array2DRowRealMatrix(matrixPlayers, false);
DecompositionSolver solver = new QRDecomposition(coefficients).getSolver(); // exception

RealVector constants = new ArrayRealVector(matrixGames, false);
RealVector solution = solver.solve(constants); 

Ça devrais bien faire une décomposition QR et donc pouvoir fonctionner.

Ohhhh exact quel âne !!! J'ai honte lol… Effectivement, en utilisant la bonne classe je n'ai plus l'exception à cet endroit, mais au moment du solve.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 java.lang.reflect.InvocationTargetException
    at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
    at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62)
    at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
    at java.lang.reflect.Constructor.newInstance(Constructor.java:408)
    at StartMenu.ButtonOkListener$1.run(ButtonOkListener.java:113)
 Caused by: org.apache.commons.math3.linear.SingularMatrixException: matrice singulière
    at org.apache.commons.math3.linear.QRDecomposition$Solver.solve(QRDecomposition.java:354)
    at ConcreteProblems.topTeams.Approx.ApproxMatrix.<init>(ApproxMatrix.java:54)
    at ConcreteProblems.topTeams.Approx.ApproxProblem.<init>(ApproxProblem.java:32)
    at ConcreteProblems.topTeams.Approx.ApproxLauncher.<init>(ApproxLauncher.java:21)
    ... 5 more

Pour information :

Matrice singulière

En algèbre linéaire, une matrice carrée est dite singulière si elle n'est pas inversible. Par conséquent, un système d'équations représenté par une matrice singulière n'admet pas de solution unique, car on ne peut pas l'inverser.

Ce qui est mon cas car je n'ai pas de solution unique, et je cherche la "solution" la plus proche. (Que c'est compliqué!!!)

Edit : la classe SingularValueDecomposition a l'air de ne pas faire planter le solve ! Et les résultats ont l'air de tenir la route !!

énorme merci à toi ! A bientôt