Java逆矩阵计算
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1992638/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java inverse matrix calculation
提问by dedalo
I'm trying to calculate the inverse matrix in Java.
我正在尝试用 Java 计算逆矩阵。
I'm following the adjoint method (first calculation of the adjoint matrix, then transpose this matrix and finally, multiply it for the inverse of the value of the determinant).
我遵循伴随方法（首先计算伴随矩阵，然后转置该矩阵，最后乘以行列式值的倒数）。
It works when the matrix is not too big. I've checked that for matrixes up to a size of 12x12 the result is quickly provided. However, when the matrix is bigger than 12x12 the time it needs to complete the calculation increases exponentially.
当矩阵不是太大时它起作用。我已经检查过，对于大小为 12x12 的矩阵，可以快速提供结果。但是，当矩阵大于 12x12 时，完成计算所需的时间呈指数增长。
The matrix I need to invert is 19x19, and it takes too much time. The method that more time consumes is the method used for the calculation of the determinant.
我需要求逆的矩阵是 19x19，太耗时了。耗时较多的方法是用于计算行列式的方法。
The code I'm using is:
我正在使用的代码是：
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;
}
Does anybody know how to calculate the determinant of a large matrix more efficiently? If not, does anyone knows how to calcultate the inverse of a large matrix using other algorithm?
有人知道如何更有效地计算大矩阵的行列式吗？如果没有，有没有人知道如何使用其他算法计算大矩阵的逆？
Thanks
谢谢
采纳答案by duffymo
Exponentially? No, I believe matrix inversion is O(N^3).
指数级？不，我相信矩阵求逆是 O(N^3)。
I would recommend using LU decompositionto solve a matrix equation. You don't have to solve for the determinant when you use it.
我建议使用LU 分解来求解矩阵方程。使用时不必求解行列式。
Better yet, look into a package to help you. JAMAcomes to mind.
更好的是，查看一个包来帮助你。 想到了JAMA。
12x12 or 19x19 are not large matricies. It's common to solve problems with tens or hundreds of thousandsof degrees of freedom.
12x12 或 19x19 不是大矩阵。解决具有数万或数十万自由度的问题很常见。
Here's a working example of how to use JAMA. You have to have the JAMA JAR in your CLASSPATH when you compile and run:
这是一个如何使用 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);
}
}
Here's the same problem solved using Apache Commons Math, per quant_dev's recommendation:
根据 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);
}
}
Adapt these to your situation.
使这些适应您的情况。
回答by Pablo Rodriguez
Matrix inversion is computationally very intensive. As duffymo answered LU is a good algorithm, and there are other variants (QR, for instance).
矩阵求逆在计算上非常密集。正如 duffymo 回答 LU 是一个很好的算法，还有其他变体（例如 QR）。
Unfortunately you can't get rid of the heavy calculations... and maybe the bottelneck is the getSubmatrix method if you are not using an optimized library.
不幸的是，您无法摆脱繁重的计算……如果您没有使用优化的库，那么瓶颈可能是 getSubmatrix 方法。
Also, special matrix structures (band-matricity, symmetry, diagonality, sparsity) have a great impact in performance if considered in the calculations. Your mileage may vary...
此外，如果在计算中考虑，特殊的矩阵结构（带矩阵、对称性、对角性、稀疏性）对性能有很大影响。你的旅费可能会改变...
回答by Pablo Rodriguez
You NEVER want to compute an inverse matrix this way. Ok, computation of the inverse itself is to be avoided, as it is almost always better to use a factorization such as an LU.
您永远不想以这种方式计算逆矩阵。好的，应该避免逆本身的计算，因为使用诸如 LU 之类的因式分解几乎总是更好。
Computation of the determinant using recursive computations is a numerically obscene thing to do. It turns out that a better choice is to use an LU factorization to compute a determinant. But, if you are going to bother to compute LU factors, then why would you possibly want to compute the inverse? You have already done the difficult work by computing the LU factors.
使用递归计算来计算行列式在数值上是一件令人讨厌的事情。事实证明，更好的选择是使用 LU 分解来计算行列式。但是，如果您要费心计算 LU 因子，那么您为什么要计算逆呢？您已经通过计算 LU 因子完成了艰巨的工作。
Once you have LU factors, you can use them to do back and forward substitution.
一旦有了 LU 因子，就可以使用它们进行前后替换。
As far as a 19x19 matrix being big, it is not even close to what I'd think of as big.
至于 19x19 矩阵很大，它甚至不接近我认为的大。
回答by Hamish Grubijan
It is tough to beat Matlab at their game. They also are cautiou about precision. If you have 2.0 and 2.00001 as pivots - watch out! Your answer might end up being very imprecise. Also, check out Python's implementation (it is in numpy / scipy somewhere ...)
在他们的比赛中很难击败 Matlab。他们对精度也很谨慎。如果你有 2.0 和 2.00001 作为支点——当心！您的回答最终可能会非常不准确。另外，请查看 Python 的实现（它在 numpy / scipy 中的某处......）
回答by JaakkoK
Your algorithm to compute a determinant is indeed exponential. The basic problem is that you are computing from the definition, and the straight definition leads to an exponential amount of subdeterminants to compute. You really need to transform the matrix first before computing either its determinant or its inverse. (I thought of explaining about dynamic programming, but this problem cannot be solved by dynamic programming as the number of subproblems is exponential too.)
您计算行列式的算法确实是指数级的。基本问题是您正在根据定义进行计算，而直接定义导致要计算的子行列式数量呈指数级增长。在计算其行列式或逆矩阵之前，您确实需要先变换矩阵。（我想解释一下动态规划，但这个问题不能通过动态规划解决，因为子问题的数量也是指数级的。）
LU decomposition, as recommended by others, is a good choice. If you are new to matrix calculation, you might also want to look at Gaussian elimination to compute determinants and inverses, as that might be a bit easier to comprehend at first.
其他人推荐的LU分解是一个不错的选择。如果您不熟悉矩阵计算，您可能还想看看高斯消元法来计算行列式和逆，因为这可能更容易理解。
And one thing to remember in matrix inversion is numerical stability, since you are dealing with floating point numbers. All the good algorithm include permutations of rows and/or columns to choose the suitable pivots, as they are called. At least in Gaussian elimination, you want to, at each step, to permute the columns so that the element largest in absolute value is chosen as the pivot, as this is the stablest choice.
在矩阵求逆中要记住的一件事是数值稳定性，因为您正在处理浮点数。所有好的算法都包括行和/或列的排列以选择合适的枢轴，正如它们所称的那样。至少在高斯消元中，您希望在每一步都对列进行置换，以便选择绝对值最大的元素作为主元，因为这是最稳定的选择。
回答by quant_dev
I would recommend using Apache Commons Math 2.0 for this. JAMA is a dead project. ACM 2.0 actually took linear algebra from JAMA and developed it further.
我建议为此使用 Apache Commons Math 2.0。JAMA 是一个死的项目。ACM 2.0 实际上从 JAMA 中汲取了线性代数并对其进行了进一步的发展。
回答by davidtbernal
Do you have to have an exact solution? An approximate solver (Gauss-Seidelis very performant and easy to implement) will likely work for you, and will converge very quickly. 19x19 is quite a small matrix. I think the Gauss-Seidel code that I used could solve a 128x128 matrix in the blink of an eye (but don't quote me on that, it's been a while).
你必须有一个确切的解决方案吗？近似求解器（Gauss-Seidel非常高效且易于实现）可能适合您，并且会很快收敛。19x19 是一个很小的矩阵。我认为我使用的 Gauss-Seidel 代码可以在眨眼间解决 128x128 矩阵（但不要引用我的话，已经有一段时间了）。
回答by Vladimir Kostyukov
The la4j(Linear Algebra for Java) library supports matrix inversion. Here is the brief example:
所述la4j（线性代数为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
回答by Soumya Kanti
Since ACM library has updated over the years, here is the implementation conforming to latest definition for matrix inversion.
由于 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);
}
}
回答by CoolMind
For those who seeks matrix inversion (not fast), see https://github.com/rchen8/Algorithms/blob/master/Matrix.java.
对于那些寻求矩阵求逆（不快）的人，请参阅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));
}
}
