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

10

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

Вероятно, гауссово исключение. nhahtdh
@JustinPeel: декомпозиция LU будет превосходить SVD для детерминанта, но SVD дает вам больше информации: она говорит вам, "какие направления" являются единственными для матрицы. В любом случае, проверка того, является ли матрица численно сингулярной, лучше всего выполнять путем вычисления (ограничения) ее номера условия, а не путем вычисления определителя (определитель здесь 16-линейный, поэтому небольшие ошибки возводятся в 16-ю степень), поэтому SVD Хорошо, если скорость не является серьезной проблемой. Alexandre C.
Не уверен, что это самый быстрый, но SVD скажет вам. Если любое из сингулярных значений, найденных SVD, равно 0, то ваша матрица является сингулярной. Justin Peel
Я думаю, что это обычная ситуация с переполнением стека: вот как сделать X - действительно ли это то, что вы хотите сделать? Почему вы хотите найти определитель / если матрица обратима? Вполне возможно, что вы все равно захотите, чтобы SVD оправился от ситуации, когда матрица не обратима или почти не обратима. mcdowella

Ваш Ответ

3   ответа
-3

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
}
-1 При n = 15 формула Лейбница будет иметь 1,3 триллиона слагаемых. Это не реалистичный ответ.
-1, проблема не в том, как эффективно сгенерировать код. Проблема в общей сложности времени.
Для n = 16 это может быть довольно громоздким для записи.
Проверка расстояния от эпсилона от нуля выполняется для матриц с плавающей запятой.
Ему понадобится метапрограмма для генерации формулы жесткого кода.
7

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

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

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

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

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

Похожие вопросы