cálculo de la matriz inversa de Java

Question

Estoy tratando de calcular la matriz inversa en Java.

Estoy siguiendo el método adjunto (primer cálculo de la matriz adjunta, luego transpone esta matriz y, finalmente, la multiplica por la inversa del valor del determinante).

Funciona cuando la matriz no es demasiado grande. He comprobado que para las matrices de hasta un tamaño de 12x12, el resultado se proporciona rápidamente. Sin embargo, cuando la matriz es más grande que 12x12, el tiempo que necesita para completar el cálculo aumenta exponencialmente.

La matriz que necesito invertir es 19x19, y lleva demasiado tiempo. El método que consume más tiempo es el método utilizado para el cálculo del determinante.

El código que estoy usando es:

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

¿Alguien sabe cómo calcular el determinante de una matriz grande de manera más eficiente? Si no, ¿alguien sabe cómo calcular la inversa de una matriz grande utilizando otro algoritmo?

Gracias

Answer 1

exponencial? No, creo que la inversión de la matriz es O (N^3).

Recomendaría usar LU decomposition para resolver una ecuación matricial. No tiene que resolver el determinante cuando lo usa.

Mejor aún, busque en un paquete para ayudarlo. JAMA me viene a la mente.

12x12 o 19x19 no son grandes matrículas. Es común resolver problemas con decenas o cientos de miles de grados de libertad.

Aquí hay un ejemplo práctico de cómo usar JAMA. Tienes que tener el JAR JAMA en su CLASSPATH cuando se compila y ejecuta:

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

Aquí es el mismo problema que resuelve usando Apache Commons Matemáticas, según la recomendación del 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); 
    } 
} 

adaptarlos a su situación.

Answer 2

La inversión de matriz es computacionalmente muy intensiva. Como Duffymo respondió LU es un buen algoritmo, y hay otras variantes (QR, por ejemplo).

Desafortunadamente no puede deshacerse de los cálculos pesados ​​... y tal vez el bottelneck es el método getSubmatrix si no está utilizando una biblioteca optimizada.

Además, las estructuras de matriz especiales (banda-matricidad, simetría, diagonales, espaciamiento) tienen un gran impacto en el rendimiento si se consideran en los cálculos. Su kilometraje puede variar ...

Answer 3

NUNCA quiere calcular una matriz inversa de esta manera. De acuerdo, se debe evitar el cálculo de la inversa, ya que casi siempre es mejor usar una factorización como una LU.

El cálculo del determinante mediante cálculos recursivos es una cosa numéricamente obscena. Resulta que una mejor opción es usar una factorización LU para calcular un determinante.Pero, si te vas a molestar en calcular los factores LU, ¿por qué querrías calcular el inverso? Ya has hecho el trabajo difícil al calcular los factores LU.

Una vez que tenga los factores LU, puede usarlos para hacer la sustitución hacia adelante y hacia atrás.

En cuanto a que una matriz de 19x19 sea grande, ni siquiera está cerca de lo que yo consideraría como grande.

Answer 4

Es difícil vencer a Matlab en su juego. También son cautos acerca de la precisión. Si tiene 2.0 y 2.00001 como pivotes, ¡cuidado! Su respuesta puede terminar siendo muy imprecisa. Además, consulte la implementación de Python (está en numpy/scipy en algún lugar ...)

Answer 5

Su algoritmo para calcular un determinante es de hecho exponencial. El problema básico es que está computando a partir de la definición, y la definición directa conduce a una cantidad exponencial de subdeterminantes para calcular. Realmente necesita transformar la matriz primero antes de calcular su determinante o su inverso. (Pensé en explicar sobre programación dinámica, pero este problema no puede resolverse mediante programación dinámica, ya que el número de subproblemas también es exponencial).

La descomposición de LU, como recomiendan otros, es una buena opción. Si es nuevo en el cálculo de matrices, también puede considerar la eliminación gaussiana para calcular determinantes e inversas, ya que puede ser un poco más fácil de comprender al principio.

Y una cosa para recordar en la inversión de matrices es la estabilidad numérica, ya que se trata de números en coma flotante. Todos los buenos algoritmos incluyen permutaciones de filas y/o columnas para elegir los pivotes adecuados, como se denominan. Al menos en la eliminación gaussiana, desea, en cada paso, permutar las columnas para que el elemento más grande en valor absoluto se elija como pivote, ya que esta es la opción más estable.

Answer 6

Recomendaría usar Apache Commons Math 2.0 para esto. JAMA es un proyecto muerto. ACM 2.0 realmente tomó álgebra lineal de JAMA y la desarrolló aún más.

Answer 7

¿Tienes que tener una solución exacta? Es probable que un solucionador aproximado (Gauss-Seidel sea muy eficaz y fácil de implementar) funcione para usted y converja muy rápidamente. 19x19 es una matriz bastante pequeña. Creo que el código de Gauss-Seidel que usé podría resolver una matriz de 128x128 en un abrir y cerrar de ojos (pero no me cites sobre eso, ha pasado un tiempo).

Answer 8

La biblioteca la4j (Álgebra lineal para Java) admite inversión de matriz. Aquí está la breve ejemplo:

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

Desde la biblioteca ACM ha actualizado en los últimos años, esta es la aplicación conforme a la última definición de inversión de la matriz.

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 descomposición de LU funciona bien para las matrices dispersas. Else GaussJordan podría hacer. También puede probar el método de Dodgson, pero debe tener cuidado con la división por cero.