Java逆矩阵计算
我正在尝试用Java计算逆矩阵。
我正在遵循伴随方法（首先计算伴随矩阵，然后转置这个矩阵，最后，将它乘以行列式值的倒数）。
它在矩阵不太大时起作用。 我已经检查过，对于尺寸为12×12的矩阵，可以快速得到结果。 但是，当矩阵大于12×12时，完成计算所需的时间呈指数增长。
我需要反转的矩阵是19×19，需要花费太多时间。 更多时间消耗的方法是用于计算行列式的方法。
我正在使用的代码是：
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; } 有人知道如何更有效地计算大矩阵的行列式吗？ 如果没有，有没有人知道如何使用其他算法计算大矩阵的逆？
谢谢
成倍？ 不，我相信矩阵求逆是O（N ^ 3）。
我建议使用LU分解来求解矩阵方程。 使用它时，您无需为行列式求解。
更好的是，查看一个包来帮助你。 JAMA浮现在脑海中。
12×12或19×19不是大型matricies。 解决数十或数十万自由度的问题是很常见的。
这是一个如何使用JAMA的工作示例。 编译和运行时，必须在CLASSPATH中使用JAMA JAR：
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); } }
根据quant_dev的建议，使用Apache Commons Math解决了同样的问题：
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); } }
根据您的情况调整这些。
我建议使用Apache Commons Math 2.0。 JAMA是一个死的项目。 ACM 2.0实际上采用了JAMA的线性代数并进一步发展。
矩阵求逆在计算上是非常密集的。 由于duffymo回答LU是一个很好的算法，还有其他变种（例如QR）。
不幸的是，你无法摆脱繁重的计算……如果你没有使用优化的库，那么bottelneck可能是getSubmatrix方法。
此外，如果在计算中考虑，特殊矩阵结构（带质，对称性，对角性，稀疏性）对性能有很大影响。 你的旅费可能会改变…
你永远不想用这种方式计算逆矩阵。 好吧，要避免计算逆本身，因为使用像LU这样的因子化几乎总是更好。
使用递归计算计算行列式是一个数字上淫秽的事情。 事实certificate，更好的选择是使用LU分解来计算行列式。 但是，如果您打算计算LU因子，那么为什么您可能想要计算逆？ 您已经通过计算LU因子完成了困难的工作。
一旦有了LU因子，就可以使用它们进行前后替换。
至于19×19矩阵很大，它甚至都不像我想象的那么大。
la4j （线性代数for Java）库支持矩阵求逆。 这是一个简短的例子：
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
计算行列式的算法确实是指数的。 基本问题是您从定义计算，直接定义导致计算的指数量的子确定。 在计算其行列式或其逆矩阵之前，您确实需要先转换矩阵。 （我想解释有关动态编程的问题，但这个问题无法通过动态编程解决，因为子问题的数量也是指数级的。）
其他人推荐的LU分解是一个不错的选择。 如果您不熟悉矩阵计算，您可能还需要查看高斯消元来计算行列式和倒数，因为这可能比较容易理解。
在矩阵求逆中要记住的一件事是数值稳定性，因为你正在处理浮点数。 所有好的算法都包括行和/或列的排列以选择合适的枢轴，因为它们被称为。 至少在高斯消除中，您希望在每一步都置换列，以便选择绝对值最大的元素作为枢轴，因为这是最稳定的选择。
在比赛中击败Matlab很难。 他们对精确度也很谨慎。 如果你有2.0和2.00001作为支点 – 小心！ 你的答案最终可能会非常不精确。 另外，看看Python的实现（它在某处numpy / scipy ……）
你必须有一个确切的解决方案吗？ 近似求解器（ Gauss-Seidel非常高效且易于实现）可能对您有用，并且会很快收敛。 19×19是一个非常小的矩阵。 我认为我使用的Gauss-Seidel代码可以在眨眼间解决128×128矩阵（但不要引用我的话，已经有一段时间了）。
由于ACM库多年来一直在更新，因此这里的实现符合矩阵求逆的最新定义。
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); } }
对于那些寻求矩阵求逆（不快）的人，请参阅https://github.com/rchen8/Algorithms/blob/master/Matrix.java 。
import java.util.Arrays; public class Matrix { private static double determinant(double[][] matrix) { if (matrix.length != matrix[0].length) throw new IllegalStateException("invalid dimensions"); if (matrix.length == 2) return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]; double det = 0; for (int i = 0; i < matrix[0].length; i++) det += Math.pow(-1, i) * matrix[0][i] * determinant(minor(matrix, 0, i)); return det; } private static double[][] inverse(double[][] matrix) { double[][] inverse = new double[matrix.length][matrix.length]; // minors and cofactors for (int i = 0; i < matrix.length; i++) for (int j = 0; j < matrix[i].length; j++) inverse[i][j] = Math.pow(-1, i + j) * determinant(minor(matrix, i, j)); // adjugate and determinant double det = 1.0 / determinant(matrix); for (int i = 0; i < inverse.length; i++) { for (int j = 0; j <= i; j++) { double temp = inverse[i][j]; inverse[i][j] = inverse[j][i] * det; inverse[j][i] = temp * det; } } return inverse; } private static double[][] minor(double[][] matrix, int row, int column) { double[][] minor = new double[matrix.length - 1][matrix.length - 1]; for (int i = 0; i < matrix.length; i++) for (int j = 0; i != row && j < matrix[i].length; j++) if (j != column) minor[i < row ? i : i - 1][j < column ? j : j - 1] = matrix[i][j]; return minor; } private static double[][] multiply(double[][] a, double[][] b) { if (a[0].length != b.length) throw new IllegalStateException("invalid dimensions"); double[][] matrix = new double[a.length][b[0].length]; for (int i = 0; i < a.length; i++) { for (int j = 0; j < b[0].length; j++) { double sum = 0; for (int k = 0; k < a[i].length; k++) sum += a[i][k] * b[k][j]; matrix[i][j] = sum; } } return matrix; } private static double[][] rref(double[][] matrix) { double[][] rref = new double[matrix.length][]; for (int i = 0; i < matrix.length; i++) rref[i] = Arrays.copyOf(matrix[i], matrix[i].length); int r = 0; for (int c = 0; c < rref[0].length && r < rref.length; c++) { int j = r; for (int i = r + 1; i < rref.length; i++) if (Math.abs(rref[i][c]) > Math.abs(rref[j][c])) j = i; if (Math.abs(rref[j][c]) < 0.00001) continue; double[] temp = rref[j]; rref[j] = rref[r]; rref[r] = temp; double s = 1.0 / rref[r][c]; for (j = 0; j < rref[0].length; j++) rref[r][j] *= s; for (int i = 0; i < rref.length; i++) { if (i != r) { double t = rref[i][c]; for (j = 0; j < rref[0].length; j++) rref[i][j] -= t * rref[r][j]; } } r++; } return rref; } private static double[][] transpose(double[][] matrix) { double[][] transpose = new double[matrix[0].length][matrix.length]; for (int i = 0; i < matrix.length; i++) for (int j = 0; j < matrix[i].length; j++) transpose[j][i] = matrix[i][j]; return transpose; } public static void main(String[] args) { // example 1 - solving a system of equations double[][] a = { { 1, 1, 1 }, { 0, 2, 5 }, { 2, 5, -1 } }; double[][] b = { { 6 }, { -4 }, { 27 } }; double[][] matrix = multiply(inverse(a), b); for (double[] i : matrix) System.out.println(Arrays.toString(i)); System.out.println(); // example 2 - example 1 using reduced row echelon form a = new double[][]{ { 1, 1, 1, 6 }, { 0, 2, 5, -4 }, { 2, 5, -1, 27 } }; matrix = rref(a); for (double[] i : matrix) System.out.println(Arrays.toString(i)); System.out.println(); // example 3 - solving a normal equation for linear regression double[][] x = { { 2104, 5, 1, 45 }, { 1416, 3, 2, 40 }, { 1534, 3, 2, 30 }, { 852, 2, 1, 36 } }; double[][] y = { { 460 }, { 232 }, { 315 }, { 178 } }; matrix = multiply( multiply(inverse(multiply(transpose(x), x)), transpose(x)), y); for (double[] i : matrix) System.out.println(Arrays.toString(i)); } }