Calcul de matrice inverse Java

Question

J'essaie de calculer la matrice inverse en Java. Je suis la méthode adjointe (premier calcul de la matrice adjointe, puis transpose cette matrice et finalement la multiplie par l'inverse de la valeur du déterminant).

Fonctionne lorsque la matrice n'est pas trop grande. J'ai vérifié que pour les matrices jusqu'à une taille de 12x12 le résultat est rapidement fourni. Cependant, lorsque la matrice est plus grande que 12x12, le temps nécessaire pour compléter le calcul augmente exponentiellement.

La matrice que j'ai besoin d'inverser est 19x19, et cela prend trop de temps. La méthode qui consomme le plus de temps est la méthode utilisée pour le calcul du déterminant.

Le code J'utilise est:

public static double determinant(double[][] input) { 
    int rows = nRows(input);  //number of rows in the matrix 
    int columns = nColumns(input); //number of columns in the matrix 
    double determinant = 0; 

    if ((rows== 1) && (columns == 1)) return input[0][0]; 

    int sign = 1;  
    for (int column = 0; column < columns; column++) { 
    double[][] submatrix = getSubmatrix(input, rows, columns,column); 
    determinant = determinant + sign*input[0][column]*determinant(submatrix); 
    sign*=-1; 
    } 
    return determinant; 
} 

Quelqu'un sait comment calculer le déterminant d'une grande matrice plus efficace? Sinon, est-ce que quelqu'un sait comment calculer l'inverse d'une grande matrice en utilisant un autre algorithme?

Merci

Answer 1

Exponentiellement? Non, je crois que l'inversion de matrice est O (N^3).

Je recommanderais d'utiliser LU decomposition pour résoudre une équation matricielle. Vous n'avez pas à résoudre pour le déterminant lorsque vous l'utilisez.

Mieux encore, regardez dans un paquet pour vous aider. JAMA vient à l'esprit.

12x12 ou 19x19 ne sont pas de grandes matrices. Il est courant de résoudre des problèmes avec des dizaines ou des centaines de degrés de liberté.

Voici un exemple d'utilisation de JAMA. Vous devez avoir le JAR JAMA dans votre CLASSPATH lorsque vous compilez et exécutez:

package linearalgebra; 

import Jama.LUDecomposition; 
import Jama.Matrix; 

public class JamaDemo 
{ 
    public static void main(String[] args) 
    { 
     double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}}; // each array is a row in the matrix 
     double [] rhs = { 9, 1, 0 }; // rhs vector 
     double [] answer = { 1, 2, 3 }; // this is the answer that you should get. 

     Matrix a = new Matrix(values); 
     a.print(10, 2); 
     LUDecomposition luDecomposition = new LUDecomposition(a); 
     luDecomposition.getL().print(10, 2); // lower matrix 
     luDecomposition.getU().print(10, 2); // upper matrix 

     Matrix b = new Matrix(rhs, rhs.length); 
     Matrix x = luDecomposition.solve(b); // solve Ax = b for the unknown vector x 
     x.print(10, 2); // print the solution 
     Matrix residual = a.times(x).minus(b); // calculate the residual error 
     double rnorm = residual.normInf(); // get the max error (yes, it's very small) 
     System.out.println("residual: " + rnorm); 
    } 
} 

est ici le même problème résolu en utilisant Apache Commons Math, selon la recommandation de quant_dev:

package linearalgebra; 

import org.apache.commons.math.linear.Array2DRowRealMatrix; 
import org.apache.commons.math.linear.ArrayRealVector; 
import org.apache.commons.math.linear.DecompositionSolver; 
import org.apache.commons.math.linear.LUDecompositionImpl; 
import org.apache.commons.math.linear.RealMatrix; 
import org.apache.commons.math.linear.RealVector; 

public class LinearAlgebraDemo 
{ 
    public static void main(String[] args) 
    { 
     double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}}; 
     double [] rhs = { 9, 1, 0 }; 

     RealMatrix a = new Array2DRowRealMatrix(values); 
     System.out.println("a matrix: " + a); 
     DecompositionSolver solver = new LUDecompositionImpl(a).getSolver(); 

     RealVector b = new ArrayRealVector(rhs); 
     RealVector x = solver.solve(b); 
     System.out.println("solution x: " + x);; 
     RealVector residual = a.operate(x).subtract(b); 
     double rnorm = residual.getLInfNorm(); 
     System.out.println("residual: " + rnorm); 
    } 
} 

les adapter à votre situation.

Answer 2

L'inversion de matrice est très intensive en termes de calculs. Comme Duffymo répondu LU est un bon algorithme, et il existe d'autres variantes (QR, par exemple). Malheureusement, vous ne pouvez pas vous débarrasser des calculs lourds ... et peut-être que le Bottelneck est la méthode getSubmatrix si vous n'utilisez pas une bibliothèque optimisée.

De plus, les structures matricielles spéciales (bande-matricité, symétrie, diagonalité, parcimonie) ont un impact important sur les performances si elles sont prises en compte dans les calculs. Votre kilométrage peut varier ...

