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 分解を使用することをお勧めします。使用時に行列式を解く必要はありません。

さらに良いことに、あなたを助けるためにパッケージを調べてください. ジャムが思い浮かびます。

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 に答える
3

逆行列は、計算量が非常に多くなります。ダフィーモが答えたように、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 分解は良い選択です。行列計算に慣れていない場合は、行列式と逆行列を計算するためにガウスの消去法を検討することもできます。最初は理解しやすいかもしれません。

逆行列で覚えておくべきことの 1 つは、数値の安定性です。これは、浮動小数点数を扱っているためです。すべての優れたアルゴリズムには、適切なピボットを選択するための行および/または列の順列が含まれています。少なくともガウス消去法では、各ステップで列を並べ替えて、絶対値が最大の要素がピボットとして選択されるようにする必要があります。これが最も安定した選択であるためです。

于 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 に答える