14

我正在尝试在 Java 中计算逆矩阵。

我遵循伴随方法（首先计算伴随矩阵，然后转置该矩阵，最后将其乘以行列式值的倒数）。

它适用于矩阵不太大的情况。我已经检查过，对于大小为 12x12 的矩阵，可以快速提供结果。但是，当矩阵大于 12x12 时，完成计算所需的时间呈指数增长。

我需要反转的矩阵是 19x19，而且需要太多时间。花费更多时间的方法是用于计算行列式的方法。

我正在使用的代码是：

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

有人知道如何更有效地计算大矩阵的行列式吗？如果没有，有谁知道如何使用其他算法计算大矩阵的逆？

谢谢

4

11 回答 11

17

成指数的？不，我相信矩阵求逆是 O(N^3)。

我建议使用LU 分解来求解矩阵方程。使用时不必求解行列式。

更好的是，查看一个包来帮助你。 JAMA 浮现在脑海中。

12x12 或 19x19 不是大矩阵。解决具有数万或数十万自由度的问题是很常见的。

这是一个如何使用 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);
    }
}

根据您的情况调整这些。

于 2010-01-02T19:59:06.230 回答
9

我建议为此使用 Apache Commons Math 2.0。JAMA 是一个死项目。ACM 2.0 实际上从 JAMA 中提取了线性代数并对其进行了进一步的发展。

于 2010-01-02T20:26:53.790 回答
4

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
于 2013-03-12T06:45:37.920 回答
4

对于那些寻求矩阵求逆（不快）的人，请参阅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(submatrix(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(submatrix(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[][] submatrix(double[][] matrix, int row, int column) {
        double[][] submatrix = 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)
                    submatrix[i < row ? i : i - 1][j < column ? j : j - 1] = matrix[i][j];
        return submatrix;
    }

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

}
于 2018-03-13T08:31:35.390 回答
3

矩阵求逆的计算量非常大。正如 duffymo 回答的那样，LU 是一个很好的算法，并且还有其他变体（例如 QR）。

不幸的是，您无法摆脱繁重的计算……如果您不使用优化的库，那么瓶颈可能是 getSubmatrix 方法。

此外，如果在计算中考虑，特殊的矩阵结构（带矩阵、对称性、对角性、稀疏性）对性能有很大影响。你的旅费可能会改变...

于 2010-01-02T20:05:51.910 回答
3

您永远不想以这种方式计算逆矩阵。好的，要避免计算逆本身，因为使用诸如 LU 之类的因式分解几乎总是更好。

使用递归计算来计算行列式在数值上是一件令人讨厌的事情。事实证明，更好的选择是使用 LU 分解来计算行列式。但是，如果你要费心计算 LU 因子，那么你为什么要计算逆？您已经通过计算 LU 因子完成了艰巨的工作。

一旦有了 LU 因子，就可以使用它们进行前后替换。

就 19x19 矩阵而言，它甚至不接近我认为的那么大。

于 2010-01-02T20:13:27.713 回答
3

由于 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);
    }
}
于 2015-09-08T15:58:50.357 回答
2

您计算行列式的算法确实是指数级的。基本问题是您是根据定义进行计算的，而直接定义会导致要计算的子行列式数量呈指数级增长。在计算其行列式或逆矩阵之前，您确实需要先转换矩阵。（我想解释一下动态规划，但是这个问题不能通过动态规划来解决，因为子问题的数量也是指数级的。）

其他人推荐的LU分解是一个不错的选择。如果您是矩阵计算的新手，您可能还想查看高斯消元法来计算行列式和逆矩阵，因为起初这可能更容易理解。

在矩阵求逆中要记住的一件事是数值稳定性，因为您正在处理浮点数。所有好的算法都包括行和/或列的排列，以选择合适的枢轴，因为它们被称为。至少在高斯消元中，您希望在每一步都对列进行置换，以便选择绝对值最大的元素作为枢轴，因为这是最稳定的选择。

于 2010-01-02T20:21:28.183 回答
1

在他们的游戏中很难击败 Matlab。他们对精度也很谨慎。如果您有 2.0 和 2.00001 作为枢轴 - 小心！您的答案可能最终会变得非常不精确。另外，查看 Python 的实现（它在 numpy / scipy 某处......）

于 2010-01-02T20:14:51.440 回答
1

你必须有一个确切的解决方案吗？近似求解器（Gauss-Seidel性能非常好且易于实现）可能对您有用，并且会很快收敛。19x19 是一个相当小的矩阵。我认为我使用的 Gauss-Seidel 代码可以在眨眼之间解决 128x128 矩阵（但不要引用我的话，已经有一段时间了）。

于 2010-01-02T20:37:51.817 回答
0

通过 ACM，您可以在没有 rhs 的情况下执行此操作：

RealMatrix A = new Array2DRowRealMatrix(ARR);
System.out.println(new LUDecomposition(A).getSolver().getInverse());
于 2020-05-24T12:28:06.263 回答