Answer 3

Vous ne voulez JAMAIS calculer une matrice inverse de cette façon. Ok, le calcul de l'inverse lui-même doit être évité, car il est presque toujours préférable d'utiliser une factorisation telle qu'une LU.

Le calcul du déterminant en utilisant des calculs récursifs est une chose numériquement obscène à faire. Il s'avère qu'un meilleur choix consiste à utiliser une factorisation LU pour calculer un déterminant.Mais, si vous voulez prendre la peine de calculer les facteurs LU, alors pourquoi voudriez-vous calculer l'inverse? Vous avez déjà fait le travail difficile en calculant les facteurs LU.

Une fois que vous avez des facteurs LU, vous pouvez les utiliser pour effectuer une substitution en arrière et en avant.

Dans la mesure où une matrice de 19x19 est grande, elle n'est même pas proche de ce que je pense être grande.

Answer 4

Il est difficile de battre Matlab à leur niveau. Ils sont aussi prudents sur la précision. Si vous avez 2.0 et 2.00001 comme pivots - attention! Votre réponse pourrait finir par être très imprécise. En outre, vérifiez l'implémentation de Python (elle est dans numpy/scipy quelque part ...)

Answer 5

Votre algorithme pour calculer un déterminant est en effet exponentiel. Le problème fondamental est que vous calculez à partir de la définition, et la définition directe conduit à une quantité exponentielle de sous-déterminants à calculer. Vous devez vraiment transformer la matrice avant de calculer son déterminant ou son inverse. (J'ai pensé expliquer la programmation dynamique, mais ce problème ne peut pas être résolu par la programmation dynamique car le nombre de sous-problèmes est aussi exponentiel.)

La décomposition de LU, comme recommandé par d'autres, est un bon choix. Si vous êtes novice dans le calcul matriciel, vous pouvez aussi regarder l'élimination gaussienne pour calculer les déterminants et les inverses, car cela pourrait être un peu plus facile à comprendre au début.

Et une chose à retenir dans l'inversion de matrice est la stabilité numérique, puisque vous avez affaire à des nombres à virgule flottante. Tous les bons algorithmes incluent des permutations de lignes et/ou de colonnes pour choisir les pivots appropriés, comme on les appelle. Au moins en élimination gaussienne, vous voulez, à chaque étape, permuter les colonnes de sorte que l'élément le plus grand en valeur absolue soit choisi comme pivot, car c'est le choix le plus stable.

Answer 6

Je recommanderais d'utiliser Apache Commons Math 2.0 pour cela. JAMA est un projet mort. ACM 2.0 a effectivement pris l'algèbre linéaire de JAMA et l'a développée plus loin.

Answer 7

Avez-vous besoin d'une solution exacte? Un solveur approximatif (Gauss-Seidel est très performant et facile à implémenter) fonctionnera probablement pour vous, et convergera très rapidement. 19x19 est une petite matrice. Je pense que le code de Gauss-Seidel que j'ai utilisé pouvait résoudre une matrice de 128x128 en un clin d'œil (mais ne me citez pas dessus, ça fait longtemps).

Answer 8

La bibliothèque la4j (Algèbre linéaire pour Java) prend en charge l'inversion matricielle. Voici l'exemple bref:

Matrix a = new Basic2DMatrix(new double[][]{ 
    { 1.0, 2.0, 3.0 }, 
    { 4.0, 5.0, 6.0 }, 
    { 7.0, 8.0. 9.0 } 
}); 

Matrix b = a.invert(Matrices.DEFAULT_INVERTOR); // uses Gaussian Elimination 

Answer 9

Depuis la bibliothèque ACM a mis à jour au fil des ans, voici la mise en œuvre conforme à la dernière définition pour l'inversion de la matrice.

import org.apache.commons.math3.linear.Array2DRowRealMatrix; 
import org.apache.commons.math3.linear.ArrayRealVector; 
import org.apache.commons.math3.linear.DecompositionSolver; 
import org.apache.commons.math3.linear.LUDecomposition; 
import org.apache.commons.math3.linear.RealMatrix; 
import org.apache.commons.math3.linear.RealVector; 

public class LinearAlgebraDemo 
{ 
    public static void main(String[] args) 
    { 
     double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}}; 
     double [][] rhs = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; 

     // Solving AB = I for given A 
     RealMatrix A = new Array2DRowRealMatrix(values); 
     System.out.println("Input A: " + A); 
     DecompositionSolver solver = new LUDecomposition(A).getSolver(); 

     RealMatrix I = new Array2DRowRealMatrix(rhs); 
     RealMatrix B = solver.solve(I); 
     System.out.println("Inverse B: " + B); 
    } 
} 

Answer 10

La décomposition de LU fonctionne bien pour les matrices creuses. Else GaussJordan pourrait le faire. Vous pouvez également essayer la méthode Dodgson, mais vous devez faire attention à la division par zéro.