Быстрый способ проверить, является ли матрица единственной? (необратимый, дет = 0)

Какой самый быстрый алгоритм (ссылка на пример C или C ++ был бы классным), чтобы проверить, является ли маленькая квадратная матрица (& lt; 16 * 16 элементов) единственной (необратимой, det = 0)?

 Justin Peel31 мая 2012 г., 05:37
Не уверен, что это самый быстрый, но SVD скажет вам. Если любое из сингулярных значений, найденных SVD, равно 0, то ваша матрица является сингулярной.
 Alexandre C.31 мая 2012 г., 10:14
@JustinPeel: декомпозиция LU будет превосходить SVD для детерминанта, но SVD дает вам больше информации: она говорит вам, "какие направления" являются единственными для матрицы. В любом случае, проверка того, является ли матрица численно сингулярной, лучше всего выполнять путем вычисления (ограничения) ее номера условия, а не путем вычисления определителя (определитель здесь 16-линейный, поэтому небольшие ошибки возводятся в 16-ю степень), поэтому SVD Хорошо, если скорость не является серьезной проблемой.
 mcdowella01 июн. 2012 г., 06:22
Я думаю, что это обычная ситуация с переполнением стека: вот как сделать X - действительно ли это то, что вы хотите сделать? Почему вы хотите найти определитель / если матрица обратима? Вполне возможно, что вы все равно захотите, чтобы SVD оправился от ситуации, когда матрица не обратима или почти не обратима.
 nhahtdh31 мая 2012 г., 04:51
Вероятно, гауссово исключение.

Ответы на вопрос(3)

Я согласен с устранением Гаусса.http://math.nist.gov/javanumerics/jama/doc/Jama/LUDecomposition.html документы LU-разложение - после построения LU-разложения из матрицы вы можете вызвать метод, чтобы получить определитель. Я предполагаю, что, по крайней мере, стоит рассчитать время, чтобы сравнить его с любой более специализированной схемой.

 31 мая 2012 г., 10:13
LU разложениеthe Стандартный способ вычисления определителей. Детерминанты просто не являются стандартным способом проверки дефектности матрицы.

fastest Возможно, это жестко закодировать детерминантную функцию для каждой матрицы размера, с которой вы собираетесь иметь дело.

Вот некоторый псевдо-код для N = 3, но если вы посмотритеФормула Лейбница для определителей картина должна быть ясна для всех N.

function is_singular3(matrix) {
    det = matrix[1][1]*matrix[2][2]*matrix[3][3]
        - matrix[1][1]*matrix[2][3]*matrix[3][2]
        - matrix[1][2]*matrix[2][1]*matrix[3][3]
        + matrix[1][2]*matrix[2][3]*matrix[3][1]
        + matrix[1][3]*matrix[2][1]*matrix[3][2]
        - matrix[1][3]*matrix[2][2]*matrix[3][1];

     if(det==0) return true
     else return false
}
 31 мая 2012 г., 18:00
-1 При n = 15 формула Лейбница будет иметь 1,3 триллиона слагаемых. Это не реалистичный ответ.
 27 мая 2013 г., 13:33
-1, проблема не в том, как эффективно сгенерировать код. Проблема в общей сложности времени.
 31 мая 2012 г., 06:59
Ему понадобится метапрограмма для генерации формулы жесткого кода.
 31 мая 2012 г., 10:13
Для n = 16 это может быть довольно громоздким для записи.
 31 мая 2012 г., 06:25
Проверка расстояния от эпсилона от нуля выполняется для матриц с плавающей запятой.
Решение Вопроса

Лучший способ - это вычислитьномер условия через SVD и убедитесь, что он больше 1 / эпсилон, где эпсилон - точность станка.

Если вы разрешаете ложные отрицания (т. Е. Матрица неисправна, но ваш алгоритм может ее не обнаружить), вы можете использовать формулу max (a_ii) / min (a_ii) из статьи Википедии в качестве прокси для номера условия, но вы сначала нужно вычислить QR-разложение (формула применяется к треугольным матрицам): A = QR с R, ортогональным, затем cond (A) = cond (Q). Существуют также методы для вычисления числа условий Q с помощью операций O (N), но они являются более сложными.

 17 сент. 2012 г., 17:16
Используя LAPACK, мы можем использовать DGECON / SGECON для общих матриц двойной / одинарной точности или одну из аналогичных подпрограмм для матриц с полезной структурой (с полосами, симметричными и т. Д.). Это использует LU факторизацию

Ваш ответ на вопрос