Вычисление обратной матрицы Java
Я пытаюсь вычислить обратную матрицу в 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;
}
Кто-либо знает, как вычислить детерминант большой матрицы более эффективно? В противном случае кто-либо знает как к calcultate инверсия большой матрицы с помощью другого алгоритма?
Спасибо
7 ответов
экспоненциально? Нет, я считаю, что инверсия матрицы - это o (n ^ 3).
Я бы порекомендовал использовать разложение LU , чтобы решить уравнение матрицы. Вам не нужно решать для определителя, когда вы его используете.
еще лучше, посмотрите в пакет, чтобы помочь вам. Джама приходит на ум.
12x12 или 19x19 не являются большими затратами. Обычно решать проблемы с десятками или соцами тысяч сотен степени свободы.
Вот рабочий пример того, как использовать JAMA. Вы должны иметь JAMA JAMA в своем классе, когда вы компилируете и запустите:
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);
}
}
вот ту же проблема, решаемая с помощью Apache Commons Math, на рекомендацию 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);
}
}
адаптировать их к вашей ситуации.
Должно ли у вас быть точное решение? Приблизительный решатель (Gauss-Seidel очень производительный и простой в реализации), скорее всего, будет работать на вас, и очень быстро сблизится. 19х19 - довольно маленькая матрица. Я думаю, код Гаусса-Сайделя, который я использовал, мог бы решить матрицу 128x128 в мгновение ока (но не цитируйте меня, прошло много времени).
.Вы НИКОГДА не захотите таким образом вычислить обратную матрицу. Хорошо, вычисления самой обратной матрицы следует избегать, так как почти всегда лучше использовать факторизацию, такую как LU.
Вычисление детерминанта с помощью рекурсивных вычислений - это численно неприличная вещь. Получается, что лучшим выбором является использование ЛУ-факторизации для вычисления определителя. Но если нужно вычислить LU-факторы, то зачем тогда вычислять обратное? Вы уже проделали сложную работу по вычислению LU-факторов.
Как только у вас появились LU-факторы, вы можете использовать их для выполнения обратной и прямой замены.
Поскольку матрица 19х19 является большой, она даже не близка к тому, что я бы подумал о большом.
Трудно победить Матлаба в их игре. Они также настороженно относятся к точности. Если у вас есть 2.0 и 2.00001 в качестве шарниров - будьте осторожны! Ваш ответ может оказаться очень неточным. Кроме того, проверить реализацию Python (он находится в numpy / Scipy где-то ...)
.Ваш алгоритм вычисления детерминанта действительно экспоненциальный. Основная проблема заключается в том, что вы вычисляете из определения, а прямое определение приводит к экспоненциальному количеству поддетерминантов для вычисления. Вам действительно нужно сначала преобразовать матрицу, прежде чем вычислять либо детерминант, либо обратный. (Я думал объяснить насчет динамического программирования, но эта проблема не может быть решена с помощью динамического программирования, так как количество подпроблем тоже экспоненциально.)
LU-декомпозиция, как рекомендуют другие, является хорошим выбором. Если вы новичок в матричном вычислении, то, возможно, вам также захочется взглянуть на элиминирование Гаусса для вычисления детерминант и инверсов, так как это может быть немного проще для понимания вначале.
И при инверсии матриц следует помнить об одной вещи - это числовая стабильность, так как вы имеете дело с числами с плавающей точкой. Все хорошие алгоритмы включают в себя перестановки строк и/или столбцов для выбора подходящих поворотов, как они называются. По крайней мере, при гауссовом исключении, вы хотите на каждом шаге перестановки столбцов так, чтобы в качестве стержня был выбран элемент с наибольшим абсолютным значением, так как это самый стабильный выбор.
Для этого я бы порекомендовал использовать Apache Commons Math 2.0. JAMA - мертвый проект. ACM 2.0 фактически взял линейную алгебру из JAMA и развил её дальше.
Инверсия матрицы очень интенсивна с точки зрения вычислений. Как ответил Даффимо, LU - хороший алгоритм, а есть и другие варианты (например, QR).
К сожалению, от тяжелых вычислений не избавиться... и, возможно, боттельнеком является метод getSubmatrix, если вы не используете оптимизированную библиотеку.
Также большое влияние на производительность оказывают специальные матричные структуры (полосовая матрица, симметрия, диагональность, спарсительность), если их учитывать в расчетах. Ваш пробег может варьироваться.